(注意)このブログは本家 のほうの文章部分のみの転載です.ソースコードの配布,画像などについては本家のほうを参照してください.文章中のリンク先は面倒なのですべて本家のほうに変換してしまっているのでご注意ください.

もう年末ですね! でも仕事が終らん!

で,前回からちょっと間が開いてしまっているのだが,リアルタイム性をどうやって確保するか,実はちょっと思いあぐねている.

リアルタイム性を確保するためには,OSの処理中の割り込み,つまり割り込みの再入を可能にしたい.前回は割り込みハンドラを登録可能にしたが,とくに割り込みハンドラの実行中の割り込みを可能にしたい.というのは,割り込みハンドラの実行中は割り込み禁止にしてしまうと,ハンドラでなにか重い処理をしたときに,リアルタイム性が確保できないからだ.

しかし,ある重要な割り込み処理をしている最中に,どーでもいいような割り込みが上がってくるのも困る.こーいうような場合には割り込みを待たせたい.でないと重要な処理が中断されて,どーでもいい割り込みの処理に切り替わってしまうからだ.

つまり,割り込みにも優先度を持たせたいということになる.たとえば現状のKOZOSでは外部割り込みは SIGHUP の1種類のみだが,複数種類にして優先度をつけるとか,SIGALRM はもっと優先度を高くするとかだ.割り込みに優先度をつけるのは,シグナルマスクを利用することで段階的にマスクをかけることで実現可能だ.

しかし,割り込みハンドラでの処理は極力短くするのがOSの鉄則だ.ということで割り込みハンドラでは,割り込みを上げてきたハードウエアのバッファを見て(KOZOSならば,extintr が read() することに相当する),それを処理するスレッドにメッセージとして投げてやる,という設計が良い.

しかし,例えば重要な割り込みが入った際に,ハンドラがそれを受けて処理用スレッドにメッセージとして投げたとしよう.スレッドはそのメッセージを受けて処理を開始するが,この際にどーでもいいような優先度の低い割り込みが入ると,やっぱりそのスレッドは待たされてしまうことになる.つまり,優先度の高い割り込みの実際の処理をスレッドに任せることは不可能(他の優先度の低い割り込みに割り込まれてしまうので)ということになる.

これを防止するためには,スレッドの優先度と割り込みの優先度を関連づけて,たとえば優先度の高いスレッドの実行中には,それに応じた割り込みマスクをかけて,優先度の低い割り込みは受け付けないようにする,という方法がある.

もう一点,OSの処理中の割り込みを受け付けるかどうかなのだけど,以下のいずれかの対処をすることでこれは可能だ.
  • KOZOSの内部処理を再入可能にする.
  • 再入不可の箇所は,部分的に割り込み禁止にする.(割り込み禁止区間を設ける)
  • 割り込みの優先度をうまく設計することで,再入不可な関数への再入が実際には起こらないようにする.
で,KOZOSの処理中の割り込み,つまり割り込み中の割り込みを可能にしたとしよう.割り込み中にもっと優先度の高い割り込みが入り,そっちのハンドラが新たに呼ばれたとする.優先度の高い割り込みのハンドラはとりあえず処理用のスレッドにメッセージを投げて,あとはスレッドに処理を任せるとしよう.しかし,ハンドラの終了後にすぐにスレッドをディスパッチすることはできない.もともと行っていた(優先度の低い)割り込み処理にいったん戻り,処理を完了させてからディスパッチしなければならないのだ.でないともともとも割り込み処理は途中までの中途半端な位置まで実行されただけで,宙に浮いてしまう.

割り込みを階層的にした場合には,何十にもネストして発生する可能性もある.ということは,優先度の高い割り込みのハンドラがメッセージを投げて,さらにその処理用スレッドがディスパッチされるまでの時間が保証できなくなってしまう.どれくらいの割り込みがネストしていて,それらの処理にどれくらいの時間がかかるのか見積もることができないからだ(いや正確に言うと最悪時間を見積もることはできるのだけど,きっととんでもなく長い時間になってしまう).

ということで,結局のところリアルタイム性を確保するには割り込みハンドラ内ですべての処理を行うか,もしくはKOZOSの内部処理中の割り込みは禁止にして,現状のように内部処理が完了した時点で割り込み許可するかのいずれかになってしまう.前者は融通が効かなそう.後者は応答が悪そう(あと割り込み禁止区間が長くなるので,リアルタイム性を保証するのが難しくなりそう).

うーん,困った.ということでいまちょっと本を読んで勉強中なのだな.なんかうまいやりかたはないだろーか.

きれいな解決策としては,ハンドラごとにコンテキストを持たせるというか,ハンドラをスレッド化するという方法がある.実はKOZOSはもともとそんなようなつくりになっているのだけど,割り込みハンドラを単なる関数呼び出しにするのではなく,kz_setsig() によりメッセージを投げさせて,完全にスレッドとして処理させるというものだ.これならきちんと優先度をつけて処理することが可能だ.可能なのだが,うーん,でも割り込みのたびにディスパッチされるというのもねえ...きれいだけど,なんか性能悪そうでやなのよね.

あーでも,KOZOSの内部処理中に割り込み入ったらすぐにスレッドをディスパッチできないから同じことか.やっぱダメだね.
AD
(注意)このブログは本家 のほうの文章部分のみの転載です.ソースコードの配布,画像などについては本家のほうを参照してください.文章中のリンク先は面倒なのですべて本家のほうに変換してしまっているのでご注意ください.

今回は,KOZOSの割り込み応答性能についてちょっと考えてみよう.とはいっても(もう,なんべんも書いていることだが,いちおう言っておくと)KOZOSは汎用OS上で1プロセスとして動作するユーザランドOSなので,そーいうことまで考慮したKOZOS自身の本当の割り込み応答性能を論ずるのは,OSに依存してしまうのでちょっとナンセンスだ.なのでまあ勉強と言う意味で,仕組み上というかKOZOS単体としての理論上の割り込み性能,という話になる.

で,まあはっきりいってしまうと,現状のKOZOSは,割り込み応答性能がちょっとイマイチのつくりになってしまっている.

まずKOZOSの欠点として,システムコールも含めたOSの処理中は割り込み禁止になっている.これは KOZOS 起動時に呼ばれる初期化用関数である thread_start() で
 sa.sa_mask = block;
sigaction(SIGSYS , &sa, NULL);
sigaction(SIGHUP , &sa, NULL);
sigaction(SIGALRM, &sa, NULL);
sigaction(SIGBUS , &sa, NULL);
sigaction(SIGSEGV, &sa, NULL);
sigaction(SIGTRAP, &sa, NULL);
sigaction(SIGILL , &sa, NULL);

のようにして,シグナルハンドラ内部でのシグナル発生をブロックしているためだ.これはOSっぽい言いかたをすると,「割り込み中は割り込み禁止にしている」ということになる.これはKOZOSの処理中のKOZOSへの再入を防止するのが目的で,安全のためなのだけど,性能的にはよろしくない.

このため,たとえば時間のかかるようなシステムコールの処理中に割り込みが入った場合にも,割り込み禁止になっているために割り込みは待たされてしまう.割り込み発生時にどんなシステムコールが実行されているかなんて予想がつかないから,これではリアルタイムOSとはちょっと言えないだろう.

現状のKOZOSでは,システムコールなどの処理中に割り込みが発生した場合には,割り込みはブロックされ,スレッドのディスパッチの直前に
 on_os_stack = 1;
sigprocmask(SIG_UNBLOCK, &block, NULL);
sigprocmask(SIG_BLOCK, &block, NULL);
on_os_stack = 0;
/* ここで SIGALRM が発生するとシグナルを取りこぼす...要検討 */
setcontext(¤t->context.uap);

のようにして,一瞬だけ割り込み許可している部分で割り込みハンドラが起動する.上の部分は,setcontext() によるコンテキスト切替えを行うとハンドラ内部で発生したシグナルが失われてしまうという問題を回避するための対処だ.これに関しては第14回を参照.

また,割り込み発生時には kz_setsig() によってメッセージ送信を依頼したスレッドにメッセージが投げられる.つまり,実際の割り込み処理はスレッドのメッセージ受信を契機として,スレッドが行うことになる.extintr とかがまさにそのような作りになっているのだが,これも割り込み応答性能という点で見ると,ちょっとイマイチだ.割り込み処理のために当該のスレッドのディスパッチが必ず必要になってくるからだ.さらに,(extintrなどの)スレッドによる割り込みの処理中にも,他の割り込みが発生してKOZOSの割り込みハンドラが呼ばれてしまう(そして,当該スレッドへのメッセージの送信処理が行われる)ことが考えられる.これでは重要な割り込み処理が行われている最中にも,何らかの割り込みが発生すると優先度に関係なく割り込み処理が行われるということになるので,リアルタイム性という点でちょっとまずい.

現状のKOZOSで,割り込み処理をスレッドにお願いしているのは,単に簡略化のためだ.通常のOSでは,割り込み処理は割り込みハンドラが行うものだ.ということで今回は,割り込み発生時に登録した関数を呼び出してくれるような,割り込みハンドラの登録用のシステムコールを追加してみた. 修正点について,以下に説明する.まあ今回はシステムコールを追加しただけなのであまり説明するようなことは無い.本来ならば割り込みハンドラを利用するように extintr とかを書き換えるべきなのだけど,まああまり一度に説明しても重いので,今回はシステムコールの追加だけにとどめて,少しずつ説明していくつもり.(最近,長~い説明が多いので)

