MISRA C:2023 Dir 5.2

There shall be no deadlocks between threads

R2024b 以降

説明

このチェッカーは、既定の Polyspace^® as You Code 解析では非アクティブにされます。Polyspace as You Code 解析で非アクティブにされるチェッカー (Polyspace Access)を参照してください。

命令の定義

There shall be no deadlocks between threads ¹ .

根拠

同期リソースを共有するスレッドで、スレッドどうしが互いを待機する循環チェーンが作成されると、デッドロックが発生する可能性があります。次のコードについて考えます。

mtx_t mtx1, mtx2;

void worker1() { /*In thread T1*/
	mtx_lock(&mtx1);
	//...
	mtx_lock(&mtx2); // potential deadlock

}

void worker2() { /*In thread T2*/
	mtx_lock(&mtx2);
	//...
	mtx_lock(&mtx1); // potential deadlock
}

関数 worker1() および worker2() は 2 つのスレッドで同時に実行されます。関数 worker1() は mtx1 をロックしてから mtx2 のロックを試行します。同時に、worker2() は mtx2 をロックしてから mtx1 のロックを試行します。どちらか片方のスレッドが 2 つ目のミューテックスのロックを試行する前に、両方のスレッドがそれぞれの 1 つ目のミューテックスをロックすると、両方のスレッドが、もう一方のスレッドのミューテックスのロックが解除されるまで待機したままになるため、デッドロックが発生します。

デッドロックを回避するには、グローバルかつ非循環的な固定の順序でミューテックスを使用します。

Polyspace 実装

複数のスレッドが次のように循環的にミューテックス オブジェクトを待機する場合、Polyspace はこの命令の違反を報告します。

• 各スレッドが、もう一方のスレッドによってミューテックスのロックが解除されるまで待機する。

• スレッドが循環を形成する。

Polyspace は、C11 ライブラリのスレッドとミューテックス オブジェクトを認識します。Polyspace でのスレッド作成とクリティカル セクションの自動検出を参照してください。手動で、オプション [タスク] (-entry-points) を使用してスレッドを指定し、[クリティカル セクション詳細] (-critical-section-begin -critical-section-end) を使用してミューテックス オブジェクトを指定することもできます。

トラブルシューティング

ルール違反を想定していてもその違反が表示されない場合、コーディング規約違反が想定どおりに表示されない理由の診断を参照します。

例

2 つのタスクのデッドロック

この例では、関数 worker1() および worker2() がスレッド t1 と t2 で同時に実行されます。t1 はミューテックス mutex1 をロックした後、mutex1 のロックを解除する前に、別のスレッドによって既にロックされている mutex2 のロックを試行することから、デッドロックが発生します。Polyspace は違反を報告します。

#include <stdio.h>
#include <threads.h>
void doWork(void);
mtx_t mutex1, mutex2;

// Worker function 1 locks mutex1 then mutex2
int worker1(void* arg) {
    mtx_lock(&mutex1); // Locks mutex1
     
    doWork();
    mtx_lock(&mutex2); // Noncompliant - attempts to lock mutex2, but may be locked by worker2()

    mtx_unlock(&mutex2);
    mtx_unlock(&mutex1);
    return 0;
}

// Worker function 2 locks mutex2 then mutex1
int worker2(void* arg) {
    mtx_lock(&mutex2); // Locks mutex2
 
    doWork();
    mtx_lock(&mutex1); // Attempts to lock mutex1, but may be locked by worker1()
     
    mtx_unlock(&mutex1);
    mtx_unlock(&mutex2);
    return 0;
}

int main() {
    thrd_t t1, t2;

    // Initialize mutexes
    mtx_init(&mutex1, mtx_plain);
    mtx_init(&mutex2, mtx_plain);

    // Create worker threads
    if (thrd_create(&t1, worker1, NULL) != thrd_success) {
        printf("Failed to create thread 1\n");
        return 1;
    }
    if (thrd_create(&t2, worker2, NULL) != thrd_success) {
        printf("Failed to create thread 2\n");
        return 1;
    }

    // Wait for threads to finish (they won't, due to deadlock)
    thrd_join(t1, NULL);
    thrd_join(t2, NULL);

    // Clean up
    mtx_destroy(&mutex1);
    mtx_destroy(&mutex2);

    return 0;
}

この例で、マルチタスクの動作をエミュレートするには、以下のオプションを指定します。

オプション	仕様
マルチタスクを手動で構成	On
タスク (-entry-points)	worker1 worker2

修正 — 両方のタスクで同じロック順序に従う

1 つの修正方法として、ロック関数とロック解除関数の呼び出し順序を t1 および t2 とで同じにします。

#include <stdio.h>
#include <threads.h>
void doWork(void);
mtx_t mutex1, mutex2;

// Worker function 1 locks mutex1 then mutex2
int worker1(void* arg) {
    mtx_lock(&mutex1); // Locks mutex1

    doWork();
    mtx_lock(&mutex2); // Compliant

    mtx_unlock(&mutex2);
    mtx_unlock(&mutex1);
    return 0;
}

// Worker function 2 locks mutex1 then mutex2
int worker2(void* arg) {
    mtx_lock(&mutex1); // Locks mutex1

    doWork();
    mtx_lock(&mutex2); 

    mtx_unlock(&mutex1);
    mtx_unlock(&mutex2);
    return 0;
}

