見出し画像

Linuxのスケジューラを理解する(for 自作OS)

LearningHorse

この記事の概要

今回は、自作OSでLinuxのスケジューラをベースとした実用的なタスクスケジューラを実装するため、Linuxのタスクスケジューラについて調べていこうと思います。
いつもならコーディングと同時並行するところですが、あまりにもスケジューラは複雑なので、あくまでこれ単体の記事にすることにしました。それでは、スケジューラの全体像から調べて行きます。
（一応自作OSの前回の記事のリンクを貼っておきます）


スケジューラの概要

まず、スケジューラが何をしているのかというと、スケジューラはタスクの優先順位に基づいて、プレエンプションを行ったりすることで、タスクを処理する順番および時間を決めています。

ランキュー

この処理を行う上で、最も基本的なものがランキューです。ランキューは実行すべきタスクを保持しており、ここに登録されたタスクに対し、スケジューラが適切にCPUを割り当てます。Linuxでは、CPUごとにランキューを作ることで、キューのロック処理によるオーバーヘッドを避けています。

優先度

スケジューラは優先度に基づいて、どれだけタスクにCPUを割り当てるか、さらにはスケジューリングの方法を決定します。具体的には、NICE値などのタスクごとの優先度を元に、そのスケジューリングポリシーを決定し、そのポリシーに基づいて優先度が処理され、タスクにCPUが割り当てられます。

ロードバランシング

ロードバランシングとは読んで字の如く負荷の分散です。複数のCPUの負荷のバランスが偏りすぎると、他のCPUにタスクを移動します。
本当はやった方がいいんですが、実装が難しいので自作OSでは一旦実装しない予定です。

NICE値について

NICE値とは、主にユーザー側からタスクの優先度を設定するのに使われる値で、-20~19の範囲をとり、小さいほど優先度が高いです。
このNICE値は1違うとCPUの割り当て時間が約1.25倍になることが知られている。これは、NICEが実際に使われる際、load_weightという重みに変換される際、約1.25倍でずれるように定義されている。具体的には、この配列がそれに使われている。

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

計算すると結構ズレがあるが、そこの理由までは知らない。とりあえずこれが使われているところを調べてみると、set_load_weightというところでniceをload_weightに変換するのに使われている。さらに、set_load_weightが使われているのは

  • sched_fork：子プロセスへのフォーク

  • set_user_nice：ユーザーからのNICE値の変更の反映

  • __setschedular_params：内部的にNICE値を設定しているのか？（詳細不明）

  • sched_init：initプロセスの優先度設定

といった感じ、とりあえず最初と最後を実装すれば動くだろう。

スケジューラーの実装

ここからは実際にどのようにLinuxがスケジューラーを実装しているのかを簡単に説明していきます。

スケジューリングクラス

Linuxではスケジューリングに使用するアルゴリズムごとにクラスが存在しています。スケジューリングポリシーと呼ばれるものもありますが、大枠は同じでも若干まとめ方が変わったり、名前が変わったりします。とりあえず基本的なものを以下に挙げます。

  • Stop-Task クラス
    最も優先度が高く、他のどのクラスのタスクもプリエンプトして実行される

  • Deadline-Task クラス
    タスクが終了する期限を保証して実行してくれる。原則期限が早いものから実行される。(アルゴリズムはEDF+CBS)

  • Realtime-Task クラス
    一般のタスクより高い優占度で実行される。アルゴリズムはFIFOかラウンドロビン方式

  • Fair-Task クラス
    一般のタスクがこれを使う。アルゴリズムはCFS（後述）

  • Idle-Task クラス
    他のタスクが実行されていない時に実行される。

上から優先度が高いクラスなので、基本的に上のクラスのタスクが存在する限り下のクラスは実行されません。上3つのアルゴリズムは正直「やばいやつから終わらせる」みたいな感じでそんなに複雑ではないですが、CFSは少々複雑なのでこれを次に見ていきます。

CFS (Completely Fair Schedular)

これも読んで字のごとく完全に公平なスケジューラーということで、CPU時間を各タスクが公平に利用できるような仕組みです。まず、Fairクラスのタスクはvruntime（仮想実行時間）というものを持ちます。これはvruntime = （実行時間）×(NICE値で決まる重み)として算出されて、この値が小さいものから順に実行されます。このvruntimeのソートには高速にアクセスできる赤黒木という構造体が用いられます。そして、vruntimeに対応するように保存されているのがSchedEntityクラスで、ここにスケジューリングに必要なタスクの情報が保存されています。

でここからが少し大事で、赤黒木から実行するタスクのスケジュールエンティティ構造体を取得したあと、ぱっと見だとスケジュールエンティティ構造体の中にはtask_structへのポインタが見当たらないので、おそらくcontainer_ofでタスク本体の構造体へとアクセスしています。

まとめ

なんというかまだコードを書いてないのでふわっとした感じの理解で、内容も具体性に欠けるものですが、これで概要は理解できたと思うので実装したらまたコードと共に解説を書こうと思います。
ところで、この投稿は非常に久しぶり（まさかの10月以来！）ですが、その間非常に忙しく、これ以降もかなり不定期になりそうですが、OS開発を止める気は毛頭ないので今後も少しづつ進めていくつもりです（マルチタスクの実装はできれば一ヶ月以内にはやりたい）。

この記事が気に入ったらサポートをしてみませんか？