サービス・各種
お問い合わせ

サービス・各種
お問い合わせ

トップ > 新Linuxカーネル解読室 > 新Linuxカーネル解読室 - タスクスケジューラ (その3)

新Linuxカーネル解読室 - タスクスケジューラ (その3)

新Linuxカーネル解読室 Linux

「Linuxカーネル2.6解読室」（以降、旧版）出版後、Linuxには多くの機能が追加され、エンタープライズ領域をはじめとする様々な場所で使われるようになりました。
それに伴いコードが肥大かつ複雑化し、多くのエンジニアにとって解読不能なブラックボックスとなっています。
世界中のトップエンジニア達の傑作であるLinuxカーネルにメスを入れ、ブラックボックスをこじ開けて、時に好奇心の赴くままにカーネルの世界を解読する「新Linuxカーネル解読室」プロジェクト。

本稿では、(その1)、(その2)に引き続き、カーネルv6.8におけるタスクスケジューラの仕組みや実装について解説したいと思います。

執筆者 : 西村　大助

※ 「新Linuxカーネル解読室」連載記事一覧はこちら

はじめに

(その2)では、デフォルトのスケジューリングクラス(FAIRスケジューリングクラス)で利用されているEEVDFアルゴリズムにおいて、「どのタスクをどの程度実行するか」を解説しました。本稿では、残りのスケジューリングクラスである、RTとDEADLINEについても同様に解説したいと思います。
引き続き、章節番号は(その1)、(その2)からの連番となっています。

3.2 RTスケジューリングクラス

3.2.1 概要

RTスケジューリングクラスにはSCHED_FIFOとSCHED_RRがありますが、これらはPOSIXで規定されているスケジューリングポリシーで、それぞれ以下のような特徴があります。

  • SCHED_FIFO: 明示的にCPUを明け渡さない限り、タスクがCPUを使用し続ける。
  • SCHED_RR: 一定時間毎にタスクをRound-Robinで切り替える。

また、その名の通りリアルタイム性(応答性)が求められるような場合に使用されるため、(その2)で解説したFAIRスケジューリングクラスより優先度が高く、実行可能なRTスケジューリングクラスのタスクがある限り*1、FAIRスケジューリングクラスのタスクが実行される事はありません。
例えば、SCHED_FIFOは一部のRCU関連のカーネルスレッドでも使用されています。

以降の項でこれらのポリシーがどのように実現されているかを解説します。

3.2.2 rt_rq構造体とsched_rt_entity構造体

RTスケジューリングクラスでは、CPU毎のランキューに対応する物としてrt_rq構造体(以降、rt_rq)が、タスクに対応する物としてsched_rt_entity構造体(以降、rt_se)が使われます。
rt_rqにはrt_prio_array構造体のメンバ(rt_rq->active)があり、そこに、priority(1(優先度高)～99(優先度低))毎にタスク(rt_se->run_list)をリスト化しておくためのキューと、そのpriorityのタスクが存在するかどうかのビットマップ(タスクが存在するpriorityのビットを立てる)を保持しています。
(kernel/sched/sched.h)

    259 /*
    260  * This is the priority-queue data structure of the RT scheduling class:
    261  */
    262 struct rt_prio_array {
    263         DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
    264         struct list_head queue[MAX_RT_PRIO];
    265 };

