081222

昨日紹介した本、絶版でとんでもなくプレミアついてるのね。いろいろ蔵書を 調べてみた。プレミアついてたのを3冊ほど。 Mach(マーク)オペレーティングシステム—プログラミングと概念 (アジソンウェスレイ・トッパン情報科学シリーズ) J. ボイキン A. ランガーマン D. カーシェン S. ロゥバーソ 岩本 信一 これは25000円だって。これはMachの開発者による本で、実装するにあたってどういう問題に対してどう実装したかをとうとうと書かれた本。Machに限らず、その知見を感じとれるいい本です。これが絶版なのは残念ですね。
分散OS Machがわかる本 (LUNAの本シリーズ) 乾 和志 菅原 圭資 LUNA-88KにMachを移植したチームによる本。使う側から見たMachのオーバービューがよくまとまっています。これはMachいじってなければいらないかな。
オペレーティングシステム-設計と実装 (Information & Computing) R. スウィッツア Robert Switzer 斎藤 靖 これは大学の講義をまとめたもの。著者はBach本の擬似コードの抽象化を目指 したのだけど、そうはいっていない。でもそこが実はわかりやすかったりする。 本の半分以降は全部ソースコード。 僕は好きな本。でも一般的にはプレミアついてまで買う本じゃない。


今日はスレッドにプライオリティを入れました。迷ったんだけどね。これを実 装すると、パンドラの箱を開けたことになる。実装しようとするものに対して これはいらないだろうとも思うのだけど...。
問題になるのは優先度逆転だ。マーズパスファインダーもこれにはまった。火 星に着陸した。さぁデータをとるぞと、データをとるスレッドを起動したはい いけど、再起動の連続。データをとるようなスレッドは優先度が低い。システ ムクリティカルな優先度の高いスレッドはタイマ割りこみで実行されるのだけ ど、データ取りのスレッドがリソース握ったままで、起こされてもリソース待 ちで寝るだけ。ウォッチドッグタイマでリセットがかかるという事態だった。 この事件は結局セマフォを優先度継承に設定するように変更して(火星のマーズ パスファインダーに)なんとかなった。


実装します。まずはスレッド側から。プライオリティを変更するルーチンと コンテキストスイッチで次のスレッドを選ぶ部分を変更します。

#define	THREAD_PRIORITY_MAX	4

struct thread_manager
{
  struct tc_queue ready_queue[THREAD_PRIORITY_MAX];
} thread_manager;

優先度はせいぜい4つとして、レディーキューを4つに分割しました。優先順位
はITRONにしたがって、小さい方が優先度が高いことにします。ITRONの仕様と
は違って0から使うことにします。

0 割りこみスレッド
1 アプリ高
2 アプリ低
3 システム

の予定です。

int
thread_context_switch ()
{
  // already interrupt disabled.
  struct thread_control *tc;
  struct tc_queue *q;
  int i;

  if (current_thread->state == THR_RUN)
    {
      current_thread->state = THR_READY;
      q = __ready_queue (current_thread);
      SIMPLEQ_REMOVE_HEAD (q, tc_link);
      SIMPLEQ_INSERT_TAIL (q, current_thread, tc_link);

実行状態(RUN)からREADYに移るときはそのスレッドのプライオリティのレディ
キューにつなぎ直します。

    }

  for (i = 0, tc = NULL; i < THREAD_PRIORITY_MAX; i++)
    {
      q = &thread_manager.ready_queue[i];
      if ((tc = SIMPLEQ_FIRST (q)) != NULL)
	break;
    }

優先度の高いレディキューから次に実行すべきスレッドを探します。レディ
キューが分割されたおかげで、高位のレディキューがうまっていれば、低位の
レディキューは絶対に起動されません。これはプログラミングに考えるべき要
素をかなり増やします。優先度がなければ、単に自分をレディキューの後につ
なぎかえる操作で、すべてのスレッドを実行できた。

  if (tc)
    current_thread = tc;
  current_thread->state = THR_RUN;

  return 0;
}

