レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ プロセススケジューリング ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

今回はプロセススケジューリングについて見ていく。

概要

Linuxでは複数のプロセス間を非常に短いインターバルで切り替えることで、複数のプロセスを同時に実行しているように見せる(マルチプロセス)。いつどのプロセスに切り替えるのか、プロセススケジューリングと呼ばれる処理を見ていく。

参考: https://www.adamh.cz/blog/2016/07/context-switch-on-the-arm-cortex-m0/

方針

プロセススケジューリングは以下のような条件を満たす必要がある。

スケジューリングはタイムシェアリングを基礎としており、CPU時間をスライスという概念に分割し、それぞれを実行可能プロセスに割り当てることで同時多重に実行する。当然ながら瞬間的には単一のプロセッサでは単一のプロセスしか実行できない。現在動作中のプロセスがタイムスライス(クォンタムとも呼ばれる)を使い切った時はプロセス切り替えを行う。

スケジュールは優先度を用いて行い、プロセス毎に保持している値を用いてどのCPUで実行するのが効率的かなどをスケジューラに通知する。優先度は定期的に動的に変更され長時間動作しているプロセスの優先度は減少し、短時間しか動作していないプロセスの優先度は増加していく。

プロセスは大まかに2種類に分類される。

  • I/Oバウンド
  • CPUバウンド

これはあるリソースに対して頻繁にアクセスを行うことを意味する。

別の分類方法では以下の3種類に分類される。

種類 説明
対話型プロセス ユーザインタラクティブなプロセスを意味し、マウスやキーボード操作を行うプロセスのこと。入力への応答は50~150ミリ秒である必要がある。主な対話型プロセスの例としてシェル、テキストエディタGUIアプリケーションなどが挙げられる。
バッチプロセス ユーザ処理がなくバックグラウンドなどで処理されることの多い、コンパイラ、DBの検索エンジン、科学計算などを例として挙げられる。優先度を下げられることをが多い。
リアルタイムプロセス ビデオやサウンド関係、ロボット制御などが挙げられ、短い応答時間と高いスループットが要求される。

Linuxのスケジューリングアルゴリズムではリアルタイムプロセスは認識できるが、(2.6.11時点では)対話型プロセスやバッチプロセスを判断するのは容易ではない(現在のCFSスケジューラでは容易に判断が可能)。

プロセスプリエンプション

プロセスはプリエンプト可能で、あるタスクの状態がTASK_RUNNINIGに遷移する際にカレントプロセスと比較し、その優先度が高ければカレントプロセスに割り込んでスケジューリングを行い、他のプロセスに実行を移す。プリエンプトはタイムスライスを消費し切ったタイミングでも発生し、プロセスの状態にTIF_NEED_RESCHEDを設定することで次のタイマ割り込みの際に再度スケジューリングが発生する。

実行権が別のプロセスに遷移した際も、そのプロセスは待ち状態になるわけではなくTASK_RUNNINGのままCPUを使用しないような状態となる。

タイムスライス

タイムスライスはプロセスに割り当てる実行時間のことで、プロセス切り替えを行うインターバルにもなるため、短過ぎる時間を設定するとプロセス切り替えを頻繁に発生しシステムのパフォーマンスに多大な影響を与える。長過ぎた場合にもシステムに悪影響を及ぼす(インタラクティブであるはずのプロセスの反応速度が遅くなるなど)。

スケジューリングアルゴリズム

初期バージョンのスケジューリングアルゴリズムはシンプルでスケジューリング処理の度に全プロセスの優先度を再計算し最適なプロセスを実行対象として選択するものだった。しかしプロセス数の増加に比例し当該処理のコストは増加するため、多数のプロセスが動作するようなハイエンドシステムではコストがかかり過ぎるモノだった。

Linux 2.6からは実行対象を選択する処理はプロセス数に依存せず一定の時間で完了する。加えてプロセッサ毎に実行可能なプロセスのキューを保持しているためプロセッサが複数搭載されている場合にも対応している。I/OバウンドまたはCPUバウンドであるかも判断が可能となっている。

Linuxはswapperプロセス(PIDが0でスリープするだけのプロセス)を保持しており、スケジューラは必ず実行可能なプロセスを選択可能であることが保証されている。マルチプロセッサ環境では各CPUがそれぞれにswapperプロセスを保持する。

スケジューリングの種類は以下のように定義されている。

// include/linux/sched.h
/*
 * Scheduling policies
 */
