マルチプロセッサ用リアルタイムOSの解説

第19回 デッドロック回避

今回は,FMPカーネルで採用しているデッドロック回避の方法について解説します.
第14回で解説したように,FMPカーネルではロックの単位として,タスクロック,オブジェクトロックを設けています.
サービスコール内でタスクロックとオブジェクトロックの2つのロックを取得する必要のある場合には,できるだけ多くの箇所でロックの取得順序が一定になるようにする必要があります.そうすることで,デッドロック回避が必要なシステムコールを最小限にすることができます.例えばあるタスクAがタスクロック->オブジェクトロックの順序で取得し,タスクBがオブジェクトロック->タスクロックの順序で取得すると,デッドロックが発生します.そのため,システム全体でロックの取得順序を一定に定め,そのままでは,処理の関係上,定めた順序でロックを取得しない箇所に関しては,デットロック回避のための処理を加えています.

タスクロック,オブジェクトロックの両方の取得が必要なパターン
サービスコールを分析したところ,大部分のサービスコールはタスクロックかオブジェクトロックのどちらかを取得するのみであることがわかりました.一方,タスクロック,オブジェクトロックの両方をとる必要があるのは,以下の3つのパターンであることがわかりました.(詳細は第14回を参照してください.)

.織好に対する特殊操作
アクセス対象のタスクのTCBおよびレディキューと,そのタスクが持っている同期・通信オブジェクトのコントロールブロックをアクセスする.

同期・通信オブジェクトに対する待ちを伴う操作
アクセス対象の,同期・通信オブジェクトのコントロールブロックをアクセスし,自タスクが待ちに入る場合には自タスクのTCBおよびレディキューにアクセスする.この場合は,オブジェクトロック→タスクロックの順にロックを取得する.

F唄・通信オブジェクトに対するタスクの待ち解除を伴う操作
アクセス対象の同期・通信オブジェクトのコントロールブロックと,そのオブジェクトを待っているタスクがあれば,そのTCBおよびレディキューにアクセスする.この場合は,オブジェクトロック→タスクロックの順にロックを取得する.

オブジェクトロック→タスクロックの順が原則
タスクロック,オブジェクトロックの2つを取得する必要がある場合には,デッドロック回避のため,取得順序を一意に決める必要があります.

そこで,サービスコールを分析したところ,以下のことがわかりました.
・タスクロック→オブジェクトロックの順で取得
,離機璽咼好魁璽襦3個

・オブジェクトロック→タスクロックの順で取得
△離機璽咼好魁璽襪17個
のサービスコールは27個

以上より,オブジェクトロック→タスクロックの順で取得する方が多いため,オブジェクトロック→タスクロックの順で取得することを原則としています.
そのため,,離機璽咼好魁璽襪亮汰に際しては,デッドロックを回避するため,取得順序がオブジェクトロック→タスクロックの順となるような仕組みを入れています.


デッドロック回避に関連するサービスコールと内部関数を以下に示します

[サービスコール]
・ter_tsk(ID tskid)
・rel_wai(ID tskid)/irel_wai(ID tskid)
・chg_pri(ID tskid, PRI tskpri)
[内部関数]
・wait_tmout()
・make_non_wait()
※サービスコールの中で呼び出されるカーネル内の関数のことを,内部関数と呼びます.

たとえば,rel_waiサービスコールの場合,強制待ち解除を行う対象タスクがオブジェクト待ちになっている場合には,オブジェクト待ちキューから該当タスクを削除するといった処理が発生します.この場合,タスクロックを取得してはじめて,オブジェクト待ちの対象オブジェクトがわかりますので,ロックの取得順序が,タスクロック→オブジェクトロックとなります.

サービスコールの処理の関係上,ロックの取得順序が,タスクロック→オブジェクトロックとなる場合は,デッドロック回避のため,一旦タスクロックを解放してから,オブジェクトロック→タスクロックの順でロックを取得します.この順で再度ロックを取得した後に,タスクがオブジェクト待ちになっていない場合や,他のオブジェクトの待ちになっている場合は,タスクロック,オブジェクトロックともに解放して再度処理をやり直す(リトライする)必要があります.
リトライをすると実行時間の上限が定まらないため,できるだけリトライを避けるための工夫がされています.

リトライなしで実現するサービスコール
rel_wai,chg_priサービスコールは,リトライなしでデッドロック回避を実現しています.

※TCBメンバの追加
デッドロック回避をリトライなしで実現するために,以下の3つのメンバを追加しています.デッドロック回避はジャイアンロック方式以外で必要ですので,プロセッサロック方式,細粒度ロック方式を採用した場合に,この3つのメンバがTCBに追加されます.

