スケジューラ

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

作成中

Runqueue

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

図1 RunQueueの構造

周期処理

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

        sched_cswtime = time_cswitch();

        sched_tick_deadline = mach_absolute_time();

        sched_tick_continue();

負荷平均などの値を計算 - compute_averages()
thread_update_scan()
最後にタイマ付きWaitQueueに自分を積んで、thread_block()する。
カーネルスレッドがブロックしたことで次のスレッドが選択され実行される。

thread_block() (continuation=sched_tick_continue())
thread_block_reason()
:
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値の再設定を行う

プライオリティの更新