従来から kz_setsig() というシステムコールで,割り込み発生時にメッセージを送信するように設定しておくことができるが,これと似たようなシステムコールとしてkz_sethandler() というのを追加する.
diff -ruN kozos29/kozos.h kozos30/kozos.h
--- kozos29/kozos.h Mon Dec 17 21:53:06 2007
+++ kozos30/kozos.h Mon Dec 17 22:12:16 2007
@@ -4,6 +4,7 @@
#include "configure.h"
typedef int (*kz_func)(int argc, char *argv[]);
+typedef void (*kz_handler)(int signo);
/* syscall */
int kz_run(kz_func func, char *name, int pri, int argc, char *argv[]);
@@ -17,6 +18,7 @@
int kz_recv(int *idp, char **pp);
int kz_timer(int msec);
int kz_pending();
+int kz_sethandler(int signo, kz_handler handler);
int kz_setsig(int signo);
int kz_debug(int sockt);
void *kz_kmalloc(int size);

kz_sethandler() は,引数にシグナル番号と関数へのポインタをとる.シグナル(割り込み)発生時には,設定しておいた関数が呼ばれることになる.

syscall.[ch]については,まあいつもどおりのシステムコール追加なので,とくに説明しない.次に,thread.c で実際にハンドラを登録する部分.
diff -ruN kozos29/thread.c kozos30/thread.c
--- kozos29/thread.c Mon Dec 17 21:53:06 2007
+++ kozos30/thread.c Mon Dec 17 22:23:51 2007
@@ -28,9 +28,10 @@
static unsigned int readyque_bitmap;
static kz_timebuf *timers;
static kz_thread *sigcalls[SIG_NUM];
+static kz_handler handlers[SIG_NUM];
static int debug_sockt = 0;
sigset_t block;
-static int on_os_stack = 0;
+static stack_t intrstack;
kz_thread *current;
@@ -315,8 +316,17 @@
return 0;
}
+static int thread_sethandler(int signo, kz_handler handler)
+{
+ handlers[signo] = handler;
+ putcurrent();
+ return 0;
+}

kz_sethandler() のシステムコール処理用関数として thread_sethandler() を追加してある.内容は,シグナル番号をインデックスとした配列に関数を登録するだけ.

次に,ハンドラの呼び出し部分.
 static void extintr_proc(int signo)
{
+ if (handlers[signo])
+ handlers[signo](signo);
if (sigcalls[signo])
sendmsg(sigcalls[signo], 0, 0, NULL);
}

従来は extintr_proc() では kz_setsig() で設定されたスレッドに対してsendmsg() を呼び出してメッセージを送信するだけだったが,さらにハンドラ関数を呼ぶ処理を追加する.

さらに,上でも説明したように,従来はスレッドのディスパッチの直前に割り込みを一瞬だけ許可していたのだが,この際に on_os_stack というフラグを立てて,割り込み禁止してから on_os_stack を落とし,スレッドのディスパッチを行っていた.これは割り込み発生時に,KOZOSの内部処理中に呼ばれたのか,通常のスレッド実行時に呼ばれたのかを検出し,後者の場合のみコンテキスト保存を行うようにするためだ.これを検出できないと,KOZOSの内部処理中に割り込み発生した場合に,スレッドのコンテキストを上書きして壊してしまうことになるからだ.ただこの処理は,スレッドのディスパッチの前に on_os_stack をゼロに戻さないとならないため,その後のディスパッチまでの短い一瞬で割り込みが発生するとやはり割り込みを取りこぼすというタイミング問題があった.(従来の thread_intrvec() の終端部分のコメント参照)