#define SCHED_NORMAL       0
#define SCHED_FIFO     1
#define SCHED_RR       2
種類 説明
SCHED_NORMAL 従来のタイムシェアリングプロセス。
SCHED_FIFO 先入れ先出しのリアムタイムプロセス。スケジューラがプロセスに対してCPUを割り当てても実行可能プロセスキュー内の位置を変更せず、そのリアルタイムプロセスの優先度よりも高い優先度を持つプロセスが存在しない限りCPUを使用し続ける。
SCHED_RR ラウンドロビン型のリアルタイムプロセス。スケジューラがプロセスにCPUを割り当てると、そのディスクリプタをキューの末尾に移動する。スケジューラは同じ優先度を持つ全てのSCHED_RRプロセスに平等にCPU割り当てる。

SCHED_NORMAL(従来のタイムシェアリングプロセス)

静的優先度

このアルゴリズムではプロセスは全て静的優先度を保持しており、この優先度を用いて相対的な位置付けを行う。静的優先度の値はnice値に依存しており、nice値が最も高い優先度である-20の場合には100、最も低い優先度である+19の場合には139となり、静的優先度の範囲は100 ~ 139となる。

新たに生成されるプロセスは親プロセスから優先度を引き継ぎ、ユーザプロセスであればnice()setpriority()システムコールで値を変更することが可能である。

基礎タイムスライス

基礎タイムスライスとはタイムスライスを使用した後に再度割り当てるタイムスライス時間のことを意味する。

基礎タイムスライスは優先度に依存しており優先度が高い(値が低い)場合より長いタイムスライスが割り当てられる。

動的優先度及び平均休止時間

静的優先度の他に動的優先度を持ち、動的優先度は100(最も高い優先度)~139(最も低い優先度)の範囲の値を取る。この動的優先度はスケジューラが次に実行するプロセスを選択する際に使用する。

動的優先度は静的優先度に加えて、ボーナス値という値を考慮し算出する。ボーナス値はプロセスの平均休止時間を考慮し決定され、0~10の値を取る。

平均休止時間はプロセス起動からの休止した時間(ナノ秒)の平均だが、単純に休止した時間から算出されるわけではなくTASK_INTERRUPTIBLETASK_UNINTERRUPTIBLEで異なった算出方法を用いる。平均休止時間は1秒より大きくなることはない。平均休止時間はI/OバウンドかCPUバウンドかの判断にも用いられる。

アクティブプロセス及びインアクティブプロセス

優先度の高いプロセスほど大きなタイムスライスを与えられるが、優先度の低いプロセスにもタイムスライスは付与されており、どのプロセスにも必ず実行権をまわってくる。

実行可能プロセスにはタイムスライスを使い切っていないプロセスと使い切ったプロセスで以下の2種類に分類される。

名前 説明
アクティブプロセス(Active Process) 付与されたタイムスライスを使用しきっていない実行可能プロセス。
インアクティブプロセス(Inactive Process) 付与されたタイムスライスを使用し切っており、全ての実行可能プロセスがタイムスライスを使用し切るまで実行を禁止される実行可能プロセス。

アクティブプロセスはactiveキュー(リスト)に繋がれ管理され、インアクティブプロセスはexpiredキューで管理される。タイムスライスを全て消費したプロセスはactiveキューからexpiredキューに移される。

SCHED_FIFO(リアルタイムプロセス), SCHED_RR(ラウンドロビン型リアルタイムプロセス)

リアムタイムプロセスはプロセス毎にリアルタイム優先度を保持しており、1(最高優先)~99(最低優先)を値を取る。リアルタイムプロセスの中で最も高い優先度を設定されたプロセスを実行すると、それ以外のリアルタイムプロセスは実行を抑制される。実行中のリアルタイムプロセスは常にアクティブプロセスとして処理される。