int
thread_priority (int id, int npri)
{
  int s = intr_suspend ();
  struct thread_control *tc;
  struct tc_queue *new_q, *old_q;
  int opri;
  int err = E_OK;

  assert (npri >= 0 && npri < THREAD_PRIORITY_MAX);
  tc = thread_control + id;
  opri = tc->priority;
  tc->priority = npri;

  new_q = &thread_manager.ready_queue[npri];
  old_q = &thread_manager.ready_queue[opri];

  SCI_PRINTF ("%s:thread%d: pri %d->%d state = %d\n",
	      __FUNCTION__, id, opri, npri, tc->state);
  switch (tc->state)
    {
    case THR_RUN:
      SIMPLEQ_REMOVE_HEAD (old_q, tc_link);
      SIMPLEQ_INSERT_TAIL (new_q, tc, tc_link);

実行状態なので、古い優先度のキューの先頭なのは確実なので、そこから抜い
て、新しいキューに突っこみます。後からです。(ITRONの仕様により)
      if (npri >= opri) // new priority is eqaual or lower.
	{
	  tc->state = THR_READY;
	  thread_switch ();
	}
優先度が同じあるいは下がるなら、スイッチします。同一プライオリティで
thread_priorityを呼んだ時にはrotate ready queueになるのはITRONの仕様です。

      break;

    case THR_READY:
      SIMPLEQ_REMOVE (old_q, tc, thread_control, tc_link);
      SIMPLEQ_INSERT_TAIL (new_q, tc, tc_link);
      if (current_thread->priority > tc->priority)
	{
	  thread_switch ();
	}
もし、設定したスレッドのプライオリティが今のスレッドより高くなるなら、
ここでスイッチします。(??? ITRONの仕様との整合性の確認はまだ ???)

      break;
    case THR_WAIT:
      // nothing to do.
レディキューにつながれてないので、キューの操作はありません。
      break;
    case THR_DORMANT:
      /*FALLTHROUGH*/
    case THR_NONEXISTENT:
      assert (0);
      err = E_OBJ;
      break;
    }
  intr_resume (s);

  return err;
}

スレッドの優先度対応はこのくらい。問題はモニター。例えばこんな感じに、

      monitor_enter (button.mon);
      thread_priority (id, 3); // lowest
      button.data = 333;
      monitor_signal (button.mon, 3);
      monitor_exit (button.mon);

ロックをとってから優先度を最下限まで下げたとする(こんなプログラムを書い てはいけないけれど)、そうするともうこのモニタに入ろうとするスレッドは 最下限のスレッドが動くまでずっと待ちになってしまう(優先度逆転状態)
モニタに優先度継承を組みこみます。モニタに入ろう(monitor_enter)として、 モニタのロックを持っているスレッドが自分より低ければ、そのスレッドのプ ライオリティを自分と同じにて、monitor_exitまで走らせて、ロックを解除さ せます。monitor_waitでも一度ロックを解除することがあるけれど、ここでは 優先度を元に戻しません。それはmonitor_exitでシグナルを送られたスレッド が確実に入口を待つスレッドより先に動くのを確定させるため。

struct thread_control
{
  struct reg regs;
  enum thread_state state;
  int id;
  int priority;

ここから優先度継承用に、
  int native_priority; // for inherit priority
  bool inherit_priority;
継承した時に元の優先度をとっておくのと、今は継承した優先度で動いてます
よ。というフラグを追加。

  addr_t stack_bottom;
  addr_t stack_top;
  int wakeup_request;

  SIMPLEQ_ENTRY (thread_control) tc_link;

  /* monitor ops. */
  int monitor_event;
  SIMPLEQ_ENTRY (thread_control) tc_monitor_lock;
  SIMPLEQ_ENTRY (thread_control) tc_monitor_event;
  int monitor_wakeup_request;
} __attribute__((packed, aligned(4)));


void
monitor_enter (struct monitor *m)
{
  int s = intr_suspend ();
  struct thread_control *lock = 0;

ロックはboolではなく、ロックを保持しているスレッドのコントロールブロックへの
ポインタに変更しました。
  while (m->lock_thread)
    {
      // add to lock wait queue.
      SIMPLEQ_INSERT_TAIL (&m->lock_queue, current_thread, tc_monitor_lock);

ロックを保持しているスレッドの優先度が、今のスレッドの優先度より低い時は
優先度継承をします。
      if (m->lock_thread->priority > current_thread->priority)
	{
	  // Inherit priority.
	  lock = m->lock_thread;
	  if (!lock->inherit_priority) // don't overwrite native priority.
	    lock->native_priority = lock->priority; // save native priority.
元の優先度が書きかえられないように(さらに優先度継承にあたるスレッドに突
入された場合)、最初の一回だけ記憶しておきます。
	  lock->inherit_priority = TRUE;

	  thread_priority (lock->id, current_thread->priority);
これで、呼び出しもとと同じレディキューに並び、同じなのでrotate ready
queueします。もしかしたらさらに上に上げてもいいかも???。
	}
      thread_sleep (current_thread->id);
    }
  m->state = MON_LOCKED;
  m->lock_thread = current_thread;

  intr_resume (s);
}


