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

第13回 レディキューの操作関数

週末に娘の保育園で劇の発表会がありました.はじめての運動会の時は,知らない間に成長した我が子の姿に,思わず涙がこぼれました.そして,今回も涙が出そうになったところで,娘が舞台の上から私に向かって「ママ,パパはどこ?」.ホール中大爆笑でした.このままのびのび育ってほしいものです.



前回は,TCBの構造とそれを管理するレディキューの構造について解説しました【図13-1】.今回はそのレディキューを操作する関数について解説します.



【13-1 レディキューの構造】

ここで,優先度と優先順位の復習をします.

優先度
タスクやメッセージなどの処理順序を制御するために,アプリケーションによって与えられるパラメータ. ASPカーネルでは,1〜16まで,の16段階としています.

優先順位
処理が実行される順序を決める順序関係.

※優先度と,優先順位
優先度は,アプリケーションによって与えられるパラメータです.それに対し,優先順位は,使用中に処理の実行順序を明確にするために用いる概念です.
(例)同じ優先度のタスクが複数あった場合に,どの順番でタスクが実行されるか.というのが,優先順位.
この関数では,タスクを実行できる状態へ移行します. 
具体的には,レディキューにつながっていなかったTCBを,レディキューに追加します.この関数の引数は,実行可能状態にしたいタスクのTCBです.レディキューにそのTCBを挿入し,その結果p_schedtskが更新された場合はディスパッチが必要です.p_schedtskに変更がなければ,ディスパッチの必要はありません.この関数の戻り値は,ディスパッチが必要かどうかです.

※p_schedtsk
レディキューの中で最高優先順位のタスクを示す変数です.言い換えれば,本来なら動くべきタスクです.p_schedtskには,該当タスクのTCBへのポインタが格納されています.

ソースコードを見て行きます.
</kernel/task.c>
81 QUEUE   ready_queue[TNUM_TPRI];
82
89 uint16_t ready_primap;

232 BOOL
233 make_runnable(TCB *p_tcb)
234 {
235 uint_t pri = p_tcb->priority;
236
237 p_tcb->tstat = TS_RUNNABLE;
238 LOG_TSKSTAT(p_tcb); 
239 queue_insert_prev(&(ready_queue[pri]), &(p_tcb->task_queue));
240 primap_set(pri);
241
242 if (p_schedtsk == (TCB *) NULL || pri < p_schedtsk->priority) {
243 p_schedtsk = p_tcb;
244 return(dspflg); 
245 }
246 return(FALSE);
247 }


81,89行目:タスクの優先度は16段階です.前回解説したように,この16段階の優先度ごとのレディキューを管理するために,ダブルリンクキューのための,QUEUE型配列と,ビットマップのための16bitの変数を宣言します(【図13-1】参照).

233行目:レディキューに挿入したいタスクのTCBを引数TCB *p_tcbで受け取ります.
235行目:該当タスクの優先度を取得します.
237行目:該当タスクの状態を,TS_RUNNABLEにします.

タスクの状態について
TCB内のタスク状態では,実行状態(RUNNING)と実行可能状態(READY)は区別しません.2つの状態を総称してRUNNABLEとしています.待ち状態の表現については後日解説します.TCB内のタスク状態に設定する値は,task.hで以下のように定義されています.


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

239行目:ダブルリンクキューの該当優先度の最後尾に該当TCBを挿入します.(queue_insert_prev()の呼び出し)
以下の例で説明します.



挿入するタスク4の優先度が2だった場合,優先度2のレディキューにはすでに,タスク1とタスク2がつながっています.ASPカーネルのスケジューリング規則は,優先度ベーススケジューリングであり,同一優先度のタスク間ではFIFOスケジューリングがなされます.この場合,優先度2の実行可能状態のタスクは,タスク1,タスク2の順番に実行可能状態となり,レディキューに接続されています.タスク4はこの2つのタスクより後に実行可能状態になったので,優先度2のレディキューの末尾につながります.

※queue_insert_prev()の概要 (詳細は後で解説します.)
第1引数:レディキューの該当優先度のアドレス,第2引数:該当タスクTCBのメンバー<タスクキュー>のアドレス
ダブルリンクキューの該当優先度の前に,このタスクをつなぎます.ダブルリンクキューとTCBはぐるっとつながって輪になっていますので,ダブルリンクキューの前につなぐということは,つまりは最後尾につなぐとこになります.ダブルリンクキューの一個後ろがその優先度における最高優先順位のタスクになります.

240行目:該当優先度のビットマップをセットします.もともと1になっていた場合でも,上書きしています.
242,243行目:p_schedtskを更新する必要があるかどうかを判定します.
p_schedtskを更新する必要があるのは,今まで実行できるタスクがなかったとき(p_schedtskがNULLのとき),もしくは,p_schedtskの優先度より該当タスクの優先度の方が高い(小さい)場合です.この場合は,p_schedtskに該当タスクのTCBへのポインタをセットします.
244行目:戻り値として,ディスパッチフラグを返します.ディスパッチフラグは,ディスパッチ禁止状態ならFALSE, 禁止でなければTRUEとなっています.つまり,p_schedtskが更新された場合,かつ,ディスパッチ禁止状態でないばあいに,TRUEが戻り値となります.



ASPカーネルのスケジューリング規則は,優先度ベーススケジューリングであり,同一優先度のタスク間ではFIFOスケジューリングがなされます.つまり,新たにTCBをレディキューに挿入するときには,該当優先度の末尾に挿入します.


