リアルタイムOSの内部構造を見てみよう!

第16回 待ち状態を管理するためのデータ構造

春うらら♪
急に春になりました.外を歩くと自然に笑顔になります.秋冬に聴いていた音楽が重く感じられるようになったので,音楽を衣替えしました.先月発売になった,ブラジリアン・ポップのアルバムが今の気分にぴったりです.


前回までのソースコードの解説の中で,休止状態,実行可能状態,実行状態の管理の仕方については触れてきました.今回はそれに加えて,待ち状態の管理の仕方について解説します.待ち状態の管理の仕方は他の状態と比較して少し複雑です.
ASPカーネルの仕様において,タスクが待ち状態になる要因(タスクが待ち状態となる可能性のあるシステムコール)を洗い出したものを以下に示します.

a. 起床待ち状態(slp_tsk)
b. 時間経過待ち状態(dly_tsk)
c. セマフォ資源の獲得待ち状態(wai_sem等)
d. イベントフラグ待ち状態(wai_flg等)
e. データキューへの送信待ち状態(snd_dtq等)
f. データキューから受信待ち状態(rcv_dtq等)
g. 優先度データキューへの送信待ち状態(snd_pdq等)
h. 優先度データキューからの受信待ち状態(rcv_pdq等)
i. メールボックスからの受信待ち状態(rcv_mbx等)
j. 固定長メモリブロックの獲得待ち状態(get_mpf等)

この中で,a,bは他のc〜jまでの要因とタイプが違います.この二つはオブジェクトがかかわっていない.タスク単独で作られる待ち状態です.これに対して,c〜jは,何らかのオブジェクトを待っている状態です.この2つは単に待ち状態と言っても,性質が異なりますので扱いも違ってきます.

次に待ち状態を管理するために必要な情報を見ていきます.待ち状態になっているタスク側で管理する情報と,待っているオブジェクト側で管理する情報があります.

まず,タスク側で管理する情報です.
A- .織好が待ち状態であること 
A-◆‖圓曽態となっている要因 どうして待ち状態になったのか
A- 待っているオブジェクト
A-ぁ‖圓辰討い襯ブジェクトの付随情報(オブジェクトによって必要なものと必要でないものがある)
A-ァ‖圓漸鮟時のエラーコードを返すための情報
A-Α.織ぅ爛▲Ε箸亡悗垢訃霾鵝淵織ぅ爛▲Ε箸垢襯機璽咼好魁璽襪両豺隋

次は,待ちオブジェクト側で管理すべき情報です.
B- ‖圓曽態のタスクキュー
B-◆‖圓船ブジェクトの状態(セマフォのカウント値,イベントフラグのビットパターン)


では,具体的に待ち状態をどのように管理しているか見ていきましょう.

A-.織好が待ち状態であること 
タスクの状態は,TCB中のtstatで管理していました.また,実行状態と実行可能状態は区別せず,実行できる状態(RUNNABLE)と呼びTS_RUNNABLEと定義しています.そして,休止状態をTS_DORMANT,待ち状態をTS_WAITING,強制待ち状態をTS_SUSPENDEDと定義しています.二重待ち状態は,(TS_WAITING | TS_SUSPENDED)で表現します.
それぞれの状態の定義は以下のようにしています.

/kernel/task.h
67 #define TS_DORMANT      0x00U           /* 休止状態 */
68 #define TS_RUNNABLE 0x01U /* 実行できる状態 */
69 #define TS_WAITING 0x02U /* 待ち状態 */
70 #define TS_SUSPENDED 0x04U /* 強制待ち状態 */


次に.タスクの状態を判別するマクロは以下のようになっています.

/kernel/task.h
91 #define TSTAT_DORMANT(tstat)    ((tstat) == TS_DORMANT)
92 #define TSTAT_RUNNABLE(tstat) (((tstat) & TS_RUNNABLE) != 0U)
93 #define TSTAT_WAITING(tstat) (((tstat) & TS_WAITING) != 0U)
94 #define TSTAT_SUSPENDED(tstat) (((tstat) & TS_SUSPENDED) != 0U)


つまり,実行できる状態,待ち状態,強制待ち状態を表現するのに,それぞれ1ビットずつ割り当て合計3ビットで表現しています.(【図16-1】)