void
monitor_exit (struct monitor *m)
{
  struct thread_control *tc;
  int s = intr_suspend ();

  assert (m->lock_thread == current_thread);
  // wakeup scheduled thread if any.
  // monitor assures wakeuped thread can handle resource.
  SIMPLEQ_FOREACH (tc, &m->event_queue, tc_monitor_event)
    {
      if (!tc->monitor_wakeup_request)
	continue;

      thread_wakeup (tc->id);
    }

  while ((tc = SIMPLEQ_FIRST(&m->lock_queue)) != NULL)
    {
      SIMPLEQ_REMOVE_HEAD(&m->lock_queue, tc_monitor_lock);
      thread_wakeup (tc->id);
    }

  m->state = MON_UNLOCKED;
  m->lock_thread = NULL;
  if (current_thread->inherit_priority)
    {
      SCI_PRINTF ("return to normal priority.(exit)\n");
優先度継承で動いてきていたのなら、ここで元の優先度に戻して制御を明けは
なします。これの目的は優先度の高いスレッドがロックをとれればいいだけの
ことなので、ここまででいい。
      current_thread->inherit_priority = FALSE;
      thread_priority (current_thread->id, current_thread->native_priority);
確実に優先度の下がる操作なので、thread_priorityの中でthread_switchが実
行されます。

    }

  intr_resume (s);
}


void
monitor_wait (struct monitor *m, int event)
{
  int s = intr_suspend ();

  // monitor wait operation always blocked.
  SIMPLEQ_INSERT_TAIL (&m->event_queue, current_thread, tc_monitor_event);
  current_thread->monitor_wakeup_request = 0;
  current_thread->monitor_event = event;
  m->state = MON_WAIT;

  m->lock_thread = NULL;
シグナルを待ってロックを外します。

  if (current_thread->inherit_priority)
   {
     // nothing to do
ここはmonitor_enterでロックをとったけれど、そこで割りこまれて制御をとら
れた。優先度継承で優先度を上げられてここまできた状況。優先度が低いのが
待つのはいくらでも待たせていいので、ここで元の優先度に戻してもよさそう
だけれど、モニタはシグナルで起こされたスレッドが、入口で待っているスレッ
ドより前に確実に実行されることを保証しないといけない。monitor_exitまで
優先度を継承しないとモニタのセマンティクスを保証しないので、優先度はこ
のまま。
   }

  thread_sleep (current_thread->id);
  current_thread->monitor_wakeup_request = 0;
  SIMPLEQ_REMOVE (&m->event_queue, current_thread, thread_control,
		  tc_monitor_event);
  assert (!m->lock_thread);
  m->lock_thread = current_thread;

  intr_resume (s);
}

こんな感じで実装して、先の強引に低優先度でロックを保持したプログラムは

thread create 1: pc=815ec sp=82ffc
thread create 2: pc=815ec sp=830fc
thread create 3: pc=815ec sp=831fc
thread create 4: pc=81568 sp=832fc
control thread 0
thread_priority:thread0: pri 0->3 state = 0 ここで強引に低優先度にした。
thread 2(receiver):
0: inherit waiters(2) priority 0.(enter) 優先度0の受信スレッドが来た。
thread_priority:thread0: pri 3->0 state = 1 優先度上げた。
thread 4(sender):
return to normal priority.(exit)
thread_priority:thread0: pri 0->3 state = 0 モニタを抜けたので元に戻った。
thread 3(receiver):
thread 4: SEND 2 channel 2
thread 3: RECV 2
thread 2: RECV 2
thread 4: SEND 8 channel 2
thread 3: RECV 8
thread 2: RECV 8

なんとか動いてそう。大丈夫かな? もうこれ以上色気づいた実装はしないこと にします。これでハード、ソフトともに開発機の開発は終了です。長かった。 お膳立てで疲れきったよ。