CFSのvruntimeの値の粒度 - akachochinの日記

Linuxのスケジューラ CFSの実装を読んでいる。このスケジューラはタスクの中で一番vruntimeの少ないタスクを次の動作タスクに選ぶ。

このvruntimeの粒度がどの程度のものか知りたくソースを読んだ。
結論から言うと、ナノ秒単位のモノトニックタイマがvruntimeのもとになっていることがわかった。

kernel/sched/fair.cの__update_curr()でvruntimeに足している値はdelta_exec_weighted。
delta_exec_weightedはdelta_execから作られる。
さらにdelta_execはupdate_curr()で「rq_of(cfs_rq)->clock_task」と「curr->exec_start」の差から作られる。
ということは「rq_of(cfs_rq)->clock_task」と「curr->exec_start」のいずれかの単位がわかれば目的が達成できることになる。

kernel/sched/fair.cを見ると、「curr->exec_start」はある時点での「rq->clock_task」である。
つまり、「rq->clock_task」の単位を調べるしかない。

grepすると、core.cにclock_taskを更新する関数があることがわかる。

 752 static void update_rq_clock_task(struct rq *rq, s64 delta)
 753 {
(略)
 804   rq->clock_task += delta;

update_rq_clock_task()を呼び出しているのがupdate_rq_clock()である。
こいつは以下の関数。

 117 void update_rq_clock(struct rq *rq)
 118 {
 119   s64 delta;
 120 
 121   if (rq->skip_clock_update > 0)
 122     return;
 123 
 124   delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
 125   rq->clock += delta;
 126   update_rq_clock_task(rq, delta);
 127 }

元になっているのが、sched_clock_cpu()であることがわかる。
この関数はkernel/sched/clock.cにいる関数。

sched_clock_cpu()はsched_clock_remote()もしくはsched_clock_local()経由で時間を取得している。
簡単そうなsched_clock_local()をみる。

CPUごとにsched_clock_data構造体を持っていて、こいつを使って時間を計算している。
やっていることは今ひとつよくわからんが、sched_clock()で取得している時間を使っていることから、この関数の戻り値の単位がわかれば目的達成ということになる。

sched_clock()はkernel/sched/clock.cで以下の様に定義されている。

 70 /*
 71  * Scheduler clock - returns current time in nanosec units.
 72  * This is default implementation.
 73  * Architectures and sub-architectures can override this.
 74  */
 75 unsigned long long __attribute__((weak)) sched_clock(void)
 76 {
 77   return (unsigned long long)(jiffies - INITIAL_JIFFIES)
 78           * (NSEC_PER_SEC / HZ);
 79 }
 80 EXPORT_SYMBOL_GPL(sched_clock);

この関数のコメントや実装から、モノトニックなタイマをナノ秒単位にしたものだということがわかる。さらにこの実装はweakシンボルなので、上書きが可能である。

ちなみにx86の場合、arch/x86/kernel/tsc.cにsched_clock()の別実装がある。
こいつはTSCの値を元にしてナノ秒単位のモノトニックな時間経過の値を返している。
TSCについては http://en.wikipedia.org/wiki/Time_Stamp_Counter を参考にすると良い。
今日は遅いので、ここでおしまい。