1.6　プロセススケジューラの実装

　Linuxカーネル2.6のプロセススケジューラには、スケーラビリティがあります。Linuxカーネル2.4以前のプロセススケジューラは非常に単純な構造で、マルチプロセッサシステムであっても、単一のキューに実行可能プロセスをすべてつなぎ、再スケジューリングの度にキューに登録されているすべてのプロセスを検索して、実行権を与えるプロセスを選び出していました。

　実行可能プロセス数があまり多くならないシステムでは、これでも十分期待どおりの結果が出ていましたが、大きなシステムへのLinuxカーネル適用を考えたとき、従来の構造ではオーバーヘッドが大きくなります。そこで、Linuxカーネル2.6ではプロセス数によらず、プロセススケジューラの処理量が一定となる構造のプロセススケジューラが導入されました。

1.6.1　実行優先度ごとのRUNキュー

　実行可能なプロセスはRUNキューに登録されます。Linuxカーネル2.6のRUNキューは実行優先度ごとにスロットを用意しています。次に実行するプロセスは、プロセスが存在する最も高い実行優先度のスロットから、先頭に登録されているプロセスを選択するだけです。これによって、再スケジューリング時、最も実行優先度の高いプロセスを容易に見つけることができます。実行可能なプロセスがいくつ存在していても、検索量は常に一定であるため、検索指定（オーダー）が1のスケジューラ、つまり「O(1)スケジューラ」と呼ばれています（図1-8）。

図1-8　O(1)スケジューラの構造

1.6.2　2種類のRUNキュー

　Linuxカーネル2.6は、2種類のRUNキューを持ちます。それぞれ、activeキュー、expiredキューと呼ばれています。activeキューには、実行可能で、実行割り当て時間を持っているプロセスを登録します。expiredキューには、実行可能状態だが、実行割り当て時間を使い果たしてしまったプロセスを登録します。expiredキューの構造はactiveキューの構造とまったく同じで、プロセスは実行優先度ごとに分類して登録されています。

　実行を続けているとactiveキュー上のプロセスは、実行割り当て時間を使い果たしてexpiredキューに移動するか、もしくは何らかの事象待ちのために待機状態に遷移します。いずれactiveキュー上のすべてのプロセスがいなくなります。すると、プロセススケジューラはactiveキューをexpiredキューと交換して処理を継続します。それまでのexpiredキューがactiveキューとなり、プロセススケジューラは、そのキューに登録されている中で最も実行優先度の高いプロセスに実行権を与えます。

　このRUNキューの構造によって、一度実行割り当て時間を与えられactiveキューに登録されたプロセスは、いくら低い優先度であっても、必ず実行権が回ってくることが保証されます。

1.6.3　CPUごとのRUNキュー

　マルチプロセッサシステムでは、RUNキュー（activeキューとexpiredキューの組み）をCPUごとに用意します（図1-9）。CPUごとに用意したプロセススケジューラは、そのCPU用のRUNキュー上のプロセスに対して働きます。この構造により、特定のプロセスは、毎回特定のCPU上で実行されることとなり、キャッシュメモリやTLBが有効利用されます。

図1-9　CPUごとのRUNキュー間の負荷バランス

　ただし、RUNキュー間で負荷状態に偏りが出たときは、RUNキュー間で実行待ちプロセスの移動を行いバランスを取ります（load_balance関数）。また、プロセスの起床時（後述try_to_wake_up関数）にもアイドル状態のプロセッサにそのプロセスを割り付けることにより、負荷バランスを保つようになっています。

1.6.4　アイドルプロセス

　実行可能なプロセスが1つも存在しないとき、Linuxカーネルは実行権を与えるべき対象がありません。このようなときには、プロセススケジューラ自体がアイドル状態となるOSもありますが、Linuxカーネルの実装では何も実行しないアイドルプロセスを用意し、このプロセスに実行権を与えます。アイドルプロセスは何もせず、実行可能なプロセスが現れ、プリエンプトされるのを待ち続けます。

