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

第19回 待ちオブジェクトのコントロールブロック構造

主人が「北斗の拳」DVD全巻を借りてきました.私ははじめて観たのですが,こんなに面白いとは知りませんでした.当時同級生が,「おまえはもう死んでいる」と,ケンシロウの決め台詞を言いあっていたのを思い出します.GWは「北斗の拳」三昧になりそうです.




今回は,待ちオブジェクトのコントロールブロックの構造について解説します.ここでは,セマフォ待ちの場合にタスクとセマフォが管理するデータ構造を例にして解説します.
セマフォとは,使用されていない資源の有無や数量を数値で表現することにより,その資源を使用する際の排他制御や同期を行うためのオブジェクトです.セマフォは対応する資源の有無や数量を表現する資源数と,資源の獲得を待つタスクの待ち行列を持ちます.資源を返却する側では,セマフォの資源数を1つ増やします.セマフォの資源数が足りなくなった場合は,資源を獲得しようとしたタスクは,次に資源が返却されるまでセマフォ資源の獲得待ち状態となります.セマフォ資源の獲得待ち状態になったタスクは,そのセマフォの待ち行列につながれます.
また,セマフォに対して資源が返却され過ぎるのを防ぐために,セマフォごとに最大資源数を設定することができます.最大資源数を超える資源がセマフォに返却されようとした場合には,エラーとなります.
次に,第16回でも解説しましたが,待ち状態を管理するデータ構造について復習します.

null

【図1 セマフォ待ち状態時のデータ構造】

図1にセマフォ待ち状態時に形成するデータ構造を示します.

セマフォ待ち状態を管理するために必要な情報

A.タスク側で管理すべき情報
A- .織好が待ち状態であること [TCBのtstat]
A-◆‖圓曽態となっている要因 どうして待ち状態になったのか[TCBのtstat]
A- 待っているオブジェクト[WINFOのwobjcb]
A-ぁ‖圓辰討い襯ブジェクトの付随情報(オブジェクトによって必要なものと必要でないものがある)[WINFO_xxx]→セマフォの場合は必要ありません.
A-ァ‖圓漸鮟時のエラーコードを返すための情報[WINFOのwercd]
A-Α.織ぅ爛▲Ε箸亡悗垢訃霾鵝淵織ぅ爛▲Ε箸垢襯機璽咼好魁璽襪両豺隋[WINFOのtmevtb]

タスク側で管理する情報については,第12回で解説しました.

B.セマフォごとに管理すべき情報とその管理場所
B- .札泪侫ID[SEMCBのインデックス]
B-◆.札泪侫属性[SEMINIBのsematr]
B- セマフォの資源数の初期値[SEMINIBのisemcnt]
B-ぁ.札泪侫の最大資源数[SEMINIBのmaxsem]
B-ァ.札泪侫待ちキュー[SEMCBのtask_queue]
B-Α.札泪侫の資源数[SEMCBのsemcnt]

上記のようにセマフォごとに管理すべき情報は,SEMCBとSEMINIBに記憶されます.
ASPカーネルはRAMの使用量を抑える方針をとっています.そこで,セマフォにもこの方針を適用し,ROMに置くことができる情報はできるだけROMに置き,RAM使用量を抑えています.つまり,セマフォごとに管理する情報を,システム稼働中に変わらない情報と,サービスコール発行で変わる可能性のある情報の二つにわけて管理しています.
システム稼働中に値が変わらないためにROMに置くことができる情報を「セマフォ初期化ブロック(SEMINIB)」と呼ぶ構造体に,サービスコール発行によって値が変化するためにRAMに置かなければならない情報を「セマフォ管理ブロック(SEMCB)」と呼ぶ構造体に格納するようして分離しています.1つのセマフォに対して,それぞれ1つのSEMINIBと1つSEMCBがあるわけです.この2つの構造体で1つのセマフォを管理しています.
では,どの情報をどちらに入れるのでしょうか?

セマフォの生成静的APIは以下のように,セマフォの属性,セマフォ資源の初期値,セマフォ最大資源数を引数として持ちます.

CRE_SEM(ID semid,{ATR sematr,UINT isemcnt,UINT maxsem})
つまり,この3つの情報はシステム稼働中に変わらない情報と言えます.よって,この3つの情報は,SEMINIBに置き,他の情報はシステム稼働中に変化しますので,SEMCBに置く仕組みとしています.


※SEMCB領域,SEMINIB領域の割付方法
SEMCBとSEMINIBは以下のように,構造体で定義されています.

kernel/semaphore.h

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


セマフォ初期化ブロック
59 typedef struct semaphore_initialization_block {
60 ATR sematr; /* セマフォ属性 */
61 uint_t isemcnt; /* セマフォの資源数の初期値 */
62 uint_t maxsem; /* セマフォの最大資源数 */
63 } SEMINIB;



・SEMCB領域
セマフォ数分の要素を持つ,SEMCB型構造体配列で定義(semcb_table)されています.この構造体配列の中身は,実行中に値が変わりますので,RAMに生成されます.

・SEMINIB領域
同様にSEMINIB型構造体配列で定義されています(seminib_table).ただし,内容が定数の配列ですので,コンフィギュレータがconst配列としてROMに生成します.

図1のデータ構造を形成する,それぞれの構造体の存在場所を図2に示します.




【図2 各構造体の存在場所】


セマフォ待ちキュー
セマフォの獲得を待っているタスクを,セマフォ待ちキューで管理します.セマフォ待ちキューとは,タスクのTCBをセマフォを獲得できる順序でつないだキューのことです.

