株式会社ワタリドリのブログ

未知との出会いとワクワクを。

  1. HOME
  2. Tech
  3. OS自作入門 -Advent33-

OS自作入門 -Advent33-

NO IMAGE
目次

Step9 優先度スケジューリング 後半戦

step8の前半戦でラウンドロビン方式から優先度スレッドにする必要がある。というのを理解した。またアイドル・スレッドというのを何も処理がない時（優先度が最も低い状態の処理として）実装するのが必要そうである。

さっそくやっていこう。

優先度の実装

以下のファイルに実装していく。なおこのstepからブートローダへの処理追加はなくなったのでOSへの修正だけでよい。

  • test09_1.c, test09_2.c, test09_3.c（新規）
  • kozos.h, kozos.c（修正）
  • syscall.h, syscall.c（修正）
  • main.c（修正）
  • Makefile（修正）

優先度の対応とシステム・コールの追加

スレッドへ「優先度」をいれる。

まずはkozos.hへの修正。

kz_run()とkz_start()にpriorityを渡して実行できるようにする。

kz_thread_id_t kz_run(kz_func_t func, char *name, int priority, int stacksize,
                      int argc, char *argv[]);
void kz_start(kz_func_t func, char *name, int priority, int stacksize,
              int argc, char *argv[]);

また、システムコールの追加も行なっている。それぞれ

  • kz_wait
    カレント・スレッドをレディー・キューの後ろに接続して、カレント・スレッドを切り替える
  • kz_sleep
    スレッドをレディー・キューから外す
  • kz_wakeup
    スリープ状態のスレッドをレディー・キューにつなぎ直す
  • kz_getid
    自身のスレッドIDを取得する
  • kz_chpri
    スレッドの優先度を変更する

構造体の修正

kozos.cへ修正を加える。

新たにflagsというフィールドが追加されているが、これはKZ_THREAD_FLAG_READYという値を持ち、スレッドがレディー状態のときにはKZ_THREAD_FLAG_READYが立つようにする。また、レディー・キューを配列にすることにより、優先度ごとのレディー・キューとして取り扱えるようにした。

（補足）ビット操作に関して

書籍の方にはビット演算に関することが載っていたので、ビット演算の活用法あたりを読んでおくといいのではないか。

現状のものを用いて軽く説明をすると

#define KZ_THREAD_FLAG_READY (1 << 0)
current->flags |= KZ_THREAD_FLAG_READY;  // これでONになる（フラグを立てる）
current->flags &= -KZ_THREAD_FLAG_READY; // これでOFFになる（フラグを落とす）

これで レディー状態の状態管理 ができるようになった。状態変数としてreadyを宣言して以下のように書くこともできる。

current->ready = 1; // これでON
current->ready = 0; // これでOFF

この方法の場合、アクティブ状態を管理したくなった際にactiveを定義して

current->active = 1; // これでON
current->active = 0; // これでOFF

としなくてはならない。だが、上述のようなビット演算で管理しておくと

#define KZ_THREAD_FLAG_ACTIVE (1 << 1)
current->flags |= KZ_THREAD_FLAG_ACTIVE;  // これでONになる（フラグを立てる）
current->flags &= -KZ_THREAD_FLAG_ACTIVE; // これでOFFになる（フラグを落とす）

これでアクティブ状態の管理もできるようになる。

もう少し詳細に書いておくとflagsの型はuint32 flags;で定義されているので32bitの整数である。なので、

00000000 00000000 00000000 00000000

こんな感じ。

KZ_THREAD_FLAG_READYとKZ_THREAD_FLAG_ACTIVEはそれぞれ

00000000 00000000 00000000 00000001 // KZ_THREAD_FLAG_READY
00000000 00000000 00000000 00000010 // KZ_THREAD_FLAG_ACTIVE

こうなる。これらの|(OR), &(AND)演算なので

00000000 00000000 00000000 00000000 | 00000000 00000000 00000000 00000001 // KZ_THREAD_FLAG_READY ON
00000000 00000000 00000000 00000000 | 00000000 00000000 00000000 00000010 // KZ_THREAD_FLAG_ACTIVE ON