　このアイドルプロセスを、各CPUに1つ用意しています。アイドルプロセスはRUNキューには登録されておらず、RUNキュー上に実行可能プロセスが1つも存在しなくなったときにのみ、プロセススケジューラが実行対象として選択します。

1.6.5　カレントプロセス

　まさにCPU上で実行中のプロセスのことを、カレントプロセスと呼ぶこともあります。カレントプロセスはCPUの数だけ存在します。Linuxカーネルの実装では、カレントプロセスもRUNキューに登録されたままになっています。データ構造上での実行待ち状態のプロセスとの違いは、currentというポインタで指されていることです（RUNキューのcurrメンバーによっても指されています）。　Linuxカーネルコード中には、カレントプロセスを指すcurrentというポインタ変数が頻繁に登場します。このcurrentという変数はおのおののCPUで異なる値となるため、Intel x86用Linuxカーネルの実装では、スタックポインタの値を基に計算して求めるようになっています。

図1-10　スタックポインタとカレントプロセス

　Linuxカーネル2.4では、カーネルスタックはtask_struct構造体中に確保されていたのですが、Linuxカーネル2.6ではtask_struct構造体中の一部のメンバーとともに、thread_info構造体に分割されました。そのため、スタックポインタ（ESP）の下位ビットをマスクすることによって、このプロセス用のthread_info構造体が求められ、さらにthread_info構造体からtask_struct構造体を求めます（図1-10）。

1.6.6　プロセッサバインド機能

　プロセスを明示的に特定のCPU用のRUNキューにくくり付けることが可能です。これにはsched_setaffinityシステムコールを使います。この情報は、task_struct構造体中に保存され、RUNキュー間での負荷バランス調整を行うときに考慮されます。

　O(1)スケジューラは、プロセスのCPU間移動を抑制する構造になっていますが、プロセッサバインド機能によってプロセス移動を明示的に禁止できます。システム構築者が、前もって負荷バランスを見積もり、プロセスを割り付けるCPUを決定したい場合に使えます。

　また、カーネルスレッドの中には特定のCPU用のデータ構造操作を目的とするものがあり、これらのスレッドもプロセッサバインド機能を利用して、必ず目的のCPU上で動作するようにしています。

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

　プロセススケジューリングに関係する関数はたくさんあるのですが、ここではプロセススケジューラの本体であるschedule関数を取り上げ、簡単に中身を見て行くことにします（リスト1-4）。