実際に enqueue 処理の実体である __enqueue_rt_entity() を見ると以下のようになっており、その通りだとわかります。
(kernel/sched/rt.c)

   1375 static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
   1376 {
   1377         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
   1378         struct rt_prio_array *array = &rt_rq->active;
   1379         struct rt_rq *group_rq = group_rt_rq(rt_se);
   1380         struct list_head *queue = array->queue + rt_se_prio(rt_se);
    ...
   1394         if (move_entity(flags)) {
   1395                 WARN_ON_ONCE(rt_se->on_list);
   1396                 if (flags & ENQUEUE_HEAD)
   1397                         list_add(&rt_se->run_list, queue);
   1398                 else
   1399                         list_add_tail(&rt_se->run_list, queue);
   1400
   1401                 __set_bit(rt_se_prio(rt_se), array->bitmap);
   1402                 rt_se->on_list = 1;
   1403         }

3.2.3 pick_next_task()ハンドラ

前項の解説から想像がつくかもしれませんが、RTスケジューリングクラスのpick_next_task()ハンドラであるpick_next_task_rt()(その本質的な処理はpick_next_rt_entity())では、タスクの存在するpriorityの内、最優先(最もpriorityが小さい)のpriorityに対応したリストから先頭の物を返すようになっています。
(kernel/sched/rt.c)

   1714 static struct sched_rt_entity *pick_next_rt_entity(struct rt_rq *rt_rq)
   1715 {
   1716         struct rt_prio_array *array = &rt_rq->active;
   1717         struct sched_rt_entity *next = NULL;
   1718         struct list_head *queue;
   1719         int idx;
   1720
   1721         idx = sched_find_first_bit(array->bitmap);
   1722         BUG_ON(idx >= MAX_RT_PRIO);
   1723
   1724         queue = array->queue + idx;
   1725         if (SCHED_WARN_ON(list_empty(queue)))
   1726                 return NULL;
   1727         next = list_entry(queue->next, struct sched_rt_entity, run_list);
   1728
   1729         return next;
   1730 }

1つ特筆すべき点として、前回解説したEEVDFではタスクを実行状態にする際に当該タスクをrb-treeから削除していましたが、RTスケジューリングクラスでは*2タスクはリストに繋がったまま、という事は覚えておいてください。

3.2.4 TIF_NEED_RESCHEDを立てるタイミング

RTスケジューリングクラスにおいて、タスクをどの程度実行するか(どのタイミングでTIF_NEED_RESCHEDを立てるか)は、(その2)で解説したSCHED_FAIRの場合と同様に、tick時の処理(task_tick()ハンドラ)が鍵になります。RTスケジューリングクラスのtask_tick()ハンドラであるtask_tick_rt()は以下のようになっており、
(kernel/sched/rt.c)

   2588 static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
   2589 {
    ...
   2597         /*
   2598          * RR tasks need a special form of timeslice management.
   2599          * FIFO tasks have no timeslices.
   2600          */
   2601         if (p->policy != SCHED_RR)
   2602                 return;
   2603
   2604         if (--p->rt.time_slice)
   2605                 return;
   2606
   2607         p->rt.time_slice = sched_rr_timeslice;
   2608
   2609         /*
   2610          * Requeue to the end of queue if we (and all of our ancestors) are not
   2611          * the only element on the queue
   2612          */
   2613         for_each_sched_rt_entity(rt_se) {
   2614                 if (rt_se->run_list.prev != rt_se->run_list.next) {
   2615                         requeue_task_rt(rq, p, 0);
   2616                         resched_curr(rq);
   2617                         return;
   2618                 }
   2619         }
   2620 }

基本的な考え方としては*3、「RRで(L2601-L2602)、且つtimesliceを使い切り(L2604-L2605)、且つ自タスク以外がリストに存在する場合(L2614)に限り、タスクをリストの最後尾に繋ぎなおし(L2615)*4、TIF_NEED_RESCHEDを立てる(L2616)」という風に、最初に説明した

  • SCHED_FIFO: 明示的にCPUを明け渡さない限り、タスクがCPUを使用し続ける。
  • SCHED_RR: 一定時間毎にタスクをRound-Robinで切り替える。

の動作となっている事がわかります。

3.3 DEADLINEスケジューリングクラス

3.3.1 概要

DEADLINEスケジューリングクラスのタスクを特徴づけるパラメータとして、"runtime", "period", "deadline" の3つの値がありますが、DEADLINEスケジューリングクラスでは、"period"期間中の"deadline"までに"runtime"のCPU時間を割り当てるようにタスクをスケジューリングします*5。イメージとしては、「RTスケジューリングクラスではできなかった、性能の要件を細かく指定できるようにした、リアルタイムスケジューリングクラス」といった所でしょうか。この要件を満たすため、DEADLINEスケジューリングクラスはRTスケジューリングクラスより更に優先度が高くなっています*6。

この要件を満たすようにどのようにタスクがスケジューリングされるかを解説する前に、いくつか前提として知っておくべき事についてまとめます。

まず、タスクをDEADLINEスケジューリングクラスのタスクとするには、(通常、スケジューリングクラスを変更する際に使われるsched_setscheduler(2)ではなく)sched_setattr(2)を使う必要があり、その引数(@attr)で前述の "runtime", "period", "deadline" のパラメータを指定しますが、その際に指定したパラメータが実現可能な設定なのか(前述の要件を満たすことができるのか)の確認をします(実現不可能なパラメータだとsched_setattr(2)が失敗します)。この、「実現可能な設定なのかの確認」は"admission control"とも呼ばれ、sched_dl_overflow()で行われます。本稿では"admission control"について詳細には触れませんが、イメージとしては、bandwidth(帯域)を

\displaystyle{bandwidth = \frac{runtime}{period}}

と定義する時、「全DEADLINEスケジューリングクラスタスクのbandwidth(帯域)の合計が100%*7を超えない」ようなチェックが行われます。
また、DEADLINEスケジューリングクラスのタスクはfork(2)やclone(2)といったシステムコールで子プロセスを生成する事ができません(sched_setattr(2)でSCHED_FLAG_RESET_ON_FORKを立てていれば子プロセスの生成自体はできますが、その場合子プロセスのスケジューリングクラスはFAIRスケジューリングクラスとなるので、いずれにしてもDEADLINEスケジューリングクラスのタスクを増やす事はできません)。

これらの事により、既に存在するDEADLINEスケジューリングクラスのタスクについては"addmission control"済である事が保証されるので、設定済みのパラメータに基づいてタスクをスケジューリングすれば、全てのDEADLINEスケジューリングクラスのタスクの要件を満たす事ができるようになっています。

3.3.2 dl_rq構造体とsched_dl_entity構造体

DEADLINEスケジューリングクラスにおいても、他のスケジューリングクラスと同様に、CPU毎のランキューに対応する物としてのdl_rq構造体(以降、dl_rq)と、タスクに対応する物としてのsched_dl_entity構造体(以降、dl_se)を使用します。

dl_seで特に重要となるのは以下のメンバーです。
(include/linux/sched.h)

    598 struct sched_dl_entity {
    599         struct rb_node                  rb_node;
    600
    601         /*
    602          * Original scheduling parameters. Copied here from sched_attr
    603          * during sched_setattr(), they will remain the same until
    604          * the next sched_setattr().
    605          */
    606         u64                             dl_runtime;     /* Maximum runtime for each instance    */
    607         u64                             dl_deadline;    /* Relative deadline of each instance   */
    608         u64                             dl_period;      /* Separation of two instances (period) */
    ...
    612         /*
    613          * Actual scheduling parameters. Initialized with the values above,
    614          * they are continuously updated during task execution. Note that
    615          * the remaining runtime could be < 0 in case we are in overrun.
    616          */
    617         s64                             runtime;        /* Remaining runtime for this instance  */
    618         u64                             deadline;       /* Absolute deadline for this instance  */
    ...
    647         /*
    648          * Bandwidth enforcement timer. Each -deadline task has its
    649          * own bandwidth to be enforced, thus we need one timer per task.
    650          */
    651         struct hrtimer                  dl_timer;
    ...
メンバー 用途
dl_se->node dl_rq->rootをルートとするrb-treeに繋ぐためのrb_node
dl_se->dl_runtime sched_setattr(2)で指定されたruntime
dl_se->dl_deadline sched_setattr(2)で指定されたdeadline
dl_se->dl_period sched_setattr(2)で指定されたperiod
dl_se->runtime 残りのruntime
dl_se->deadline 実時間でのdeadline
dl_se->dl_timer 帯域制御のためのtimer

これらのメンバーが、具体的にどのようにタスクのスケジューリングロジックに使われているかを次項以降で説明していきます。

3.3.3 enqueue

dl_se->runtime, dl_se->deadlineは、タスクが実行可能状態となる際(enqueue時)にsched_setattr(2)で指定されたパラメータを元に設定されます*8。
(kernel/sched/deadline.c)

    769 static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
    770                                             struct rq *rq)
    771 {
    772         /* for non-boosted task, pi_of(dl_se) == dl_se */
    773         dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
    774         dl_se->runtime = pi_of(dl_se)->dl_runtime;
    775 }

また、前項でも触れた通り、enqueue時に各タスク(dl_se)はdl_rq->rootをルートとするrb-treeに繋がれますが、そのrb-tree内での「大小」は__dl_less()で計算され、dl_se->deadlineで決まります。
(kernel/sched/deadline.c)

   1598 static inline bool __dl_less(struct rb_node *a, const struct rb_node *b)
   1599 {
   1600         return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline);
   1601 }