・bool_t pend_relwai : タスクの待ち解除実行中を表す
・bool_t pend_chgpri : chg_pri(ID tskid, PRI tskpri)実行中を表す.
・UINT pend_newpri : 優先度変更保留の新優先度

たとえば,rel_waiサービスコール処理中には,pend_relwaiをtrueにします.前述したように,デッドロック回避のため,一旦取得したタスクロックを解放して,オブジェクトロック→タスクロックの順にロックを取得しなおします.そのロックを解放している間に他の処理単位が,待ち解除対象タスクを待ち解除する可能性があります.その際,pend_relwaiをfalseにすることで,rel_waiサービスコールの処理に戻った時に,対象タスクがすでに待ち解除されていることを知ることができます.よって,リトライをする必要がありません.

リトライを許容せざるを得ないサービスコール
ter_tskサービスコールはマイグレーション対応のためリトライを許容します.

リトライをすると,実行時間の上限が定まらないため,本来であれば避けたいです.リトライを行わないように,rel_waiサービスコールと同様に他の箇所で処理を代行する方法は,ter_tskサービスコールではマイグレーションの関係で採用することができません.具体的には,mact_tskがキューイングされていると,ter_tskの処理の中で,再起動時にマイグレーションが発生する可能性があります.そのためリトライせずに,他の処理単位が処理を代行すると,対象タスクが割り付けられているプロセッサと異なるプロセッサから実行される可能性があるため,異なるプロセッサからマイグレーションが発生する可能性があります.FMPカーネルのマイグレーションは,他プロセッサに割付けられているタスクに対して発行できないという制約があります.
よって,マイグレーションの発生の可能性があるter_tskサービスコールはリトライを許容しています.


make_non_wait() に関しては,この関数自体はデッドロック回避を必要としませんが,他のサービスコールのデッドロック回避をリトライなしで実現するための仕組みを入れています.


ここでは,rel_wai(待ち状態の強制解除サービスコール)と,make_non_wait()(内部関数)を解説します.
rel_wai(ID tskid)/irel_wai(ID tskid)
【機能】
tskidで指定されるタスクが待ち状態にある場合に,強制的に待ち解除を行う.すなわち,対象タスクが待ち状態のときは実行可能状態に,二重待ち状態のときは強制待ち状態に移行させる.
※このサービスコールでは,強制待ちからの再開は行わない.強制待ちからの再開を行う必要がある場合には,frsm_tsk(またはrsm_tsk)を用いる.

[kernel/task_sync.c]

360 ER
361 ER
362 rel_wai(ID tskid)
363 {
364 TCB *p_tcb;
365 ER ercd;
366 bool_t dspreq = false;
367 PCB *p_pcb;
368
369 LOG_REL_WAI_ENTER(tskid);
370 CHECK_TSKCTX_UNL();
371 CHECK_TSKID(tskid);
372 p_tcb = get_tcb(tskid);
373
374 t_lock_cpu();
375 p_pcb = t_acquire_tsk_lock(p_tcb);
376 if (!TSTAT_WAITING(p_tcb->tstat)) {
377 ercd = E_OBJ;
378 }
379 else {
380 #if TTYPE_KLOCK == G_KLOCK
381 if (wait_release(p_tcb)) {
382 dspreq = dispatch_request(p_pcb);
383 }
384 #else /* TTYPE_KLOCK != G_KLOCK */
385 if (!TSTAT_WAIT_WOBJ(p_tcb->tstat)) {
386 /* オブジェクト待ちでない場合 */
387 dspreq = wait_release(p_tcb);
388 }
389 else {
390 /*
391 * オブジェクト待ちの場合
392 * デッドロック回避のため,ロックを取得し直す
393 */
394 WOBJCB *p_wobjcb = p_tcb->p_wobjcb;
395 p_tcb->pend_relwai = true;
396 release_tsk_lock(p_pcb);
397
398 /*
399 * あらためて
400 * オブジェクトロック -> タスクロック
401 * の順でロックを取得
402 */
403 retry:
404 t_acquire_obj_lock(&GET_OBJLOCK(p_wobjcb));
405 if ((p_pcb = t_acquire_nested_tsk_lock(p_tcb, &GET_OBJLOCK(p_wobjcb))) == NULL){
406 goto retry;
407 }
408
409 /* タスクの状態が変化していないかチェック */
410 if (!(p_tcb->pend_relwai)) {
411 /* 既に他の箇所で待ち解除処理がなされた */
412 release_nested_tsk_lock(p_pcb);
413 release_obj_lock(&GET_OBJLOCK(p_wobjcb));
414 t_unlock_cpu();
415 ercd = E_OBJ;
416 goto error_exit;
417 }
418 p_tcb->pend_relwai = false;
419 dspreq = wait_release(p_tcb);
420 release_obj_lock(&GET_OBJLOCK(p_wobjcb));
421 }
422 if (dspreq) {
423 dspreq = dispatch_request(p_pcb);
424 }
425 #endif /* TTYPE_KLOCK != G_KLOCK */
426 ercd = E_OK;
427 }
428 release_tsk_lock_and_dispatch(p_pcb, dspreq);
429 t_unlock_cpu();
430
431 error_exit:
432 LOG_REL_WAI_LEAVE(ercd);
433 return(ercd);
434 }


