スケジューラ

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

作成中

Runqueue

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

図1 RunQueueの構造

周期処理

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

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

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

スレッドの撰択

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状態に
}

[Quantumの更新]
thread->current_quantumはタイマハンドラで減算されていくのではなく、あらかじめQuantum満了時刻に合わせてタイマを仕掛けている。

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

Quantumを使い切ると、タイマハンドラthread_quantum_expire()
優先度の更新、Quantum値の再設定を行う

プライオリティの更新

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

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