int main() {
    thrd_t t1, t2;

    // Initialize mutexes
    mtx_init(&mutex1, mtx_plain);
    mtx_init(&mutex2, mtx_plain);

    // Create worker threads
    if (thrd_create(&t1, worker1, NULL) != thrd_success) {
        printf("Failed to create thread 1\n");
        return 1;
    }
    if (thrd_create(&t2, worker2, NULL) != thrd_success) {
        printf("Failed to create thread 2\n");
        return 1;
    }

    // Wait for threads to finish 
    thrd_join(t1, NULL);
    thrd_join(t2, NULL);

    // Clean up
    mtx_destroy(&mutex1);
    mtx_destroy(&mutex2);

    return 0;
}

3 つ以上のタスクのデッドロック

以下の例では、3 つのスレッドが循環依存関係を形成し、各スレッドが循環的に他のスレッドによって保持されているミューテックスを待機するため、デッドロックが発生します。

#include <stdio.h>
#include <threads.h>
#include <stdlib.h>
void doWork(void);
mtx_t mutex1, mutex2, mutex3;

int thread1(void *arg) {
    mtx_lock(&mutex1); // Thread 1 locks mutex1
    doWork();
    mtx_lock(&mutex2); // Noncompliant
    // Critical section (not reached)
    mtx_unlock(&mutex2);
    mtx_unlock(&mutex1);
    return 0;
}

int thread2(void *arg) {
    mtx_lock(&mutex2); // Thread 2 locks mutex2
    doWork();
    mtx_lock(&mutex3); // Waits for Thread 3 to release mutex3
    // Critical section (not reached)
    mtx_unlock(&mutex3);
    mtx_unlock(&mutex2);
    return 0;
}

int thread3(void *arg) {
    mtx_lock(&mutex3); // Thread 3 locks mutex3
    doWork();
    mtx_lock(&mutex1); // Waits for Thread 1 to release mutex1
    // Critical section (not reached)
    mtx_unlock(&mutex1);
    mtx_unlock(&mutex3);
    return 0;
}

int main() {
    thrd_t t1, t2, t3;

    mtx_init(&mutex1, mtx_plain);
    mtx_init(&mutex2, mtx_plain);
    mtx_init(&mutex3, mtx_plain);

    thrd_create(&t1, thread1, NULL);
    thrd_create(&t2, thread2, NULL);
    thrd_create(&t3, thread3, NULL);

    thrd_join(t1, NULL);
    thrd_join(t2, NULL);
    thrd_join(t3, NULL);

    mtx_destroy(&mutex1);
    mtx_destroy(&mutex2);
    mtx_destroy(&mutex3);

    return 0;
}

この例で、マルチタスクの動作をエミュレートするには、以下のオプションを指定します。

オプション	仕様
マルチタスクを手動で構成	On
タスク (-entry-points)	thread1 thread2 thread3

修正 — 一貫したグローバルな順序を使用して循環を断ち切る

クリティカル セクション間の循環的な順序を断ち切るには、すべてのスレッドで同じグローバルな順序 (mutex1、mutex2、mutex3) を使用します。

#include <stdio.h>
#include <threads.h>
#include <stdlib.h>
void doWork(void);
mtx_t mutex1, mutex2, mutex3;

int thread1(void *arg) {
	mtx_lock(&mutex1); // Thread 1 locks mutex1 first
	void doWork(void);
	mtx_lock(&mutex2); // Then locks mutex2
	mtx_lock(&mutex3); // Finally locks mutex3
	// Critical section
	mtx_unlock(&mutex3);
	mtx_unlock(&mutex2);
	mtx_unlock(&mutex1);
	return 0;
}

int thread2(void *arg) {
	mtx_lock(&mutex1); // Thread 2 also starts by locking mutex1 first
	void doWork(void);
	mtx_lock(&mutex2); // Then locks mutex2
	mtx_lock(&mutex3); // Finally locks mutex3
	// Critical section
	mtx_unlock(&mutex3);
	mtx_unlock(&mutex2);
	mtx_unlock(&mutex1);
	return 0;
}

int thread3(void *arg) {
	mtx_lock(&mutex1); // Thread 3 also starts by locking mutex1 first
	void doWork(void);
	mtx_lock(&mutex2); // Then locks mutex2
	mtx_lock(&mutex3); // Finally locks mutex3
	// Critical section
	mtx_unlock(&mutex3);
	mtx_unlock(&mutex2);
	mtx_unlock(&mutex1);
	return 0;
}

int main() {
	thrd_t t1, t2, t3;

	mtx_init(&mutex1, mtx_plain);
	mtx_init(&mutex2, mtx_plain);
	mtx_init(&mutex3, mtx_plain);

	thrd_create(&t1, thread1, NULL);
	thrd_create(&t2, thread2, NULL);
	thrd_create(&t3, thread3, NULL);

	thrd_join(t1, NULL);
	thrd_join(t2, NULL);
	thrd_join(t3, NULL);

	mtx_destroy(&mutex1);
	mtx_destroy(&mutex2);
	mtx_destroy(&mutex3);

	return 0;
}

チェック情報

グループ: 同時実行の考慮事項

カテゴリ: 必要

AGC カテゴリ: 必要

バージョン履歴

R2024b で導入

参考

MISRA C:2023 のチェック (-misra-c-2023)

トピック

• コーディング規約違反のチェックおよびレビュー

---

¹ All MISRA coding rules and directives are © Copyright The MISRA Consortium Limited 2021.

The MISRA coding standards referenced in the Polyspace Bug Finder™ documentation are from the following MISRA standards:

• MISRA C:2004

• MISRA C:2012

• MISRA C:2023

• MISRA C++:2008

• MISRA C++:2023

MISRA and MISRA C are registered trademarks of The MISRA Consortium Limited 2021.