3.3.4 pick_next_task()ハンドラ

DEADLINEスケジューリングクラスのpick_next_task()ハンドラであるpick_next_task_dl()(その本体であるpick_next_dl_entity())では、前述のdl_rq->rootをルートとするrb-treeから「最小」の物を持ってくるだけなので、dl_se->deadlineが最も小さい(時間的に近い)タスクが選択される事になります。
また、RTスケジューリングクラス同様、実行状態となってもタスクはrb-treeに繋がったままです。

3.3.5 TIF_NEED_RESCHEDを立てるタイミングとdl_timer

DEADLINEスケジューリングクラスにおいても、タスクをどの程度実行するか(どのタイミングでTIF_NEED_RESCHEDを立てるか)は、tick時の処理(task_tick()ハンドラ)が鍵になります。
DEADLINEスケジューリングクラスのtask_tick()ハンドラはtask_tick_dl()ですが、その処理のコアはupdate_curr_dl_se()です。
(kernel/sched/deadline.c)

   1326 static void update_curr_dl_se(struct rq *rq, struct sched_dl_entity *dl_se, s64 delta_exec)
   1327 {
   1328         s64 scaled_delta_exec;
    ...
   1357         dl_se->runtime -= scaled_delta_exec;
   1358
   1359 throttle:
   1360         if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
   1361                 dl_se->dl_throttled = 1;
    ...
   1368                 dequeue_dl_entity(dl_se, 0);
    ...
   1374                 if (unlikely(is_dl_boosted(dl_se) || !start_dl_timer(dl_se))) {
   1375                         if (dl_server(dl_se))
   1376                                 enqueue_dl_entity(dl_se, ENQUEUE_REPLENISH);
   1377                         else
   1378                                 enqueue_task_dl(rq, dl_task_of(dl_se), ENQUEUE_REPLENISH);
   1379                 }
   1380
   1381                 if (!is_leftmost(dl_se, &rq->dl))
   1382                         resched_curr(rq);
   1383         }