rel_waiサービスコールの処理概要(ジャイアントロック方式以外)

(a)待ち状態でない(376〜378行目)
タスクロックのみ取得
戻り値:E_OBJ(エラー)

(b)待ち状態
(b-1)オブジェクト待ちでない(385〜388行目)
タスクロックのみ取得
待ち状態の強制解除を行う.
戻り値:E_OK

(b-2)オブジェクト待ち(389〜421行目)
タスクロック,オブジェクトロックの両方の取得が必要
タスクロックを取得してはじめて,オブジェクト待ちの対象オブジェクトがわかる.よって,オブジェクトロックを先に取得することができないため,デッドロック回避が必要.デッドロック回避のために,すでに取得しているタスクロックを一旦解放してから,オブジェクトロック→タスクロックの順にロックを取得しなおす.その間に他の処理単位(タスクやハンドラ)が対象タスクを待ち解除しようとする可能性がある.その場合は,他の処理単位が待ち解除を代行する.
TCBに追加したメンバの,pend_relwaiをtrueにすることで,そのタスクが待ち解除実行中であることを表す.他の処理単位が待ち解除しようとしているタスクのpend_relwaiがtrueの場合は,処理を代行する.
(b-2-1)他の処理単位が待ち解除を代行した場合
戻り値:E_OBJ
対象タスクが待ち解除されているので,強制解除の必要がない.
(b-2-2) タスクの状態が変わらなかった場合
戻り値:E_OK
待ち状態の強制解除を行う.





[図1 rel_wai全体の流れ]


それでは,詳細を見ていきます.
380〜384行目はジャイアントロック方式の場合です.ジャイアントロック方式ではデッドロックは発生しませんので,ここでは説明を省略します.

374行目:割込み禁止とする・
375行目:待ち解除するタスクのタスクロックを取得する.

(a)待ち状態でない場合
377行目:ercdにE_OBJを格納し,エラーとする.

(b-1)オブジェクト待ちでない待ち状態
387行目:wait_release()を発行し,ディスパッチが必要かどうかをdspreqに格納する.

[wait_release()の処理概要]
該当タスクの待ち状態を強制解除します.

[kernel/wait.c]
238 bool_t 
239 wait_release(TCB *p_tcb)
240 {
241 wait_dequeue_wobj(p_tcb);
242 wait_dequeue_tmevtb(p_tcb);
243 p_tcb->wercd = E_RLWAI;
244 return(make_non_wait(p_tcb));
245 }


241行目:wait_dequeue_wobj(p_tcb) オブジェクト待ちキューからの削除
p_tcbで指定されるタスクが,同期・通信オブジェクトの待ちキューにつながれていれば,待ちキューから削除する.
242行目:wait_dequeue_tmevtb(p_tcb) 時間待ちのためのタイムイベントブロックの登録解除
p_tcbで指定されるタスクに対して,時間待ちのためのタイムイベントブロックが登録されていれば,それを登録解除する.
243行目:該当タスクのTCBのwercdにE_RLWAIを格納し,強制待ち解除されたことを登録する.
244行目:make_non_wait()を発行する.
※make_non_wait()の詳細については,後述します.

(b-2)オブジェクト待ち状態
394行目:待ち解除するタスクの待ちオブジェクト管理ブロックのアドレスを,*p_wobjcbに格納する.この*p_wobjcbを用いて,オブジェクトロックを取得する.
→ここではじめて,取得するべきオブジェクトロックが判明する.(デッドロック回避が必要)
395行目:pend_relwaiをtrueにし, タスクの強制待ち解除実行中であることを示す.
396行目:375行目で獲得したタスクロックを一旦解放する.
→デッドロック回避のため,オブジェクトロック→タスクロックの順に取得しなおす.取得するべきオブジェクトロックは,394行目で取得済み.