リスト1-4　schedule()関数

 asmlinkage void __sched schedule(void)
 {
         long *switch_count;
         task_t *prev, *next;
         runqueue_t *rq;
         prio_array_t *array;
         struct list_head *queue;
         unsigned long long now;
         unsigned long run_time;
         int cpu, idx, new_prio;
 
         profile_hit(SCHED_PROFILING, __builtin_return_address(0));
 
 need_resched:
         preempt_disable(); ――<31>
         prev = current;
 release_kernel_lock(prev);
 
 need_resched_nonpreemptible:
         rq = this_rq();
 
         schedstat_inc(rq, sched_cnt);
         now = sched_clock();
         if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) { ――<32>
                 run_time = now - prev->timestamp;
                 if (unlikely((long long)(now - prev->timestamp) < 0))
                         run_time = 0;
         } else
         run_time = NS_MAX_SLEEP_AVG;
 
         run_time /= (CURRENT_BONUS(prev) ? : 1); ――<33>
 
         spin_lock_irq(&rq->lock);
 
         if (unlikely(prev->flags & PF_DEAD))
                 prev->state = EXIT_DEAD;
 
         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 {
                         if (prev->state == TASK_UNINTERRUPTIBLE)
                                 rq->nr_uninterruptible++;
                         deactivate_task(prev, rq); ――<35>
                 }
         }
 
         cpu = smp_processor_id();
         if (unlikely(!rq->nr_running)) { ――<36>
 go_idle:
                 idle_balance(cpu, rq);
                 if (!rq->nr_running) {
                         next = rq->idle; ――<37>
                         rq->expired_timestamp = 0;
                         wake_sleeping_dependent(cpu, rq);
                         if (!rq->nr_running)
                                 goto switch_tasks;
                 }
         } else {
                 if (dependent_sleeper(cpu, rq)) {
                         next = rq->idle;
                         goto switch_tasks;
                 }
                 if (unlikely(!rq->nr_running))
                         goto go_idle;
         }
 
         array = rq->active;
         if (unlikely(!array->nr_active)) {
                 schedstat_inc(rq, sched_switch);
                 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 (!rt_task(next) && next->activated > 0) { ――<40>
                 unsigned long long delta = now - next->timestamp;
                 if (unlikely((long long)(now - next->timestamp) < 0))
                         delta = 0;
 
         if (next->activated == 1) ――<41>
                 delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
 
         array = next->array;
         new_prio = recalc_task_prio(next, next->timestamp + delta); ――<42>
         if (unlikely(next->prio != new_prio)) {
                 dequeue_task(next, array);
                 next->prio = new_prio;
                 enqueue_task(next, array);
         } else
                 requeue_task(next, array);
         }
         next->activated = 0;
 switch_tasks:
         if (next == rq->idle)
                 schedstat_inc(rq, sched_goidle);
         prefetch(next);
         prefetch_stack(next);
         clear_tsk_need_resched(prev); ――<43>
         rcu_qsctr_inc(task_cpu(prev));
 
         update_cpu_clock(prev, rq, now);
 
         prev->sleep_avg -= run_time; ――<44>
         if ((long)prev->sleep_avg <= 0)
                 prev->sleep_avg = 0;
         prev->timestamp = prev->last_ran = now;
 
         sched_info_switch(prev, next);
         if (likely(prev != next)) {
                 next->timestamp = now;
                 rq->nr_switches++;
                 rq->curr = next;
                 ++*switch_count;
 
                 prepare_task_switch(rq, next);
                 prev = context_switch(rq, prev, next); ――<45>
                 barrier();
                 finish_task_switch(this_rq(), prev);
         } else
                 spin_unlock_irq(&rq->lock);
 
         prev = current;
         if (unlikely(reacquire_kernel_lock(prev) < 0))
                 goto need_resched_nonpreemptible;
         preempt_enable_no_resched(); ――<46>
         if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) ――<47>
                 goto need_resched;
 }

　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>）*1。ほかのRUNキュー上にも奪えるプロセスがなければ、次に実行権を与えるプロセスとして、アイドルプロセスを選択します（<37>）。

　次に動作すべきプロセスnextが決定したらプロセスディスパッチャ（context_switch関数）を呼び出し、プロセスprevからプロセスnextにコンテキストを切り替えます（<45>）。これらのプロセススケジューリング処理の間に、新しいスケジューリング要求が発生してしまうこともあります。プロセススケジューリング処理の最中に、同じCPU上で別のプロセススケジューリング処理が動作すると、プロセススケジューリング関連のデータ構造に不整合が生じます。そのためプロセススケジューリング処理中は、再度プロセススケジューリング処理が動作しないように抑制する必要があります（<31>、<46>）。プロセススケジューリング処理の間に発生した新しいスケジューリング要求に対しては、一度プロセススケジューリング処理が完全に終了した時点で、再度プロセススケジューリング処理を最初からやり直すことによって対応しています（<47>）。

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

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

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

　1.7.2　起床処理の表1-3でも説明していますので、参照してください。

Up: 第1章　プロセススケジューリング

Prev: 1.5　プロセススケジューラ

Next: 1.7　事象の待ち合わせ

*1CPUに結び付けられているプロセスや、短周期で待機と実行を繰り返しているプロセスは移動させません。後者は、キャッシュメモリーなどの利用効率を考慮したものです。

Linux Kernel Documents
Fork
linux-2.6
linux-2.4.36

目次

まえがき

Part 1　カーネルプリミティブ

Wikiガイド