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

1.スケジュール処理

schedule()

    rq = this_rq(); - 自CPUのRunQueueを取得
    :
    :
    if (prev->state && !(preempt_count() &
PREEMPT_ACTIVE) {
        /* prevがTASK_RUNNING以外の状態で
         * 切り替えがプリエンプションでなく
         * 通常の切り替えだった場合 (*1) */

        if (prevがTASK_INTERRUPTIBLE状態 && シグナルがペンディングされている)
            TASK_RUNNING状態に戻す
        else
            deactivate_task(prev, rq) - RunQueueから取り外す
    }

    if (!rq->nr_running) {
        /* RunQueueにプロセスがない */

        idle_balance(cpu, rq) - 他のCPUのRunQueueからプロセスを持って来る
        if (rq->nr_running) {
            /* まだRunQueueにプロセスがない */
            wake_sleeping_dependent(cpu, rq) - SMT用処理
                同じ物理プロセッサ内の他の論理プロセッサ(Sibling)で
                RunQueueにプロセスがあるのにIdle状態になっている
                ものがあればWakeupする。
                dependent_sleeper()によりRunQueueにプロセスがあっても
                Idleになっている可能性があるため。

            if (!rq->nr_running)
                goto switch_tasks
        }
    } else {
        if (dependent_sleeper()) { - SMT用処理
            /* Idle状態にする */
            next = rq->idle;
            goto switch_tasks;
        }

    if (unlikely(!array->nr_active)) {
        /* RunQueueのActiveリストにプロセスがない場合 */

        全RUNNINGプロセスがCPU時間を使い切った事になるので
        rq->active <-> rq->expireを入れ換える
        (次のQuantamが開始になる)
    }

    /* 次の実行プロセスを選択
     * Activeリストから動的優先度の最も小さいプロセスを取得 */
    idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, task_t, run_list);

    if (!rt_task(next) && next->activated > 0) {
        /* 選択したプロセスが非リアルタイムプロセスで
           Wakeup後、初回実行の時 (*2) */

        recalc_task_prio() - 動的優先順位再計算
            sleepしていた時間に応じてsleep_avgを更新し
            effective_prio(p)で優先順位を計算する

        RunQueue内の優先度に対応するリストにつなぎ直す
    }

switch_tasks:
    :
    prev->sleep_avgを使用したCPU時間分だけ減算
    (この影響で動的優先度は下がっていく)

    if (選択したプロセスが以前と異なる) {
        prepare_task_switch(rq, next)
        context_switch(rq, prev, next) - プロセス切替え

            MMの切替え
            if (next->mmがない) { - Kernel Process
                アドレス空間を持たないので切替え不要

                next->active_mm = prev->active_mm;
                <-- 前のプロセスからActiveマップを引き継ぐ
                enter_lazy_tlb(prev->active_mm, next)
            } else {
                switch_mm(prev->active_mm,next->mm,next)
                    :
                    load_cr3(next->mm->pgd) - PageTable切替え
            }
            :
            switch_to(prev, next, prev) - レジスタ、スタックの切替え
        barrier()
        finish_task_switch(this_rq(), prev);
    }

Hyper Threadへの対応

cpu_sibling_map[]
     +-----------+
CPU0 |  ...0011B | ビットマップ右側がCPU0に対応とする
     +-----------+
CPU1 |  ...0011B |
     +-----------+
CPU2 |  ...1100B |
     +-----------+
CPU3 |  ...1100B |
     +-----------+
           :

2. タイマ処理

scheduler_tick()
    if (rt_task(p)) {
        /* リアルタイムプロセスの処理 */
    }
    if (p->time_slice減算し0になった) {
        /* プロセスがCPU時間を使いきった (*1) */
        rq->activeから外す
        set_tsk_need_resched(p) - TIF_NEED_RESCHEDをセットしてプロセスの切替え要求
        (Linux2.4のp->need_reschedule = 1に相当)
        p->prio設定 (effective_prio()参照)
        p->time_slice設定 (CPU時間の割り当て)
            設定値
            nice値          -20   ... 0     ...  19
            p->static_prio  100   ... 120   ... 139
            p->time_slice   200ms ... 100ms ... 5ms
        if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
            プロセスがinteractiveで無ければ
            (interactiveであってもEXPIRD_STARVINGなら)
            rq->expireに追加
        } else {
            プロセスがinteractiveなら
            rq->activeに戻す
        }
    } else {
        /* time_sliceが0になっていなくても、ある程度使ったら
           一旦CPUを手放す処理。(Expireさせるわけではない) */

        if (1. TASK_INTERACTIVE(p) && (*2)
            2. 使用したCPU時間がちょうどTIMESLICE_GRANULARITY()の倍数
&&
            3. 残りのCPU時間がTIMESLICE_GRANULARITY()以上残っている) {
                set_tsk_need_resched(p) - スケジュール要のフラグセット
                p->prio = effective_prio(p) - 動的優先度再計算
                rq->activeの対応するPrioのリストにつなぎなおす
        }
    }
    rebalance_tick()

3. 'Interactive'なプロセスとは

             sleepが多い                    少ない
動的優先度の変動幅      -5 <------ 0 ------> +5
TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
TASK_INTERACTIVE(  0): [1,1,1,1,0,0,0,0,0,0,0]
TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]

()の中の値はnice値。
'1'はInteractiveであることを示す。