【図16-1 タスクの状態のビット割り当て】

たとえば,実行できる状態の時,tstatの状態は,【図16-2】になっています.


【図16-2 実行できる状態時のtstat】
よって,現在のタスクの状態が実行できる状態かどうかは,TS_RUNNABLEかどうかを表しているビットに,1が立っているかどうかを調べることで判定できます.(92行目)

同じように,待ち状態の時のts_tatの状態は,【図16-3】のようになっています.


【図16-3 待ち状態時のtstat】

二重待ち状態のときは,【図16-4】になっています.


【図16-4 二重待ち状態時のtstat】

よって,TS_WAITINGかどうかを表すビットに1が立っているときは,待ち状態もしくは,二重待ち状態のときと言えます.よって,93行目は,待ち状態と二重待ち状態のいずれかであることを判定するマクロです.
同様に94行目は,強制待ち状態と二重待ち状態のいずれかであることを判定するマクロです.

A-待ち状態となっている要因
ここまでで,タスクの状態が,休止状態,実行できる状態,待ち状態,強制待ち状態,二重待ち状態のいずれであるかを区別できるようになりました.これは,TCBのtstatの3bitを使用して表現しています.
残りの5ビットのうち4ビットを使用して,待ち状態の時の待ち要因の情報を格納します.これは待ち状態(二重待ち状態も含みます)の場合にのみ設定するビットです.



前述のASPカーネルの仕様での10の待ち要因を,それぞれ以下のようにマクロ定義しています.

/kernel/task.h
72 #define TS_WAIT_DLY     (0x00U << 3)    /* 時間経過待ち */
73 #define TS_WAIT_SLP (0x01U << 3) /* 起床待ち */
74 #define TS_WAIT_RDTQ (0x02U << 3) /* データキューからの受信待ち */
75 #define TS_WAIT_RPDQ (0x03U << 3) /* 優先度データキューからの受信待ち */
76 #define TS_WAIT_SEM (0x04U << 3) /* セマフォ資源の獲得待ち */
77 #define TS_WAIT_FLG (0x05U << 3) /* イベントフラグ待ち */
78 #define TS_WAIT_SDTQ (0x06U << 3) /* データキューへの送信待ち */
79 #define TS_WAIT_SPDQ (0x07U << 3) /* 優先度データキューへの送信待ち */
80 #define TS_WAIT_MBX (0x08U << 3) /* メールボックスからの受信待ち */
81 #define TS_WAIT_MPF (0x09U << 3) /* 固定長メモリブロックの獲得待ち */


以下に,それぞれの待ち要因時のTCBのtstatの状態を示します.

a. 時間経過待ち TS_WAIT_DLY



b. 起床待ち TS_WAIT_SLP



c. データキューからの受信待ち TS_WAIT_RDTQ



d. 優先度データーキューからの受信待ち TS_WAIT_RPDQ



e. セマフォ資源の獲得待ち TS_WAIT_SEM



f. イベントフラグ待ち TS_WAIT_FLG



g. データキューへの送信待ち TS_WAIT_SDTQ



h. 優先度データキューへの送信待ち TS_WAIT_SPDQ



i. メールボックスからの受信待ち TS_WAIT_MBX



j. 固定長メモリブロックの獲得待ち TS_WAIT_MPF




この,待ち状態の並べ方の順番には意味がありますが,後日解説します.
オブジェクトが絡まない場合,つまりタスク単独で作られる待ち状態の管理について解説します.
この状態には,slp_tskを発行して起床待ち状態になっている,.dly_tskを発行して時間経過待ち状態になっている2通りの場合があります.


【図16-5 オブジェクト待ちでない待ち状態の管理方法】

TCB中のp_winfo(待ち情報ブロックへのポインタ)に,そのタスクの待ち情報を管理するWINFO型の待ち情報管理ブロックへのポインタを格納します.

【WINFO型】
/kernel/task.h
157 typedef union waiting_information {
158 ER wercd; /* 待ち解除時のエラーコード */
159 TMEVTB *p_tmevtb; /* 待ち状態用のタイムイベントブロック */
160 } WINFO;


