【読解入門】Linuxカーネル （スケジューラ編その2）

スケジューリングポリシーの概要

Linuxの各プロセス/スレッドはそれぞれの性質に合わせて合計で6つのスケジューリング ポリシーを選択できます。
性質とは、例えば実行要求があったら即座に反応したい、バッチ処理を行いたい、デッドラインを死守したい、などです。
このポリシー（クラス）によってスケジューラによってディスパッチ（選択）される順番がかわります。

それでは、早速スケジューリング ポリシーの定義を見てみましょう。

include/uapi/linux/sched.h

/*
 * Scheduling policies
 */
#define SCHED_NORMAL            0
#define SCHED_FIFO              1
#define SCHED_RR                2
#define SCHED_BATCH             3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE              5
#define SCHED_DEADLINE          6

※SCHED_NORMALはPOSIXに準拠する為にユーザー空間のプログラムからはSCHED_OTHERと指定します。

（1）IDLEクラス

SCHED_IDLEです。
一番低優先度のクラスで他のクラスの実行可能なプロセスが存在しなかった時に本クラスのプロセスがディスパッチされます。

（2）一般クラス（FAIRクラス）

SCHED_NORMALとSCHED_BATCHです。
本クラスは一般的なクラスで、何も指定せずにプロセスを実行するとこのクラスになります。

（3）リアルタイム（RT）クラス

SCHED_FIFO、SCHED_RRです。
リアルタイムに処理をしたいときに対象プロセスを本クラスに指定します。
SCHED_FIFO：実行プロセスが自分から実行権を譲らない限り、実行し続ける。（自分より高優先度プロセスが実行可能となった場合はプリエンプションされ、実行中断されます）
SCHED_RR：ラウンドロビン形式です。一定時間ごとに同一優先度の他プロセスに実行権を譲り、実行プロセスが順々に入れ替わります。

（4）DEADLINEクラス

SCHED_DEADLINEです。
デッドラインが近いプロセスを最優先して実行します。後述しますが、RTや一般クラスより優先度が高いです。

（5）STOPクラス

これはユーザーには公開していませんが、全クラスの中で一番高優先で実行されます。SMPシステムのCPUホットプラグで使用されます。

　クラスの優先順位

kernel/sched/sched.h

1 #ifdef CONFIG_SMP
2 #define sched_class_highest (&stop_sched_class)
3 #else
4 #define sched_class_highest (&dl_sched_class)
5 #endif
6 #define for_each_class(class) \
7   for (class = sched_class_highest; class; class = class->next)

上記を見ると判ると思いますが、sched_class_highestが最高優先度のクラスになります。
1、2行目：SMPシステム（CONFIG_SMPが有効）の場合、stop_sched_class（stopクラス）が最高優先度
3、4行目：UP（Uni-Processor）システムではdl_sched_class（deadlineクラス）が最高優先度
そしてスケジューラの至る所で実行されるfor_each_class( )ですが、コードを見ると以下の順番であることが判ります。各クラスのnextメンバーで次のクラスを辿っていきます。ここではSMPシステムの場合を例に見ます。

kernel/sched/stop_task.c

