こんにちは。
前回はZephyrの概要とスケジューラの概要を述べました。
今回はスケジューラ内部を読解していきます。
ちなみに、RTOSにおけるリアルタイム応答性能は非常に重要であり、スケジューラの仕組みを理解することは有益です。

優先度の管理

前回、述べた内容のまとめです。

- スレッドにはcooperativeスレッドとpreemptibleスレッドがあり、cooperativeスレッドを優先して実行する。
- cooperativeスレッド及びpreemptibleスレッドの優先度の数はビルド時のコンフィグで決定する。
- 以下はデフォルトのcooperativeスレッドが16段階、preemptibleスレッドが16段階の図。 (カーネル内部)



　　　　　　　　図1

- 優先度の最大段数（範囲）は257段階。
　　cooperativeスレッドの範囲は0～128。
　　コンフィグ項目CONFIG_COOP_PRIORITESの★で定義。defaultは16。

config NUM_COOP_PRIORITIES
        int
        prompt "Number of coop priorities" if MULTITHREADING
        default 16
        default 1 if !MULTITHREADING
        range 0 128 ★

　　preemptibleスレッドの範囲は0～128。
　　コンフィグ項目CONFIG_PREEMPT_PRIORITESの★で定義。defaultは15。

config NUM_PREEMPT_PRIORITIES
        int
        prompt "Number of preemptible priorities" if MULTITHREADING
        default 15
        default 0 if !MULTITHREADING
        range 0 128 ★

- 優先度の値が小さい方が高優先度。
- スケジューラは優先度に基づいた制御を行う

スケジューラを理解する上で優先度は非常に重要な要素です。
従って、まずは優先度にフォーカスをあてた後にスケジューラの構造/アルゴリズムを見ていきます。なお、本記事ではより理解しやすいUP（Uni-Processor）向け処理をスコープとし、SMP向け処理については割愛します。

ユーザーの指定方法とカーネルにおける管理

cooperative、preemptibleスレッドの優先度がそれぞれ128段階の場合、ユーザーは以下の2種類の方法で指定可能です。
(1) 即値指定
　　cooperativeスレッド：-128～-1の即値（-128が最高優先度）
　　preemptibleスレッド：0～128の即値（0が最高優先度）
(2) マクロ指定
　　cooperativeスレッド：K_PRIO_COOP(0)～K_PRIO_COOP(127)（K_PRIO_COOP(0)が最高優先度）
　　preemptibleスレッド：K_PRIO_PREEMPT(0)～K_PRIO_PREEMPT(128)（K_PRIO_PREEMPT(0)が最高優先度）
　　　　　　　　　　　　※これらのマクロについては後述します

では、これらの優先度をカーネルはどのように使用しているのでしょうか。
実際のコードと照らし合わせて見てみましょう。

static void _gpio_sch_manage_callback(struct device *dev)
{
    :
                        k_thread_create(&gpio->polling_thread,
                                        gpio->polling_stack,
                                        GPIO_SCH_POLLING_STACK_SIZE,
                                        (k_thread_entry_t)_gpio_sch_poll_status,
                                        dev, NULL, NULL,
                                        K_PRIO_COOP(1), 0, 0);
   :
}

例としてgpioのポーリング処理のスレッド生成部を抜粋しました。
k_thread_createでスレッドを生成しますが、引数は順に
1)k_thread構造体
2)スタックアドレス
3)スタックサイズ
4)スレッドが実行する関数
5)引数1
6)引数2
7)引数3
8)優先度
9)スレッドオプション
10)スケジューリングディレイを許すか否か
となっています。

注目すべきは優先度の部分です。K_PRIO_COOP(1)と指定しています。
上で少し触れましたが、Zephyrではユーザーがcooperativeスレッドの優先度を設定する時、即値指定も許していますが、基本的にはこのK_PRIO_COOP()の引数で指定する方法が望ましいです。

次に、このK_PRIO_COOP(1)がどう処理されるかを見てみましょう。

#define K_PRIO_COOP(x) (-(_NUM_COOP_PRIO - (x)))　[1]
#define K_PRIO_PREEMPT(x) (x)                     [2]

#define _NUM_COOP_PRIO (CONFIG_NUM_COOP_PRIORITIES+1)

