ミューテックス：セマフォとの違い
ミューテックス
第3回では共有資源を使用する際にタスク間で排他制御を行うための機能としてセマフォを紹介しましたが、T-Kernelではセマフォだけでなくミューテックスも提供しています。
ミューテックスはセマフォと同様にタスク間の排他制御を行うための機能を提供しますが、排他制御に伴って発生する上限のない優先度逆転を防ぐ機構をサポートします。
排他制御に伴う一時的な実行順序の逆転
T-Kernelでは各タスクに優先度が与えられており、優先度の高いタスクが優先的に実行されます。このようにして次に実行すべきタスクを決定する処理を優先度ベースのスケジューリングと呼びます。
優先度ベースのスケジューリングでは常に優先度の高いタスクが優先的に実行されますが、タスク間で共有資源の排他制御を行うと、優先度の高いタスクが一時的に待ち状態になるため、タスクの優先度とタスクの実行順序が一致しない場合が生じます。
リスト1に高優先度タスクと低優先度タスクの実行順序が逆転するプログラム例を示します。
高優先度のタスクAは10秒に1度、5秒かかる処理を実行します。処理後は5秒間起床待ち状態に遷移します。
低優先度のタスクCは5秒かかる処理を起床待ち状態に遷移することなく繰り返し実行します。タスクAとタスクCは資源(リスト1ではループ変数)を共有しているので排他制御を行う必要があります※１。これをセマフォを使って実現します。
※ 以下のサンプルプログラムはこちらからダウンロードできます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <basic.h> #include <tk/tkernel.h> #include <tm/tmonitor.h> IMPORT void doWorkA( void ); IMPORT void doWorkC( void ); INT i; /* タスクAとタスクCで共有 */ ID semid; /* セマフォID */ void taskA( INT stacd, VP exinf ) { while(1){ tm_putstring( (UB*)"A enters critical section!\n" ); tk_wai_sem(semid, 1, TMO_FEVR); doWorkA(); /* タスクA用の処理 */ tm_putstring( (UB*)"A exits critical section!\n" ); tk_sig_sem(semid, 1); tk_dly_tsk(5000); } tk_ext_tsk(); } void taskC( INT stacd, VP exinf ) { while(1){ tm_putstring( (UB*)"C enters critical section!\n" ); tk_wai_sem(semid, 1, TMO_FEVR); doWorkC(); /* タスクC用の処理 */ tm_putstring( (UB*)"C exits critical section!\n" ); tk_sig_sem(semid, 1); } tk_ext_tsk(); } EXPORT INT usermain( void ) /* 初期タスクから呼ばれる関数 */ { T_CSEM csem = { NULL, TA_TFIFO|TA_FIRST, 1, 1 }; T_CTSK ctskA = { NULL, TA_HLNG|TA_RNG0, taskA, 1, 4*1024 }; T_CTSK ctskC = { NULL, TA_HLNG|TA_RNG0, taskC, 3, 4*1024 }; ID tskIdA; /* タスクAの識別子 */ ID tskIdC; /* タスクCの識別子 */ tk_chg_pri(TSK_SELF,1); semid = tk_cre_sem( &csem ); /* セマフォを生成 */ tskIdA = tk_cre_tsk( &ctskA ); /* タスクAを生成 */ tk_sta_tsk( tskIdA, 0 ); /* タスクAの実行を開始 */ tskIdC = tk_cre_tsk( &ctskC ); /* タスクCを生成 */ tk_sta_tsk( tskIdC, 0 ); /* タスクCの実行を開始 */ tk_slp_tsk(TMO_FEVR); /* 起床待ち状態に移行 */ return 0; } void doWorkA( void ) { for (i = 0; i < 50; i++) { tm_putstring( (UB*)"A is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ (※２) */ } } void doWorkC( void ) { for (i = 0; i < 50; i++) { tm_putstring( (UB*)"C is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } |
図1は、タスクCがタスクAより先にセマフォを獲得したことによって、タスクAがタスクCに待たされ、実行の順序が逆転する際のタスク状態の変化を示しています。
図1 タスクの実行順序が逆転する例
図1で示した例では、タスクAとタスクCの実行順序の逆転状態は、タスクCがセマフォを解放するまで続きます。これは、排他制御に伴う待ち状態の発生により一時的に生じた逆転状態であり、設計者の意図の範囲ですので、特に問題はありません。
上限のない優先度逆転
リスト1で示したプログラムに中優先度のタスクBが追加されたプログラムをリスト2に示します。
タスクBは28秒に1度、23秒かかる処理を実行します。処理後は5秒間起床待ち状態に遷移します。ただし、タスクBはタスクAとタスクCが共有する資源を使用していませんので、排他制御は行っていません。
※ 以下のサンプルプログラムはこちらからダウンロードできます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include <basic.h> #include <tk/tkernel.h> #include <tm/tmonitor.h> IMPORT void doWorkA( void ); IMPORT void doWorkB( void ); IMPORT void doWorkC( void ); INT i; /* タスクAとタスクCで共有 */ ID semid; /* セマフォID */ void taskA( INT stacd, VP exinf ) { while(1){ tm_putstring( (UB*)"A enters critical section!\n" ); tk_wai_sem(semid, 1, TMO_FEVR); doWorkA(); /* タスクA用の処理 */ tm_putstring( (UB*)"A exits critical section!\n" ); tk_sig_sem(semid, 1); tk_dly_tsk(5000); } tk_ext_tsk(); } void taskB( INT stacd, VP exinf ) { while(1){ doWorkB(); /* タスクB用の処理 */ tk_dly_tsk(5000); } tk_ext_tsk(); } void taskC( INT stacd, VP exinf ) { while(1){ tm_putstring( (UB*)"C enters critical section!\n" ); tk_wai_sem(semid, 1, TMO_FEVR); doWorkC(); /* タスクC用の処理 */ tm_putstring( (UB*)"C exits critical section!\n" ); tk_sig_sem(semid, 1); } tk_ext_tsk(); } EXPORT INT usermain( void ) /* 初期タスクから呼ばれる関数 */ { T_CSEM csem = { NULL, TA_TFIFO|TA_FIRST, 1, 1 }; T_CTSK ctskA = { NULL, TA_HLNG|TA_RNG0, taskA, 1, 4*1024 }; T_CTSK ctskB = { NULL, TA_HLNG|TA_RNG0, taskB, 2, 4*1024 }; T_CTSK ctskC = { NULL, TA_HLNG|TA_RNG0, taskC, 3, 4*1024 }; ID tskIdA; /* タスクAの識別子 */ ID tskIdB; /* タスクBの識別子 */ ID tskIdC; /* タスクCの識別子 */ tk_chg_pri(TSK_SELF,1); semid = tk_cre_sem( &csem ); /* セマフォを生成 */ tskIdA = tk_cre_tsk( &ctskA ); /* タスクAを生成 */ tk_sta_tsk( tskIdA, 0 ); /* タスクAの実行を開始 */ tskIdB = tk_cre_tsk( &ctskB ); /* タスクBを生成 */ tk_sta_tsk( tskIdB, 0 ); /* タスクBの実行を開始 */ tskIdC = tk_cre_tsk( &ctskC ); /* タスクCを生成 */ tk_sta_tsk( tskIdC, 0 ); /* タスクCの実行を開始 */ tk_slp_tsk(TMO_FEVR); /* 起床待ち状態に移行 */ return 0; } void doWorkA( void ) { for (i = 0; i < 50; i++) { tm_putstring( (UB*)"A is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } void doWorkB( void ) { INT j; for (j = 0; j < 230; j++) { tm_putstring( (UB*)"B is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } void doWorkC( void ) { for (i = 0; i < 50; i++) { tm_putstring( (UB*)"C is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } |
図1で示したタスク実行例と同様にタスクCがタスクAより先にセマフォを獲得すると、タスクAはタスクCがセマフォを解放するまで待ち状態になります。この状態でタスクBが処理を開始すると、タスクBは低優先度のタスクCを実行状態から実行可能状態にするので、タスクCは処理を停止し、タスクCのセマフォ解放を待っているタスクAもタスクBの処理が完了するまで待たされることになります。この時のタスク状態の変化を図2に示します。
図2 上限のない優先度逆転の
このような現象を「上限のない優先度逆転」（unbounded priority inversion）と呼びます。
リスト2では一定時間でタスクBの処理が完了するように実装してありますが、より複雑なプログラムであった場合、タスクBによる待ちがいつ完了するか明確でない場合もあり、システムとして深刻な状態に陥ることがあります。
例えば、1997年に火星に着陸したマーズ・パスファインダー号の制御プログラムでも上限のない優先度逆転が発生し、システムが再起動に陥るという事態が発生したというのは有名な話です。
ミューテックスの利用
リスト3はリスト2と同じタスクから構成されるプログラムですが、タスクAとタスクCの排他制御をミューテックスを使って実現しています。
※ 以下のサンプルプログラムはこちらからダウンロードできます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include <basic.h> #include <tk/tkernel.h> #include <tm/tmonitor.h> IMPORT void doWorkA( void ); IMPORT void doWorkB( void ); IMPORT void doWorkC( void ); INT i; /* タスクAとタスクCで共有 */ ID mtxid; /* ミューテックスID */ void taskA( INT stacd, VP exinf ) { while(1){ tm_putstring( (UB*)"A enters critical section!\n" ); tk_loc_mtx(mtxid, TMO_FEVR); doWorkA(); /* タスクA用の処理 */ tm_putstring( (UB*)"A exits critical section!\n" ); tk_unl_mtx(mtxid); tk_dly_tsk(5000); } tk_ext_tsk(); } void taskB( INT stacd, VP exinf ) { while(1){ doWorkB(); /* タスクB用の処理 */ tk_dly_tsk(5000); } tk_ext_tsk(); } void taskC( INT stacd, VP exinf ) { while(1){ tm_putstring( (UB*)"C enters critical section!\n" ); tk_loc_mtx(mtxid, TMO_FEVR); doWorkC(); /* タスクC用の処理 */ tm_putstring( (UB*)"C exits critical section!\n" ); tk_unl_mtx(mtxid); } tk_ext_tsk(); } EXPORT INT usermain( void ) /* 初期タスクから呼ばれる関数 */ { T_CMTX cmtx = { NULL, TA_INHERIT, 1 }; T_CTSK ctskA = { NULL, TA_HLNG|TA_RNG0, taskA, 1, 4*1024 }; T_CTSK ctskB = { NULL, TA_HLNG|TA_RNG0, taskB, 2, 4*1024 }; T_CTSK ctskC = { NULL, TA_HLNG|TA_RNG0, taskC, 3, 4*1024 }; ID tskIdA; /* タスクAの識別子 */ ID tskIdB; /* タスクBの識別子 */ ID tskIdC; /* タスクCの識別子 */ tk_chg_pri(TSK_SELF,1); mtxid = tk_cre_mtx( &cmtx ); /* ミューテックスを生成 */ tskIdA = tk_cre_tsk( &ctskA ); /* タスクAを生成 */ tk_sta_tsk( tskIdA, 0 ); /* タスクAの実行を開始 */ tskIdB = tk_cre_tsk( &ctskB ); /* タスクBを生成 */ tk_sta_tsk( tskIdB, 0 ); /* タスクBの実行を開始 */ tskIdC = tk_cre_tsk( &ctskC ); /* タスクCを生成 */ tk_sta_tsk( tskIdC, 0 ); /* タスクCの実行を開始 */ tk_slp_tsk(TMO_FEVR); /* 起床待ち状態に移行 */ return 0; } void doWorkA( void ) { for (i = 0; i < 50; i++) { tm_putstring( (UB*)"A is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } void doWorkB( void ) { INT j; for (j = 0; j < 230; j++) { tm_putstring( (UB*)"B is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } void doWorkC( void ) { for (i = 0; i < 50; i++) { tm_putstring( (UB*)"C is working!\n" ); WaitUsec(100000); /* 100 ms のビジーループ */ } } |
ミューテックスを利用した場合、タスクAがミューテックスのロックを試みた時点で、タスクCの優先度がタスクAの優先度と同じ値まで引き上げられますので、タスクCはタスクBよりも優先的に処理が実行されることになります。これにより、タスクCが(ミューテックスをロックしている間は)タスクBよりも優先的に実行されることになり、結果的にタスクAがタスクBに待たされる状態になることを防ぐことができます。
この時のタスク状態の変化を図3に示します。
図3 ミューテックスを利用した場合の動作
セマフォとの違い
ミューテックスとセマフォは共にタスク間の排他制御を行うためのデータ構造です。ミューテックスは優先度逆転を防ぐ機構を利用できる以外は、資源数が1のセマフォ（バイナリセマフォ）と同等の機能と言えますが、その他に以下の違いもありますので注意が必要です。
a. ミューテックスでは、ロックしたタスク以外はロックを解除できない。
b. ミューテックスをロックしたままタスクが終了すると、ロックが自動的に解除される。
優先度逆転を防ぐ機構
T-Kernelが提供するミューテックスは上限のない優先度逆転を防ぐための機構として、優先度継承プロトコル（priority inheritance protocol）と優先度上限プロトコル（priority ceiling protocol）をサポートしています(コラム参照)。
リスト3で利用していたのは優先度継承プロトコルです。
優先度継承プロトコルは、ミューテックスをロックしているタスクの優先度を、ロックを待っているタスクの優先度の中で一番高い優先度に一時的に変更する(図3のχの区間)ことで優先度逆転を防いでいます。
優先度上限プロトコルは、ミューテックスをロックしたタスクの優先度を、ミューテックス生成時に指定した上限優先度に一時的に引き上げることで優先度逆転を防いでいます。
2種類の機構のうちどちらを利用した方がよいかはシステムの構成によります。ミューテックスの動作についてはT-Kernel 2.0仕様書でも説明していますので、まずはミューテックスの基本的な動作を理解し、実際の開発にミューテックスを活用してください。
なお、T-Kernel 2.0 Software Packageに含まれるエミュレータなどを利用すれば、実際にリスト1～3を動作させることが可能です。実際にリスト1～3を動作させてそれぞれのタスクの挙動を確認してみてください。
コラム ミューテックスのプロトコル
優先度継承プロトコル
優先度継承プロトコルを用いるミューテックスでは、
A. あるタスクがミューテックスのロックを試みた際に待ち状態になる場合、または
B. ミューテックスのロックを待っているタスクが待ちを終了した場合、
の両ケースでミューテックスをロック中のタスクの優先度が変更されます。
Aのケースでは、ミューテックスをロック中のタスクの優先度がロックを試みた結果待ち状態になるタスクの優先度より低ければ、ロック中のタスクの優先度はロックを試みたタスクの優先度まで引き上げられます。
Bのケースでは、ミューテックスをロック中のタスクの優先度を、以下のうち最も高い優先度まで引き下げる場合があります。(実際に優先度を引き下げるかどうかは実装依存です)
a. ロック待ちしているタスクの優先度のうち最も高い優先度
b. そのタスクがロックしている他のすべてのミューテックスに対してロック待ちしているタスクのうち最も高い優先度
c. そのタスクのベース優先度
優先度上限プロトコル
優先度上限プロトコルを用いる場合、ミューテックス生成時に上限優先度を設定します。上限優先度は、そのミューテックスをロックする可能性のあるタスクの中で最も高いベース優先度を選択します。上限優先度より高い優先度を持つタスクはミューテックスをロックできません。
優先度上限プロトコルでは、あるタスクがミューテックスのロックを獲得した場合に、タスクの優先度がミューテックスの上限優先度より低ければタスクの優先度は上限優先度まで引き上げられます。
タスクがミューテックスのロックを解除する場合、タスクの優先度は以下のいずれかに引き下げられます。
a. そのタスクがロックしている他のすべてのミューテックスのうち最も高い優先度、もしくは
b. そのタスクのベース優先度
セマフォを利用すれば排他制御を実現できますが、例えば、チームで手分けして開発を行った場合や、既存のシステムに新たなタスクを追加する場合などに、今回説明したような上限のない優先度逆転現象が発生することがあります。
ミューテックスは、致命的な欠陥につながる優先度逆転現象を回避するためにとても有効な排他制御機能ですので、ぜひ活用してください。
※１ リスト1でループ変数を共有していることに特別な意味はありません。何らかの資源を共有する場合、排他制御を行わなければ正しく動作しないことを分りやすく示すために例としてこのように実装しています。
※２ WaitUsec()は、指定された時間分(マイクロ秒)の微小待ちを行うAPIです。短時間の待ちを行う場合などに利用します。この待ちは通常はビジーループで実装されますので、タスクは実行状態のままになります。本稿に示したリスト1～3では「(カーネルの待ちを含まない)一定時間の処理」であることを表わすために利用しています。