KOZOSの割り込み応答性能を改善するためには,KOZOSの処理中(主にシステムコールの処理中)の割り込みを許すようにしたい.つまり,KOZOSへの再入を可能にしたい.そのための準備として,どこからでも割り込みを受け付けられるように,従来の on_os_stack を用いた再入検出を改良する.
@@ -496,19 +510,16 @@
* これはOSの割り込み処理の再入になるが,以下の位置に限定して再入が行われる
* ので問題は無い.
*/
- on_os_stack = 1;
sigprocmask(SIG_UNBLOCK, &block, NULL);
- sigprocmask(SIG_BLOCK, &block, NULL);
- on_os_stack = 0;
-
- /* ここで SIGALRM が発生するとシグナルを取りこぼす...要検討 */
setcontext(¤t->context.uap);
}
static void thread_intr(int signo, siginfo_t *info, ucontext_t *uap)
{
- if (!on_os_stack) {
+ unsigned int esp = uap->uc_mcontext.mc_esp;
+ if ((esp < (unsigned int)intrstack.ss_sp) ||
+ (esp >= (unsigned int)intrstack.ss_sp + intrstack.ss_size)) {
memcpy(¤t->context.uap, uap, sizeof(ucontext_t));
}
thread_intrvec(signo);

まあ見ればわかるが,スタックポインタの値を見て,スレッド実行中の割り込みなのか,KOZOSの内部処理中の割り込みなのかを判断するように修正した.これだと Linux とかに移植する際には修正が必要になるのでちょっとうーむだが,まあしかたがない.

あとはまあ細かい修正がいくつかあるが,面倒なのでとくに説明はしない.あととりあえず今回の修正をして,gdbで繋いでtelnetなどがひととおり従来通り動くことは確認した.

これで割り込みハンドラを登録できるようになった.次回は実際に割り込みハンドラを利用するように改良することで,割り込み応答性能を改善してみたい.
AD
(注意)このブログは本家のほうの文章部分のみの転載です.ソースコードの配布,画像などについては本家のほうを参照してください.文章中のリンク先は面倒なのですべて本家のほうに変換してしまっているのでご注意ください.

前回は動的メモリ獲得のリアルタイム化を行ったのだけど,KOZOSの内部にはループを使用しているためにリアルタイム性がいまいち確保できていない部分が他にもある.

たとえば割り込み処理(thread_intrvec())の終了直前には,スレッドのスケジューリングが行われる(schedule()).ここではレディーキューの検索が行われるのだが,現状で以下のようになっている.

static void schedule()
{
int i;
for (i = 0; i < PRI_NUM; i++) {
if (readyque[i].head) break;
}
if (i == PRI_NUM) {
/* 実行可能なスレッドが存在しないので,終了する */
exit(0);
}
current = readyque[i].head;
}

つまりレディーキューの数だけループして,実行可能なスレッドがあるかどうかを検索している.これはキューの状態によってループされる回数が変化するためにループ回数が予測できないので,リアルタイム性が無い.いや,実はそうでもなくて PRI_NUM は固定値なので,ループの最悪数をもって最悪実行時間を見積もることはできる.よってリアルタイム性が全く無いというわけでもないのだが,schedule() は割り込みのたびに必ず呼ばれるため,このような作りになっていてリアルタイム性を唱うというのもちょっと気が引ける.というかこれでリアルタイムと言い張るにはちょっと弱い.

で,どうするかなのだが,このような場合にリアルタイム性を確保するための書き方がある.まあ簡単にいうと,レディーキューの状態をビットマップ状に管理し,ビットの立っている位置を高速に検索するというものだ.まあ言葉だけで説明してもわかりにくいので,まずはソースコード.以下に修正差分を示しながら,リアルタイム性を確保する方法について説明する.

まず thread.c に対して,レディーキューの状態をビットマップ管理するための変数として readyque_bitmap を追加.

kz_thread threads[THREAD_NUM];
static struct {
kz_thread *head;
kz_thread *tail;
} readyque[PRI_NUM];
+static unsigned int readyque_bitmap;
static kz_timebuf *timers;
static kz_thread *sigcalls[SIG_NUM];
static int debug_sockt = 0;
sigset_t block;
static int on_os_stack = 0;

現状では優先度の個数(PRI_NUM)が32個のため,unsigned int 型の変数ひとつでreadyque_bitmap が表現できている.しかしもしも PRI_NUM が256とかになった場合には,これではまずい.これについては後述する.まあ本来はこーいうのは,PRI_NUM が増加してビットマップが拡張されたときのために,先を見越した(拡張のしやすい)書き方をしておくべきなのだ.しかしまあ今回は,わかりやすさを優先してベタに書いてしまう.

次にKOZOSの起動部分に,ビットマップの初期化を追加.

static void thread_start(kz_func func, char *name, int pri, int argc, char *argv[])
{
struct sigaction sa;
stack_t sigstack;

memset(threads, 0, sizeof(threads));
memset(readyque, 0, sizeof(readyque));
memset(sigcalls, 0, sizeof(sigcalls));

+ readyque_bitmap = 0;
timers = NULL;

...

さらに,スレッドのレディーキューへの出し入れを行う getcurrent(), putcurrent()に対して,キューにスレッドが追加されたら readyque_bitmap のビットを立て,キューが空になったらビットを落とす処理を追加.

static void getcurrent()
{
readyque[current->pri].head = current->next;
- if (readyque[current->pri].head == NULL)
+ if (readyque[current->pri].head == NULL) {
readyque[current->pri].tail = NULL;
+ readyque_bitmap &= ~(1 << current->pri);
+ }
current->flags &= ~KZ_THREAD_FLAG_RUNNING;
current->next = NULL;
}


static int putcurrent()
{
if (current->flags & KZ_THREAD_FLAG_RUNNING) {
/* すでに有る場合は無視 */
return -1;
}

if (readyque[current->pri].tail) {
readyque[current->pri].tail->next = current;
} else {
readyque[current->pri].head = current;
}
readyque[current->pri].tail = current;
+ readyque_bitmap |= (1 << current->pri);
current->flags |= KZ_THREAD_FLAG_RUNNING;

return 0;
}

まあここまでは簡単な処理の追加だけだ.ここまでの修正により,レディーキューにスレッドが存在するか否かがreadyque_bitmap によってビットマップ管理されることになる.よって readyque_bitmap の中で一番最下位にあるビット(一番右にあるビット)を検索すると,その位置が「最も優先度の高いスレッドが存在するレディーキュー」となるはずだ.

ただしそれを,for ループでぐるぐる回して

bit = 1;
for (i = 0; i < PRI_NUM; i++) {
if (readyque_bitmap & bit)
...
bit <<= 1;
}

のようにして検索してはいけない.これではループによってレディーキューを検索するのとたいして変わらないので,以前と変わらずリアルタイム性を確保できないからだ.これではわざわざビットマップにした意味が無い.どうにかしてループを使用せずに,固定の命令数で最下位ビットの位置を検索する必要がある.

で,最近のCPUだと,まさにこのような用途のために「ビットサーチ命令」というのが用意されていて,そのような命令に readyque_bitmap を渡すことで,「最も最下位にある,立っているビットの位置」を1命令で検索することができたりする.当然,普通にCで書いていてコンパイルしたところで,コンパイラがこのような命令を使ってくれることは無いので,インラインアセンブラを使って,ビットサーチ命令を明示的に使うように自前で書かなければならないのだけど,これを使えば確実にリアルタイム性を確保できる.

しかしまあこれはCPU依存になるので,ここではそーいうような命令が使えなかった場合の一般的な書き方をしよう.

static void schedule()
{
#if PRI_NUM > 32
#error ビットマップを配列化する必要あり
#endif
unsigned int bitmap = readyque_bitmap;
int n = 0;
static int bitmap2num[16] = {
-32, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

if (!(bitmap & 0xffff)) {
bitmap >>= 16;
n += 16;
}
if (!(bitmap & 0xff)) {
bitmap >>= 8;
n += 8;
}
if (!(bitmap & 0xf)) {
bitmap >>= 4;
n += 4;
}
n += bitmap2num[bitmap & 0xf];
if (n < 0) {
/* 実行可能なスレッドが存在しないので,終了する */
exit(0);
}

current = readyque[n].head;
}

これは Toppers のスケジューリング部分をわかりやすく噛み砕いたものなのだけど,ループが利用されていない点に注目してほしい.このため,処理にかかる時間を固定で見積もることができる.

で,そのアルゴリズムはこうだ.
  • まず右16ビットを調べ,まったくビットが無い(つまり,ゼロ)ならば,16ビット詰める.
  • 次に右8ビットを調べ,まったくビットが無い(つまり,ゼロ)ならば,8ビット詰める.
  • 次に右4ビットを調べ,まったくビットが無い(つまり,ゼロ)ならば,4ビット詰める.
詰める際には,詰めた数をnに加えていく.こーすることで,ビットマップをlog2に比例した回数で調べることができる.つまり,検索数を O(log n) にできる.

で,このまま2ビット,1ビットと詰めていってもいいのだけど,最後の4ビットは高速化のために,配列で検索している.これが

n += bitmap2num[bitmap & 0xf];

という部分だ.

bitmap2num[]は,以下のような値になっている.

n num
-----------
0 0000 -32
1 0001 0
2 0010 1
3 0011 0
4 0100 2
5 0101 0
6 0110 1
7 0111 0
8 1000 3
9 1001 0
10 1010 1
11 1011 0
12 1100 2
13 1101 0
14 1110 1
15 1111 0

ちょっとわかりにくいかもしれないが,与えられた4ビットの値に対して,その4ビットをビットマップ化した際の最下位ビットの位置を値としてあらかじめ持っている.なので,4ビットまで丸め込めば,あとはbitmap2num[]を通すことで最下位ビットを調べることができるわけだ.これも Toppers の書き方をマネしたもの.

4ビットまで丸め込んだらあとはbitmap2num[]を通すというのは,単に高速化のためだ.まあこう考えると原理的には32ビットビットマップ用のbitmap2num[]を配列として用意すれば,始めから配列を使って一撃で検索できるわけなのだけど,それには4ギガ個の配列が必要になるのでまったく現実的でない.ということで,最初のうちは半分ずつに丸め込んでいき,適当なところで配列で一気に検索,というしくみになっている.

ここで注意なのは,現状のKOZOSではレディーキューの個数が32個なので,ビットマップが unsigned int 型の変数ひとつに収まっているということだ.しかし優先度の数が32個というのは実は組み込みOSとしてはちょっと心もとなくて,256個とかの優先度が必要になることもあるようだ.この場合にはビットマップをunsigned int 型の変数8個に拡張しなければならない.このため,schedule() の先頭では

#if PRI_NUM > 32
#error ビットマップを配列化する必要あり
#endif

のようにして,PRI_NUMが32を超えた場合にはエラーでコンパイルを中断するようにしてある.こういうときにはそれっぽくコンパイルできて動いてしまう(が,32以上の優先度がうまく動作しない)というのではなく,#error でコンパイルできないようにするのが正しい.そもそも32以上の優先度がうまく動作しないので改造が必要なのだから,エラーによって「未対応なので改造が必要ですよ」と教えてくれたほうが,はるかに親切だからだ.(コンパイルが通ってしまい,問題無いもんだと思って使っていたらあるとき突然バグ発生,ということを想像してほしい.どーせ直さにゃならんのだから,早く気づけたほうが遥かに良い)

で,まあ本来ならば優先度の個数を拡張したときにもすんなりと改造できるような(もしくは PRI_NUM を増やすだけで,他に修正する必要が無いような),先を見越した書き方(ビットの上げ下げをマクロ化しておくなど)をしておくべきなのだけど,まあ今回は優先度の個数は32個までと限定して,わかりやすさを優先して単純に書いてみた.schedule()内部で16,8,4ビットと半分ずつ狭めていく部分も,ほんとはループ化(このループ化は,ループ回数を固定にできるのでリアルタイム性の問題は無い)してもっとカッコいい書き方ができると思うのだけど,まあわかりやすくするために,ベタに書いてみた.

ちなみに優先度の個数を32よりも増やした場合なのだけど,この場合はビットマップが unsigned int 型の変数1個では収まらなくなるので,複数の変数に分ける,つまりビットマップを配列化する必要が出てくる.たとえば優先度を1024個とかにした際には,ビットマップの個数も32個になる.この配列をループで検索すると,やはりリアルタイム性という意味ではちょっとうーむな作りになってしまう.このような場合には,ビットマップがゼロかそうでないかの状態(配列の状態)を管理するためのビットマップを別途追加すれば,ビットマップの配列の検索も,ループを用いずに行える.ビットマップを階層構造にするわけだ.

あーあと言うの忘れたけど,今回の改良版のソースで,gdbの接続,continue,telnet 接続などは一通り行えることは確認してある.念のため.

ここまでで,徐々にそれっぽくなってきた.ていうか,リアルタイムOSっぽいつくりになってきた.次回は割り込みの応答性とか,割り込み禁止区間とかについて考えてみたい.

うーむ,咳が止まらん...
AD
(注意)このブログは本家のほうの文章部分のみの転載です.ソースコードの配布,画像などについては本家のほうを参照してください.文章中のリンク先は面倒なのですべて本家のほうに変換してしまっているのでご注意ください.

えーと,風邪を引いてしまいました.咳が止まらないです(で,会社を休んで連載を書いている).みなさんも風邪には気をつけて,うがいをマメにするようにしましょう.

で,今回はKOZOSの,というよりもOS一般のメモリ管理について考えてみよう.

前回の最後に説明したことなのだけど,現状のKOZOSでは内部のメモリ管理にmalloc ライブラリをそのまま用いている.まあKOZOSはユーザランドで動作する疑似OSなのでこんなことができているわけだが,まああたりまえだが普通のOSではただ内部で malloc() を呼び出せばメモリが得られる,なんてことはない.

UNIX の malloc() ライブラリは,sbrk() システムコールによってOSからページサイズ単位(通常,4KB)で得られたメモリ領域を可変サイズで切り売りするものだ.基本的に,OSは任意サイズでメモリを管理するようなことはまああまり無い(この理由は後述).なので固定サイズのメモリの内部を任意サイズでうまいこと分割して管理してくれるのが malloc() ライブラリだ.まあこのへんの話は K&R2 にもあるし,ほかにも探せばいろいろと出てくると思うので,そちらを参考にしてほしい.

で,OSの内部でも,内部の処理用に動的にメモリが欲しい場合は多々ある.KOZOSの内部でも,メッセージキューやタイマキューの管理のために,sendmsg(), thread_timer() などで動的にメモリを獲得している.で,現状では malloc() を呼んでしまっているのだが,実際のOSではこんなふうに何も考えず内部で malloc() を使えることはなく,OSの内部で独自に動的メモリ管理を行わなければならない.で,とりあえず簡単に考えると,以下のような仕組みにすることを思いつく.

  1. static char membuf[1024*256];

    のようにして,巨大なメモリ空間を静的に確保する.
  2. 上記メモリ空間を(malloc() ライブラリで行っているように)内部を可変長で細分化して管理する.
まあ何を言っているのかわかりにくいかもしれないが,つまりOSの内部に malloc() のような可変長メモリ管理を導入するというものだ.

で,これでいいかというと,まあ実際にこれでもOSは動作するだろう.しかし普通のOSでは,このような構造はまあ採用されないだろうと思う.というのはこのように固定領域の内部を可変長で管理するという方法だと,内部をリンクリスト管理する必要性が出てくるため,メモリ獲得時のリンクリストの検索が避けられなくなっている(工夫することで回数を減らすことはできるだろうが,根本的に解決することはできない).で,こーいうのはOSの応答性能に如実にかかわってくる.動的メモリ獲得はOS内部のいろいろなところで利用されるため,その都度,メモリ獲得にかかる時間が予測できなくなってしまうわけだ.

これはまず,リアルタイムOSでは致命的だ.しかしリアルタイムでない汎用OSなどでも,性能の問題になるのでまああまりよろしくない.ということでふつうはどういうふうに動的メモリ管理を行うかというと,まずは可変長という仕組みを廃止して,固定長で管理するのが普通だと思う.

固定長ならば配列として管理できるので,領域の使用/未使用をビットマップ管理することができる.このため空き領域の検索処理を高速化したり,書き方を工夫することでリアルタイム性を確保することができる.まあこのへんはそのうち機会があったら説明するが,ビットマップ管理されているならば,CPUのビットサーチ命令を使ったり,ビットマップを半分ずつ分割してゼロチェックしていく方法(Toppersで優先度キューの検索に使われている)などにより,一定時間での空き領域検索が可能になるため,リアルタイム性を確保することができるのだ.

とくにOSの内部では,それほど巨大なメモリ領域が必要となる機会はそれほど多くはないので,巨大メモリを確保している場所は限定できる場合が多い.なので,数KBくらいの固定長メモリ管理で十分に役目を果たせる場合が多い.利用効率を考えるならば,数十バイト,数百バイト,数キロバイトの数種類のサイズの固定メモリ管理を用意し,必要に応じて利用者側で選択(もしくは自動選択)するようにすればよい.

で,そーいう理由なのかどうか歴史的ないきさつはあまりよくは知らないのだけど,BSDでは mbuf という,固定サイズの動的メモリ管理機構をOS内部で持っている.主にネットワーク転送のためにパケットを格納するのに利用されたりするが,他にも固定サイズの動的メモリとして,様々な箇所で利用される.Linux だとまた別に何かあったと思う,たしか.こんなふうに,OSは内部に汎用的な固定サイズの動的メモリ獲得機構を持っている場合が多い.

OSのカーネルソースを読むと,なぜメモリ獲得に malloc() を使っていないのか,なぜ固定長なのか,という疑問にぶちあたるのだけど,まあこーいう理由があるのだ.

で,今回はKOZOS内部のメモリ管理を設計しなおしてみよう.
  • KOZOS内部では,タイマ管理やメッセージ管理のためにちょっとした領域を動的に利用している.これらは数百バイトのサイズがあればよい.
  • これとは別に,kz_memalloc() ではやはり現状で malloc() によってメモリ獲得しているが,これはどれくらいのサイズが要求されるのか,アプリに依存する.もしかしたら数百キロバイトなどの巨大な空間を利用するようなアプリがそのうち移植されるかもしれない.
  • デバッグのためには,OS内部で利用する動的メモリと,kz_memalloc() によってアプリ側で利用される動的メモリを区別して管理したほうがよい.
  • アプリによっては,リアルタイム性を確保するために,動的メモリ獲得のためのシステムコールが必ず一定時間で完了してほしい場合もあるかも.
ということで,以下のように設計しよう.
  • KOZOS内部での動的メモリ獲得のためのサービス関数(kzmem_alloc(), kzmem_free())を用意する.これはリアルタイム性を確保した設計にする.
  • スレッドからの呼び出し用に,動的メモリ獲得用の新規システムコールとして,kz_kmalloc(), kz_kmfree() を新設する.これは内部から kzmem_alloc(), kzmem_free() を呼び出すだけのものであるため,スレッド側ではリアルタイム性のある動的メモリ確保が行える.(本来ならばOS内部の動的メモリ管理とスレッド用の動的メモリ管理は分割するべきなのかもしれないが,まあ面倒なのでいっしょにしてしまう.そのうち必要があれば分割する)
  • kz_memalloc(), kz_memfree() は従来通り,内部で malloc(), free() を呼び出すだけとする.これは数百キロバイトなどの巨大なメモリ空間が必要な場合に利用する目的のものだが,リアルタイム性は無い.
たとえば extintr では,リードしたデータのメッセージ送信のために2KBの領域(BUFFER_SIZE として定義されている)を kz_memalloc() によって獲得している.これは応答性のことを考えると,kz_memalloc() ではなく kz_kmalloc() を利用するのが望ましい.このように,固定サイズだとはっきりとわかっているような場合には kz_kmalloc() を使ったほうがよい.リアルタイム性が確保できるし,リアルタイム性が不要だとしても,とりあえず高速だからだ.しかし必要サイズが実行時までわからないような場合には,kz_memalloc() を利用する,ということになる.

で,修正したのが以下.

以下に修正点について説明する.今回はけっこういっぱい修正しているので注意してほしい.

まず,固定サイズの動的メモリ管理のために memory.h, memory.c を追加している.memory.h はまあたいして説明することは無いので説明は省略.memory.c は,まあ単なるC言語の関数なのだが,今回の目玉でもあるので以下に詳細に説明しよう.

まずは memory.c の先頭部分.

#define MEMORY_AREA1_SIZE 128
#define MEMORY_AREA1_NUM 100
#define MEMORY_AREA2_SIZE 512
#define MEMORY_AREA2_NUM 50
#define MEMORY_AREA3_SIZE 2048
#define MEMORY_AREA3_NUM 20

static char memory_area_1[MEMORY_AREA1_SIZE * MEMORY_AREA1_NUM];
static char memory_area_2[MEMORY_AREA2_SIZE * MEMORY_AREA2_NUM];
static char memory_area_3[MEMORY_AREA3_SIZE * MEMORY_AREA3_NUM];

今回作成した固定サイズ動的メモリ管理ライブラリでは,固定領域のサイズとして128バイト,512バイト,2キロバイトの3種類のサイズを用意している.それぞれの獲得最大数は,とりあえず100個,50個,20個に設定してある.このためそれぞれのメモリプールのサイズは128×100バイト,512×50バイト,2048×20バイトの固定領域を static に獲得している.

このように,メモリの動的管理のためにあらかじめ確保する巨大な空きメモリのことを一般に「プール」とか「メモリプール」とか「フリープール」とか呼ぶ.メモリプールは物理メモリの空き部分である「ヒープ領域」から一定のサイズを獲得している場合が多いのだが,KOZOSではとりあえず static なバッファとしてmemory.c の先頭で獲得している.

OS内部の固定サイズ動的メモリ管理機構は,このようにして確保したメモリプールを固定サイズの配列に区画分けして,必要に応じて割り当てるという作業を行うことになる.

次に,領域の管理用構造体の定義.

typedef struct _kzmem {
struct _kzmem *next;
int size;
int dummy[2];
} kzmem;

typedef struct _kzmem_pool {
char *area;
int size;
int num;
kzmem *free;
} kzmem_pool;

static kzmem_pool pool[] = {
{ memory_area_1, MEMORY_AREA1_SIZE, MEMORY_AREA1_NUM, NULL },
{ memory_area_2, MEMORY_AREA2_SIZE, MEMORY_AREA2_NUM, NULL },
{ memory_area_3, MEMORY_AREA3_SIZE, MEMORY_AREA3_NUM, NULL },
};

#define MEMORY_AREA_NUM (sizeof(pool) / sizeof(*pool))

まあ構造体の使いかたについては,たいして難しくはないので memory.c を読んでほしい.注意として,メモリ領域の先頭には管理領域として必ず kzmem 構造体が付加されている.kzmem 構造体のサイズは16バイトなので,たとえば今回の設計では固定領域のサイズとして128バイト,512バイト,2キロバイトの3種類のサイズが利用できるが,128バイト領域が実際に格納できるサイズは 128 - 16 で112バイトということになる.

ちなみに kzmem 構造体は,ダミーのメンバを入れることでサイズを16バイトに調整してある.これは,将来的に管理用に新しいメンバ(マジックナンバとか,メモリの種別とか,フラグとか)を追加したくなった際に,ダミーの部分を置き換えることで kzmem のサイズを変更せずに拡張できるようにするためだ.まあサイズが変わったところで実害は無いのでここまで考えておく必要は無いかもしれないが,いちおうあらかじめダミーを入れておくことにした.

次に,メモリ管理の初期化.

static int kzmem_init_pool(kzmem_pool *p)
{
int i;
kzmem *mp;
kzmem **mpp;

mp = (kzmem *)p->area;
mpp = &p->free;
for (i = 0; i < p->num; i++) {
*mpp = mp;
memset(mp, 0, sizeof(*mp));
mp->size = p->size;
mpp = &(mp->next);
mp = (kzmem *)((char *)mp + p->size);
}

return 0;
}

int kzmem_init()
{
int i;
for (i = 0; i < MEMORY_AREA_NUM; i++) {
kzmem_init_pool(&pool[i]);
}
return 0;
}

kzmem_init() を呼び出すと,3種類の固定メモリのメモリプールの初期化を行う.まあ具体的には kzmem_init_pool() を呼び出し,メモリプールを固定サイズに分割してぜんぶフリーリストに繋げておく,ということを行う.kzmem_init() はKOZOSの起動時に読んでもらう必要がある.ちなみにここではループ処理を行っているためリアルタイム性を確保できないが,起動時に1回呼ぶだけの初期化処理なのでまあ気にしないことにする.このへんはメモリ獲得のたびに徐々に切り取っていくようにするなどすれば,kzmem_init() で一気に初期化しないようにすることもできる.そのうち改良が必要かも.

次に,実際のメモリ獲得処理.

void *kzmem_alloc(int size)
{
int i;
kzmem *mp;
kzmem_pool *p;

for (i = 0; i < MEMORY_AREA_NUM; i++) {
p = &pool[i];
if (size <= p->size - sizeof(kzmem)) {
if (p->free == NULL) {
kz_sysdown();
}
mp = p->free;
p->free = p->free->next;
mp->next = NULL;
return (char *)mp + sizeof(kzmem);
}
}

kz_sysdown();
return NULL;
}

kzmem_alloc()は,メモリ獲得用のライブラリ関数だ.与えられたサイズに応じて,3種類の固定メモリの中から適切なサイズのものを返す.ちなみに最適サイズの検索のために

for (i = 0; i < MEMORY_AREA_NUM; i++) ...

のようなループを行っているが,これはループ回数を固定で見積もれるため,リアルタイム性に関する問題は無い.

プールのサイズは有限なので,プールが不足するとメモリが獲得できないということになる.この場合はどうするべきか?また実際の領域は3種類の固定サイズ(128バイト,512バイト,2キロバイト)の中から適切なものが選択されるが,たとえば4キロバイトの領域を獲得しようとした場合にはどうすべきか?

これについては kzmem_alloc() がNULLを返し,呼び出し元でNULLチェックして判断する,という方法もある.しかし組み込みOSでは,システム全体を1単位として開発元でチューニングすることができる.よって「メモリ領域が足りなくなったらどうするか?」ではなく,「メモリ領域が足りなくならないように,各アプリが必要とする領域数に合わせて領域数を拡張しておく」という設計が可能だ.なので,今回は足りなくなったときにはNULLを返すのではなく,システムダウンする設計にする.上述したように,領域が不足しているということはそもそも領域を拡張するようなチューニングが必要だ,ということなので,NULLを返してそれなりに動いてしまうのではなく,領域不足としてダウンしてくれたほうが親切だ.4キロバイトなどのオーバーサイズの領域を獲得しようとした場合についても,同様にシステムダウンする設計にする.

次に解放用のライブラリ関数.

void kzmem_free(void *mem)
{
int i;
kzmem *mp;
kzmem_pool *p;

mp = (kzmem *)((char *)mem - sizeof(kzmem));

for (i = 0; i < MEMORY_AREA_NUM; i++) {
p = &pool[i];
if (mp->size == p->size) {
mp->next = p->free;
p->free = mp;
return;
}
}

kz_sysdown();
}

こちらは返された領域をフリーリストに繋ぎなおすだけだ.

注目なのは,未使用領域の獲得時にはキューの先頭から領域取得して,領域の解放時にはキューの先頭に繋げるだけのため,ループによる検索などは行っていないことだ.このためメモリの獲得・解放はリアルタイム性を保証できる.

次に,他の部分の修正差分について説明しよう.

まず thread.h についてなのだけど,実はメッセージの管理用構造体がkz_membuf という名前になっていて,今回追加したメモリ管理と名前が混乱しやすい.なので kz_membuf を kz_msgbuf という本来の名前に変更する.

diff -ruN kozos27/thread.h kozos28/thread.h
--- kozos27/thread.h Wed Dec 12 13:19:43 2007
+++ kozos28/thread.h Wed Dec 12 15:00:49 2007
@@ -12,12 +12,12 @@
#define PRI_NUM 32
#define THREAD_NAME_SIZE 16

-typedef struct _kz_membuf {
- struct _kz_membuf *next;
+typedef struct _kz_msgbuf {
+ struct _kz_msgbuf *next;
int id;
int size;
char *p;
-} kz_membuf;
+} kz_msgbuf;

typedef struct _kz_thread {
struct _kz_thread *next;
@@ -35,8 +35,8 @@
} syscall;

struct {
- kz_membuf *head;
- kz_membuf *tail;
+ kz_msgbuf *head;
+ kz_msgbuf *tail;
} messages;

struct {

次に thread.c の修正が以下.

diff -ruN kozos27/thread.c kozos28/thread.c
--- kozos27/thread.c Wed Dec 12 13:19:43 2007
+++ kozos28/thread.c Wed Dec 12 15:00:50 2007
@@ -8,6 +8,7 @@

#include "kozos.h"
#include "syscall.h"
+#include "memory.h"
#include "thread.h"
#include "stublib.h"

@@ -164,7 +165,7 @@

static void recvmsg()
{
- kz_membuf *mp;
+ kz_msgbuf *mp;

mp = current->messages.head;
current->messages.head = mp->next;
@@ -177,16 +178,16 @@
*(current->syscall.param->un.recv.idp) = mp->id;
if (current->syscall.param->un.recv.pp)
*(current->syscall.param->un.recv.pp) = mp->p;
- free(mp);
+ kzmem_free(mp);
}

static void sendmsg(kz_thread *thp, int id, int size, char *p)
{
- kz_membuf *mp;
+ kz_msgbuf *mp;

current = thp;

- mp = (kz_membuf *)malloc(sizeof(*mp));
+ mp = (kz_msgbuf *)kzmem_alloc(sizeof(*mp));
if (mp == NULL) {
fprintf(stderr, "cannot allocate memory.\n");
exit(1);
@@ -238,7 +239,7 @@
int diffmsec;
struct itimerval itm;

- tmp = malloc(sizeof(*tmp));
+ tmp = kzmem_alloc(sizeof(*tmp));
tmp->next = NULL;
tmp->thp = current;

@@ -286,7 +287,7 @@
sendmsg(timers->thp, 0, 0, NULL);
tmp = timers;
timers = timers->next;
- free(tmp);
+ kzmem_free(tmp);
if (timers) {
gettimeofday(&alarm_tm, NULL);
itm.it_interval.tv_sec = 0;
@@ -324,6 +325,19 @@
return 0;
}

thread.h と同様に kz_membuf → kz_msgbuf の修正が各箇所に入っている.あとメッセージ管理とタイマ管理に malloc()/free() を利用していた部分があり,kzmem_alloc()/kzmem_free()に変更している.これらの部分では sizeof(kz_msgbuf) や sizeof(kz_timebuf)のサイズの領域が獲得されている.つまり,構造体のサイズのメモリ領域が獲得されている.よってここで獲得される領域サイズは固定なので,kzmem_alloc()/kzmem_free() に移行してしまって問題は無い.これにより,メッセージ処理部分,タイマ処理部分(タイマ設定部分を除く)に対してリアルタイム性を持たせることができる.

次に,まあ kzmem_alloc()/kzmem_free() は本来はKOZOSのカーネル内部での動的メモリ管理のためのライブラリなのだが,リアルタイム性のあるメモリ管理が行えるため,それをそのままサービスするためのシステムコールを追加する.

+static void *thread_kmalloc(int size)
+{
+ putcurrent();
+ return kzmem_alloc(size);
+}
+
+static int thread_kmfree(char *p)
+{
+ kzmem_free(p);
+ putcurrent();
+ return 0;
+}
+
static void *thread_memalloc(int size)
{
putcurrent();
@@ -386,6 +400,12 @@
case KZ_SYSCALL_TYPE_DEBUG:
p->un.debug.ret = thread_debug(p->un.debug.sockt);
break;
+ case KZ_SYSCALL_TYPE_KMALLOC:
+ p->un.kmalloc.ret = thread_kmalloc(p->un.kmalloc.size);
+ break;
+ case KZ_SYSCALL_TYPE_KMFREE:
+ p->un.kmfree.ret = thread_kmfree(p->un.kmfree.p);
+ break;
case KZ_SYSCALL_TYPE_MEMALLOC:
p->un.memalloc.ret = thread_memalloc(p->un.memalloc.size);
break;

本来ならばカーネル用のメモリプールとユーザースレッド用(システムコール用)のメモリプールを別に管理すべきなような気もするが,面倒なのでまあいいとしよう.

こーいうように,カーネルのための資源とユーザーのための資源をごっちゃにしてしまうと,ユーザースレッドがへんなことをしたらカーネル側にもそれが伝搬してシステム全体が落ちる,ということの原因になり得るので,本来ならばきちんと資源を分離すべきだと思う.

しかしまあ第25回の最後のほうで書いたように,組み込みOSは性善説に基づいているというか,ユーザースレッドがおかしなことをしたときには,「そのスレッドはどうでもいいとして,全体としては落ちることなく動作する」というのではなく,「そのユーザースレッドを正すべき」という考えだ.なのできちんと資源を分離することには,デバッグが楽になるという以上の意味は無い.(これが汎用OSならば,おかしなアプリが動いたときにOS全体がおかしくなることを防止する,という意味があるのだが,組み込みOSではそうなったらそーいうアプリのバグを直すべきなので,そーいう意味で,デバッグが楽になる以上の意味は無い)

次に,KOZOSの起動部分に kzmem_init() の呼び出しを追加.さらにシステムダウン用のサービス関数として,kz_sysdown() を作成する.

@@ -512,6 +532,8 @@

void kz_start(kz_func func, char *name, int pri, int argc, char *argv[])
{
+ kzmem_init();
+
sigemptyset(&block);
sigaddset(&block, SIGSYS);
sigaddset(&block, SIGHUP);
@@ -525,6 +547,11 @@

/* ここには返ってこない */
abort();
+}
+
+void kz_sysdown()
+{
+ kill(getpid(), SIGILL);
}

void kz_trap()

次に,システムコールの追加について.今回は新規システムコールとして,リアルタイムな動的メモリ獲得のためのkz_kmalloc()/kz_kmfree() が追加されている.

diff -ruN kozos27/syscall.c kozos28/syscall.c
--- kozos27/syscall.c Wed Dec 12 13:19:43 2007
+++ kozos28/syscall.c Wed Dec 12 14:58:54 2007
@@ -120,6 +120,22 @@
return param.un.debug.ret;
}

+void *kz_kmalloc(int size)
+{
+ kz_syscall_param_t param;
+ param.un.kmalloc.size = size;
+ kz_syscall(KZ_SYSCALL_TYPE_KMALLOC, ¶m);
+ return param.un.kmalloc.ret;
+}
+
+int kz_kmfree(void *p)
+{
+ kz_syscall_param_t param;
+ param.un.kmfree.p = p;
+ kz_syscall(KZ_SYSCALL_TYPE_KMFREE, ¶m);
+ return param.un.kmfree.ret;
+}
+
void *kz_memalloc(int size)
{
kz_syscall_param_t param;
diff -ruN kozos27/syscall.h kozos28/syscall.h
--- kozos27/syscall.h Wed Dec 12 13:19:43 2007
+++ kozos28/syscall.h Wed Dec 12 14:51:32 2007
@@ -17,6 +17,8 @@
KZ_SYSCALL_TYPE_PENDING,
KZ_SYSCALL_TYPE_SETSIG,
KZ_SYSCALL_TYPE_DEBUG,
+ KZ_SYSCALL_TYPE_KMALLOC,
+ KZ_SYSCALL_TYPE_KMFREE,
KZ_SYSCALL_TYPE_MEMALLOC,
KZ_SYSCALL_TYPE_MEMFREE,
} kz_syscall_type_t;
@@ -77,6 +79,14 @@
int sockt;
int ret;
} debug;
+ struct {
+ int size;
+ void *ret;
+ } kmalloc;
+ struct {
+ char *p;
+ int ret;
+ } kmfree;
struct {
int size;
void *ret;

まあシステムコールの追加については連載のかなり初期のほうで説明しているので,ここでは詳しくは説明しない.

次に,各種スレッドについてちょっと修正.まずは extintr.c の修正について.

diff -ruN kozos27/extintr.c kozos28/extintr.c
--- kozos27/extintr.c Wed Dec 12 13:19:43 2007
+++ kozos28/extintr.c Wed Dec 12 15:10:44 2007
@@ -10,7 +10,7 @@
#include "kozos.h"
#include "thread.h"

-#define BUFFER_SIZE 2048
+#define BUFFER_SIZE 1024

int extintr_id;

まずは外部割り込み発生時に,ソケットをリードして当該のスレッドにメッセージ送信するためのバッファのサイズなのだが,今までは2KBになっていた.しかし今回,このメモリ獲得を kzmem_alloc() に移行する.memory.c で管理している固定メモリ領域の最大サイズは2キロバイトなので,これはギリギリ入りそうに思えるのだが,実はこの2キロバイトというサイズは管理領域である kzmem 構造体のサイズも含まれているため,実際に利用できるのは 2048 - 16 = 2032 バイトとなる.よって BUFFER_SIZE を1KBに縮小している.まあ BUFFER_SIZE を縮小したところで,足りなければ数回に渡って read() されるだけなので実害は無い.

あとついでに,memory.c での固定メモリ領域の最大サイズを2048バイト(実質は2032バイト)にしている理由なのだが,将来的に ethernet フレームを扱う際に,フレーム全体(最大で約1.5KB)が格納できるサイズにしておきたかったから.

次に,extintr.c 内部で kz_memalloc()/kz_memfree() によってメモリ獲得していた部分を,kz_kmalloc()/kz_kmfree() に移行する.これは外部割り込みの処理に,リアルタイム性を持たせたかったため.

@@ -96,12 +96,12 @@
FD_CLR(fd, &readfds);
ibp = *ibpp;
*ibpp = (*ibpp)->next;
- kz_memfree(ibp);
+ kz_kmfree(ibp);
return -1;
}
}

- ibp = kz_memalloc(sizeof(*ibp));
+ ibp = kz_kmalloc(sizeof(*ibp));
ibp->next = NULL;
ibp->fd = fd;
ibp->id = id;
@@ -154,7 +154,7 @@
kz_send(ibp->id, s, NULL);
break;
case INTR_TYPE_READ:
- buffer = kz_memalloc(BUFFER_SIZE);
+ buffer = kz_kmalloc(BUFFER_SIZE);
size = read(ibp->fd, buffer, BUFFER_SIZE);
if (size >= 0)
kz_send(ibp->id, size, buffer);

extintr はソケットの監視を行い,受信データが届いた際には read() してメッセージによって該当のスレッドに送信する.この際利用されるデータ格納のバッファが kz_kmalloc() で獲得されるように修正されたので,ソケットの監視に extintr を利用しているスレッドは,kz_memalloc() でなく kz_kmalloc() によって獲得されたメモリ領域を受けることになる.以下はそのための各スレッドの修正.

diff -ruN kozos27/httpd.c kozos28/httpd.c
--- kozos27/httpd.c Wed Dec 12 13:19:43 2007
+++ kozos28/httpd.c Wed Dec 12 14:56:28 2007
@@ -37,7 +37,7 @@
break;
}
memcpy(buffer + len, p, size);
- kz_memfree(p);
+ kz_kmfree(p);
len += size;
buffer[len] = '\0';
} while (strchr(buffer, '\n') == NULL);


diff -ruN kozos27/telnetd.c kozos28/telnetd.c
--- kozos27/telnetd.c Wed Dec 12 13:19:43 2007
+++ kozos28/telnetd.c Wed Dec 12 14:57:04 2007
@@ -43,7 +43,7 @@
|| memchr(p, 0xff, size) /* Ctrl-C対応 */
) break;
memcpy(buffer + len, p, size);
- kz_memfree(p);
+ kz_kmfree(p);
len += size;
buffer[len] = '\0';


diff -ruN kozos27/stubd.c kozos28/stubd.c
--- kozos27/stubd.c Wed Dec 12 13:19:43 2007
+++ kozos28/stubd.c Wed Dec 12 14:56:52 2007
@@ -81,7 +81,7 @@
fprintf(stderr, "\'%c\'", p[i]);
}
}
- kz_memfree(p);
+ kz_kmfree(p);
}