const struct sched_class stop_sched_class = {
        .next                   = &dl_sched_class, //DEADLINEクラス

kernel/sched/deadline.c

const struct sched_class dl_sched_class = {
        .next                   = &rt_sched_class, //RTクラス

kernel/sched/rt.c

const struct sched_class rt_sched_class = {
        .next                   = &fair_sched_class, //FAIRクラス

kernel/sched/fair.c

const struct sched_class fair_sched_class = {
        .next                   = &idle_sched_class, //IDLEクラス

kernel/sched/idle.c

const struct sched_class idle_sched_class = {
        /* .next is NULL */

上記から、優先順位は以下の通りであることが理解できます。
1.stopクラス
2.deadlineクラス
3.rtクラス
4.fairクラス
5.idleクラス

スケジューリングクラスの指定方法と優先度

本節はユーザーアプリ側から見た内容になりますが、各スケジューリング クラスの指定方法について述べます。
1.stopクラス
　本クラスはユーザーから指定できません。CPUのホットプラグであるコアをofflineにするときなど本クラスを用いて、可能な限り早く処理を完了させるためのクラスです。スケジューラとしても、本クラスのプロセスに優先度は設定せずにクラスを設定すると問答無用で本クラスのプロセスが優先して実行されます。

2.deadlineクラス
　sched_setattrシステムコールで指定します。実際の設定処理は後で載せますが、本クラスで指定するプロセスの優先度は-1としてカーネルで管理されます。

include/linux/sched/deadline.h

/*
 * SCHED_DEADLINE tasks has negative priorities, reflecting
 * the fact that any of them has higher prio than RT and
 * NORMAL/BATCH tasks.
 */

#define MAX_DL_PRIO             0
：

3.rtクラス
sched_setattr、sched_setschedulerシステムコールで指定します。SCHED_FIFOかSCHED_RR、そして指定可能な優先度は0から99までです。
ユーザーが指定する段階では、99が最高優先度ですが、カーネル内部ではその値を反転させて99で指定したプロセスは最高優先度0、ユーザ指定値0の最低優先度99になります。

include/linux/sched/prio.h

:
/*
 * Priority of a process goes from 0..MAX_PRIO-1, valid RT
 * priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH
 * tasks are in the range MAX_RT_PRIO..MAX_PRIO-1. Priority
 * values are inverted: lower p->prio value means higher priority.
 *
 * The MAX_USER_RT_PRIO value allows the actual maximum
 * RT priority to be separate from the value exported to
 * user-space.  This allows kernel threads to set their
 * priority to a value higher than any user task. Note:
 * MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
 */

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
:

4.fairクラス
sched_setattrシステムコール、niceシステムコールで指定可能です。
nice値は-20から19で指定し、-20が最高値、19が最低値であることはご存知かと思いますが、そのnice値をスケジューラは下記の通り優先度に変換します。なお、DEFAULT_PRIOは、同ファイルで120を定義しています。

include/linux/sched/prio.h

#define MAX_NICE        19
#define MIN_NICE        -20
#define NICE_WIDTH      (MAX_NICE - MIN_NICE + 1) //NICE_WIDTHは40
：
#define MAX_PRIO                (MAX_RT_PRIO + NICE_WIDTH) //MAX_PRIOは140
：

include/linux/sched/prio.h

:
/*
 * Convert user-nice values [ -20 ... 0 ... 19 ]
 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
 * and back.
 */
#define NICE_TO_PRIO(nice)  ((nice) + DEFAULT_PRIO) //nice値から優先度への変換。DEFAULT_PRIOは120
#define PRIO_TO_NICE(prio)  ((prio) - DEFAULT_PRIO) //優先度→niceへの変換

ここでポイントはMAX_PRIOがMAX_RT_PRIOの100 + NICE_WIDTHの40であることです。
idleプロセスの説明の後、整理します。

5.idleクラス
本クラスはsched_setattrシステムコールで設定します。なお、本クラスで設定したプロセスは優先度が存在しません。

では、スケジューラが扱う優先度を下図で整理したいと思います。

下記は余談ですので、読み飛ばしてもらって構いません。
なお、RTクラスの優先度50に割込みスレッドのデフォルト優先度と記載しています。これは、およそ15年ほど前から、Linuxのリアルタイム応答性を向上させるための活動で現在はThe Linux Foundation傘下のコラボラティブ プロジェクトReal-Time Linux Projectで取り組んでいるPreempt-RTというLinuxカーネルをフルプリエンプティブにするアプローチの取組みの一環で割込みハンドラのスレッド化という機能がありました。この機能がメインラインにマージされて現在のLinuxでは割込みハンドラはタイマー割込み以外を"irq/<割込み番号>"というスレッド名でスレッド化しました。
さらに逸れてしまいますが、なぜ本機能が必要かと言うと、一言でいうと「スケジューラが割込みを制御できるから」です。
従来は割込みが入ると直前に実行していたプロセスのコンテキストで動作しており、割込み自身にはtask_struct構造体もなくスケジューラの管理外でした。
これが、割込みハンドラのスレッド化によって割込みハンドラもtask_struct構造体を用いてスケジューラが管理できるため、Aというプロセスのレスポンスが重要だからXという割込みより優先度を上げて処理をするという事が可能になりました。
※従来は割込み禁止にしていない限り、割込みが常に優先されていました。

スケジューラの構成

linux-2.6.22までは、kernel/sched.cでRTクラスと一般クラスを記載していたのですが、linux-2.6.23で一般クラスの刷新があり、スケジューラのソースファイルが複数になりました。その後、deadlineクラスなども追加され、現在はkernel/sched配下のファイルがスケジューラ関連ファイルとなります。

そして、スケジューラの動作としては基本的にはモジュール形式となり以下のようなイメージなります。

例えば、次のプロセスを決定する関数としてpick_next_task( )があるのですが、本関数の実装は下記の通りです。

kernel/sched/core.c

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
1        const struct sched_class *class;
2        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in the fair class we can
         * call that function directly, but only if the @prev task wasn't of a
         * higher scheduling class, because otherwise those loose the
         * opportunity to pull in more work from other CPUs.
         */
3        if (likely((prev->sched_class == &idle_sched_class ||
4                    prev->sched_class == &fair_sched_class) &&
5                   rq->nr_running == rq->cfs.h_nr_running)) {

6                p = fair_sched_class.pick_next_task(rq, prev, rf);
7                if (unlikely(p == RETRY_TASK))
8                        goto again;

                /* Assumes fair_sched_class->next == idle_sched_class */
9                if (unlikely(!p))
10                        p = idle_sched_class.pick_next_task(rq, prev, rf);

11                return p;
12        }

13 again:
14        for_each_class(class) {
15                p = class->pick_next_task(rq, prev, rf);
16                if (p) {
17                        if (unlikely(p == RETRY_TASK))
18                                goto again;
19                        return p;
20                }
21        }

        /* The idle class should always have a runnable task: */
22        BUG();
23}

3行目から12行目までは最適化処理で、ある条件の時はFAIRクラスを見れば良い、IDLEクラスを見れば良いという決め打ちで特定のクラスのpick_next_taskメンバーを呼び出していますが、ここで見ていただきたいのは14行～21行目です。
先ほど出てきたfor_each_classの15行目のpick_next_taskで高優先度クラスからそれぞれのクラスで定義しているpick_next_taskメンバーを呼び出して、対象プロセスが存在しなければ、次の優先度のpick_next_taskメンバーを順に呼び出していきます。

次回は各スケジューリング クラスのデータ構造やスケジューリング アルゴリズムについて述べたいと思います。

初回：【読解入門】Linuxカーネル （概要編）
前回：【読解入門】Linuxカーネル （スケジューラ編その1）
次回：【読解入門】Linuxカーネル （スケジューラ編その3-1）