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

第12回 TCBとレディキューの構造

バレンタインデーはいかがでしたか?通勤時に聞いているラジオ番組の中に,「海外で活躍する日本人に電話を繋ぐ」というコーナーがあります.その中でロンドン在住の方が,「イギリス人のバレンタインデープレゼントの平均予算は,19,000円」とおっしゃっていました.日本とは習慣が少し異なるのでしょうか,「高い!!」というのが私の感想です.


今回は,タスクコントロールブロック(TCB)の構造と,それを管理するレディキューについて解説します.これまでにも,ディスパッチする際に,スタックに保存する情報とTCBに保存する情報があるといったように,TCBにまつわる話は出てきましたが,今回は詳しくTCBの構造を解説します.
今後,1つの機能を解説するために,複数のファイルを参照することが多くなります.その都度,参照するファイルの存在場所も記載していきます.そこで,ASPカーネルのディレクトリー構成をもう一度示します.(第3回 解説済み)

ASPカーネルのデイレクトリ構成
\include アプリケーション向けヘッダファイル
\kernel カーネルのソースファイル
\syssvc シリアルドライバ,システムログタスクなどの,システムサービスソースファイル
\library サポートライブラリソースファイル
\target ターゲット依存部
\arch ターゲット依存部の共通部分
\pdic デバイスドライバのターゲット依存部
\cfg カーネルのコンフィギュレータ
\utils ユーティリティプログラム
TCBとは,タスクごとに管理すべき情報を格納するものです.タスク1つに対して,1つのTCBが存在します.
第3回で解説しましたが,ASPカーネルはRAMの使用量を抑える方針をとっています.そこで,TCBにもこの方針を適用し,ROMに置くことができる情報はできるだけROMに置き,RAM使用量を抑えています.つまり,タスクごとに管理する情報を,システム稼働中に変わらない情報と,サービスコール発行で変わる可能性のある情報の二つにわけて管理しています.
システム稼働中に値が変わらないためにROMに置くことができる情報のかたまり(構造体)を「タスク初期化ブロック(TINIB)」とし,サービスコール発行によって値が変化するためにRAMに置かなければならない情報のかたまり(構造体)を「タスク管理ブロック(TCB)」として分離しています.1つのタスクに対して,それぞれ1つのTINIBと1つTCBがあるわけです.この2つの構造体で1つのタスクを管理しています.そしてこの2つの構造体をつなぐために,TCB内に対応するタスク初期化ブロックをさすポインタを格納しています.【図12-1】
TINIB内に,対応するTCBを指すポインタを入れるほうがRAM節約の観点からは望ましいのですが,実行効率が悪くなるため採用していません.



【図12-1 TINIBとTCBの関係】

TINIBの構造

では,TINIBの構造をソースコードで詳しく見ていきましょう.

176 typedef struct task_initialization_block {
177 ATR tskatr; /* タスク属性 */
178 intptr_t exinf; /* タスクの拡張情報 */
179 TASK task; /* タスクの起動番地 */
180 uint_t ipriority;  /* タスクの起動時優先度(内部表現) */
181 SIZE stksz; /* スタック領域のサイズ(丸めた値) */
182 void *stk; /* スタック領域の先頭番地 */
183
184 ATR texatr; /* タスク例外処理ルーチン属性 */
185 TEXRTN texrtn; /* タスク例外処理ルーチンの起動番地 */
186 } TINIB;


このようにTINIBは,構造体でタスクごとに管理すべき情報のうち,システム稼働中に値が変わらないものを管理しています.その変わらない値は,タスク生成静的API(CRE_TSK())でアプリケーションエンジニアが指定した値になります.

タスク生成静的API
CRE_TSK(ID tskid, { ATR tskatr, intptr_t exinf, TASK task, PRI itskpri, SIZE stksz, STK_T *stk })

ここで指定した値が,タスク初期情報となってTINIBに格納されます.

<タスク初期情報>
1. tskatr タスクの属性
((TA_HLANG || TA_ASM)|[TA_ACT])の指定ができます.TA_HLANG(=0x00)が指定された場合は,高級言語用のインターフェース,TA_ASM(=0x01)が指定された場合にはアセンブリ言語用のインターフェースでタスクを起動します.TA_ACT(=0x02)が指定されない場合には,対象タスクを休止状態に移行させ,指定された場合には対象タスクを実行可能状態に移行させます.
※ “||”は,両項のうちどちらかを指定可能,“|”の後ろの指定はしてもしなくてもいいという意味です.
2. exinf タスクの拡張情報
タスクを起動させる際のパラメータ
3. task タスクの起動番地
4. ipriority タスクの起動時優先度(内部表現)
5. stksz スタック領域のサイズ
6. *stk スタック領域の先頭番地
stkで指定された番地からstkszバイトのメモリ領域を,タスクが実行するためのスタック領域として使用します.stkにNULL(=0)が指定された場合は,stkszで指定されたサイズのメモリ領域をカーネルが確保します.
7. texatr タスクの例外処理ルーチン属性
8. texrtn タスクの例外処理ルーチンの起動番地

