LinuxプロセススケジューリングのCFSスケジューラの概要--Linuxプロセスの管理とスケジューリング(24)

日付
カーネルバージョン
スキーマ＃スキーマ＃
作成者
GitHub
CSDN
2016-07-29
Linux-4.6
X86 & arm
gatieme
LinuxDeviceDrivers
Linuxプロセス管理とスケジューリング
1前景レビュー
1.1プロセススケジュール
メモリには、各プロセスの一意の説明が保存され、いくつかの構造を介して他のプロセスに接続されている.
スケジューラが直面する場合、そのタスクは、プログラム間でCPU時間を共有し、並列に実行する錯覚を作り出すものであり、このタスクは2つの異なる部分に分けられ、そのうちの1つはスケジューリングポリシーに関し、もう1つはコンテキスト切替に関する.
1.2プロセスの分類
linuxはプロセスをリアルタイムプロセスと非リアルタイムプロセスに分け、非リアルタイムプロセスはさらにインタラクティブプロセスとバッチプロセスに分けます.
プロセスの分類によってLinuxは異なるスケジューリング戦略を採用する.
リアルタイムプロセスについては、FIFO、Round RobinまたはEarliest Deadline First(EDF)の最も早い締め切り優先スケジューリングアルゴリズム|のスケジューリングポリシーを採用する.
1.3 linuxスケジューラの進化
フィールド
バージョン#バージョン#
O(n)のイニシャルスケジューリングアルゴリズム
linux-0.11~2.4
O(1)スケジューラ
linux-2.5
CFSスケジューラ
linux-2.6~現在まで
1.4 Linuxのスケジューラ構成
2つのスケジューラ
スケジュールをアクティブ化するには、2つの方法があります.

は、プロセスが睡眠をとるか、または他の理由でCPU

を放棄するかのような直接的なものである.

もう1つは周期的な機構により一定の周波数で動作、時々の検出が必要かどうか