cooperativeスレッドは[1]の通りです。
CONFIG_NUM_COOP_PRIORITIESが128でxに0（最高優先度）を指定した場合、_NUM_COOP_PRIOは128ですのでK_PRIO_COOPマクロ展開後は-128になります。
またCONFIG_NUM_COOP_PRIORITIESが128でxに127（cooperativeスレッドの最低優先度）を指定した場合、マクロ展開後は-1になります。
また、CONFIG_NUM_PREEMPT_PRIORITIESが128でxに0を指定した場合、そのまま0になります。(上記[2]）

これらのマクロ展開後の優先度一覧が図1であり、ユーザーが指定した優先度をスケジューラは内部向けにこのように変換して管理しています。

readyキューの構造

スケジューラは実行可能なスレッド群から適切なスレッドをディスパッチする役割を担いますが、まずは実行可能なスレッド群の管理方法を理解しておきましょう。

struct _ready_q {
        /* always contains next thread to run: cannot be NULL */
        struct k_thread *cache;

        /* bitmap of priorities that contain at least one ready thread */
        u32_t prio_bmap[K_NUM_PRIO_BITMAPS];

        /* ready queues, one per priority */
        sys_dlist_t q[K_NUM_PRIORITIES];
};

各メンバーについて順に見ていきます。

なお、readyキューと複雑度は異なりますが、
LinuxカーネルのRTクラス(SCHED_FIFO、SCHED_RR)を制御する
runキューも役割/仕組みは大体同じと思ってもらって結構です。

1) cacheメンバ
　本メンバで次に実行するスレッドのポインタを常に保持しておくことでスケジューリング処理を高速化します。本メンバは主にスレッドをreadyキューを操作する時（キューへの登録や削除）に更新します。
前記事で実際にコンテキストスイッチする_Swap()を見ました。この関数で次に実行するスレッドnew_threadは、_get_next_ready_thread()の復帰値を設定していました。
この復帰値は以下のとおり、readyキューのcacheメンバを返すようになっています。

static ALWAYS_INLINE struct k_thread *_get_next_ready_thread(void)
{
        return _ready_q.cache; //★常にcacheを返す
}

2) prio_bmapメンバ
　優先度のビットマップになります。各ビットに対応する優先度のスレッドが存在する or しないを示します。従って、優先度の段数だけビットを用意しています。
例えば、64段階の優先度を使用する場合は64ビット用意します。
これまではcooperativeスレッドは負の値で管理すると述べてきましたが、このreadyキューの段階になると各優先度を配列の要素番号として使用するため、正の値で管理します。例えばcooperativeスレッドを46段階、preemptibleスレッドを20段階の優先度の場合は0～63ビットにマッピングされます。なお、スケジューラはprio_bmapメンバの0ビット目を最高優先度として扱います。
以下にこの例のビットマップの図を示します。

このメンバはreadyキューを操作する時（cacheの更新時や最高優先度のスレッド探索処理）で使用されます。

3) qメンバ
　最後のメンバq配列も優先度の段数の数が要素数となります。各優先度ごとに双方向循環リストになっています。
このメンバもprio_bmapメンバと同様に実行するスレッドを決定するcacheを操作する時に使用されます。

　readyキュー操作時にprio_bmapとこのq配列から高優先度のスレッドを探索し、prio_bmapでヒットしたビットを用いてq配列から対象スレッドをcacheに設定します。次の図の場合は優先度1でスレッドDを見つけるのでスレッドDをcacheポインタで示します。