404行目:オブジェクトロックを取得する.
405行目:タスクロックを取得しにいき,t_acquire_nested_tsk_lock()の戻り値がNULLの場合は,403行目からやり直す.
※t_acquire_nested_tsk_lock()の戻り値がNULLの場合は,ロック取得中に割込みが入り,マイグレーションした可能性があることを意味します.
t_acquire_nested_tsk_lock()の詳細は,第18回を参照してください.

(b-2-1)他の処理単位が,待ち解除を代行した場合
410行目:pend_relwaiがfalseの場合
pend_relwaiは,395行目でtrueにしています.それがfalseになっているということは,他のプロセッサが待ち解除を代行したということになります.よって,ここでは待ち解除の処理は行う必要はありません.詳細は後述します.
412行目:タスクロックを解放する.
413行目:オブジェクトロックを解放する.
414行目:割込み許可にする.
415行目:ercdにE_OBJを格納し,エラーとする.

(b-2-2)状態が変化していないとき
待ち解除処理を行います.
418行目:pend_relwaiをfalseにクリアする.
419行目:wait_release()を発行し,ディスパッチが必要かどうかをdspreqに格納する.
420行目:オブジェクトロックを解放する.

(b-1),(b-2-2)の場合の後処理
422行目:dspreqがtrueの場合は,dispatch_request()を発行する.
dspreqは,366行目でfalseに初期化されます.その後,いずれかのプロセッサでディスパッチが必要な場合に,trueになります.
dispatch_request()では,対象タスクの割り付けられているプロセッサが自プロセッサの場合は,trueを返します.他プロセッサの場合は,CPU間割込みを発生させ,falseを返します.
このdispatch_request()の戻り値(dspreq)は,自プロセッサでのディスパッチ必要性の判断に使用されます.
426行目:戻り値をE_OKとする.
428行目:タスクロックを解放し,dspreqがtrueの場合にはディスパッチする.
429行目:割込み許可とする.

前述したように,優先度の変更chg_priサービスコールと,強制待ち解除rel_waiサービスコールは,デッドロック回避のために,タスクロックをいったん解放し,オブジェクトロック->タスクロックの順でロックを取得します.その間に他のタスクやハンドラにより,対象タスクの待ち解除が行われる場合があります.その際,待ち解除を行う処理は全てmake_non_wait()を呼び出します.

リトライなしでデッドロック回避を実現する, chg_priと, rel_waiの処理中であれば,処理を代行します.

[kernel/wait.c]
84 Inline bool_t 
85 make_non_wait(TCB *p_tcb)
86 {
87 assert(TSTAT_WAITING(p_tcb->tstat));
88
89 #if TTYPE_KLOCK != G_KLOCK
90 /* 優先度変更フラグチェック */
91 if (p_tcb->pend_chgpri) {
92 p_tcb->priority = p_tcb->pend_newpri;
93 /* 優先度変更フラグのクリア */
94 p_tcb->pend_chgpri = false;
95 }
96
97 /* タスク強制待ち解除保留クリア */
98 p_tcb->pend_relwai = false;
99 #endif /* TTYPE_KLOCK != G_KLOCK */
100
101 if (!TSTAT_SUSPENDED(p_tcb->tstat)) {
102 /*
103 * 待ち状態から実行できる状態への遷移
104 */
105 p_tcb->tstat = TS_RUNNABLE;
106 LOG_TSKSTAT(p_tcb);
107 return(make_runnable(p_tcb));
108 }
109 else {
110 /*
111 * 二重待ち状態から強制待ち状態への遷移
112 */
113 p_tcb->tstat = TS_SUSPENDED;
114 LOG_TSKSTAT(p_tcb);
115 return(false);
116 }
117 }


91〜95行目:優先度変更中である場合の処理
※ここでは省略します.

98行目:pend_relwaiをfalseにクリアする.
他のプロセッサで該当タスクに対して強制待ち解除中(rel_wai)である場合は,pend_relwaiがtrueになっています.そこで,ここでは保留されている待ち解除処理を代行します. rel_wai(強制待ち解除)処理中では,このpend_relwaiがfalseになっていると,待ち解除処理が他のプロセッサによって代行されたと判断します.

待ち解除した場合のタスクの状態遷移(図2)
待ち状態→実行可能状態
二重待ち状態→強制待ち状態
※強制待ち状態からの再開は,待ち解除(make_non_wait)では行いません.



[図2 タスクの状態遷移]

単なる待ち状態の場合(101〜108行目)
タスクの状態を実行可能状態とし,make_runnable()を発行し,ディスパッチが必要かどうかを戻り値とします.

二重待ち状態の場合(109〜116行目)
タスクの状態を強制待ち状態とし,falseを戻り値とします.