sched_delta_execは引数の@delta_execから計算されますが、基本的にタスクが実行された時間相当の値です。その分だけdl_se->runtimeを減算して(L1357)、dl_se->runtimeを使い切ったら(L1360)、ここで一旦rb-treeから削除します(L1368)。
次に、start_dl_timer()が実行されますが(L1374)、この関数はdl_se->dl_timerが次の"period"期間の開始時刻に発火するように設定します(timerの設定に成功すれば1を返し、既に開始時刻が過ぎている等の理由でtimerの設定ができなければ0を返しますが、'unlikely'が付いていることからもわかる通り、基本的にはtimerの設定が成功する事になります)。
dl_se->dl_timerのハンドラはdl_task_timer()で(init_dl_task_timer()参照)、この関数はタスクをenqueueするのが基本的な役割なので、結局、次の"period"の開始時刻にタスクがenqueueされる(rb-treeへ繋がれる)(逆にこのタスクが実行されることはない)ことになります。
そして最後に、(一応、leftmostかどうか(rb-tree内で「最小」かどうか)の確認は行われますが(L1381))タスクにTIF_NEED_RESCHEDが立てられる事になります(L1382)。

前述のdl_task_timer()ですが、重要なのは以下の部分で、
(kernel/sched/deadline.c)

   1220         enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
   1221         if (dl_task(rq->curr))
   1222                 wakeup_preempt_dl(rq, p, 0);
   1223         else
   1224                 resched_curr(rq);