close(s);

httpd, telnetd, stubd で受信したバッファを kz_memfree() でなく kz_kmfree() で解放するように修正した.

次に,コンソールへのログ出力のために outlog スレッドというのがいるが,これも kz_memalloc() によって獲得した領域を利用していたため,kz_kmalloc() に移行する.これにより,出力できるログの長さに上限ができることになるが,まあ2000文字以上のログを出すこともあまり無いと思われるので気にしない.outlog を利用している clock スレッドにも,同様の修正を入れる.

diff -ruN kozos27/outlog.c kozos28/outlog.c
--- kozos27/outlog.c Wed Dec 12 13:19:43 2007
+++ kozos28/outlog.c Wed Dec 12 14:56:38 2007
@@ -11,6 +11,6 @@
while (1) {
kz_recv(NULL, &p);
fprintf(stderr, "%s", p);
- kz_memfree(p);
+ kz_kmfree(p);
}
}


diff -ruN kozos27/clock.c kozos28/clock.c
--- kozos27/clock.c Wed Dec 12 13:19:43 2007
+++ kozos28/clock.c Wed Dec 12 14:56:14 2007
@@ -17,7 +17,7 @@
kz_recv(NULL, NULL);

t = time(NULL);
- p = kz_memalloc(128);
+ p = kz_kmalloc(128);
strcpy(p, ctime(&t));
kz_send(outlog_id, 0, p);
}

