CERT C: Rule POS51-C

Avoid deadlock with POSIX threads by locking in predefined order

説明

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

ルール定義

事前定義された順序でロックすることによって POSIX スレッドのデッドロックを回避します。¹

Polyspace 実装

ルールチェッカーは、"デッドロック" をチェックします。

チェッカーの拡張

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

例

すべて展開する

Deadlock

問題

デッドロックは複数のタスクが 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 が対応するロック解除関数を呼び出すまで待たなくてはなりません。ロック関数およびロック解除関数は両方 void func(void) 形式に準拠しなくてはなりません。

この欠陥を検出するには、解析前にマルチタスキングオプションを指定しなくてはなりません。[構成] ペインで [マルチタスキング] を選択してこれらのオプションを指定します。

リスク

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

修正方法

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

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

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

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

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

例 - 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(); //Noncompliant
    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();
 } 
}

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

オプション	仕様
マルチタスクを手動で構成
エントリポイント	`task1` `task2`
クリティカルセクション詳細	開始ルーチン	終了ルーチン
	`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(); //Noncompliant
    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();
 } 
}

チェック情報

グループ: Rule 50.POSIX (POS)

バージョン履歴

R2019a で導入

参考

SEI CERT-C をチェック (-cert-c)

トピック

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

外部の Web サイト

POS51-C

¹ This software has been created by MathWorks incorporating portions of: the “SEI CERT-C Website,” © 2017 Carnegie Mellon University, the SEI CERT-C++ Web site © 2017 Carnegie Mellon University, ”SEI CERT C Coding Standard – Rules for Developing safe, Reliable and Secure systems – 2016 Edition,” © 2016 Carnegie Mellon University, and “SEI CERT C++ Coding Standard – Rules for Developing safe, Reliable and Secure systems in C++ – 2016 Edition” © 2016 Carnegie Mellon University, with special permission from its Software Engineering Institute.

ANY MATERIAL OF CARNEGIE MELLON UNIVERSITY AND/OR ITS SOFTWARE ENGINEERING INSTITUTE CONTAINED HEREIN IS FURNISHED ON AN "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.

This software and associated documentation has not been reviewed nor is it endorsed by Carnegie Mellon University or its Software Engineering Institute.