Get in Touch
  • If you’re interested in a Wind River product, simply answer a few questions and we’ll get in touch right away.
  • If you’d like to speak with someone immediately, call our number for sales inquiries below.

    Toll-free: 800-545-WIND (800-545-9463)

【設計しながら学ぶRTOSの基本編】第5回 TCBの具体的設計とレディキュー その2

こんにちは、南角 です。
個人的な事情で、また少し間が空いてしまいました。申し訳ありません。
最初に前回の宿題を振り返っておきましょう。
一つ目の宿題は、次に実行する命令を保持しているレジスタ(プログラムカウントレジスタPCやインストラクションポインタIPなど)と、直近の命令実行結果やCPUの状態などを保持しているプロセッサステータスレジスタPSWの二つを、なぜアトミックデータとして扱わねばならないかでした。

たとえばC言語やC++言語におけるifやwhileなどの制御構造において、ある整数変数の値が10と異なる間は何らかの動作を実行するという場合を、仮想的なアセンブラニーモニックで考えてみましょう。
元のC言語のプログラムが

たとえばC言語やC++言語におけるifやwhileなどの制御構造において、ある整数変数の値が10と異なる間は何らかの動作を実行するという場合を、仮想的なアセンブラニーモニックで考えてみましょう。
元のC言語のプログラムが