85 Inline void
86 queue_insert_prev(QUEUE *p_queue, QUEUE *p_entry)
87 {
88 p_entry->p_prev = p_queue->p_prev;
89 p_entry->p_next = p_queue;
90 p_queue->p_prev->p_next = p_entry;
91 p_queue->p_prev = p_entry;
92 }


第1引数:レディキューの該当優先度のアドレス,第2引数:該当タスクTCBのメンバー<タスクキュー>のアドレスを受け取ります.



【図13-2 初めの状態】

88行目 p_entry->p_prev = p_queue->p_prev;
挿入するTCBのp_prevが,現在ダブルリンクキュートップのp_prevが指しているTCBを指すようにします.



89行目 p_entry->p_next = p_queue;
挿入するTCBのp_nextが,ダブルリンクキュートップを指すようにします.



90行目 p_queue->p_prev->p_next = p_entry;
p_queue->p_prev->p_next ダブルリンクキュートップのp_prev,つまり最後尾のTCBのp_nextが,p_entryを指すようにします.



91行目 p_queue->p_prev = p_entry;
ダブルリンクキュートップのp_prevがp_entryを指すようにします.


タスクを実行できる状態から他の状態へ移行します.そして,レディキューにつながっているTCBをはずします.
この関数の引数は,レディキューから外すタスクのTCBです.
この関数でのポイントは,レディキューから外すタスクが,p_schedtskだった場合です.その場合には,p_schedtskを更新する必要があります.削除するタスクがどういう状態かによって,場合分けが必要です.

</kernel/task.c>
261 BOOL
262 make_non_runnable(TCB *p_tcb)
263 {
264 uint_t pri = p_tcb->priority;
265 QUEUE *p_queue = &(ready_queue[pri]);
266
267 queue_delete(&(p_tcb->task_queue));
268 if (queue_empty(p_queue)) {
269 primap_clear(pri);
270 if (p_schedtsk == p_tcb) {
271 p_schedtsk = primap_empty() ? (TCB * ) NULL : search_schedtsk();
272 return(dspflg);
273 }
274 }
275 else {
276 if (p_schedtsk == p_tcb) {
277 p_schedtsk = (TCB *)(p_queue->p_next);
278 return(dspflg);
279 }
280 }
281 return(FALSE);
282 }




268行目からの流れを以下の図に示します.【図13-3】



【図13-3 p_schedtskの更新】





【図13-4 同優先度にタスクがいない例】

STEP1〜STEP5は,レディキューから外すタスクと同じ優先度のタスクがいない場合,【図13-4】
でタスク3をレディキューから外すような場合です.p_schedtskはタスク4になります.






【図13-5 同優先度にタスクがいる例】

STEP6〜STEP9は,レディキューから外すタスクと同じ優先度に他のタスクがつながっている場合,【図13-5】でタスク1をレディキューに外す場合です.p_schedtskはタスク2になります.



262行目:削除するタスクのTCBを引数TCB *p_tcbで受け取ります.
264行目:該当タスクの優先度を取得します.
265行目:該当タスクがつながっているレディキューの,該当優先度を示すアドレスを取得します.
267行目:レディキューからTCBを削除します.(queue_delete()の呼び出し)
※queue_delete()については,後ほど解説します.


STEP1
268行目;レディキューから外したタスクと同じ優先度に,他のタスクがいなければ
STEP2
269行目:ビットマップをクリア
STEP3
270行目:外したタスクが,p_schedtskだった場合
STEP4
271行目:レディキューに他にタスクがつながっていない場合は,p_schedtskをNULLに,他にタスクがレディキューにつながっている場合は,最高優先順位のタスクを探します.(search_schedtsk())
※ search_schedtsk()については,後ほど解説します.
STEP5
272行目:ディスパッチフラグを戻り値とします.
275行目:レディキューから外したタスクと同じ優先度に他のタスクがいる場合
STEP6
276行目:外したタスクが,p_schedtskだった場合
STEP7
277行目:該当タスクの次につながっているタスクを,p_schedtskとします.

続いて,先ほどのmake_non_runnable関数から呼ばれる,レディキューからTCBを外す関数を見ていきます.



99 Inline void
100 queue_delete(QUEUE *p_entry)
101 {
102 p_entry->p_prev->p_next = p_entry->p_next;
103 p_entry->p_next->p_prev = p_entry->p_prev;
104 }




【図13-6 始めの状態】

102行目 p_entry->p_prev->p_next = p_entry->p_next;
レディキューから外すタスクの前につながっているTCBのp_nextが,レディキューから外すタスクの次につながっているTCBを指すようにします.



103行目 p_entry->p_next->p_prev = p_entry->p_prev;
レディキューから外すタスクの次のTCBのp_revが,削除するタスクの前のTCBを指すようにします.




続いて,make_non_runnable関数から,STEP4で呼ばれるsearch_schedtsk関数を見ていきます.


212 TCB *
213 search_schedtsk(void)
214 {
215 uint_t schedpri;
216
217 schedpri = primap_search();
218 return((TCB *)(ready_queue[schedpri].p_next));
219 }




217行目:primap_search()は,ビットマップをサーチして,レディキューにつながっているTCBが存在する優先度のうち,最高優先度を求める関数です.
218行目:217行目でレディキューにTCBが存在する優先度のうち,最高優先度が,schedpriに格納されていますので,ready_queue[schedpri].p_nextが,求めるTCBとなります.