である.
したがって、現在のlinuxのスケジューラは、プライマリスケジューラ、サイクルスケジューラ(汎用スケジューラ(generic scheduler)またはコアスケジューラ(core scheduler)の2つのスケジューラから構成されています.
各スケジューラには、スケジューラフレームワーク(実質的に2つの関数フレームワーク)とスケジューラクラスの2つの内容が含まれています.
6種類のスケジューリングポリシー
linuxカーネルでは、異なるタイプのプロセスをスケジューリングしたり、特定の機能をサポートしたりするための6つのスケジューリングポリシー(すなわち、スケジューリングアルゴリズム)が実装されています.

SCHED_NORMALとSCHED_BATCHスケジューリング通常の非リアルタイムプロセス

SCHED_FIFOとSCHED_RRとSCHED_DEADLINEは、異なるスケジューリングポリシーを用いてリアルタイムプロセス

をスケジューリングする.

SCHED_IDLEは、システムのアイドル時にidleプロセスを呼び出す.

5つのスケジューラクラス
そのスケジューリングポリシーによって5つのスケジューラクラスが実現する、1つのスケジューラクラスは、ある種類のプロセスを1つまたは複数のスケジューリングポリシーでスケジューリングすることができ、特殊な状況や特殊な機能をスケジューリングするプロセスにも使用することができる.
プロセスの優先順位は次のとおりです.

stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

3つのスケジューリングエンティティ
スケジューラは、スケジューリングプロセスに限定するものではなく、グループスケジューリングを実現するなど、より大きなエンティティをスケジューリングすることもできる.
この一般的な要件は、スケジューラがプロセスを直接操作するのではなく、スケジューラ可能なエンティティを処理することであるため、このスケジューラエンティティ、すなわちseched_を記述する汎用的なデータ構造が必要である.entity構造は、実際にはスケジューリング対象を表す、プロセスであってもよいし、プロセスグループであってもよい.
linuxでは、現在スケジューリング可能なリアルタイムおよび非リアルタイムプロセスのタイプをseched_と定義しています.entityの3つのスケジューリングエンティティ

sched_dl_entity EDFアルゴリズムによるリアルタイムスケジューリングエンティティ

sched_rt_entity Roound-RobinまたはFIFOアルゴリズムでスケジューリングされたリアルタイムスケジューリングエンティティrt_sched_class

sched_entity CFSアルゴリズムを用いてスケジューリングされる通常の非リアルタイムプロセスのスケジューリングエンティティ

2 cfs完全公平スケジューラ
2.1 CFSスケジューラクラスfair_sched_class
CFS完全公平スケジューラのスケジューラクラスをfairと呼ぶsched_class、kernel/sched/fairで定義されています.c,line 8521,struct sched_とよく知られていますclassスケジューラクラスタイプ、私たちのCFSスケジューラをいくつかの特定の関数に関連付けます

/*
 * All the scheduling class methods:
 */
const struct sched_class fair_sched_class = {
        .next                   = &idle_sched_class,  /*           ,         next        */
        .enqueue_task           = enqueue_task_fair,
        .dequeue_task           = dequeue_task_fair,
        .yield_task             = yield_task_fair,
        .yield_to_task          = yield_to_task_fair,

        .check_preempt_curr     = check_preempt_wakeup,

        .pick_next_task         = pick_next_task_fair,
        .put_prev_task          = put_prev_task_fair,

#ifdef CONFIG_SMP
        .select_task_rq         = select_task_rq_fair,
        .migrate_task_rq        = migrate_task_rq_fair,

        .rq_online              = rq_online_fair,
        .rq_offline             = rq_offline_fair,

        .task_waking            = task_waking_fair,
        .task_dead              = task_dead_fair,
        .set_cpus_allowed       = set_cpus_allowed_common,
#endif

        .set_curr_task          = set_curr_task_fair,
        .task_tick              = task_tick_fair,
        .task_fork              = task_fork_fair,

        .prio_changed           = prio_changed_fair,
        .switched_from          = switched_from_fair,
        .switched_to            = switched_to_fair,

        .get_rr_interval        = get_rr_interval_fair,

        .update_curr            = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
        .task_move_group        = task_move_group_fair,
#endif
};

メンバー＃メンバー＃
説明
enqueue_task
準備キューにプロセスを追加します.タスクが実行可能な状態に入ると、関数が呼び出されます.スケジューリングエンティティ(プロセス)を赤と黒のツリーに配置し、nr_running変数に1を加える
dequeue_task
プロセスをReadyキューから削除し、タスクが実行可能状態を終了すると関数が呼び出され、対応するスケジューリングエンティティが赤と黒のツリーから削除され、nr_running変数で1を減算
yield_task
プロセスがリソースをプロセッサに対する制御権を放棄したい場合、sched_に使用できます.yieldシステム呼び出し、カーネルAPI yield_を呼び出すtaskはこの仕事を完了した.compat_yield sysctlがオフの場合、この関数は実際に先にデキューされた後にデキューされます.この場合、スケジューラエンティティは赤と黒のツリーの右端に配置されます.
check_preempt_curr
この関数は、現在実行されているタスクがプリエンプトされているかどうかを確認します.実行中のタスクを実際にプリエンプトする前に、CFSスケジューラモジュールは公平性テストを実行します.これにより、ウェイクアップ(wakeup)プリエンプトが駆動されます.
pick_next_task
この関数は、次に実行する最適なプロセスを選択します.
put_prev_task
現在実行中のプロセスの代わりに別のプロセスを使用
set_curr_task
この関数は、タスクがスケジューリングクラスを変更したり、タスクグループを変更したりすると呼び出されます.
task_tick
周期スケジューラがアクティブになるたびに、time tick関数から呼び出される周期スケジューラによって呼び出されます.プロセスの切り替えを引き起こす可能性があります.これにより、ランタイムプリエンプトが駆動されます.
task_new
カーネルスケジューラは、forkシステム呼び出しとスケジューラの関連付けを確立するために、スケジューラモジュールに新しいタスクの起動を管理する機会を提供します.新しいプロセスが確立されるたびにnew_taskはスケジューラに通知し、CFSスケジューラはそれを使用してグループスケジューリングを行い、リアルタイムタスクのスケジューラはこの関数を使用しません.
2.2 cfsの準備キュー
準備キューはグローバルスケジューラの多くの操作の起点ですが、プロセスは準備キューによって直接管理されるわけではありません.スケジューリング管理は各スケジューラの職責です.したがって、各レディキューには、特定のスケジューリングクラスのサブレディキュー(cfsの上位スケジューリングは、キューstruct cfs_rq、リアルタイムスケジューリングクラスのレディキューstruct rt_rq、deadlineスケジューリングクラスのレディキューstruct dl_rqについて

/* CFS-related fields in a runqueue */
/* CFS       ，  CPU rq     cfs_rq，       sched_entity        cfs_rq   */
struct cfs_rq {
    /* CFS              */
    struct load_weight load;
    /*
     *  nr_running: cfs_rq       
     *  h_nr_running:        ，        cfs_rq nr_running  
    */
    unsigned int nr_running, h_nr_running;

    u64 exec_clock;

    /*
     *   CFS         ，    
     *          : 
     * 1、                
     * 2、         ，        ，            vruntime    min_vruntime，        。
     */

    u64 min_vruntime;
#ifndef CONFIG_64BIT
    u64 min_vruntime_copy;
#endif
    /*      root */
    struct rb_root tasks_timeline;
     /*        (        ，             ) */
    struct rb_node *rb_leftmost;

    /*
     * 'curr' points to currently running entity on this cfs_rq.
     * It is set to NULL otherwise (i.e when none are currently running).
     * curr:        sched_entity（         cpu   ，          task cpu   ，      cfs_rq       cfs_rq        sched_entity）
     * next:           ，     CFS        ，        next    ，    next
     *
     * skip:     (    skip       )
     */
    struct sched_entity *curr, *next, *last, *skip;

#ifdef  CONFIG_SCHED_DEBUG
    unsigned int nr_spread_over;
#endif

#ifdef CONFIG_SMP
    /*
     * CFS load tracking
     */
    struct sched_avg avg;
    u64 runnable_load_sum;
    unsigned long runnable_load_avg;
#ifdef CONFIG_FAIR_GROUP_SCHED
    unsigned long tg_load_avg_contrib;
#endif
    atomic_long_t removed_load_avg, removed_util_avg;
#ifndef CONFIG_64BIT
    u64 load_last_update_time_copy;
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
    /*
     *   h_load = weight * f(tg)
     *
     * Where f(tg) is the recursive weight fraction assigned to
     * this group.
     */
    unsigned long h_load;
    u64 last_h_load_update;
    struct sched_entity *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */

#ifdef CONFIG_FAIR_GROUP_SCHED
    /*     CPU rq */
    struct rq *rq;  /* cpu runqueue to which this cfs_rq is attached */

    /*
     * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
     * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
     * (like users, containers etc.)
     *
     * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
     * list is used during load balance.
     */
    int on_list;
    struct list_head leaf_cfs_rq_list;
    /*    CFS         */
    struct task_group *tg;  /* group that "owns" this runqueue */

#ifdef CONFIG_CFS_BANDWIDTH
    int runtime_enabled;
    u64 runtime_expires;
    s64 runtime_remaining;

    u64 throttled_clock, throttled_clock_task;
    u64 throttled_clock_task_time;
    int throttled, throttle_count;
    struct list_head throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};

メンバー＃メンバー＃
説明
nr_running
キューで実行可能なプロセスの数
load
Ready Queueで実行可能なプロセスの累積負荷ウェイト
min_vruntime
記録キュー上のすべてのプロセスの最小仮想実行時間を追跡する.この値は、準備キューに関連する仮想クロックを実現するための基礎です.
tasks_timeline
時間順の赤と黒のツリーですべてのプロセスを管理
rb_leftmost
常に赤と黒の木の一番左のノード、すなわちスケジューリングが必要なプロセスを指すように設定.この値は実際には症例赤黒樹で得ることができるが,この値を記憶することで赤黒樹の探索にかかる平均時間を減らすことができる.
curr
現在実行中のsched_entity(グループについてはcpu上では実行されませんが、その下層にtaskがcpu上で実行されている場合、そのcfs_rqは、cfs_rq上で現在実行中のsched_entityとみなされます.
next
CFSスケジューリングに従わなくても実行しなければならないプロセスがあることを示し、スケジューリング時にnextがスケジューリングを必要としているかどうかをチェックし、nextがスケジューリングされているかどうかを確認します.
skip
プロセスを省略(skipで指定したプロセススケジューリングは選択されません)
3参考
Linuxプロセスグループスケジューリングメカニズム分析
Linuxカーネル学習ノート(一)CFS完全公平スケジューリングクラス
CFSスケジューラ学習ノート
linuxスケジューラ(五)——プロセス管理とCFS
CFSプロセススケジューリング
CFSグループスケジューリングの理解
いくつかの問題からCFSスケジューラを理解する