あとは Makefile とか kozos.h とかにちょこちょこと対応が入っているが,まあたいした修正ではないのでここでは説明しない.ちなみに今回は,全体的な動作確認のため,main.c を第23回のものに戻している(ので diff.txt を見ると main.c にいっぱい修正が入っていることになっている)ので注意してほしい.

で,make して動作確認した.まあ確認結果は面倒なので省くが,gdbからの接続,continueによる動作開始,時刻表示,telnet接続,telnetでのコマンド実行,telnetでのブレーク,ブレークからのcontinueによる動作再開と,ひととおり動作を確認できた.まあ問題は無いようだ.

ちなみに今回の修正でKOZOS内部での malloc()/free() 呼び出しをkzmem_alloc()/kzmem_free() に移行してリアルタイム性を持たせたが,部分的に malloc()/free() が残っている箇所がある.kz_start() による起動時のスタック作成と,kz_run() によるスレッド作成時のスタック作成部分だ.これらは,スタックにはわりと大きめの領域が必要となるという理由で,あえてそのままにしてある.まあ kz_start() は起動時の1回だけなのでいいとして,kz_run() は起動後もスレッド作成のたびに頻繁に呼ばれる(そしてスレッドの作成は,例えば telnetd ならば接続要求を受け付けるたびに行われる)ので,これはたぶん問題だろう.これについては,またあとで考えることにしよう.