以下のいずれかの事象が起こった際にリアルタイムプロセスから他のプロセスに実行が移る。

  • より高いリアルタイム優先度を保持したリアルタイムプロセスが実行可能状態に遷移した(実行がそのプロセスに移る)
  • プロセスが自身の実行を中断し、TASK_INTERRUPTIBLEまたはTASK_UNINTERRUPTIBLE状態に遷移した。
  • プロセスが中断されTASK_STOPPEDまたはTASK_TRACED状態に遷移した。
  • プロセスが強制終了され、EXIT_ZOMBIEまたはEXIT_DEAD状態に遷移した。
  • プロセスがsched_yield()システムコールを発行し、自発的にプロセッサを明け渡した。
  • リアルタイムプロセスがラウンドロビン型でタイムスライスを使い切った。`

nice()システムコールまたはsetpriority()システムコールラウンドロビン型のリアルタイムプロセスに適応すると静的優先度が変更されるが、リアルタイム優先度が変更されることはない。

スケジューラが使用するデータ構造

runqueue 構造体

システムに搭載されている全てのCPUは個別のランキュー(アクティブプロセスやインアクティブプロセスを保持する構造体)を持ち、CPU毎の変数であるrunqueues変数に格納される。

// kernel/sched.c
static DEFINE_PER_CPU(struct runqueue, runqueues);

#define cpu_rq(cpu)        (&per_cpu(runqueues, (cpu))) // 指定したCPUに対応するランキューを取得
#define this_rq()      (&__get_cpu_var(runqueues)) // ローカルCPUのランキューを取得
#define task_rq(p)     cpu_rq(task_cpu(p)) // 指定したタスクに対応するランキューを取得

runqueues変数には上記あるようなマクロが用意されている。

runqueue構造体は以下のように定義されている。

struct runqueue {
    spinlock_t lock; // ロック用変数

    unsigned long nr_running; // 実行可能なプロセス数
#ifdef CONFIG_SMP
    unsigned long cpu_load; // 平均プロセス数から算出されるCPU負荷
#endif
    unsigned long long nr_switches; // CPUが実行したコンテキストスイッチの回数

    // このCPU上で現在"TASK_UNINTERRUPTIBLE"で休止しているプロセスの総数
    unsigned long nr_uninterruptible;

    unsigned long expired_timestamp; // タイムスライスを使い切ったプロセスを最初に時間切れプロセス専用キューに追加した時刻
    unsigned long long timestamp_last_tick; // 最後に発生したtick割り込みの発生時刻
    // カレントプロセスへのポインタ及びswapperプロセスへのポインタ
    task_t *curr, *idle; 
    struct mm_struct *prev_mm; // 切り替えられるプロセスのメモリディスクリプタのアドレス
    // activeキューへのポインタ、expiredキューへのポインタ及びそれぞれのプロセスキュー(リスト)
    prio_array_t *active, *expired, arrays[2]; 
    int best_expired_prio; // 時間切れプロセスの中で最も高い優先度の値
    atomic_t nr_iowait; // ディスクI/O待ちのプロセスの総数

#ifdef CONFIG_SMP
    struct sched_domain *sd; // ローカルCPUのスケジューリングドメインへのポインタ(後述)

    /* For active balancing */
    int active_balance; // CPUのキュー間でプロセスの移動を行う時に用いたられるフラグ
    int push_cpu; // 未使用

    task_t *migration_thread; // マイグレーション用カーネルスレッドのプロセスディスクリプタへのポインタ
    struct list_head migration_queue; // 実行可能プロセス専用キューから削除予定のプロセスリスト
#endif
};

システム上の実行可能プロセスは必ずそれぞれのCPUが保持している上記のランキューのいずれかに属しており、そのCPUのみが当該プロセスを実行することが可能となる。しかしロードバランシングなどで実行可能プロセスはCPUが持つランキュー間を移動(マイグレーション)することもある。

以下のようにactive及びexpiredarraysのどちらかを指す。

参考: https://www.oreilly.co.jp/books/9784873113135/

activeが指すリストが保持する全てのプロセスがタイムスライスを使い切った際にactive及びexpiredが指すリストを入れ替える。

prio_array_t構造体は以下のように定義されており、上記の図の用にqueueメンバで優先度別にプロセスのリストを管理しているのがわかる。

// include/linux/sched.h
typedef struct prio_array prio_array_t;

// kernel/sched.c
struct prio_array {
    unsigned int nr_active; // activeプロセスの総数
    // 優先度別のビットマップで、リストにプロセスが存在しているか否かを保持している。
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};

// include/linux/sched.h
#define MAX_USER_RT_PRIO   100
#define MAX_RT_PRIO        MAX_USER_RT_PRIO

#define MAX_PRIO       (MAX_RT_PRIO + 40)

thread_info 及び task_struct

プロセスディスクリプタに用いられる構造体であるtask_structのメンバでスケジューリングに関係するメンバは以下。

// include/linux/sched.h
struct task_struct {
    volatile long state;  /* -1 unrunnable, 0 runnable, >0 stopped */
    struct thread_info *thread_info;
    atomic_t usage;
    unsigned long flags;  /* per process flags, defined below */
    unsigned long ptrace;

    int lock_depth;        /* Lock depth */

    // 動的優先度及び静的優先度
    int prio, static_prio;
    struct list_head run_list; // このプロセスが属しているキューの前後の要素
    prio_array_t *array; // このプロセスが属している方(active or expired)のキューへのポインタ

    unsigned long sleep_avg; // 平均休止時間
    
    /*
    * timestamp: このプロセスをランキューに挿入またはこのプロセスを対象としたコンテキストスイッチが最後に行われた時刻
    * last_run: このプロセスが最後に実行された時刻
    */
    unsigned long long timestamp, last_ran;
    int activated; // 起床時に使用されるコード

    unsigned long policy; // スケジューリングの種類(SCHED_NORMAL, SCHED_FIFO, SCHED_RR)
    cpumask_t cpus_allowed; // このプロセスが使用可能なCPUのビットマスク
    
    /* 
    * time_slice: 残りのタイムスライス(tick数)
    * first_time_slice: タイムスライスを全く消費していない時は"1"
    */
    unsigned int time_slice, first_time_slice;
    
    :
    (省略)
    :

    unsigned long rt_priority; // リアルタイム優先度
    
    :
    (省略)
    :
};

// include/asm-i386/thread_info.h
struct thread_info {
    struct task_struct *task;      /* main task structure */
    struct exec_domain *exec_domain;   /* execution domain */
    unsigned long     flags;      /* 再スケジューリングが必要な場合には"TIF_NEED_RESCHED" */
    unsigned long     status;     /* thread-synchronous flags */
    __u32           cpu;        /* 対象のプロセスが所属しているキューを保持するCPU番号 */
    
    :
    (省略)
    :
};

sched_fork()

プロセスをforkする際に呼び出されるsched_fork()関数内では上記のメンバが一部使用されている。

// kernel/sched.c
/*
 * task_t *p: 新たに生成したプロセス
 */
void fastcall sched_fork(task_t *p)
{
    p->state = TASK_RUNNING; // 実行可能状態
    INIT_LIST_HEAD(&p->run_list); // リストの初期化
    p->array = NULL; // キューへのポインタの初期化
    spin_lock_init(&p->switch_lock);
#ifdef CONFIG_SCHEDSTATS
    memset(&p->sched_info, 0, sizeof(p->sched_info));
#endif
#ifdef CONFIG_PREEMPT
    p->thread_info->preempt_count = 1;
#endif
    local_irq_disable();
    /*
    * 親と子でタイムスライス(tick数)を分け合うことでシステム上のトータル的なタイムスライス量
    * は変わらず、より公平なスケジューリングを行うことが可能となる。
    */
    p->time_slice = (current->time_slice + 1) >> 1;
    p->first_time_slice = 1;
    current->time_slice >>= 1;
    
    p->timestamp = sched_clock(); // タイムスタンプの設定
    
    /* タイムスライス(tick数)が"1"しかなかった場合 */
    if (unlikely(!current->time_slice)) {
        current->time_slice = 1; // 1に戻す(これより前の処理で"0"になっているため)
        preempt_disable();
        scheduler_tick();
        local_irq_enable();
        preempt_enable();
    } else
        local_irq_enable();
}

スケジューラが使用する関数

scheduler_tick()

タイマ割り込みでtickに呼び出されるscheduler_tick()は以下のように定義されている。(親プロセスのタイムスライスが変更された際にも呼び出される)

void scheduler_tick(void)
{
    int cpu = smp_processor_id(); // ローカルCPUの取得
    runqueue_t *rq = this_rq(); // CPUに対応するランキューの取得
    task_t *p = current; // カレントプロセス

    rq->timestamp_last_tick = sched_clock(); // 現在時刻(ナノ秒)を設定

    if (p == rq->idle) { // swapperプロセスの場合
        if (wake_priority_sleeper(rq)) // 再スケジューリングのフラグを立てる
            goto out;
        rebalance_tick(cpu, rq, SCHED_IDLE); // CPU間のロードバランシング
        return;
    }

    /* プロセスのキューがexpired(タイムスライスの時間切れ)キューを指している = タイムスライスを使い切っている */
    if (p->array != rq->active) {
        set_tsk_need_resched(p); // 強制的に再スケジューリング
        goto out;
    }
    spin_lock(&rq->lock); // スピンロック
    
    
    /* リアルタイムプロセスの場合 */
    if (rt_task(p)) {
        /* ラウンドロビン型で且つタイムスライスを使い切った場合 */
        if ((p->policy == SCHED_RR) && !--p->time_slice) { // 
            p->time_slice = task_timeslice(p); // 再度タイムスライスを補充
            p->first_time_slice = 0; // タイムスライスを使用し切った
            set_tsk_need_resched(p); // 再スケジューリングのフラグを立てる

            /* activeキューの末尾に繋ぎ直す */
            requeue_task(p, rq->active);
        }
        goto out_unlock; // 終了処理へ
        /* ラウンドロビン型でないリアルタイムプロセスの場合タイムスライスの概念はない */
    }
    
    /* 通常プロセスの場合 */
    if (!--p->time_slice) { // タイムスライスの減算を行う、0になった場合には以下の処理に続く
        dequeue_task(p, rq->active); // activeキューから削除
        set_tsk_need_resched(p); // 再スケジューリングのフラグを立てる
        p->prio = effective_prio(p); // 動的優先度の更新
        p->time_slice = task_timeslice(p); // タイムスライスの再設定
        p->first_time_slice = 0; // タイムスライスを使用し切った

        /* expired_timestampが設定されていない = expiredキューが空の場合 */
        if (!rq->expired_timestamp)
            rq->expired_timestamp = jiffies; // 値を設定

        /* ユーザインタラクティブなプロセスでない若しくはタイムスライスを使用し切ったプロセスが長い時間待たされている場合 */
        if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
            enqueue_task(p, rq->expired); // 強制的にexpiredキューに移動
            /* expiredキュー内の最高優先度値を更新 */
            if (p->static_prio < rq->best_expired_prio)
                rq->best_expired_prio = p->static_prio;
        } else
            enqueue_task(p, rq->active); // activeキューへ
    } else {
        /* CPUの独占を回避するための処理 */
        if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
            p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
            (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
            (p->array == rq->active)) {

            requeue_task(p, rq->active); // activeキューへ
            set_tsk_need_resched(p); // 再スケジューリング用のフラグを設定
        }
    }
out_unlock:
    spin_unlock(&rq->lock); // スピンロックを解除
out:
    rebalance_tick(cpu, rq, NOT_IDLE); // CPU間でのロードバランシング
}

try_to_wake_up()

この関数は休止または中断しているプロセスを起床し、プロセスの状態をTASK_RUNNINGに設定した後、CPUのランキューにプロセスを挿入する。当該関数の定義は以下。

// kernel/sched.c
/*
 * task_t *p: 起床されるプロセスディスクリプタ
 * unsigned int state: プロセスの状態を指定するマスク
 * int sync: ローカルプリエンプトを禁止するフラグ
 */
static int try_to_wake_up(task_t * p, unsigned int state, int sync)
{
    int cpu, this_cpu, success = 0;
    unsigned long flags;
    long old_state;
    runqueue_t *rq;
#ifdef CONFIG_SMP
    unsigned long load, this_load;
    struct sched_domain *sd;
    int new_cpu;
#endif

    rq = task_rq_lock(p, &flags); // ランキューのロック
    schedstat_inc(rq, ttwu_cnt); // 統計情報更新
    old_state = p->state;
    if (!(old_state & state)) // 指定した状態でない場合
        goto out; // 終了処理へ

    if (p->array) // arrayが存在する -> このプロセスはランキュー上に存在する
        goto out_running; // 終了処理へ

    cpu = task_cpu(p); // 前回そのプロセスを実行していたCPUを取得
    this_cpu = smp_processor_id(); // ローカルCPUを取得

#ifdef CONFIG_SMP
    if (unlikely(task_running(rq, p))) // 既に実行中
        goto out_activate; // 起床処理を省略

    new_cpu = cpu;

    /* 当プロセスのローカルCPU使用が許可されていない */
    if (cpu == this_cpu || unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
        goto out_set_cpu; // 

    load = source_load(cpu); // 前回そのプロセスを実行していたCPU負荷の取得
    this_load = target_load(this_cpu); // ローカルCPU負荷を取得

    /* syncが設定されている場合にはカレントプロセスの動作不可分を減算する */
    if (sync)
        this_load -= SCHED_LOAD_SCALE;

    /* ローカルCPUよりも前回実行したCPUの負荷の方が小さい場合 */
    if (load < SCHED_LOAD_SCALE/2 && this_load > SCHED_LOAD_SCALE/2)
        goto out_set_cpu; // CPUはそのまま

    new_cpu = this_cpu; // プロセスを実行するCPUをローカルCPUに変更

    /* プロセスが直近に実行されていないかどうか。されていないなら選定処理を抜ける */
    for_each_domain(this_cpu, sd) {
        unsigned int imbalance;
        imbalance = sd->imbalance_pct + (sd->imbalance_pct - 100) / 2;
        if ((sd->flags & SD_WAKE_AFFINE) &&
                !task_hot(p, rq->timestamp_last_tick, sd)) {
            if (cpu_isset(cpu, sd->span)) {
                schedstat_inc(sd, ttwu_wake_affine);
                goto out_set_cpu;
            }
        } else if ((sd->flags & SD_WAKE_BALANCE) &&
                imbalance*this_load <= 100*load) {
            if (cpu_isset(cpu, sd->span)) {
                schedstat_inc(sd, ttwu_wake_balance);
                goto out_set_cpu;
            }
        }
    }

    /* 直近で実行されていた場合、キャッシュ効率などを考慮し前回使用したCPUを選択 */
    new_cpu = cpu; 
out_set_cpu:
    schedstat_inc(rq, ttwu_attempts);
    new_cpu = wake_idle(new_cpu, p);
    if (new_cpu != cpu) {
        schedstat_inc(rq, ttwu_moved);
        set_task_cpu(p, new_cpu); // プロセスを実行するCPUを更新
        task_rq_unlock(rq, &flags); // ロックを解除
        /* might preempt at this point */
        rq = task_rq_lock(p, &flags); // ランキューのロックを取得
        old_state = p->state; // 
        if (!(old_state & state)) // 指定のステータスと同じでない
            goto out; // 終了処理へ
        if (p->array) // 既にキューに登録されている場合
            goto out_running; // 終了処理へ

        this_cpu = smp_processor_id(); // ローカルCPUを取得
        cpu = task_cpu(p); // プロセスのCPUを取得
    }

out_activate:
#endif /* CONFIG_SMP */
    if (old_state == TASK_UNINTERRUPTIBLE) {
        rq->nr_uninterruptible--; // "TASK_UNINTERRUPTIBLE"なプロセスの総数を減算
        p->activated = -1; // プロセスの起床時の状態
    }

    /* activeキューに起床プロセスを登録し、動的優先度の再計算を行う */
    activate_task(p, rq, cpu == this_cpu);
    // 同機起床でなく、プロセスを実行するCPUがローカルCPUでなかった場合
    if (!sync || cpu != this_cpu) {
        if (TASK_PREEMPTS_CURR(p, rq)) // 起床プロセスとカレントプロセスを比較し、起床プロセスの優先度の方が高い場合
            resched_task(rq->curr); // カレントプロセスに再スケジューリング用のフラグを立てる。
    }
    success = 1;

out_running:
    p->state = TASK_RUNNING; // 起床タスクを実行状態に
out:
    task_rq_unlock(rq, &flags); // ロックを解除
    return success;
}

activatedメンバに設定される値には以下のように意味がある。

説明
0 プロセスは"TASK_RUNNING"状態だった。
1 プロセスは"TASK_INTERRUPTIBLE"または"TASK_STOPPED"だった。加えてシステムコールまたはカーネルスレッドによって起床中である。
2 プロセスは"TASK_INTERRUPTIBLE"または"TASK_STOPPED"だった。加えて割り込みハンドラまたは遅延処理によって起床中である。
-1 プロセスは"TASK_UNINTERRUPTIBLE"だった。現在起床中である。

上記で呼ばれているactive_task()関数は以下のように定義されている。

// kernel/sched.c
static void activate_task(task_t *p, runqueue_t *rq, int local)
{
    unsigned long long now;

    now = sched_clock(); // 現在時刻(ナノ秒)を設定
#ifdef CONFIG_SMP
    /* 現在時刻の修正 */
    if (!local) {
        runqueue_t *this_rq = this_rq();
        now = (now - this_rq->timestamp_last_tick)
            + rq->timestamp_last_tick;
    }
#endif
    recalc_task_prio(p, now); // 動的優先度の再計算

    // プロセスの状態を記録
    if (!p->activated) {
        if (in_interrupt())
            p->activated = 2; // 
        else {
            p->activated = 1;
        }
    }
    p->timestamp = now; // タイムスタンプを更新

    __activate_task(p, rq);
}

static inline void __activate_task(task_t *p, runqueue_t *rq)
{
    enqueue_task(p, rq->active); // activeキューに追加
    rq->nr_running++; // 実行可能プロセスの総数をインクリメント
}

recalc_task_prio()

上記で見たactivate_task()関数内部で呼ばれているrecalc_task_prio()は平均休止時間と動的優先度を更新する。定義は以下。

// kernel/sched.c
static void recalc_task_prio(task_t *p, unsigned long long now)
{
    // 現在時刻からスリープ時間を減算することでスリープしていた時間を求める
    unsigned long long __sleep_time = now - p->timestamp;
    unsigned long sleep_time;

    if (__sleep_time > NS_MAX_SLEEP_AVG) // スリープ時間が1秒以上であれば
        sleep_time = NS_MAX_SLEEP_AVG;
    else
        sleep_time = (unsigned long)__sleep_time;

    /* スリープしていれば */   
    if (likely(sleep_time > 0)) {
        /* カーネルスレッドでない && TASK_UNINTERRUPTIBLEでなかった && インタラクティブプロセスであると推測されるスリープ時間である場合 */
        if (p->mm && p->activated != -1 &&
            sleep_time > INTERACTIVE_SLEEP(p)) {
                p->sleep_avg = JIFFIES_TO_NS(MAX_SLEEP_AVG -
                        DEF_TIMESLICE);
        } else {
            // 平均休止時間が短いほど、値は急速に増加する
            sleep_time *= (MAX_BONUS - CURRENT_BONUS(p)) ? : 1;

            // TASK_UNINTERRUPTIBLE状態 && カーネルスレッドでない 場合
            if (p->activated == -1 && p->mm) {
                if (p->sleep_avg >= INTERACTIVE_SLEEP(p)) // 平均休止時間がインタラクティブプロセスだと思われる時間以上である場合
                    sleep_time = 0; // 平均休止時間を考慮しない
                else if (p->sleep_avg + sleep_time >=
                        INTERACTIVE_SLEEP(p)) { // 
                    p->sleep_avg = INTERACTIVE_SLEEP(p);
                    sleep_time = 0;
                }
            }

            p->sleep_avg += sleep_time;
            
            // 長い時間休止しているパッチプロセスに対して大き過ぎる平均休止時間を設定してしまうのを防ぐ
            if (p->sleep_avg > NS_MAX_SLEEP_AVG)
                p->sleep_avg = NS_MAX_SLEEP_AVG;
        }
    }

    p->prio = effective_prio(p); // 動的優先度の更新
}

schedule()

プロセスのスケジューリング処理を行う関数でカーネル内の複数箇所から呼び出される。実行キューからプロセスを取り出しCPUを割り当てる。

当該関数が呼び出される方法として以下の2つが挙げられる。

直接的な呼び出し

必要な資源の利用などが不可能でカレントプロセスを停止させる必要がある際に以下のような流れでスケジューラを呼び出す。

  1. カレントプロセスをキューに挿入。
  2. カレントプロセスにTASK_INTERRUPTIBLEまたはTASK_UNINTERRUPTIBLEを設定する。
  3. schedule()関数を呼び出す。(他のプロセスに実行が移る)
  4. (他のプロセスから実行権が返ってくる)
  5. 資源の利用が可能であるかを確認し、できなければ2へ。
  6. 資源の利用が可能であればカレントプロセスをキューから取り出し実行する。

上記のように繰り返し資源が利用可能であるかを確認し、利用が不可能であれば再度スケジューリング処理を呼び出す。長時間繰り返し処理を行うデバイスドライバの多くはTIF_NEED_RESCHEDフラグを確認し、もし当該フラグが設定されていれば直接的にスケジューリング処理を呼び出す。

遅延的な呼び出し

カレントプロセスにTIF_NEED_RESCHEDフラグを設定することで遅延的なスケジューラの呼び出しを行うことが可能で、ユーザプロセスに実行を戻す際などに必ず当該フラグを確認するので、近いうちにスケジューリング処理が走ることになる。

遅延的にスケジューラを呼び出すタイミングは以下。

  • カレントプロセスがタイムスライスを使用し切った場合。scheduler_tick()が当該フラグを設定する。
  • プロセスの起床時にその優先度がカレントプロセスの優先度を上回る場合。try_to_wake_up()が当該フラグを設定する。
  • sched_setscheduler()システムコールが発行された場合。

関数定義

スケジューリングを行うschedule()関数の定義は以下。

// kernel/sched.c
/*
 * schedule() is the main scheduler function.
 */
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;

need_resched:
    preempt_disable(); // プリエンプションの禁止
    prev = current;
    release_kernel_lock(prev); // ビッグカーネルロックの解放
need_resched_nonpreemptible:
    rq = this_rq(); // ランキューの取得

    schedstat_inc(rq, sched_cnt);
    now = sched_clock(); // 現在時刻をナノ秒で取得
    if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
        run_time = now - prev->timestamp; // 最後に起床した時刻から現在までの時間 -> 実行時間を算出
    else
        run_time = NS_MAX_SLEEP_AVG; // 1秒以上なら実行時間に1秒を設定

    run_time /= (CURRENT_BONUS(prev) ? : 1); // ボーナス値で実行時間を除算

    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; // タスクを動作可能状態に
        else {
            if (prev->state == TASK_UNINTERRUPTIBLE) // タスクがインタラプト不可の場合
                rq->nr_uninterruptible++; // 総数をインクリメント
            deactivate_task(prev, rq); // activeキューから取り除く
        }
    }

    cpu = smp_processor_id(); // ローカルCPUの取得
    if (unlikely(!rq->nr_running)) { // 実行可能プロセスが一つも存在しない
go_idle:
        idle_balance(cpu, rq); // ローカルの実行キューへプロセスを移動
        if (!rq->nr_running) { // それでも実行可能プロセスが存在しない場合
            next = rq->idle; // swapper(idle)プロセスを実行対象に設定
            rq->expired_timestamp = 0;
            wake_sleeping_dependent(cpu, rq); // 待機論理CPUに再スケジューリングを要求する
            if (!rq->nr_running) // 実行可能プロセスが存在しない
                goto switch_tasks; // コンテキストスイッチ処理へ
        }
    } else {
        if (dependent_sleeper(cpu, rq)) { // 次に実行対象であるプロセスの優先度が別の論理CPU上で実行されている兄弟プロセスよりも大幅に低い場合
            next = rq->idle; // 実行対象にswapperプロセスを選択
            goto switch_tasks; // コンテキストスイッチ処理へ
        }
        if (unlikely(!rq->nr_running)) // まだ実行可能プロセスが存在しない場合
            goto go_idle; // 戻って処理を繰り返す
    }

    array = rq->active;
    if (unlikely(!array->nr_active)) { // activeキューが空である場合
        // activeキューとexpiredキューを入れ替える。
        schedstat_inc(rq, sched_switch);
        rq->active = rq->expired; // expiredキュー(タイムスライス切れのプロセスリスト)をactiveに設定
        rq->expired = array; // activeキューをexpiredキューへ
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO; // リセット(最大値を設定)
    } else
        schedstat_inc(rq, sched_noswitch);

    idx = sched_find_first_bit(array->bitmap); // 優先度に対応するビットマップから次に実行すべき優先度を取得
    queue = array->queue + idx; // 優先度に対応するインデックスからキューを取得
    next = list_entry(queue->next, task_t, run_list); // キューからプロセスディスクリプタを取得

    /* リアルタイムプロセスでなく、TASK_INTERRUPTIBLEまたはTASK_STOPPEDからの復帰であった場合 */
    if (!rt_task(next) && next->activated > 0) {
        unsigned long long delta = now - next->timestamp; // キューに挿入されてからの時間

        if (next->activated == 1) // システムコールやカーネルスレッドが起床させたプロセスの場合
            delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128; // 待ち時間の一部のみ加算

        array = next->array;
        dequeue_task(next, array); // 実行対象をキューから取り出し
        recalc_task_prio(next, next->timestamp + delta); // 優先度を変更
        enqueue_task(next, array); // 再度キューに戻す
    }
    next->activated = 0; // TASK_RUNNING
switch_tasks:
    if (next == rq->idle) // swapperプロセスの場合
        schedstat_inc(rq, sched_goidle);
    prefetch(next); // CPUキャッシュにディスクリプタを載せる
    clear_tsk_need_resched(prev); // "TIF_NEED_RESCHED"フラグをクリア
    rcu_qsctr_inc(task_cpu(prev));

    prev->sleep_avg -= run_time; // 平均休止時間から実行時間を減算
    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_arch_switch(rq, next); // x86では何もしない
        prev = context_switch(rq, prev, next); // コンテキストスイッチ
        barrier(); // 最適化の防止

        finish_task_switch(prev); // メモリディスクリプタの解放
    
    /* 実行対象がカレントプロセスとは異なる場合 */
    } else
        spin_unlock_irq(&rq->lock); // ロック解除

    prev = current;
    if (unlikely(reacquire_kernel_lock(prev) < 0)) // ビッグカーネルロックの再取得
        goto need_resched_nonpreemptible;
    preempt_enable_no_resched(); // プリエンプションの許可
    if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) // TIF_NEED_RESCHEDフラグが設定されている場合
        goto need_resched; // 再度スケジューリング処理を行う。
}

プロセスの切り替えを実際に行うcontext_switch()の定義は以下。

// kernel/sched.c
/*
 * context_switch - switch to the new MM and the new
 * thread's register state.
 */
static inline
task_t * context_switch(runqueue_t *rq, task_t *prev, task_t *next)
{
    struct mm_struct *mm = next->mm; // 実行対象プロセスのメモリディスクリプタ
    struct mm_struct *oldmm = prev->active_mm;
    
    /*
    * mm: プロセスが所有するメモリディスクリプタ
    * active_mm: プロセスが利用するメモリディスクリプタ
    * 
    * カーネルスレッドの場合はmmを持たない。全てのプロセスがメモリ空間の3GB以降に
    * 同じカーネル空間をマッピングしているためカーネルはメモリ空間を保持する必要がない。
    */
    
    /* mmが存在しない(実行対象がカーネルスレッドである)場合 */
    if (unlikely(!mm)) {
        next->active_mm = oldmm; // カレントプロセスのメモリディスクリプタをそのまま使用する。
        atomic_inc(&oldmm->mm_count);
        enter_lazy_tlb(oldmm, next);
    } else
        switch_mm(oldmm, mm, next); // メモリディスクリプタの切り替え
    
    /* mmが存在しない(カレントプロセスがカーネルスレッドまたは終了中のプロセスである)場合 */
    if (unlikely(!prev->mm)) {
        prev->active_mm = NULL;
        WARN_ON(rq->prev_mm);
        rq->prev_mm = oldmm;
    }

    /* レジスタやスタックなどの切り替え */
    switch_to(prev, next, prev);

    return prev;
}

参考

  • Documentation/sched-coding.txt
  • Documentation/sched-design.txt