Deadlock

ロック関数の呼び出し順による 2 つのタスクの相互ブロック

説明

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

この欠陥は、以下の理由で、複数のタスクがクリティカルセクション (CS) にスタックされた場合に発生します。

各 CS は別の CS が終了するのを待機します。
クリティカルセクション (CS) は循環を形成します。以下に例を示します。
- CS #1 は CS #2 が終了するのを待機し、CS #2 は CS #1が終了するのを待機します。
- CS #1 は CS #2 が終了するのを待機し、CS #2 は CS #3 が終了するのを待機し、CS #3 は CS #1 が終了するのを待機します。

Polyspace はコードのクリティカルセクションが指定された形式に準拠すると想定します。クリティカルセクションはロック関数およびロック解除関数の呼び出しの間に置かれています。タスク my_task がロック関数 my_lock を呼び出すとき、my_lock を呼び出し中の他のタスクは my_task が対応するロック解除関数を呼び出すまで待たなくてはなりません。

この欠陥を検出するには、次のいずれかのメソッドを使用してロック関数とロック解除関数を指定します。

Polyspace Bug Finder™ で自動的に検出できるいずれかの同時実行プリミティブ型を呼び出します。Polyspace でのスレッド作成とクリティカルセクションの自動検出を参照してください。
ロック関数およびロック解除関数は、解析前に構成オプションとして明示的に指定します。Polyspace ではロック関数およびロック解除関数の両方が void func(void) 形式に準拠しなくてはなりません。クリティカルセクション詳細 (-critical-section-begin -critical-section-end) を参照してください。

リスク

各タスクは、別のタスクのクリティカルセクションが終了するのを待機しているため続行できません。このプログラムはいつまでもフリーズし続ける可能性があります。

修正方法

修正方法は欠陥の根本原因によって異なります。次のいずれかの方法で、タスク間の周期的な順序の中断を試みることができます。

特定のシーケンスにおけるデッドロックに関連するすべてのクリティカルセクションを書き出します。タスク内でクリティカルセクションのロック関数を呼び出す場合は常に、そのシーケンス内の順序に従います。以下の例を参照してください。
デッドロックに関連するいずれかのクリティカルセクションが割り込みで発生する場合、すべてのタスクのクリティカルセクションの間、すべての割り込みの無効化を試みます。すべての割り込みを無効にする (-routine-disable-interrupts -routine-enable-interrupts) を参照してください。

この欠陥のレビューは、クリティカルセクションでのすべての操作が本当にAtomic ブロックとしての実行を意図しているかどうかをチェックする機会になります。クリティカルセクションは必要最小限に留めることをお勧めします。

問題を修正しない場合は、改めてレビューされないように結果またはコードにコメントを追加します。詳細は、以下を参照してください。

Polyspace ユーザーインターフェイスでのバグ修正または正当化による結果への対処 (Polyspace ユーザーインターフェイスで結果をレビューする場合)。
Polyspace Access でのバグ修正または正当化による結果への対処 (Polyspace Access) (Web ブラウザーで結果をレビューする場合)。
コードへの注釈付けと既知の結果または許容可能な結果の非表示 (IDE で結果をレビューする場合)

チェッカーの拡張

Polyspace ではサポートされていないマルチスレッド関数を使用する場合があります。その場合、マルチスレッド関数の各関数を、それぞれに対応する既知の POSIX^® 関数にマッピングすることで、このチェッカーを拡張します。サポートされていないマルチスレッド環境への同時実行欠陥チェッカーの拡張を参照してください。

例

すべて展開する

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



void task1(void);
void task2(void);

int var;
void perform_task_cycle(void) {
 var++;
}

void begin_critical_section_1(void);
void end_critical_section_1(void);

void begin_critical_section_2(void);
void end_critical_section_2(void);

void task1() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

void task2() {
 while(1) {
    begin_critical_section_2();
    begin_critical_section_1();
    perform_task_cycle();
    end_critical_section_1();
    end_critical_section_2();
 } 
}

この例では、マルチタスクの動作をエミュレートするため、以下のオプションを指定しなければなりません。