今回はメモリ管理についてだいぶ修正した.動的なメモリ管理のサービスを内部で持っていないOSは,相当簡略化されたものを除けば,まあほとんど無いと思われる.動的なメモリ管理に関しては他にもいろいろと資料があると思われるのでそちらも参照してほしいのだが,OS内部で利用するには独自の流儀というか,単なるライブラリ関数に求められるものとは要求されるものが違ってくるので注意が必要だ.逆のいいかたをすると,OS内部で利用するためには何が必要なのかを理解できれば,なぜ mbuf のようなメモリ管理が実装されているのかが自ずとわかってくるものだ.
(注意)このブログは本家のほうの文章部分のみの転載です.ソースコードの配布,画像などについては本家のほうを参照してください.文章中のリンク先は面倒なのですべて本家のほうに変換してしまっているのでご注意ください.

前回はリアルタイム性の一般的な話をしたが,今回はKOZOSのリアルタイム性について考えてみよう.

まず最初に断っておくが,KOZOSは汎用OS上で1プロセスとして動作するアプリケーション・プログラムだ.なので,KOZOS自体にはリアルタイム性は無い.というより,汎用OSの上で動く以上,保証のしようがない.いつFreeBSDのページングが発生して動きが止まるか,まったく予測できないからだ.

なので,今回考える「KOZOSのリアルタイム性」というのは,KOZOSの内部構造的に,そのまま組み込みOSとしたときにリアルタイム性を確保できるか,というあくまで理論的な話になる.「KOZOSが単体で動いていたら...」というように,読みかえて理解して欲しい.KOZOSの場合は,実時間でなくプロセス内部の時間としてリアルタイム性が確保できるか,という話になる.そーいう意味で,「似非リアルタイム」(エセリアルタイム)とでも言ったほうがいいかなーとも思う.

まずリアルタイム性を確保するためには,優先度をベースにしたプリエンプティブな動作が重要になってくる.たとえば汎用OSのように,割り込みによってあるタスクが動作可能になっても,他のタスクが動作中なのでそれが一段楽するまで待たされる(そしてその時間は,例えばエアバッグ制御のような緊急を要する処理に対して考えると,おそらくとおっっっても長い),というのでは話にならない.ということで,まあたいていは優先度の高いタスクが割り込めるように,プリエンプティブな構造にすることになる.

さらにリアルタイム性を確保するためには,ページング処理はダメだ.ハードディスクに退避された情報が復帰する場合に,どれくらい時間がかかるのか,まったく見積もれない(たとえ見積もれたとしても,それは話にならないくらい遅い)からだ.

