プロセススケジューラの実装――プロセススケジューリング（その4）：UNIX USER 2004年6月号「Linuxカーネル2.6解読室」より転載（2/2 ページ）

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

プロセススケジューラのアルゴリズム

　プロセススケジューリングに関係する関数はたくさんあるのですが、ここではプロセススケジューラの本体であるschedule関数を取り上げ、簡単に中身を見て行くことにします（リスト4）。schedule関数の中で利用されているprev変数は現在実行中のプロセスを指します。next変数は、次に実行権を与える候補のプロセスを指します。変数rqは、このプロセススケジューラが管理しているRUNキューを指します。

　いまままで実行権を持っていたプロセスprevが待機状態になった場合、プロセススケジューラは、まずそのプロセスprevをRUNキューから外す処理を行います（35）。ただし、シグナル受信が可能な待機状態（TASK_INTERRUPTIBLE）で、シグナルを受信してしまっていた場合は、実行可能状態（TASK_RUNNING）に戻します（34）。実行可能状態に戻ったプロセスprevは、RUNキューに登録したままにしておきます。

　続いてプロセススケジューラは、activeキューを検索し次に実行権を与えるべきプロセスとして最も実行優先度の高いプロセスを選び出します（39）。つまり、activeキューにおいてプロセスが登録されているスロットを見付け、先頭のものからプロセスを選びます。もしactiveキューが空なら、activeキューとexpiredキューと交換した後（38）、交換後のactiveキューからプロセスを撰択します。

　もし、このプロセススケジューラが担当しているRUNキュー上に、実行可能なプロセスがいない場合（activeキューにもexpiredキューにもプロセスが存在しない場合）は、ほかのCPU用のプロセススケジューラが管理しているRUNキューからプロセスを奪ってきます（36）。ほかのRUNキュー上にも奪えるプロセスがなければ※、次に実行権を与えるプロセスとして、アイドルプロセスを選択します（37）。

　次に動作すべきプロセスnextが決定したらプロセスディスパッチャ（context_switch関数）を呼び出し、プロセスprevからプロセスnextにコンテキストを切り替えます（45）。

　これらのプロセススケジューリング処理の間に、新しいスケジューリング要求が発生してしまうこともあります。プロセススケジューリング処理の最中に、同じCPU上で別のプロセススケジューリング処理が動作すると、プロセススケジューリング関連のデータ構造に不整合が生じます。そのためプロセススケジューリング処理中は、再度プロセススケジューリング処理が動作しないように抑制する必要があります（31、46）。

　プロセススケジューリング処理の間に発生した新しいスケジューリング要求に対しては、一度プロセススケジューリング処理が完全に終了した時点で、再度プロセススケジューリング処理を最初からやり直すことにより対応しています（47）。

　プロセス実行優先度を決める、変動優先度部分の計算に利用される各種データも、プロセススケジューリング時に準備します。変動優先度は、プロセスの走行時間（32）と待機時間（44）をベースとして求めます。対話型と思われるプロセスに対しては、走行時間を短めに見積もることによって、優先度を上げ応答性を少し高めようとします（33）。

　もし次に動作するプロセスnextが、シグナル受信が可能な待機状態（TASK_INTERRUPTIBLE）から起床したばかりであれば（40）、実行優先度の再計算を行います（42）。計算時には、プロセスが実行可能状態になった要因も考慮します。プロセス起床処理（後述）で、シグナル受信可能な待機状態（TASK_INTERRUPTIBLE）から起床したとき※は、応答性確保のために一時的に高めの実行優先度を与えています。そのため、本来の優先度に戻す処理が必要となります（42）。

　ただし、ほかのプロセスによる起床ではなく、割り込み処理による起床であった場合には、その後も少しだけ高い実行優先度を維持できるように考慮しています（41）。割り込み処理から起床したプロセスは、対話型プロセスである可能性が高いためです。つまり、パイプ待ちより、ソケット待ちや端末待ちから起床したプロセスのほうが、より対話型指向であると見なされます。

---

　次回で、プロセススケジューラについての解説は最終回となる。最終回では、事象の待ち合わせについて解説していく。

リスト4 schedule(void)

schedule(void) {     need_resched:     preempt_disable(); ← 31     prev = current;     rq = this_rq();     release_kernel_lock(prev);     now = sched_clock();     if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG)) ← 32         run_time = now - prev->timestamp;     else         run_time = NS_MAX_SLEEP_AVG;     if (HIGH_CREDIT(prev)) ← 33         run_time /= (CURRENT_BONUS(prev) ? : 1);     spin_lock_irq(&rq->lock);     switch_count = &prev->nivcsw;     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {         switch_count = &prev->nvcsw;         if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&             unlikely(signal_pending(prev))))             prev->state = TASK_RUNNING; ← 34         else             deactivate_task(prev, rq); ← 35     }     if (unlikely(!rq->nr_running)) { ← 36         load_balance(rq, 1, cpu_to_node_mask(smp_processor_id()));         if (!rq->nr_running) {             next = rq->idle; ← 37             rq->expired_timestamp = 0;             goto switch_tasks;         }     }     array = rq->active;     if (unlikely(!array->nr_active)) {         rq->active = rq->expired; ← 38         rq->expired = array;         array = rq->active;         rq->expired_timestamp = 0;         rq->best_expired_prio = MAX_PRIO;     }     idx = sched_find_first_bit(array->bitmap); ← 39     queue = array->queue + idx;     next = list_entry(queue->next, task_t, run_list);     if (next->activated > 0) { ← 40         unsigned long long delta = now - next->timestamp;         if (next->activated == 1) ← 41             delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;         array = next->array;         dequeue_task(next, array);         recalc_task_prio(next, next->timestamp + delta); ← 42         enqueue_task(next, array);     }     next->activated = 0;     switch_tasks:     prefetch(next);     clear_tsk_need_resched(prev); ← 43     RCU_qsctr(task_cpu(prev))++;     prev->sleep_avg -= run_time; ← 44     if ((long)prev->sleep_avg <= 0) {         prev->sleep_avg = 0;         if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))             prev->interactive_credit--;     }     prev->timestamp = now;     if (likely(prev != next)) {         next->timestamp = now;         rq->nr_switches++;         rq->curr = next;         ++*switch_count;         prepare_arch_switch(rq, next);         prev = context_switch(rq, prev, next); ← 45         barrier();         finish_task_switch(prev);     } else         spin_unlock_irq(&rq->lock);     reacquire_kernel_lock(current);     preempt_enable_no_resched(); ← 46     if (test_thread_flag(TIF_NEED_RESCHED)) ← 47     goto need_resched; }

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

スタックポインタの値を基に計算 個人的には、CPU固有空間を用意して、その上にCPU固有のデータを置けば美しいと思う。 ほかのRUNキュー上に奪えるプロセスがなければ CPUに結び付けられているプロセスや、単周期で待機と実行を繰り返しているプロセスは移動させない。後者はキャッシュメモリなどの利用効率を考慮したもの。 シグナル受信可能な待機状態から起床したとき ディスクI/Oではなく、ソケットや端末やパイプから起床するプロセスは、対話型である可能性が高いとの経験に基づく。

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