タスクをenqueuするのはもちろん(L1220)、必要に応じて(実行中のタスクもDEADLINEスケジューリングクラスだった場合、それぞれのdl_se->deadlineの比較等も行います。wakeup_preempt_dl()、及びdl_entity_preempt()参照)enqueueしたタスクが実行されるように、現在実行中のタスクにTIF_NEED_RESCHEDを立てています(L1221-L1224)。

3.3.6 具体例

前項まで、実装に沿ってDEADLINEスケジューリングクラスのスケジューリングロジックを解説しましたが、これだけだと動きがイメージしづらいと思うので、最後に具体的な例を挙げて、どのようにタスクがスケジューリングされるかを見てみたいと思います。
ここでは、以下のようなパラメータ設定がされている2つのタスクを考えます。

  • タスク1(\displaystyle{T_1})
    • period = 5
    • deadline = 2
    • runtime = 1
  • タスク2(\displaystyle{T_2})
    • period = 15
    • deadline = 15
    • runtime = 10

タスク1は応答性重視(deadlineが短めだが帯域は小さめ(25%))、タスク2はスループット重視(deadlineは長いが帯域は大きめ(66%))に設定しています。ちなみに、DEADLINEスケジューリングクラスでは、タスク1のようにperiodより小さいdeadlineを"implicit"、タスク2のようにperiodと同じdeadlineを"constrained"と表現しています。
これらのタスクが常時実行可能状態だとして、前項までで説明したロジックでそれぞれのタスクのdl_se->runtime(上段)とdl_se->deadline(下段)がどのようになるかを整理すると以下のようになり(薄青:rb-tree内、赤矢印:実行状態、グレー矢印:dl_timer)、

それぞれのタスクについて「"period"期間中の"deadline"までに"runtime"のCPU時間を割り当てる」が満たされている事がわかります。

最後に

(その2)から本稿にかけて、「どのタスクをどの程度実行するか」というタスクスケジューラの最重要機能について、スケジューリングクラス毎に解説しました。
タスクスケジューラのもう1つの役割として、「どのCPUでタスクを実行するか」を判断するというものもあります。次回(「タスクスケジューラ」の解説としては最後となる予定)は、その辺りについてまとめられればと思っています。

*1:sched_rt_runtime_usの制限に抵触した場合は例外です。

*2:後述するDEADLINEスケジューリングクラスも同様です。

*3:sched_rt_runtime_usの制限を超えていないかのチェックも行われますが、それについては触れていません。

*4:前述した通り、実行状態でもタスクはリストに繋がったままです。

*5:その定義から必ず\displaystyle{runtime \leqq deadline \leqq period}が成り立ちます。

*6:タスクが指定できる最高優先度です。sugovカーネルスレッド(cpufreqのschedutil governorのカーネルスレッド)は、この「最高優先度」という性質を利用するためにDEADLINEスケジューリングクラスに設定されています。

*7:厳密には、sched_rt_runtime_usの制限やCPU数も考慮され、もう少し複雑です。

*8:実際は色々なパターンがあるのですが、ここでは一番シンプルなケースで考えます。