また,OS内でキューの検索などをしているのもダメだ.キューが長くなった場合に検索にかかる時間を見積もれないからだ.基本的に,ループ処理は時間を見積もれない原因になるので,リアルタイム性という点で見ると,OS内で使うのはよろしくない.どうしてもループを使うのならば,ループの最大回数(つまり,最悪値)がきちんと見積もれないとならない.

割り込み禁止区間が長いのも問題だ.その間は割り込みを受け付けないため,たとえ割り込みが発生しても,それを受け付けて,処理するアプリケーションを即ディスパッチすることができないからだ.

このように考えると,KOZOSではリアルタイムを確保できていない部分がいくつかある.
  1. スレッドの優先度キューへの挿入時に,ループでキューのお尻の検索をしている.(putcurrent())
  2. メッセージの送信時に,ループでキューのお尻の検索をしている.(sendmsg())
  3. タイマ設定時のキューの挿入にループが利用されている.(thread_timer())
  4. メモリ獲得が malloc() で行われている.(thread_memalloc(), thread_memfree())
  5. その他,各所で malloc() が使われている.
  6. スケジューリング時の優先度キュー検索にループが利用されている.(schedule())
  7. KOZOS内部での処理中は,ずっと割り込み禁止になっている.(sigaction()で sa.sa_mask = block として設定しているため,割り込みハンドラ内部ではシグナルがブロックされる.これはOS内部の再入を防止するため)
ということでいくつかあるのだけど,まず今回は1と2について考えてみよう.というのはこの処理は,以下の問題があるからだ.
  • 優先度キューの処理も,メッセージ送信の処理も,KOZOS内部で頻繁に呼ばれるため,使用頻度が非常に高い.
  • キューが長くなったときに処理時間が見積もれなくなってしまう.
これらは現状,for ループで検索しているため,キューが長くなるといつまでかかるのかがわからない.つまり,putcurrent() や sendmsg() を呼び出したときに,どれくらいの時間で関数から返ってくるのかを固定値として計算することができないわけだ.

たとえばあるスレッドが kz_send() によってメッセージ送信をしたときに,KOZOSがメッセージ送信処理をしている最中にタイマ割り込み(アラームシグナル)が入って,もっと優先度の高いスレッドが動作可能になった場合のことを考えてみよう.

KOZOSはシステムコールの処理中は,ずっと割り込み禁止になっている.この場合,KOZOSは以下のように動作する.
  1. システムコール(kz_send())の処理中は割り込み禁止(シグナルがブロックされる)なので,タイマ割り込み(アラームシグナル)は保留される.
  2. kz_send()の処理が終り,次に動作するスレッドのスケジューリングが行われた後,ディスパッチの直前に,一瞬だけ割り込み許可になる部分がある(これについては第14回を参照).ここで保留中のタイマ割り込みがハンドリングされる.(thread_intrvec()の終端部分)
  3. タイマ割り込みがハンドリングされると,タイマをかけたスレッドに対してメッセージが投げられる.(alarm_handler())
  4. その後スケジューリングが行われる(schedule()).タイマをかけたスレッドのほうが優先度が高いためにカレントスレッドとなり,ディスパッチされる.(thread_intrvec()の終端部分)
ここでまず,1の割り込み禁止区間について考えてほしい.

kz_send()の処理中は割り込み禁止になっているため,この間は割り込みが発生してもハンドリングできない.そして kz_send() によるメッセージ送信処理では sendmsg()が呼ばれる.sendmsg() は前述したようにループによってキューのお尻の検索を行うので,実行にどれくらいの時間がかかるのか,キューの状態によって変化する.というよりも,メッセージがたまっていてキューが長くなっているとそれだけ時間がかかるため,「最長でもXXマイクロ秒で実行が完了します」といった言いかたができない.上限が無いわけだ.(メッセージのたまっている数がわかれば理論上は計算はできるが,そんなふうに動的に変わってしまうんでは組み込みシステムの設計はとてもとてもできないので却下.固定値で絶対にXXマイクロ秒以内,というようにはっきりしていないとダメ)

ということは,kz_send() によるメッセージ送信処理の最中(この間は割り込み禁止)にタイマ割り込みが発生したときには,いつになったら割り込み禁止が解除されて割り込みのハンドリングが行われるのかがなんともわからないので,タイマ割り込みが発生してから実際にハンドリングされるまでの時間が保証できない.よってタイマ割り込みが起こった瞬間から,それによって動作可能になるはずのスレッドが実際にディスパッチされるまでの時間が固定値として保証できない.こーいうのが,「リアルタイム性が無い」ということなのだ.

ついでにいうならば,kz_send() の呼び出し時には putcurrent() も呼ばれる.putcurrent() では優先度キューのお尻の検索にやはりループが行われているので,おなじ優先度のキューにスレッドが複数たまっていると,putcurrent() の完了にどれくらいの時間がかかるのか,固定値として保証できない.putcurrent() はシステムコールの処理用関数から呼ばれているので,これはシステムコールの呼び出しの際(この間は割り込み禁止)に,いつまで割り込み禁止になっているのか保証できないということになるので,これもやはりリアルタイム性を確保できない原因になる.

さらに,タイマ割り込みのハンドリング時にタイマをかけたスレッドに対してメッセージを投げる際(上記3の処理)にも,メッセージキューのお尻の検索が行われている.これもやはり,メッセージがいっぱいたまっているといつまでかかるのかが固定値として保証できない.これは「割り込みのハンドリング後に,動作可能となるスレッドがディスパッチされるまでの時間が保証できない」ということになる.

上記のことをまとめると
  • KOZOSの内部処理のために割り込み禁止になっている時間が固定値として保証できないため,実際に割り込みが発生した際に,いつになったら割り込みがハンドリングされるのかが保証できない.
  • 実際に割り込みがハンドリングされた後にも,それによって動作可能になるスレッドが実際にディスパッチされて動作を開始するまでの時間が保証できない.
という2つの問題が現状のKOZOSには存在することになる.

ということで今回は,putcurrent() と sendmsg() の処理について直すことで,KOZOSをリアルタイムOSに向けてもう少し近付けてみた.まあまだまだ不十分なのだけど,いっぺんにやると説明がたいへんなので,少しずつ修正することにする.以下に修正内容を説明する.

まず putcurrent() でのレディーキューの検索なのだけど,これはキューのお尻を指すポインタを別途保持するようにする.さらにランニング状態なのかスリープ状態なのかを現在はレディーキュー上にあるかどうかで判断している部分があるが,状態を表わすフラグを追加して,フラグを見ればいいように修正する.

まず配列 readyque は単なるスレッドへのポインタの配列ではなく,キューの先頭とお尻を格納する構造体に変更する.

diff -ruN kozos25/thread.c kozos27/thread.c
--- kozos25/thread.c Sun Dec 9 22:19:16 2007
+++ kozos27/thread.c Mon Dec 10 20:23:28 2007
@@ -20,7 +20,10 @@
} kz_timebuf;

kz_thread threads[THREAD_NUM];
-kz_thread *readyque[PRI_NUM];
+static struct {
+ kz_thread *head;
+ kz_thread *tail;
+} readyque[PRI_NUM];
static kz_timebuf *timers;
static kz_thread *sigcalls[SIG_NUM];
static int debug_sockt = 0;

getcurrent() はカレントスレッドをレディーキューから抜き出す関数だが,レディーキューにお尻を指すポインタとして tail が追加されたのでその対処と,あとレディーキューから抜いたのでRUNNINGフラグを落とす処理を追加する.

static void getcurrent()
{
- readyque[current->pri] = current->next;
+ readyque[current->pri].head = current->next;
+ if (readyque[current->pri].head == NULL)
+ readyque[current->pri].tail = NULL;
+ current->flags &= ~KZ_THREAD_FLAG_RUNNING;
current->next = NULL;
}

putcurrent()にも同様に,tail とフラグの設定処理を追加する.

