(第27回)リアルタイム性について考える(その2:KOZOSはリアルタイムOSか?)

2007/12/10

あなたは 人目のお客様です.

前回はリアルタイム性の一般的な話をしたが, 今回は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について考えてみよう. というのはこの処理は,以下の問題があるからだ. これらは現状,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の処理)にも,メッセージキューのお尻の検索が 行われている. これもやはり,メッセージがいっぱいたまっているといつまでかかるのかが 固定値として保証できない.これは「割り込みのハンドリング後に,動作可能となる スレッドがディスパッチされるまでの時間が保証できない」ということになる.

上記のことをまとめると

という2つの問題が現状のKOZOSには存在することになる.

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

(2009/04/10 ライセンスに関する文書として,KL-01とLICENSEを追加. 詳しくは第43回を参照)

以下に修正内容を説明する.

まず 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にはまだ以下の部分で,実行時間が見積もれなくなっている.

とくに malloc() が利用されていることが問題だ.実は動的メモリ獲得のために, とりあえず malloc() を使っている部分がちらほらとあるからだ. malloc() は可変長のメモリ獲得を行うため,関数の内部で空き領域の検索が 行われるために実行時間が見積もれない.なので,malloc() を使っている部分では リアルタイム性を確保できない.そしてそーいう場所がちらほらあるので, KOZOSの処理中(割り込み禁止区間)にかかる時間がまったくもって見積もれない. これではリアルタイムOSとはとても言えたものではない.

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


メールは kozos(アットマーク)kozos.jp まで