オプション	仕様
`マルチタスクを手動で構成`
`タスク (-entry-points)`	`task1` `task2`
`クリティカルセクション詳細 (-critical-section-begin -critical-section-end)`	開始ルーチン	終了ルーチン
	`begin_critical_section_1`	`end_critical_section_1`
	`begin_critical_section_2`	`end_critical_section_2`

[デッドロック] は命令を以下の順番で実行するために発生します。

task1 が begin_critical_section_1 を呼び出す。
task2 が begin_critical_section_2 を呼び出す。
task1 が命令 begin_critical_section_2(); に到達。task2 が既に begin_critical_section_2 を呼び出し済みのため、task1 は task2 が end_critical_section_2 を呼び出すのを待機します。
task2 が命令 begin_critical_section_1(); に到達。task1 が既に begin_critical_section_1 を呼び出し済みのため、task2 は task1 が end_critical_section_1 を呼び出すのを待機します。

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

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



void task1(void);
void task2(void);
void perform_task_cycle(void);

void begin_critical_section_1(void);
void end_critical_section_1(void);

void begin_critical_section_2(void);
void end_critical_section_2(void);

void task1() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

void task2() {
 while(1) {
    begin_critical_section_1();
    begin_critical_section_2();
    perform_task_cycle();
    end_critical_section_2();
    end_critical_section_1();
 } 
}

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



int var;
void performTaskCycle() {
 var++;
}

void lock1(void);
void lock2(void);
void lock3(void);


void unlock1(void);
void unlock2(void);
void unlock3(void);

void task1() {
 while(1) {
    lock1();
    lock2();
    performTaskCycle();
    unlock2();
    unlock1();
 } 
}

void task2() {
 while(1) {
    lock2();
    lock3();
    performTaskCycle();
    unlock3();
    unlock2();
 } 
}

void task3() {
 while(1) {
    lock3();
    lock1();
    performTaskCycle();
    unlock1();
    unlock3();
 } 
}

この例では、マルチタスクの動作をエミュレートするため、以下のオプションを指定しなければなりません。

オプション	仕様
マルチタスクを手動で構成
エントリポイント	`task1` `task2` `task3`
クリティカルセクション詳細	開始ルーチン	終了ルーチン
	`lock1`	`unlock1`
	`lock2`	`unlock2`
	`lock3`	`unlock3`

[デッドロック] は命令を以下の順番で実行するために発生します。

task1 が lock1 を呼び出す。
task2 が lock2 を呼び出す。
task3 が lock3 を呼び出す。
task1 が命令 lock2(); に到達。task2 が既に lock2 を呼び出し済みのため、task1 は unlock2 の呼び出しを待機。
task2 が命令 lock3(); に到達。task3 が既に lock3 を呼び出し済みのため、task2 は unlock3 の呼び出しを待機。
task3 が命令 lock1(); に到達。task1 が既に lock1 を呼び出し済みのため、task3 は unlock1 の呼び出しを待機。

修正 — 周期的な順序を中断

クリティカルセクション間の周期的な順序を中断するには、コード内のすべてのロック関数は一定の順序に従わなくてはなりません。次に例を示します。

lock1
lock2
lock3

1 つのタスク内で複数ロック関数を使用する場合、シーケンス内に現れる順に使用します。たとえば、 lock1 の後に lock2 を使用できますが、lock2 の後には lock1 を使用できません。



int var;
void performTaskCycle() {
 var++;
}

void lock1(void);
void lock2(void);
void lock3(void);

void unlock1(void);
void unlock2(void);
void unlock3(void);

void task1() {
 while(1) {
    lock1();
    lock2();
    performTaskCycle();
    unlock2();
    unlock1();
 } 
}

void task2() {
 while(1) {
    lock2();
    lock3();
    performTaskCycle();
    unlock3();
    unlock2();
 } 
}

void task3() {
 while(1) {
    lock1();
    lock3();
    performTaskCycle();
    unlock3();
    unlock1();
 } 
}

結果情報

グループ: 同時実行

言語: C | C++

既定値: オン

コマンドライン構文: DEADLOCK

影響度: High

バージョン履歴

R2014b で導入

参考