static int putcurrent()
{
- kz_thread **thpp;
- for (thpp = &readyque[current->pri]; *thpp; thpp = &((*thpp)->next)) {
+ if (current->flags & KZ_THREAD_FLAG_RUNNING) {
/* すでに有る場合は無視 */
- if (*thpp == current) return -1;
+ return -1;
+ }
+
+ if (readyque[current->pri].tail) {
+ readyque[current->pri].tail->next = current;
+ } else {
+ readyque[current->pri].head = current;
}
- *thpp = current;
+ readyque[current->pri].tail = current;
+ current->flags |= KZ_THREAD_FLAG_RUNNING;
+
return 0;
}

この putcurrent() の修正で注目すべきなのが,フラグと tail を見ればよくなったためにforループが無くなっていることだ.このため putcurrent() の処理は,キューの長さがどんなに長くなっても,それに比例して実行時間がかかるわけではなく,一定の時間内に処理が必ず終了する.つまり,命令数を数えることで,処理時間の最悪値を見積もれる(if文による分岐があるならば,最悪パターンでの処理時間を見積もればよい).これが「リアルタイム性がある」ということに繋がるわけだ.

あとは readyque[] がポインタの配列でなく構造体の配列になったので,そのためのちょろっとした修正.

@@ -373,13 +402,13 @@
{
int i;
for (i = 0; i < PRI_NUM; i++) {
- if (readyque[i]) break;
+ if (readyque[i].head) break;
}
if (i == PRI_NUM) {
/* 実行可能なスレッドが存在しないので,終了する */
exit(0);
}
- current = readyque[i];
+ current = readyque[i].head;
}

static void thread_intrvec(int signo)

さらに,スレッドのメッセージ送受信処理にも,同様に構造体にして,head と tail を追加する.修正内容は優先度キューの修正とほぼ同じなので,こちらはあまり詳しくは説明しない.

@@ -153,8 +166,10 @@
{
kz_membuf *mp;

- mp = current->messages;
- current->messages = mp->next;
+ mp = current->messages.head;
+ current->messages.head = mp->next;
+ if (current->messages.head == NULL)
+ current->messages.tail = NULL;
mp->next = NULL;

current->syscall.param->un.recv.ret = mp->size;
@@ -168,7 +183,6 @@
static void sendmsg(kz_thread *thp, int id, int size, char *p)
{
kz_membuf *mp;
- kz_membuf **mpp;

current = thp;

@@ -181,9 +195,13 @@
mp->size = size;
mp->id = id;
mp->p = p;
- for (mpp = ¤t->messages; *mpp; mpp = &((*mpp)->next))
- ;
- *mpp = mp;
+
+ if (current->messages.tail) {
+ current->messages.tail->next = mp;
+ } else {
+ current->messages.head = mp;
+ }
+ current->messages.tail = mp;

if (putcurrent() == 0) {
/* 受信する側がブロック中の場合には受信処理を行う */
@@ -200,7 +218,7 @@

static int thread_recv(int *idp, char **pp)
{
- if (current->messages == NULL) {
+ if (current->messages.head == NULL) {
/* メッセージが無いのでブロックする */
return -1;
}

static int thread_pending()
{
putcurrent();
- return current->messages ? 1 : 0;
+ return current->messages.head ? 1 : 0;
}

static int thread_setsig(int signo)

リアルタイムOSに近付けるための,今回のKOZOS内部の大きな(たいして大きくないけど)修正はここまで.

あと,スレッド構造体にフラグを追加する.さらにメッセージキューを構造体にして,キューのお尻を tail に格納できるようにする.あと下で説明しているのだけど,readyque[] はスタブ内でスレッドの状態の検索用に公開していたが,フラグを参照すればよくなるので公開をとりやめる.

diff -ruN kozos25/thread.h kozos27/thread.h
--- kozos25/thread.h Sun Dec 9 22:19:16 2007
+++ kozos27/thread.h Mon Dec 10 20:19:06 2007
@@ -26,13 +26,18 @@
kz_func func;
int pri;
char *stack;
+ unsigned int flags;
+#define KZ_THREAD_FLAG_RUNNING (1 << 0)

struct {
kz_syscall_type_t type;
kz_syscall_param_t *param;
} syscall;

- kz_membuf *messages;
+ struct {
+ kz_membuf *head;
+ kz_membuf *tail;
+ } messages;

struct {
ucontext_t uap;
@@ -40,7 +45,6 @@
} kz_thread;

extern kz_thread threads[THREAD_NUM];
-extern kz_thread *readyque[PRI_NUM];
extern kz_thread *current;
extern sigset_t block;

次に,ここからはおまけの修正なのだけど,GDBスタブでは,スレッドの状態(ランニングか,スリープか)を検索するためにreadyque[]を検索していたが,フラグを参照すればよくなったので,そーいうふうに修正する.(GDBスタブに関しては,デバッグ時に使われる機能なので,リアルタイム性とかは考えなくていい.なのでこれはリアルタイム性を確保するためにループを削減しようとしているのではなく,あくまでおまけの修正だ)

diff -ruN kozos25/i386-stub.c kozos27/i386-stub.c
--- kozos25/i386-stub.c Sun Dec 9 22:19:16 2007
+++ kozos27/i386-stub.c Sun Dec 9 22:26:41 2007
@@ -1075,17 +1075,12 @@
if (mode & TAG_DISPLAY) {
ptr = intNToHex(ptr, TAG_DISPLAY, 4); /* mode */
ptr = intNToHex(ptr, 3, 1); /* length */
- {
- kz_thread *thp2;
+ if (thp->flags & KZ_THREAD_FLAG_RUNNING) {
+ strcpy(ptr, "RUN");
+ } else {
strcpy(ptr, "SLP");
- for (thp2 = readyque[thp->pri]; thp2; thp2 = thp2->next) {
- if (thp == thp2) {
- strcpy(ptr, "RUN");
- break;
- }
- }
- ptr += strlen(ptr);
}
+ ptr += strlen(ptr);
}
if (mode & TAG_THREADNAME) {
ptr = intNToHex(ptr, TAG_THREADNAME, 4); /* mode */

さらにLinuxでも動きました!で出たいくつかの問題について,ちょっと直せるだけ直しておいた.

まずは Linux では ualarm() で1000000(1秒)以上の値を設定できない点について,ualarm()ではなく setitimer() を使うように修正.

@@ -218,6 +236,7 @@
kz_timebuf *tmp;
struct timeval tm;
int diffmsec;
+ struct itimerval itm;

tmp = malloc(sizeof(*tmp));
tmp->next = NULL;
@@ -247,8 +266,13 @@
*tmpp = tmp;

alarm_tm = tm;
- if (tmpp == &timers)
- ualarm(timers->msec * 1000, 0);
+ if (tmpp == &timers) {
+ itm.it_interval.tv_sec = 0;
+ itm.it_interval.tv_usec = 0;
+ itm.it_value.tv_sec = timers->msec / 1000;
+ itm.it_value.tv_usec = (timers->msec % 1000) * 1000;
+ setitimer(ITIMER_REAL, &itm, NULL);
+ }

putcurrent();
return 0;
@@ -257,6 +281,7 @@
static void alarm_handler()
{
kz_timebuf *tmp;
+ struct itimerval itm;

sendmsg(timers->thp, 0, 0, NULL);
tmp = timers;
@@ -264,14 +289,18 @@
free(tmp);
if (timers) {
gettimeofday(&alarm_tm, NULL);
- ualarm(timers->msec * 1000, 0);
+ itm.it_interval.tv_sec = 0;
+ itm.it_interval.tv_usec = 0;
+ itm.it_value.tv_sec = timers->msec / 1000;
+ itm.it_value.tv_usec = (timers->msec % 1000) * 1000;
+ setitimer(ITIMER_REAL, &itm, NULL);
}
}

あと,accept() の引数に関して修正.これらは実害はおそらく無いが,Linux でのコンパイル時にワーニングが出たため,修正することにした.このへんは,Linux だとたぶん gcc のバージョンが新しいために型などのチェックが厳しくなっているためだと思われる(これは,良いことだ).まあワーニングはバグの可能性があるというか,それを見た他の人も不安にさせるので,基本的には修正すべきだと思うので修正する.

diff -ruN kozos25/extintr.c kozos27/extintr.c
--- kozos25/extintr.c Sun Dec 9 22:19:16 2007
+++ kozos27/extintr.c Sun Dec 9 22:46:18 2007
@@ -125,7 +125,8 @@
{
fd_set fds;
char *p, *buffer;
- int fd, id, ret, cnt_fd = -1, size, s, len;
+ int fd, id, ret, cnt_fd = -1, size, s;
+ socklen_t len;
struct timeval tm = {0, 0};
intrbuf *ibp;
int fildes[2];


diff -ruN kozos25/stubd.c kozos27/stubd.c
--- kozos25/stubd.c Sun Dec 9 22:19:16 2007
+++ kozos27/stubd.c Sun Dec 9 22:46:55 2007
@@ -14,7 +14,8 @@

int stubd_main(int argc, char *argv[])
{
- int sockt, s, ret, len;
+ int sockt, s, ret;
+ socklen_t len;
char hostname[256];
struct hostent *host;
struct sockaddr_in address;

まあ修正点はこんなところだ.とりあえずこれで,問題なく動作することは確認できた.で,直すべき点は他にもいっぱいあるし,リアルタイムOSとは言えない部分がまだいっぱいあるのだけど,とりあえず現状でのKOZOSのリアルタイム性について考えてみよう.

くどいようだけど,最初のほうでも説明したように,KOZOSは汎用OS上で1プロセスとして動作するアプリケーション・プログラムという仕様上,リアルタイムに動作させることは不可能だ.これはリアルタイムではない汎用OSの上で動く以上,リアルタイム性を保証のしようがないからだ(KOZOSがリアルタイムに動いても,それが動いているOSがリアルタイムに動かなければ,KOZOSとしてはどうしようもない).なので,今回は「KOZOSのリアルタイム性」というのは,「KOZOSがもしも単体で動作したとしたら...,理論上は」というように,読みかえて読んでほしい.

で,まず結論から.上に書いたような意味で,今回の修正を加えたKOZOSはリアルタイムOSだと言えるのかどうかだが,まあ正直いって,リアルタイムOSとはいえないだろう.

まず,リアルタイム化のために今回修正したのは
  • スレッドのレディーキューへの接続時の終端検索
  • メッセージのキューへの接続時の終端検索
の2点だ.これらに関しては,従来はループによってお尻を検索していたが,構造体化して tail メンバによってお尻を保存しておくことで,検索処理が不要になった.よって putcurrent(), sendmsg() からはループは削除されたため,関数の命令数を数えることで,実行にかかる最悪時間が見積もれるようになった.これはリアルタイム化に向けてのひとつの進歩だ.

ただし,現状でKOZOSにはまだ以下の部分で,実行時間が見積もれなくなっている.
  • タイマ設定時のキューの挿入にループが利用されている.(thread_timer())
  • メモリ獲得が malloc() で行われている.(thread_memalloc(), thread_memfree())
  • その他,各所で malloc() が使われている.
  • スケジューリング時の優先度キュー検索にループが利用されている.(schedule())
  • KOZOS内部での処理中は,ずっと割り込み禁止になっている.
とくに malloc() が利用されていることが問題だ.実は動的メモリ獲得のために,とりあえず malloc() を使っている部分がちらほらとあるからだ.malloc() は可変長のメモリ獲得を行うため,関数の内部で空き領域の検索が行われるために実行時間が見積もれない.なので,malloc() を使っている部分ではリアルタイム性を確保できない.そしてそーいう場所がちらほらあるので,KOZOSの処理中(割り込み禁止区間)にかかる時間がまったくもって見積もれない.これではリアルタイムOSとはとても言えたものではない.

ということで,次回はこのへんについて改良していこう.