上記の静的APIをコンフィギュレーションファイルに記述することによって,コンフィギュレータがkernel_cfg.cを生成します.その中で,TINIBを生成しています.ASPではタスクを静的に生成しますので,コンフィグレーションファイルにCRE_TSKで記述されたタスクが生成されます.そして,タスクの数だけTINIBが存在しますので,構造体配列の形でTINIBを扱います.


コンフィギュレーションファイルに,3つのタスクを生成するための静的APIを記述したとします.すると,対応する形のTINIBがコンフィギュレーションによって,kernel_cfg.cに生成されます. 


コンフィギュレーションファイル(アプリケーションエンジニアが記述)
CRE_TSK(CONTROL_TASK,{ TA_HLNG|TA_ACT, 0, control_task, MID_PRIORITY, STACK_SIZE, NULL }); ←タスク1
CRE_TSK(HCALC_TASK, { TA_HLNG, 0, hcalc_task, HIGH_PRIORITY, STACK_SIZE, NULL }); ←タスク2
CRE_TSK(COM_TASK,{ TA_HLNG, 0, com_task, LOW_PRIORITY, STACK_SIZE, NULL }); ←タスク3




できあがったkernel_cfg.c



このように,TINIBは,const宣言することで,ROM領域に配置しています.TCBは実行中に値が変わるので,constはつけず,通常の変数として宣言し,RAM領域に配置するようにしています.

TCBの構造

では次に,TCBの構造をソースコードで詳しく見ていきます.

223 typedef struct task_control_block {
224 QUEUE task_queue; /* タスクキュー */
225 const TINIB *p_TINIB; /* 初期化ブロックへのポインタ */
226
227 #ifdef UINT8_MAX
228 uint8_t tstat; /* タスク状態(内部表現)*/
229 #else /* UINT8_MAX */
230 BIT_FIELD_UINT tstat : 8; /* タスク状態(内部表現)*/
231 #endif /* UINT8_MAX */
232 BIT_FIELD_UINT priority : TBIT_TCB_PRIORITY;
233 /* 現在の優先度(内部表現)*/
234 BIT_FIELD_BOOL actque : 1; /* 起動要求キューイング */
235 BIT_FIELD_BOOL wupque : 1; /* 起床要求キューイング */
236 BIT_FIELD_BOOL enatex : 1; /* タスク例外処理許可状態 */
237
238 TEXPTN texptn; /* 保留例外要因 */
239 WINFO *p_winfo; /* 待ち情報ブロックへのポインタ */
240 CTXB tskctxb; /* タスクコンテキストブロック */
241 } TCB;


タスクコンテキストブロック(CTXB)はターゲットごとの情報です.ターゲットに依存した情報はここに置きます.スタックポインタやプログラムカウンタの大きさもターゲットごとに違うので,このような方法を取っています.
SH3の場合のタスクコンテキストブロックは.以下のような構造をしています.


73 typedef struct task_context_block {
74 void *sp; /* スタックポインタ */
75 FP pc; /* プログラムカウンタ */
76 } CTXB;


<TCBに格納する情報>
1. task_queue タスクキュー
2. *p_TINIB 初期化ブロックへのポインタ
3. tstat タスク状態(内部表現)
4. priority 現在の優先度
5. actque 起動要求キューイング
6. wupque 起床要求キューイング
7. enatex タスク例外処理許可状態
8. texptn 保留例外要因
9. *p_winfo 待ち情報ブロックへのポインタ
10.tskctxb(タスクコンテキストブロック)
        sp:スタックポインタ
   pc:プログラムカウンタ

続いて,タスクの初期化関数を見ていきます.その中で,TCBの初期化を行っています.
このタスク初期化関数は,カーネルのスタートアップモジュールから呼び出されます.このカーネルのスタートアップモジュールは,システムのリセット後に最初に実行されるプログラムで,/arch/sh34_gcc/start.Sにアセンブラ言語で記述されています(ターゲット依存部です).このスタートアップモジュールでは,プロセッサ状態の初期化,hardware_init_hook(システムのリセット後すぐに行う必要のあるターゲットシステム依存の初期化処理)の呼び出し,bssセクションとdataセクションの初期化,software_init_hook(開発環境(特にライブラリ)に依存して必要な初期化処理)の呼び出し,最後にsta_ker関数を呼び出します.このsta_ker関数から,initialize_object関数が呼ばれその中で,initialize_task関数が呼ばれます.
このinitialize_object関数は,コンフィギュレーターが生成し,kernel_cfg.cに記述されます.今から見ていくタスクの初期化関数の他に,セマフォ,周期ハンドラなどの初期化関数が呼び出されますが,コンフィギュレータが判断して使用しない機能の初期化関数は呼び出さない仕組みになっています.【図12-2】


【図12-2 タスクの初期化関数が呼び出される流れ】