要点を以下に示します。
スケジューリング時は次に実行するスレッドはcacheで示しているスレッドを問答無用で採用し、高速化を図っている。prio_bmapやqメンバはそのcacheを決定するためのreadyキューを操作する時(addやremove、rotateなど）のために用意されている、です。

ここまでコードリーディングしていなかったので、キューを操作する処理を例として見てみましょう。

readyキューへの追加処理

ここでは例としてあるスレッドをreadyキューに追加する処理を見てみましょう。

void _add_thread_to_ready_q(struct k_thread *thread)
{
 :
1        int q_index = _get_ready_q_q_index(thread->base.prio);
2        sys_dlist_t *q = &_ready_q.q[q_index];

3        set_ready_q_prio_bit(thread->base.prio);     [1]
4        sys_dlist_append(q, &thread->base.k_q_node); [2]

5        struct k_thread **cache = &_ready_q.cache;   [3]

6        *cache = _is_t1_higher_prio_than_t2(thread, *cache) ? thread : *cache; [3]'
}

本関数に渡されるのはk_thread構造体です。(Linuxでいうtask_struct構造体）
1行目：はじめに追加するスレッドの優先度を基にq_indexを求めます。
　　　　q_indexはreadyキューのq配列の位置を指します。
3行目：set_ready_q_prio_bit()（詳細は後述）でprio_bmapビットマップの対象の優先度のビットをセットします。
4行目：readyキュー（qメンバ）に対象のスレッドを繋ぎます。（詳細は後述）
6行目：_is_t1_higher_prio_than_t2()で必要に応じて次に実行するスレッドcacheを更新します。

以下に対象ビットをセットする[1]set_ready_q_prio_bit()とキューにつなぐ[2]sys_dlist_append()を示します。

static void set_ready_q_prio_bit(int prio)
{
1        int bmap_index = _get_ready_q_prio_bmap_index(prio);
2        u32_t *bmap = &_ready_q.prio_bmap[bmap_index];

3        *bmap |= _get_ready_q_prio_bit(prio);
}

1行目：与えられたprioをもとに_get_ready_q_prio_bmap_index()で対象ビットのインデックス（配列の要素番号）を特定します。
2行目：\対象となる要素番号の_read_q.prio_bmapのポインタをbmapに設定します。
3行目：_get_ready_q_prio_bit()を利用して対象ビットをセットしてます。

static inline void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)
{
        node->next = list;
        node->prev = list->tail;

        list->tail->next = node;
        list->tail = node;
}

本関数は汎用の双方向循環リストのappend関数です。
リストの最後に対象スレッドを追加します。
_add_thread_to_ready_q()の[3]と[3]'で、次に実行するcacheポインタを更新します。

なお、readyキューから削除するときは_remove_thread_from_ready_q()を実行します。この関数ではset_ready_q_prio_bit()とsys_dlist_append()の反対の処理にあたるclear_ready_q_prio_bit()やsys_dlist_remove()を使用しています。
この関数の説明については割愛しますが、必要であれば記載しますので遠慮せずコメントください。

スケジューリング方針

　RTOSで非常に重要な役割を担うスケジューラのポリシーを理解しましょう。
これまでも述べましたが、スケジューラは最も優先度が高いスレッドを実行します。ready状態の同じ優先度のスレッドが複数存在する場合は、最も待たされているスレッドを実行します。
　以下にcooperativeスレッドとpreemptibleスレッドのスケジューリングアルゴリズムを述べます。

cooperativeスレッド

　実行中のスレッドが対象の処理を終えて自発的にunready状態にするまで、実行し続けます。この間に動作し得るのは割込みハンドラのみです。ただし、当該スレッドが長い計算などでCPUを占有し続けると、他の高優先度のcooperativeスレッドの実行を妨げるため、これを防ぐためにCPUを自発的に他のスレッドに受け渡すために2種類の関数を用意しています。
- k_yield
　当該スレッドを同優先度のリストの最後に繋ぎ直します。
　従って、そのスレッドより高優先度、または同一優先度のスレッドが存在しなければ、元のスレッドが実行し続けます。

- k_sleep
　指定した時刻の間、休眠（unready状態に）させます。従って、その間は当該スレッドより低優先度のスレッドも実行できます。

preemptibleスレッド

preemptibleスレッドが_currentスレッドになると、以下を除いて実行し続けます。
-高優先度スレッドによってプリエンプトされる
-自発的に自身をunready状態にする

ただし、「同一優先度のスレッド」が長時間実行されない場合があるため、これを防ぐために、preemptibleスレッドではk_yield、k_sleepに加えてスケジューラのタイムスライスという概念があります。
tick割込みを用いてタイムスライスを計算しますが、タイムスライスの長さはコンフィグ項目 (CONFIG_TIMESLICE_SIZE）で決定します。この項目はデフォルトで0（タイムスライスなし）で、0msから2,147,483,647msの範囲で指定可能です。

纏めると、以下の通りです。
- 高優先度によってプリエンプション可能
- 同じ優先度のスレッドを実行させるためにタイムスライスという概念がある。
タイムスライスはコンフィグで指定でき、このタイムスライス分を実行すると、同じ優先度の他のスレッドに実行権を移す。
- k_yield()を使用すると：同じ優先度の他スレッドに実行権を譲る。
　　　　　　　　　　　　　低優先度のスレッドは実行できない。
-k_sleep()を使用すると：同じ優先度のスレッドは勿論、低優先度のスレッドでも実行できる。

その他

- cooperativeスレッドか否かの判定
　　以下の通り、スレッドのbase.prioが負であれば真を返す。
　　k_thread構造体base.prioではcooperativeスレッドが負値、preemptibileスレッドが正値を保持する。

static inline int _is_coop(struct k_thread *thread)
{
        return thread->base.prio < 0;
}

- スケジューラロック
　preemptibleスレッドでクリティカルセクション実行中でプリエンプションを禁止したい場合はk_sched_lock()を使用する。許可状態に戻すときはk_sched_unlock()を使用する。

- 休眠中のスレッドを起床させる
　休眠中のスレッドを別スレッドから起床させる場合はk_wakeup()を使用する。
　※k_wakeup()はシステムコールなのでシステムコール編で述べます。

- ビジーループさせる
　CPUを明渡すことはせずに、指定した時間の間、ビジーループしたい場合はk_busy_wait()を使用する。単位はμsec。

前回：Zephyr入門（概要 & （スケジューラ：概要編））
次回：Zephyr入門（スケジューラ：システムコール編）

『各種製品名は、各社の製品名称、商標または登録商標です。本記事に記載されているシステム名、製品名には、必ずしも商標表示（(R)、TM）を付記していません。』