事象の待ち合わせ――プロセススケジューリング（その5）：UNIX USER 2004年6月号「Linuxカーネル2.6解読室」より転載（2/2 ページ）

[高橋浩和（VA Linux Systems Japan），UNIX USER]

起床処理

　待機状態プロセスを起床させる関数として、wake_up関数群があります。wake_up関数群は、プロセスをRUNキューに登録することと、プロセス状態をTASK_RUNNINGに変更することを行います。もし起床させたプロセスのほうが、現在実行中のプロセスより実行優先度が高かった場合、プロセススケジューラに対してプリエンプト要求も送ります。wake_up関数群には、表2のように微妙に動作が異なるさまざまなものがあります。

表2 wake_up関数群 関数名 概要 wake_up 事象待ちのプロセスを1つ起床させる wake_up_interruptible シグナル受信可状態で事象待ちのプロセスを1つ起床させる wake_up_all 事象待ちのプロセスをすべて起床させる wake_up_interruptible_all シグナル受信可状態で事象待ちのプロセスをすべて起床させる wake_up_all_sync 事象待ちのプロセスをすべて起床させる。ただし、プリエンプションを発生させない wake_up_interruptible_sync シグナル受信可状態で事象待ちのプロセスをすべて起床させる。ただし、プリエンプションを発生させない※ wake_up_process 指定したプロセスを起床させる

※パイプ処理で利用。パイプへの書き込みや読み出しにより、通信相手プロセスが実行可能状態になっても、現在の処理が終わるまで実行権を明け渡さない。パイプでつながったプロセス群は全体で1つの処理であるため、そのプロセス間でプリエンプトしてもオーバーヘッドが増えるだけであるため。

　WAITキューからプロセスを外すのは、実は起床したプロセス自身です（55）。通常wake_up処理側ではWAITキューの操作は行いません（WAITキュー操作まで行うwake_up処理も存在はします）。そのため、起床させられたプロセスは実行権を得るまでは、RUNキューとWAITキューの両方に登録された状態になります（図14）。

図14 起床直後のプロセス（クリックで拡大します）

　図12の状態遷移図を見るとよく分かりますが、待機状態から直接実行権を得て実行状態になることはできず、必ず実行待ち状態を経由して、RUNキュー上で実行権が割り当てられるのを待ちます。

　実際に起床処理のコードを見てみましょう。wake_up関数の先で呼び出されるプロセス1つだけを起床させるtry_to_wake_up関数をのぞいてみることにします（リスト6）。

リスト6 try_to_wake_up関数

