Linuxスケジューラ - 概要
オペレーティングシステムの課題で発表するためにいろいろ調べたことをまとめてみようと思います。
章立てとしては、
というように書こうと思っています。(順番は、流れ的に良さそうな順にしました。O(1)は昔のやつだし、時間なかったら書かないでもいいかな・・・と思って一番下。）
git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git
コミット29594404d7fe73cd80eaa4ee8c43dcc53970c60eのものを使っています。
linux 3.7です。
スケジューラはsched_classという構造体のリスト構造になっていて、そこに異なるスケジューラがそれぞれ存在する、という実装になっています。
HEADになるクラスはstop_sched_classで、これはほぼ中身は空で、ここにタスクが入るとすべてのタスクがpreemptすることができません。(kernel/sched/stop_task.c)
このクラスのnextがrt_sched_classになっています。これはkernel/sched/rt.cに実装されていて、SCHED_FIFO/RRのポリシーが実装されています。
その次がfair_sched_class。CFS(completely fair scheduler)の実装はココ(kernel/sched/fair.c)で行われています。
最後がidle_sched_class。これはSCHED_IDLEポリシーで用いられるクラスで、他に何もすることがないときに実行されるクラスになっています。
これらのsched_classをなめるのがfor_each_classマクロになっていて、kernel/sched/sched.hに定義されています。これを利用している典型的な場所がpick_next_task(kernel/sched/core.c l.2753)であり、一番優先順位の高い（次に実行すべき）タスクを選択することができます。
/*
* Pick up the highest-prio task:
*/
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
const struct sched_class *class;
struct task_struct *p;
/*
* Optimization: we know that if all tasks are in
* the fair class we can call that function directly:
*/
if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
p = fair_sched_class.pick_next_task(rq);
if (likely(p))
return p;
}
for_each_class(class) {
p = class->pick_next_task(rq);
if (p)
return p;
}
BUG(); /* the idle class will always have a runnable task */
}
高速化の工夫として、CFSを特別に先に判断してるみたいです。
なお、ここで出てくるlikelyオプションも最適化の工夫らしく、likely/unlikelyで真/偽になりやすいときにいい感じに最適化されるようになるらしいです。(Kernel : likely/unlikely macros | KernelTrap)
このpick_next_taskを読んでいるのがschedule(もっと正確には__schedule)(kernel/sched/core.c l.2814)で、これがスケジューラの中心になります。
実際にタスクを移動させているのは以下の部分。
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
++*switch_count;
context_switch(rq, prev, next); /* unlocks the rq */
/*
* The context switch have flipped the stack from under us
* and restored the local variables which were saved when
* this task called schedule() in the past. prev == current
* is still correct, but it can be moved to another cpu/rq.
*/
cpu = smp_processor_id();
rq = cpu_rq(cpu);
} else
raw_spin_unlock_irq(&rq->lock);
このうち、context_switchがメモリを直したりレジスタ退避したりなどを行なっているが、その中でもswitch_toマクロが面白いと思ったので下に書いておきます。
/*
* Saving eflags is important. It switches not only IOPL between tasks,
* it also protects other tasks from NT leaking through sysenter etc.
*/
#define switch_to(prev, next, last) \
do { \
/* \
* Context-switching clobbers all registers, so we clobber \
* them explicitly, via unused output variables. \
* (EAX and EBP is not listed because EBP is saved/restored \
* explicitly for wchan access and EAX is the return value of \
* __switch_to()) \
*/ \
unsigned long ebx, ecx, edx, esi, edi; \
\
asm volatile("pushfl\n\t" /* save flags */ \
"pushl %%ebp\n\t" /* save EBP */ \
"movl %%esp,%[prev_sp]\n\t" /* save ESP */ \
"movl %[next_sp],%%esp\n\t" /* restore ESP */ \
"movl $1f,%[prev_ip]\n\t" /* save EIP */ \
"pushl %[next_ip]\n\t" /* restore EIP */ \
__switch_canary \
"jmp __switch_to\n" /* regparm call */ \
"1:\t" \
"popl %%ebp\n\t" /* restore EBP */ \
"popfl\n" /* restore flags */ \
\
/* output parameters */ \
: [prev_sp] "=m" (prev->thread.sp), \
[prev_ip] "=m" (prev->thread.ip), \
"=a" (last), \
\
/* clobbered output registers: */ \
"=b" (ebx), "=c" (ecx), "=d" (edx), \
"=S" (esi), "=D" (edi) \
\
__switch_canary_oparam \
\
/* input parameters: */ \
: [next_sp] "m" (next->thread.sp), \
[next_ip] "m" (next->thread.ip), \
\
/* regparm parameters for __switch_to(): */ \
[prev] "a" (prev), \
[next] "d" (next) \
\
__switch_canary_iparam \
\
: /* reloaded segment registers */ \
"memory"); \
} while (0)
これまで、「スケジューリングって言うけどレジスタとか残ってるし関数ジャンプみたいにpush/popとかするのもいつ戻ってくるのかわからないしどうやってやるんだろう・・・？」と思ってたのが解消されました。それぞれがスタックポインタを構造体のメンバとして持っていて、スイッチのときにそこに突っ込んだり戻したりしてるってことでよさそう。
で、問題はここからでschedulerが呼ばれると次に実行すべきタスクが決まって、それに応じてスイッチしたりしなかったりするというのは理解したのですが、どうもnohzというものが存在するらしい。
tickless kernelと呼ばれるもので、tickごとに定期的にCPUが起こされたりすることがないので消費電力的に有利といったメリットがあるらしい。(Ticklessカーネルとクロックソースに関するお話 - めもめも) 結構これのソースが多くてどうしても目に付いた(****_nohzとかいう関数が沢山有る)のですが、わからないのはtickが無いのにいつscheduleを呼ぶんだ！ということです。ここについては未だにあまりよくわかっていないです。うーむ。
これと関連して、タイマについて少し調べてみました。
まず、クロックとしてはRTC/TSC/PIT/HPET/ACPI_PMTなどがあるそうです。(詳解Linuxカーネル p242)
TSCはプロセッサにあるレジスタであり、rdtsc命令で読み出すことができます。これはCPUのクロックごとにカウントアップされるそうです。
また、
cat /sys/devices/system/clocksource/clocksource0/available_clocksource
とすると自分のPCにどんなクロック源があるかがわかります。自分のPCではhpet acpi_pmと出ました。
hpetは最近出てきた新しいタイマチップであり、割り込みとかの発生に関してオーバーヘッドが少ない/割り込みの本数が多いようです。ちなみに、これまで利用されていたものはPIT(Programmable Interval Timer)と呼ばれるもので、8254COMSチップで実装されているそうです。これにより1kHzの割り込みを発生させているらしいです。
タイマについてもオブジェクトになっていて、timer_[タイマ名]という名前で記述されています。
次に、しょっちゅう出てくるjiffiesについてです。
これは、システムが起動されてからのtick数をカウントします。64bitで保持していますが、32bitのシステムでは64bitをアトミックに読むのが手間なので32bit変数として扱います。また、注意すべき点としては、jiffiesの初期値は-300,000になっており、5分でオーバーフローして0になるようになっているらしいです。これはオーバーフローにシステムが対応しているか簡単に確認できて、バグ出しが出来るという意味があるそうです。
また、これとは別にtimespec型のxtime変数というものもあり、これによってナノ秒単位で時刻が記録されます。
参考：
O'Reilly Japan - 詳解 Linuxカーネル 第3版
Linux カーネル 2.6 Completely Fair Scheduler の内側