では,セマフォ待ちキューの構造を図3に示します.



【図3 セマフォ待ちキュー構造】


セマフォ管理ブロックをトップとした,ダブルリンクキューを形成します.ダブルリンクキューの順序は,セマフォ属性によりFIFO順,または優先度順に管理できます.
先頭タスク以外のタスクのTCBはTCBのタスクキュー領域(tsk_queue)を使用して,順にダブルリンクキューを形成します.

この方法だと,FIFO順の場合はタスクを追加する際,キューの末尾に挿入すればよいので問題はありませんが,優先度順に管理する場合,キューの先頭から挿入場所を探しますので,オーダーn(タスクの数)の時間がかかります.ですから,1つのセマフォに対して,たくさんタスクが待っていると時間がかかる可能性があります.こういった問題を解決するために,レディキューの場合は,キューをタスクの優先度分(16個)持ち,さらにビットマップを持っています(図4).
このようなキュー構造にすることで,優先度順の管理がしやすくなり,処理速度の向上を望むことができます.




【図4 レディキューの構造】


このレディキューの構造は,ダブルリンクキューなので,1つのキュー(ダブルリンクキュートップ)に8バイト必要です.8バイト×16(段階)=128バイトこれに,ビットマップの領域2バイトを加えて,130バイト必要になります.
レディキューはカーネル全体に1つしか存在しませんが,もしセマフォでもこのような構造を採用すると,セマフォの数分この構造が必要です.セマフォを1つ増やすたびに,130バイト必要領域が増えるという計算になります.処理速度を追求するシステムではセマフォごと上記の構造を用意するといった実装もあり得ますがASPでは選択していません.1つのセマフォに,待ちタスクが大量に並ぶことはないだろうという予想と,そしてできるだけRAM使用量を抑える方針から,図3のような構造にしています.

同期通信オブジェクトには,セマフォ,イベントフラグ,データキューなどがあります.それぞれ図1に示したようなデータ構造,図3に示したようなキュー構造を形成します.そして,それらの構造は同じ要素が多くあります.その同じ要素を抜き出して共通部分として定義しています.そうすることによって,それらの構造を管理する処理関数も共通化でき,管理を効率化しています.


データ構造の共通化
同期通信オブジェクトの初期化ブロックとコントロールブロックには,共通部分が多くありますので,共通部分を抜き出して定義しています.オブジェクト指向でいう親クラスです(図5).また,それを扱う関数も,共通に利用できるものが多くあります.

null

【図5 同期通信オブジェクト待ちの共通データ構造】

同期・通信オブジェクト初期化ブロックの共通部分WOBJINIB 
・オブジェクトの属性(wobjatr)

同期・通信オブジェクト管理部分の共通部分WOBJCB 
・待ちキュー(wait_queue)
・初期化ブロックへのポインタ(*p_wobjinib)

同期・通信オブジェクト待ち情報管理ブロックの共通部分WINFO_WOBJ
・winfo 標準の待ち情報ブロック (WINFO)
・待ちオブジェクトの管理ブロックへのポインタ(*p_wobjcb)

図5のような親クラスとなる構造を定義して,この構造を継承する形で各オブジェクトごとの構造を定義しています.オブジェクトごとに必要な情報を追加して,子クラス生成するイメージです.セマフォ例をオブジェクト指向的に表現すると,図6のようになります.



【図6 共通データ構造とセマフォデータ構造との関係】


このように,共通データ構造で足りない部分を追加して,各オブジェクトごとに必要なデータ構造を定義しています.


関数の共通化
上記のように,同期・通信オブジェクト待ちの際に構成されるデータ構造を共通化しているので,この構造を形成する関数も共通化できます.

例えば,図5の構造体同士のリンク構造を構成するwobj_make_wait関数を見てみましょう.

/kernel/wait.c
195 void
196 wobj_make_wait(WOBJCB *p_wobjcb, WINFO_WOBJ *p_winfo_wobj)
197 {
198 make_wait((WINFO *) p_winfo_wobj);
199 wobj_queue_insert(p_wobjcb);
200 p_winfo_wobj->p_wobjcb = p_wobjcb;
201 LOG_TSKSTAT(p_runtsk);
202 }


STEP1:make_wait関数では,実行中のタスクを待ち状態へ移行させ,TCBとWINFO_WOBJを接続します.

STEP2:wobj_queue_insert関数では,実行中のタスクを,同期・通信オブジェクトの待ちキューへ挿入します.該当オブジェクトに対して待っているタスクがない場合,WOBJCBのwait_queueに実行中のタスクを登録します(図7).待っているタスクが既にいた場合は,キューに挿入します.

STEP3: p_winfo_wobj->p_wobjcb = p_wobjcb;
WINFO_WOBJのp_wobjcbにWOBJCBのアドレスを登録して,WINFO_WOBJとWOBJCBを接続します.

STEP1〜STEP3の各処理で接続される箇所を図7に示します.
同期・通信オブジェクト待ちの場合のデータ構造を共通化することで,この構造を構成する関数も共通化することができています.





【図7 同期・通信オブジェクト待ち共通データ構造の生成】

同じように,同期・通信オブジェクトタイムアウトつき待ち状態にする関数,wobj_make_wait_tmoutも同様に共通化しています.こちらは,wobj_make_wait関数の機能に加えて,タイムアウト処理のためのタイムイベントブロックを登録する処理が追加されています.

次回は,今回解説した構造を使用するサービスコールwai_sem,sig_semの解説を行います.