static int try_to_wake_up(task_t * p, unsigned int state, int sync) {     unsigned long flags;     int success = 0;     long old_state;     runqueue_t *rq;     repeat_lock_task:     rq = task_rq_lock(p, &flags); ← 60     old_state = p->state;     if (old_state & state) {         if (!p->array) {             if (unlikely(sync && !task_running(rq, p) &&                 (task_cpu(p) != smp_processor_id()) &&                  cpu_isset(smp_processor_id(),                  p->cpus_allowed))) {                 set_task_cpu(p, smp_processor_id()); ← 61                 task_rq_unlock(rq, &flags);                 goto repeat_lock_task;             }             if (old_state == TASK_UNINTERRUPTIBLE) {                 rq->nr_uninterruptible--;                 p->activated = -1; ← 62             }             if (sync && (task_cpu(p) == smp_processor_id())                 __activate_task(p, rq); ← 63             else {                 activate_task(p, rq); ← 64                 if (TASK_PREEMPTS_CURR(p, rq)) ← 65                     resched_task(rq->curr); ← 66             }             success = 1;         }         p->state = TASK_RUNNING; ← 67     }     task_rq_unlock(rq, &flags);     return success; } static inline void activate_task(task_t *p, runqueue_t *rq) {     unsigned long long now = sched_clock();     recalc_task_prio(p, now); ← 70     if (!p->activated) {         if (in_interrupt()             p->activated = 2; ← 71         else {             p->activated = 1; ← 72         }     }     p->timestamp = now;     __activate_task(p, rq); ← 73 }

　まず、これから起床するプロセスが属するRUNキューを選択し、ロックします（60）。プロセスはいずれかのRUNキュー（つまりCPU）に結び付けられており、前回動作した同じCPU上で実行されるようにします。

　次に起床するプロセスをRUNキューに登録します。プリエンプションを発生させない指定の場合は、__activate_task関数で単にRUNキューにつなぐだけです（63）。通常の場合は、activate_task関数を呼び出し（64）、実行優先度の再計算を行い（70）、RUNキューにつなぎます（73）。長く待機状態であったプロセスのほうが、より高い実行優先度を得られます※。現在実行権を握っているカレントプロセスより実行優先度が高くなるようだと（65）、プロセススケジューラに対し、再スケジューリング要求（プリエンプト要求）を出します（66）。ほかのCPUのプロセススケジューラに対して要求する場合は、プロセッサ間割り込みを利用します。

　プロセスをRUNキューにつなぎ終わったら、プロセスを実行可能状態に遷移させます（67）。また、これらの処理の中で、task_struct構造体のactivatedメンバーに値を設定しています。activatedメンバーには表3のような意味があります。activatedメンバーの値はプロセススケジューラ（schedule関数）が、スケジューリングする際の参考値にし、この値が大きいほど、優先的にスケジューリングしようとします。

表3 activatedメンバーの値とその意味 値 意味 -1 TASK_UNINTERRUPTIBLE状態からの起床(62) 1 TASK_INTERRUPTIBLE状態からの起床。プロセスが起床要求を出した(72) 2 TASK_INTERRUPTIBLE状態からの起床。割り込み処理が起床要求を出した(71)

　Linuxカーネル内のコードでは、プロセスを待機状態に遷移させるとき、sleep_on関数やsleep_on_interruptible関数を利用せず、その関数と同等のこと（WAITキュー操作とプロセススケジューラの呼び出し）を直接行っている個所があちこちにあります。これはなぜでしょうか？　実は微妙なタイミングが関係しています。先ほども述べたように、待機状態への遷移処理は、通常以下の手順を踏みます。

1 目的の事象が成立しているか調べる 2 成立していなければ、sleep_on関数を呼び出す 2-1 プロセスをWAITキューに登録 2-2 プロセススケジューラ（schedule関数）を呼び出す 2-3 プロセスが起床したら、プロセスをWAITキューから外す

　しかし、1と2の間で事象が起きてしまう可能性のある場合、運が悪いとこのプロセスは永久に起床させられることがなくなります。そのため、標準のsleep_on関数を利用する代わりに、次のような順序で処理を行います。

1 プロセスをWAITキューに登録（prepare_to_wait関数、またはprepare_to_wait_exclusive関数） 2 目的の事象が成立しているか調べる 3 成立していなければ、プロセススケジューラ（schedule関数）を呼び出す 4 プロセスが起床したら、プロセスをWAITキューから外す（finish_wait関数）

　この手順によって、目的の事象が成立しているか調べた直後に事象が発生しても、そのプロセス自身はすでにWAITキューに登録されているため、その事象発生により、実行可能状態に戻されることになります。プロセススケジューラを呼び出したとき、自プロセス自身も実行対象の候補となります。

　事象の成立条件が単純なときは、wait_event/wait_event_interruptibleマクロ関数を利用しても、上記処理を簡単に記述できます。

　ところで、もう1つ実装上の疑問点を持たれた方もおられると思います。プロセスが待機状態になったとき、そのプロセス用のtask_struct構造体をWAITキューに直接登録しないのはなぜなのでしょうか？　実はこの構造には面白い特徴があり、プロセスを同時に複数のWAITキューに登録できます。複数の事象を同時に待ち合わせ、いずれかの事象が成立したら起床できます（図15）。この仕組みはselectシステムコールやpollシステムコールの実現に利用しています。

図15 複数の事象待ち（クリックで拡大します）

そのほかの待機/起床処理関数

　待機/起床を行う関数の一種として、completionという仕組みも用意しています（表4）。この仕組みを利用すると、事象の発生回数とプロセスの起床回数とを揃えることができます。プロセスの待機処理前に事象が発生してしまっても、期待どおりに動作する作りになっています。

表4 completion 関数名 概要 wait_for_completion ある条件の完了を待ち合わせる complete 条件を1つ完了 complete_all ある条件の完了を待ち合わせているプロセスすべてを起床させる

子プロセスのスケジューリング

　forkシステムコールによって子プロセスが生成されたときは、この子プロセスを実行状態としてスケジューリング対象に加えます（wake_up_forked_process関数）。子プロセスの実行優先度は親プロセスから引き継ぎ※、親プロセスと同じRUNキューの親プロセスの前に挿入し、プリエンプト要求を発生させます（set_need_resched関数）。これによって子プロセスは親プロセスより、少しだけ先に動作することになります。ほとんどの子プロセスはすぐにexecシステムコールを発行するため、この順序で動作させたほうが、プロセス空間のコピーオンライト処理※の発生を抑制できるというメリットがあるためです。

　また子プロセスを生成したとき、親プロセスは実行割り当て時間の半分を子プロセスに譲るようになっています。この仕組みによって、特定のプロセスから大量にプロセスが生成された場合でも、そのことによるほかプロセスへ与える影響を最小限に抑え、スケジューリングの公平性を保つことができます。

最後に

　プロセススケジューリングは、Linuxカーネルの動作を決定する最も基本的な機能であるため、少し詳しく説明させていただきました。それでも、すべては説明し切れておらず、疑問点が残った方もおられるかもしれません。しかし、プロセススケジューリングに関する重要な点はすべて押さえているつもりなので、その応用的なコードを見ても同様に理解できるものと考えます。何度も本連載を読み返しながら、Linuxカーネルのコードと格闘してください。

---

　本連載の連載予定はこちらで確認できます。

このページで出てきた専門用語

より高い実行優先度を得られます つまり、対話型プロセスなどは待機状態の時間が長いため、応答性が良くなる。 実行優先度は親プロセスから引き継ぎ 親子共に変動優先度は低めになるようにしている。子プロセスがどんどん生成されたとき、その親子プロセスばかりを実行対象として選択してしまわないようにするため。 コピーオンライト処理 詳しくは空間管理の回に解説予定。

最新号：UNIX USER 7月号の内容 第1特集 無線LANの構造と認証強化 第2特集 UNIX/LinuxからWindowsリソースを使うには？ ［特別企画］ ・新世代Very Secure FTPDを使いこなせ ・Fedora Core 2導入ガイド