Linuxのスケジューラのデータ構造めも

linux kernel

Linuxのスケジューラはランキューには赤黒木を使っていて〜というところは見聞きしたことありますが、実際にどんなデータを使っていて、それらの関係は？と思ったので調べてみました。

スケジューラに関連する構造体はこれらのものがあります。

これらのうち、struct sched_classとstruct rqを除いたものたちはスケジューリングクラスに関連するものです。 Linuxのスケジューラはプロセスに対してスケジューリングポリシーを設定することができます。これはsched_setscheduler(2)にて行うことができます。 例えば、通常のプロセスの場合はSCHED_OTHERがスケジューリングポリシーとして設定され、この場合はスケジューリングクラスはstruct sched_entityとstruct cfs_rqが使われます。これらはCompletely Fair Schedulingクラスです。 rtがつくものはリアルタイムスケジューリングクラス、dlがつくものはdead lineスケジューリングクラスです。

で、これらを絵にしてみたのがこちらです。

f:id:masami256:20151102220618p:plain

コードを見た限り、struct sched_dl_entityとstruct sched_dl_rqは関連がなかったです。cfsとrtはランキューへのポインタを持ってましたが。

キューがどうなっているかを見てみると、cfsのランキュー(struct cfs_rq)は赤黒木で、rb_leftmostが次に動くプロセスだなってのがわかりますね。

344 struct cfs_rq {
345         struct load_weight load;
346         unsigned int nr_running, h_nr_running;
347 
348         u64 exec_clock;
349         u64 min_vruntime;
350 #ifndef CONFIG_64BIT
351         u64 min_vruntime_copy;
352 #endif
353 
354         struct rb_root tasks_timeline;
355         struct rb_node *rb_leftmost;
356

struct rt_rqのほうはというと、struct rt_prio_arrayという構造体があり、

440 /* Real-Time classes' related field in a runqueue: */
441 struct rt_rq {
442         struct rt_prio_array active;
443         unsigned int rt_nr_running;

優先度毎のリストで管理されてるようです。

126 /*
127  * This is the priority-queue data structure of the RT scheduling class:
128  */
129 struct rt_prio_array {
130         DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
131         struct list_head queue[MAX_RT_PRIO];
132 };

pick_next_rt_entity()がrt_rqのactive変数からsched_rt_entityの要素を取り出しているので、このstruct rt_prio_arrayがリアルタイムスケジューリングクラスのランキューでしょうね。

最後にDeadline Schedulingクラスを。struct dl_rqを見ると先頭に赤黒木の構造体があって、要素的にcfsと同じっぽいですね。

480 /* Deadline class' related fields in a runqueue */
481 struct dl_rq {
482         /* runqueue is an rbtree, ordered by deadline */
483         struct rb_root rb_root;
484         struct rb_node *rb_leftmost;

( ´ー｀)ﾌｩｰ．．．

Professional Linux Kernel Architecture

Professional Linux Kernel Architecture