スケジューラ

Rev.28を表示中。最新版はこちら。

作成中

RunQueue

実行可能(Running状態)なスレッドはRunQueueに入れられる。RunQueueはプロセッサセットと各プロセッサに存在する。RunQueueの構造を図1に示す。RunQueue内はPriorityが高いものをすぐに取り出せるようにPrioirty毎にわかれたリスト構造をしている。

図1 RunQueueの構造

周期処理

1secに8回sched_tick_thread()が動作する(*1)。sched_tick_thread()はカーネルスレッドとして実行されている。sched_tick_thread()は以下の処理を行う。

負荷平均などの値を計算 - compute_averages()
最高プライオリティのRunQueue内のスレッドのプライオリティを更新する - thread_update_scan()
最後にタイマ付きWaitQueueに自分を積んで、thread_block()

最後にカーネルスレッドがブロックすることで次のスレッドが選択され実行される。thread_block()の延長でthread_select()(新しいスレッドの選択),thread_invoke()(コンテキストスイッチ)される。

(*1)

タイマ値はsched_tick_interval(単位はns)。1秒に(1 << SCHED_TICK_SHIFT)回スケジューラが起動されるように初期化される。

スレッドの撰択

thread_select()でRunQueue内の最もプライオリティの高いスレッドを選択する。

thread_select()の概要

if (thread->state == TH_RUN &&
    thread->processor_set == pset &&
    (thread->bound_processor == PROCESSOR_NULL ||
     thread->bound_processor == processor)) {
     /* カレントスレッドがまだRunning状態 */

    if (thread->sched_pri >= BASEPRI_RTQUEUES &&
        first_timeslice(processor)) {
        /* カレントスレッドがリアルタイムスレッド */
        if (pset->runq.highq >= BASEPRI_RTQUEUES) {
            /* プロセッサセットのRunQueueにも
               リアルタイムスレッドがある */

            if (((thread_t)q->next)->realtime.deadline <
                processor->deadline) {
                /* そのリアルタイムスレッドのdeadlineが
                   カレントスレッドのdeadlineよりも短い */
                RunQueueからスレッド取り出し
            }
        }
        threadを返す
    }

    if ((!other_runnable ||
        (processor->runq.highq < thread->sched_pri
&&
         pset->runq.highq < thread->sched_pri))) {
             カレントスレッドが最も高プライオリティなので
             このまま継続
    }
}

/* カレントスレッドがRunning状態ではなくなっている場合 */

if (other_runnable)
    thread = choose_thread(pset, processor);
    プロセッサセット、プロセッサのRunQueueから
    プライオリティの最も高いものを取り出す。
else {
    実行可能なスレッドがないのでCPUをIdle状態に
}

プライオリティの更新

update_priority()でスレッドのプライオリティの更新を行う。
スレッドのCPU利用率に応じて、プライオリティの基本値(thread->priority)から減算した(優先度を下げる)値をthread->sched_priに書き込む。

CPUを使う程プライオリティが下がるので結果として同じプライオリティのスレッド同士は順番に実行されることになる。

Quantumの更新

各スレッドはQuantum値を持つ。Quantum値をCPUを使用できる時間でこの時間を使いきるとコンテキストスイッチが発生する。thread->current_quantumはタイマハンドラで減算されていくのではなく、あらかじめQuantum満了時刻に合わせてタイマを仕掛けている。
Quantumを使い切ると、タイマハンドラthread_quantum_expire()が呼ばれ優先度の更新、Quantum値の再設定を行う。
通常のスレッドのQuantumのデフォルト値は10ms

thread_quantum_expire()
{
        :
 myprocessor->quantum_end += thread->current_quantum;
  timer_call_enter1(&myprocessor->quantum_timer,            
                      thread, myprocessor->quantum_end);