という演算になる。各桁でそれぞれ0 | 1となっているところが結果として1になる。あとは必要な箇所で&を使ってflagsとKZ_THREAD_FLAG_READYとかを評価してやれば、

// KZ_THREAD_FLAG_READYのフラグが立っているときに判定するとtrue
00000000 00000000 00000000 00000001 & 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000001

// KZ_THREAD_FLAG_READYのフラグが落ちてるときに判定するとfalse
00000000 00000000 00000000 00000000 & 00000000 00000000 00000000 00000001
= 00000000 00000000 00000000 00000000

（bitの桁が競合していなければ、レディー状態もアクティブ状態も判断することができる）

となる。

レディー・キューの優先度対応

kozos.cのgetcurrent()、putcurrent()へ修正を加えて、レディー・キューがちゃんと使われるようにする。

if (!(current->flags & KZ_THREAD_FLAG_READY)) {
  return 1;
}
if (current->flags & KZ_THREAD_FLAG_READY) {
  return 1;
}

この辺りの処理によって、スレッドがレディー状態なのかスリープ状態なのかを判別することができる。

スレッドの生成部分の修正

kozos.cのthread_run()を修正していく。

ちょっとよくわからなかったのが、

  (uint32)thread_init | ((uint32)(priority ? 0 : 0xc0) << 24);

ここかなぁ。本によると

スレッドのディスパッチは、rte命令によって行われます。rte命令が実行されると、スタックからCCRとプログラム・カウンタの値を復旧します。・・・CCRが上位1バイト、プログラム・カウンタの値が3バイトとして、4バイトの値にまとめられた状態で格納されています。よって同様の形式でスタックを作成しておくことで、スレッドの初回ディスパッチ時にCCRの初期値を設定することができます。

とのことだが、0xc0 = 11000000なので、CCRの最上位ビットを立てていて、INTR_DISABLE（割込み禁止）で動作するようにしている。CCRの値はスレッドの切り替えの際に保存・復旧されるので、この場合、優先度ゼロのスレッドが動作している間だけ割込みが無効になるという動きになる。

これは割込み処理を行うスレッドで割込み禁止で動作させたいときに利用するためのものなのですが、本書のプログラムでは、とりあえず利用はしません。

なんということだ。

システム・コールの処理

kozos.cに新たに関数を実装していく。

  • thread_wait()
    thread_waitが呼ばれる時は、システム・コールを呼び出したカレント・スレッドがレディー・キューから抜かれた状態となっているため（syscall_proc()内部で取り出しているため）、putcurrent()を読んでレディー・キューにつなぎ直す
  • thread_sleep()
    特に何もすることがないので。カレント・スレッドはレディー・キューから外されたままの状態となりスリープ状態になる。
  • thread_wakeup()
    スレッドIDで指定されたスレッドを、putcurrent()によりレディー・キューに接続している。これで再レディー状態となる。
  • thread_getid()
    thread_wait()と同じ処理だが、戻り値にスレッドIDを返している。
  • thread_chpri()
    スレッドの優先度を変更してputcurrent()をして戻している。

この辺りはあれだな、スレッドの処理が行われるとレディー・キューから取り除かれる。ってのを頭に置いておくと理解しやすいかも知れん。

システム・コール処理の呼び出し追加

kozos.cに加えたシステム・コールだが、呼び出してくれる箇所がない。そのあたりを追加する。

    case KZ_SYSCALL_TYPE_WAIT;
      p->un.wait.ret = thread_wait();
      break;
    case KZ_SYSCALL_TYPE_SLEEP;
      p->un.sleep.ret = thread_sleep();
      .....
      .....

この辺り。システム・コール番号に応じて関数を呼び出しているだけ。

優先度に応じたスケジューリング

kozos.cのschedule()関数の修正。

readyqueが配列になったのでその対応。今回は 優先度の値が小さい方が優先度が高い という設計になっている。

kz_start()の優先度対応

kozos.cのkz_start()関数の修正。

ここも同様にreadyqueが配列になったのでその対応。

さてkozosファイルの修正が終わったので次回はsyscallファイルの修正とかを行なうとしよう。step9は次回で終わりそう（多分）。