int x; while (x != 10) { // whileの条件式がtrueの間(整数xが10でない場合)に実行される処理 } // whileを抜けてから実行される処理 の場合のアセンブラニーモニックは、変数xの値がレジスタr5に格納されているとすると、たとえば次のような(疑似)アセンブラニーモニックになります。
loop:
cmp r5,#10 jz next ;whileの条件式がtrueの場合に実行される処理 jmp loop next:
whileを抜けてからの処理

cmp命令はr5と10を比較して(r5から10を引いてみて、ただし結果はr5には反映しない)、その結果が0であれば(r5と10が等しい場合)、PSWにある直近の演算結果を示すZ(ゼロ)フラグをON(1)にする命令です。
そしてjzはそのZフラグがONの場合に限ってジャンプを実行する条件付きジャンプ命令です。
もし上記のcmp命令と条件付きジャンプ命令の間に他の処理に切替わって、その処理でZフラグの状態を変えるようなことになれば、上記の命令が正しく実行されないことになります。
そのためPCとPSWを同時に保存しておかなければならないわけです。
言い換えるとwhile文やif文がCPU命令レベルでは1命令で実行できないため、それに代わる方法としてPCとPSWを同時に保存するわけです。
上記の直近の演算結果を示すフラグ以外にも、PSWには割り込み禁止/許可のビットや、CPUがハードウェア的な割り込み優先度を備えている場合の割り込みレベルを示すビット領域などの、CPUの状態を示すビットも備えられています。
実際に処理を切り替えるには、割り込みしかないわけなので、割り込みが発生してソフトウェアが処理をできる時にはすでにPSWの状態が変化した後ということになります。
そのため割り込み発生時にはソフトウェアではなく、CPUハードウェアが割り込み発生時のPCやPSWをスタック(主にCISCの場合)やPCやPSWの保存専用のレジスタ(主にRISCの場合)に、 自動的に保存してからソフトウェアが実行を再開します。
また、続けて割り込みが発生するとこれらのデータが上書きされる可能性もあるため、CPUハードウェアは割り込み発生時には、自動的にすべての外部割込みを禁止します。
そうすると他の処理が実行されることがなくなり排他制御が実現できるため、アトミックデータに対する処理を終えた後で、ソフトウェアで割り込みを許可します。
これはタスク切り替え発生時に今までのタスクコンテキストを保存する場合だけでなく、逆にタスクを再開させる場合も同様です。
OSからタスクに制御を戻す時は、割り込み禁止にしておいて、TCBに保存しておいたタスクコンテキストを順次CPUのレジスタなどに戻していき、最後にPCを戻しますが、この時は同時にPSWも復元しなくてはなりません。
そのため通常はPCとPSWをスタックに積んでから、割り込みからの復帰命令を使用します。
割込みからの復帰命令は、1命令でPCとPSWを復元できるからです。
少し横道にそれましたが、以上がタスク切り替え時にはPCとPSWをアトミックデータとして扱わなければならない理由です。

次の宿題は、なぜシステムレディーキューを説明したような構造にするかでした。
まず優先度ごとのキューにする理由はお分かりだと思います。
キューの方が配列に比べると挿入、削除の処理時間が早く一定しているというのも理由の一つですが、この場合の質問の意味はそれではありません。
リアルタイム設計をする上で重要なのは、処理の最悪実行時間を見積れることです。
もちろん中心はアプリケーションですが、OSも出来る限り最悪実行時間を保証できるようにすべきです。
たとえば、1本のキューでシステムレディーキューを実現している場合は、タスクをキューにつなぐ時、あるいは取り出す時のどちらかの場合の処理時間が、その時にキューにつながっている、言い換えると実行可能状態のタスクの数によって異なることになります。
そこでまずタスク優先度の数だけキューを設けます。この場合同じ優先度にはタスク一つとした方が、リアルタイム設計が容易になり、優先度分の配列を持てばよいので、OSのシステムレディキューの構造も容易になるのですが、ほとんどのRTOSはそこまでの割り切りは行わず、同じ優先度のタスクも許しています。そうなると前回も示した、下図のような優先度分のキューの配列が必要になります。

しかしこの構造では今度は、どの優先度にタスクがいるのか(つながっているのか)を探すのに、状況によって時間が異なることになります。
そこでビットマップが必要となるわけです。
この場合優先度の高いタスクが配列のインデックス番号が少ないとすると、上記のビットマップ0xAからは配列のインデックス0が取り出せればよいわけです。
あるいは、優先度0にはタスクがなく、優先度1にタスクがいる場合のビットマップは 01XX
(Xは0,1どちらでもよい)ですよね。
これでわかったと思います。
実は前回間違えていまして、ビットマップの割り付けを逆にしていました、逆でも問題ないのですが下のptitblの内容が少しわかりにくくなります。
unsigned char ptitbl [16] = { 0, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
という配列を作っておきpritbl[ビットマップ]で優先度が最も高いタスクがつながっている配列のインデックスを求めることができます。
前回の図の割り付けを逆にしたビットマップではこのpritblの値が変わります、考えてみてください。
ここで少し考えなければならないのは、実行可能タスクが1つもいない、つまりビットマップが0の場合ですが、これも優先度が最低のタスクを無限ループにしておくことで、このケースを考えなくても良くなります。
これも以前に述べた、常に実行可能な優先度が最低のアイドルタスクを設けておくことで、RTOSの構造を単純にできる一つの例です。

最後にリスト構造に関してもう一つ述べておきます。
図では単方向リストを示しています。
この場合同じ優先度にタスクが複数いる場合は、挿入または削除(取り出す場合)の時の処理時間がタスクの数に影響を受けます。
下に、単方向リストの実装例を示します。
例ではmallocを使用していますが、TCBに対する操作の場合は無論mallocで新たなメモリを獲得する必要はありません、プログラムはあくまでも単方向リスト操作の例です。
下記プログラムは挿入時には先頭に挿入して、取り出す時はリストを最後まで辿ります。このたどる時間がリストの要素に左右されます。
逆の実装で挿入時にたどって、取り出す時は先頭からという実装も可能です。
この場合は取り出す時の時間は一定ですが、挿入処理の時間が要素の数に左右されます。
では、挿入時も取り出す時も要素の数(システムレディキューにおいては実行可能なタスク数)に左右されないためにはどうすればよいでしょうか?
これを今回の宿題としておきます。
ではまた次回。

/* 単方向リスト */

struct QUEUE_ELEMENT {
struct QUEUE_ELEMENT *previusp; int data; };

static struct QUEUE_ELEMENT *qtail = NULL;

int main(void);
void enqueue(int);
int dequeue(void);

void enqueue(int data) {
struct QUEUE_ELEMENT *newqp, *swapp;
/* allocate new element */ newqp = (struct QUEUE_ELEMENT*)malloc(sizeof(struct QUEUE_ELEMENT)); /* set data */ newqp->data = data; /* exchange pointer */ swapp = qtail; qtail = newqp; newqp->previusp =swapp;
return; }

int dequeue(void) {
struct QUEUE_ELEMENT *headqp; int data;
/* search last data */ headqp = qtail; if (headqp->previusp == NULL) { data = headqp->data; qtail = NULL; free(headqp); } else { while(headqp->previusp->previusp != NULL) { headqp = headqp->previusp; } data = headqp->previusp->data; free(headqp->previusp); headqp->previusp = NULL; }
return data; }

設計しながら学ぶRTOSの基本編 第5回 おわり

■著者プロフィール

南角 茂樹(なんかく しげき)

大阪電気通信大学 総合情報学部 メディアコンピュータシステム学科 准教授、同大学院総合情報学研究科(コンピュータサイエンス専攻)、エイシップ・ソリューションズ株式会社 研究顧問。
慶應義塾大学工学部数理工学科卒業後、大手電機会社を経て現職。組み込みシステムおよびリアルタイムOSを専門とし、著書、解説記事、発表・講演、登録特許等多数。

Thank You

Wind River, a wholly owned subsidiary of Intel Corporation (NASDAQ: INTC), is a world leader in embedded and mobile software. Wind River has been pioneering computing inside embedded devices since 1981 and its technology is found in more than 500 million products