WINFO(待ち情報管理ブロック)には,待ち解除した時のエラーコードを入れるwercd,タイムアウトがあるサービスコールの場合,タイムアウトキューにつなぐためのp_tmevtbの2つのメンバを持っています.これら2つともTCBに置くという設計方法もありますが,WINFO型の構造体としてTCBから切り離しています.この2つの情報は,タスクが待ち状態でない場合は必要のない情報です.待ち状態になった時だけ必要です.そのため,TCBから切り離して,待ち状態となって必要な時だけタスクのスタックに領域を確保するという方法を取っています.このように,RAM使用量をできるだけ抑えています.具体的には待ち状態となるシステムコールの内のローカル変数として確保します.詳細については,次回以降のシステムコールの解説で説明したいと思います.また,タイムアウトするためにタイムイベントキューにつなぐ場合は,TMEVTB(タイムイベントブロック)へのポインタを,WINFO中のp_tmevtbに格納します.タイムイベントブロックもタイムアウトしない時には必要のない領域ですので,TMEVTBとして分離することで,RAM使用量を少しでも抑えています.さらに,WINFOの個々のメンバを見てみると,wercdには待ち解除後にエラーコードをいれますので,このスペースが必要となるのは待ち解除後です.それに対して,p_tmevtbは待ち解除後には必要のない領域ですので,WINFOはこの2つのメンバを共用体として持つことにより,RAM使用量を抑えています.(→A-ヂ圓漸鮟時のエラーコードを返すための情報,A-Ε織ぅ爛▲Ε箸亡悗垢訃霾鵝
同期・通信オブジェクトに対する待ち状態の場合について,セマフォ資源待ち状態の管理方法を例に解説します.
まず,同期・通信オブジェクトに対する待ちの場合に必要な,共通する構造について解説します.同期・通信オブジェクト待ちの場合は,どのオブジェクトで待ち状態になっているかという情報が必要です.先ほど出てきたWINFOに,p_wobjcbを追加した構造体(WINFO_WOBJ)を使用します.どのオブジェクトで待っているかという情報が必要なため,このメンバが必要です.(→A-B圓辰討い襯ブジェクト)

WINFO,WINFO_WOBJともに,待ち状態になっているタスクごとに必要な情報です.

【WINFO-WOBJ型】
/kernel/wait.h
218 typedef struct wait_object_waiting_information {
219 WINFO winfo; /* 標準の待ち情報ブロック */
220 WOBJCB *p_wobjcb; /* 待ちオブジェクトの管理ブロック */
221 } WINFO_WOBJ


p_wobjcbには,待ち対象の同期・通信オブジェクトの管理ブロックへのポインタを格納します.このp_wobjcbポインタ変数の型WOBJCBは,そのオブジェクトを待ちになっているタスクのキュー(→B-‖圓曽態のタスクキュー)と,そのオブジェクトの初期化ブロック(WOBJCB型)へのポインタから構成されます.

【WOBJCB型】
/kernel/wait.h
206 typedef struct wait_object_control_block {
207 QUEUE wait_queue; /* 待ちキュー */
208 const WOBJINIB *p_wobjinib; /* 初期化ブロックへのポインタ */
209 } WOBJCB;



【図16-6 同期・通信オブジェクト待ちの管理方法(基本形)】

【図16-6】の形が基本となります.WINFO-WOBJと,TMEVTBは待ち状態のタスクごとに持つ情報です.それに対して,WOBJCBは,オブジェクトごとに持つ情報です.【図16-6】では,1つのオブジェクトに対して,1つのタスクが待ち状態になっている様子を表現していますが,実際には,1つのオブジェクトに対して,複数のタスクが待っていることもあります.(【図16-7】)



【図16-7 タスクごとに管理する情報とオブジェクトごとに管理する情報の多重度】

【図16-7】では,1つのオブジェクトに対して,複数のタスクが関連している,つまり複数のタスクが待ち状態となる可能性があることを表しています.

【図16-6】が基本形ですが,これに同期・通信オブジェクトごとに必要な固有の情報がある場合には,WINFO_WOBJ,WOBJCBの代わりの構造体を定義して使用します.次にセマフォの例で解説します.


セマフォ資源の獲得待ち状態

セマフォ管理ブロック(SEMCB)には,同期・通信オブジェクトの管理ブロック基本形(WOBJCB)に加えて,セマフォの現在カウント数を記憶する必要があります.これは,セマフォオブジェクト固有の情報で,かつ待っているタスクごとに管理する情報でなく,セマフォ側が管理する情報です.よって,オブジェクトが管理する情報WOBJCBの代わりにSEMCBを定義して,それに付随して,WINFO_OBJの代わりにWINFO_SEMを定義して使用します.(→B-待ちオブジェクトの状態)

【WINFO_SEM型】
/kernel/semaphore.h
85 typedef struct semaphore_waiting_information {
86 WINFO winfo; /* 標準の待ち情報ブロック */
87 SEMCB *p_semcb; /* 待っているセマフォの管理ブロック */
88 } WINFO_SEM;


【SEMCB型】
/kernel/semaphore.h
72 typedef struct semaphore_control_block {
73 QUEUE wait_queue; /* セマフォ待ちキュー */
74 const SEMINIB *p_seminib; /* 初期化ブロックへのポインタ */
75 uint_t semcnt; /* セマフォ現在カウント値 */
76 } SEMCB;



【図16-8 セマフォ待ち状態の管理方法】

【図16-8】のような構造にすることで,セマフォ側では自分をどのタスクが待っているかを,SEMCBのwait_queueから知ることができます.また,TCB側からも,自分がどのセマフォで待っているかを,TCB→*p_winfo→p_semcbでSEMCBにたどり着くことができます.

このように,セマフォ側から待っているタスクを知る必要性は,セマフォが返却された結果,待っているタスクの待ち状態を解除するような場合に必要です.また,タスクが強制終了させられた場合にそのタスクをセマフォ待ちキューから外す必要があるので,タスク側からもセマフォの情報にたどり着く必要性があります.上記の構造にすることで,TCBからSEMCBへ,SEMCBからTCBへの両方のルートを確保したことになります.

イベントフラグ待ち状態

最後に,タスク側で管理するA-ぢ圓辰討い襯ブジェクトの付随情報が必要な例として,イベントフラグ待ち状態について解説します.

イベントフラグ管理ブロック(FLGCB)には,同期・通信オブジェクトの管理ブロック基本形(WOBJCB)に加えて,イベントフラグの現在パターンを記憶する必要があります.これは,イベントフラグオブジェクト固有の情報で,かつ待っているタスクごとに管理する情報でなく,イベントフラグ側が管理する情報です.よって,オブジェクトが管理する情報WOBJCBの代わりにFLGCBを定義して,それに付随して,WINFO_OBJの代わりにWINFO_FLGを定義して使用します.ここまでは,セマフォの場合と考え方は同じです.さらにイベントフラグの場合は,そのイベントフラグをその該当タスクがどうやって待っているか.というタスクごとに管理する情報があります.タスクごとに管理するイベントフラグに関する情報は,該当イベントフラグの待ちパターン,待ちモード(and,or),待ち解除時に設定するパターンの3つです.そこで,タスクごとに管理しているイベントフラグ待ち情報管理ブロック(WINFO_FLG)に,それぞれwaiptn,wfmode,flgptnというメンバを設けて管理しています.(A-ぢ圓辰討い襯ブジェクトの付随情報)【図16-9】



【図16-9 イベントフラグ待ち状態の管理方法】

【WINFO_FLG型】
/kernel/eventflag.h
87 typedef struct eventflag_waiting_information {
88 WINFO winfo; /* 標準の待ち情報ブロック */
89 FLGCB *p_flgcb; /* 待っているイベントフラグの管理ブロック */
90 FLGPTN waiptn; /* 待ちパターン */
91 MODE wfmode; /* 待ちモード */
92 FLGPTN flgptn; /* 待ち解除時のパターン */
93 } WINFO_FLG;


【FLGCB型】
/kernel/eventflag.h
71 typedef struct eventflag_control_block {
72 QUEUE wait_queue; /* イベントフラグ待ちキュー */
73 const FLGINIB *p_flginib; /* 初期化ブロックへのポインタ */
74 FLGPTN flgptn; /* イベントフラグ現在パターン */
75 } FLGCB;



今回解説した同期・通信待ちオブジェクトの管理構造の具体的な使用方法は,次回以降のサービスコールの解説の中で具体的に示したいと思います.