</kernel/task.c>
94 void
95 initialize_task(void)
96 {
97 uint_t i, j;
98 TCB *p_tcb;
99
100 p_runtsk = p_schedtsk = NULL;
101 reqflg = FALSE;
102 disdsp = FALSE;
103 dspflg = TRUE;
104
105 for (i = 0; i < TNUM_TPRI; i++) {
106 queue_initialize(&(ready_queue[i]));
107 }
108 ready_primap = 0U;
109
110 for (i = 0; i < tnum_tsk; i++) {
111 j = INDEX_TSK(torder_table[i]);
112 p_tcb = &(tcb_table[j]);
113 p_tcb->p_tinib = &(tinib_table[j]);
114 p_tcb->actque = FALSE;
115 make_dormant(p_tcb);
116 if ((p_tcb->p_tinib->tskatr & TA_ACT) != 0U) {
117 make_active(p_tcb);
118 }
119 }
120 }


ここで注目していただきたいのは,112,113行目です.
112,113行目:TCBのp_tinibに,TINIBのアドレスを格納することで,2つの構造体を結びつけています.【図12-1】の赤い矢印で表現した接続が生成されます.

ここまで,タスクを管理する情報,TINIB,TCBの構造について見てきました.TINIBのポインタはTCBに格納されていますので,TCBを管理すればTINIBも管理できる.ということになります.
ではここからは,このTCBをどのように管理するか.ということを解説していきます. ASPではレディキューでTCBを管理しています.レディキューとは,実行できる状態(実行状態および実行可能状態)のタスクを,優先順位の順に管理するためのデータ構造です.

レディキューに対する操作には以下のようなものが考えられます.
・最高優先順位のタスクを見つける
・あるタスクを同じ優先度タスクの末尾に挿入する
・任意のタスクをキューから取り除く
・ある優先度のタスク中で優先順位が最高のものを探す

このように,レディキューに対する操作にはいろいろなものが考えられ,ほぼすべてのサービスコールでレディキューを扱いますので,もっとも効率のよい構造を採用しないと,すべてのサービスコールの実行速度が遅くなります.

概念的なレディキュー構造は,【図12-3】のようになります.優先度が高い順に並んでいるというイメージです.



【図12-3 レディキューのイメージ】

実際には以下のようなレディキューの構造が考えられます.

Aシングルリンクキュー
メモリ容量は小さく抑えられますが,実行速度は遅くなります.



Bダブルリンクキュー
実行速度は速いですが,メモリ容量がAと比べると大きくなります.



ASPカーネルでは,TCBを優先度順さらに,優先度ごとの優先順位順に管理する必要がありますので,単純なAシングルリンクキューや,Bダブルリンクキューではなく,管理を効率化するために,次の2つの要素を取り入れて工夫しています.

C優先度毎のダブルリンクキュー
Dサーチを高速化するためにビットマップを用意

ASPカーネルではこの,CとDの両方の要素を使用しています.【図12-4】



【図12-4 ASPのレディキュー概念図】

ASPカーネルではTCBをキューの要素として接続して管理し,そのキューをレディキューと呼んでいます.そしてTCBで構成されているレディキューを効率よくアクセスできるような工夫がされています.
まず,D.優先度ごとのダブルリンクキューと,C.ビットマップを持っています.このビットマップは,優先度ごとに1bit用意され,その優先度のレディキューにタスクがつながっているかどうかを,1,0で管理しています.そうすることで,任意の優先度の中で一番優先順位の高いタスクを早く見つけることができます.(ビットマップ検索,次回解説します.)

レディキューのデータ構造

レディーキューには何がつながれているかというと, TCBがつながれています.よってTCBにもダブルリンクキューのための領域が必要です.TCBの宣言で一番上のメンバーがキューの構造体になっています.ここを使ってレディキューにつないでいます.

以下に,レディキューを実現するための構造を示します.

1.ダブルリンクキューのためのデータ構造の型

63 typedef struct queue {
64 struct queue *p_next; /* 次エントリへのポインタ */
65 struct queue *p_prev; /* 前エントリへのポインタ */
66 } QUEUE;

ダブルリンクキューを実現するための構造体の型QUEUEを定義します.

2.優先度ごとのダブルリンクキュー実体
QUEUE ready_queue[16]

QUEUE型の構造体配列を宣言します.これは優先度ごとのダブルリンクキューに使用します(【図12-5】).そしてASPカーネルのタスク優先度は,1〜16の16段階ですので,構造体配列の要素数は16で宣言します.

3.ビットマップ
uint16_t ready_primap (uint16_tは,符号無し16ビット整数)

16段階の優先度につきそれぞれ,1bitの領域が必要ですので,符号なし16ビット整数型の変数を用意します.該当優先度のレディキューにタスクがつながっていれば1,つながっていなければ0が格納されます.

4.TCBをリンクするためのキュー領域
TCB中の QUEUE task_queue

TCB自体がレディキューの要素となりますので,ダブルリンクを実現するための,QUEUE型のメンバが必要です.

以上をまとめて,【図12-5】にASPにおけるレディキューの詳細構造を示します.



【図12-5 ASPのレディキューの構造】

次回は,このレディキューを操作する関数について解説します.