プロセス、スケジューリング関連

					2012年12月25日
情報科学類 オペレーティングシステム II

                                       筑波大学 システム情報工学研究科 
                                       コンピュータサイエンス専攻, 電子・情報工学系
                                       新城 靖
                                       <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2012/2012-12-25
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

■今日の大事な話

優先順位式スケジューリング
nice値の意味
スケジューラ
木構造によるレディ・キューの実装

■復習(オペレーティングシステム Iの範囲)

◆スケジューリングの目標

CPU 使用率を上げる。
スループット(単位時間辺りの仕事量)を上げる。
ターンアラウンド時間(プロセスを生成してから完了するまで)を短くする。
レディ・キューでの待ち時間を短くする。
応答時間を短くする。
プロセスに公平な CPU 時間を割り当てる。
(実時間制約を満たす)

全部は同時には成り立たない。

◆スケジューリング・アルゴリズム

FCFS (Firt-Come, First-Served), FIFO (First-In First-Out)
最短ジョブ優先(Shortest Job First)
優先度スケジューリング。飢餓状態(starvation)を起こす。 aging で優先度を上げる。
Round-Robin。時間刻み(time slice)ごとに切り替える。

◆優先順位式スケジューリング(OS一般)

プロセスごとに優先度を割り当てる。
OS は、実行可能で優先度が最も高くプロセスを(CPUの数だけ)実行する。同じものが複数あれば、ラウンドロビン。
プロセスの優先度は、利用したCPU資源や入出力のパタンで動的に変更する。

◆レディ・キュー(OS一般)

レディ・キューは、レディ状態のプロセスのリスト。優先度の順に並んでいれば、CPU はリストの先頭から要素を取り出して実行する。

■プロセス・スケジューリング関連のAPI

◆Unixにおけるプロセスに関するシステム・コール

nice(), getpriority(), setpriority(): nice値(優先度)の操作。値が小さい方が優先度が高い。一般ユーザは、値を大きくすることだけできる。値の範囲は、-20から19が普通。
sched_getscheduler(), sched_setscheduler(): POSIX 実時間拡張でのスケジューリング・ポリシーと優先度との設定。ポリシーは、SCHED_FIFO (first-in first-out), SCHED_RR (round robin), SCHED_OTHER (その他)。
sched_get_priority_max()、sched_get_priority_min(): 各ポリシーでの優先度の最大と最小を表す整数値。システムによって整数値が異なる。数字が大きい方が、優先度が高い。min < max になっている。

注意: Linux そのものは、実時間OSではない。本当に決められた時間内に完了するが求められる処理（ハードリアルタイム）には使えない。少し遅れても意味がある（ソフトリアルタイム）には、使えることがある。

◆ps -lコマンド

ps -l の結果のうち、次の属性に注目。

表示	説明
NI	Nice。優先度を表す値。

$ ps -l 
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
0 S  1000 28765 28759  0  80   0 -  1363 wait   pts/0    00:00:00 bash
0 T  1000 28825 28765  0  80   0 -  1270 signal pts/0    00:00:00 man
0 T  1000 28832 28825  0  80   0 -  1183 signal pts/0    00:00:00 less
0 T  1000 28833 28765  0  80   0 -  7606 signal pts/0    00:00:00 emacs
0 R  1000 28836 28765  0  80   0 -  1216 -      pts/0    00:00:00 ps
$ /bin/nice ps -l 
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
0 S  1000 28765 28759  0  80   0 -  1363 wait   pts/0    00:00:00 bash
0 T  1000 28825 28765  0  80   0 -  1270 signal pts/0    00:00:00 man
0 T  1000 28832 28825  0  80   0 -  1183 signal pts/0    00:00:00 less
0 T  1000 28833 28765  0  80   0 -  7606 signal pts/0    00:00:00 emacs
0 R  1000 28837 28765  0  90  10 -  1216 -      pts/0    00:00:00 ps
$ /bin/nice -19 ps -l 
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
0 S  1000 28765 28759  0  80   0 -  1363 wait   pts/0    00:00:00 bash
0 T  1000 28825 28765  0  80   0 -  1270 signal pts/0    00:00:00 man
0 T  1000 28832 28825  0  80   0 -  1183 signal pts/0    00:00:00 less
0 T  1000 28833 28765  0  80   0 -  7606 signal pts/0    00:00:00 emacs
0 R  1000 28841 28765  0  99  19 -  1216 -      pts/0    00:00:00 ps
$

ps コマンドの NI には、nice値が表示される。
nice 値を変更してプロセスを生成するには、nice コマンドが使える。デフォルトで 10 に設定される。

◆getpriority-pid.c

   1:	/*
   2:	        getpriority-pid.c -- 優先度の表示
   3:	        ~yas/syspro/proc/getpriority-pid.c
   4:	        Created on: 2009/12/14 12:15:11
   5:	*/
   6:	
   7:	#include <stdio.h>              /* stderr, fprintf() */
   8:	#include <sys/time.h>           /* getpriority() */
   9:	#include <sys/resource.h>       /* getpriority() */
  10:	#include <stdlib.h>             /* strtol() */
  11:	#include <limits.h>             /* strtol() */
  12:	
  13:	main( int argc, char *argv[] )
  14:	{
  15:	    int which, who, prio;
  16:	    pid_t pid;
  17:	        if( argc != 2 )
  18:	        {
  19:	            fprintf(stderr,"Usage: %% %s pid\n",argv[0] );
  20:	            exit( 1 );
  21:	        }
  22:	        pid = strtol( argv[1], NULL, 10 );
  23:	        prio = getpriority( PRIO_PROCESS, pid );
  24:	        printf("pid==%d, priority==%d\n", pid, prio);
  25:	}

$ echo $$ 
3788
$ ./getpriority-pid  
Usage: % ./getpriority-pid pid
$ ./getpriority-pid $$ 
pid==3788, priority==0
$ ./getpriority-pid 0  
pid==0, priority==0
$ nice -10 ./getpriority-pid 0  
pid==0, priority==10
$ nice -20 ./getpriority-pid 0 
pid==0, priority==19
$

シェルの PID は、$$ という変数で参照できる。
PID として 0 を指定すると、自分自身(シェルから継承)が表示される。
nice コマンドで値を大きくできる。最大20。 (特権ユーザは、値を小さくできる。)

◆nice値の利用法

優先度の調整方法

主にCPUを使うプロセスの優先度を下げて走らせる。Matlab とかビデオ・エンコーダとか。
(対話的な処理で入出力で待ちが多いプロセスの優先度を上げる。)

nice値の厳密な「意味」は、Unix の実装で異なる。 nice値とCPU時管理割当て方の標準はない。 Linux でも、何度か変更されている。

◆Linux(CFS)での通常のプロセス(非実時間プロセス)でのnice値の意味

nice値が1増えると、相対的に10%だけCPU時間の割当てが少なくなるようにする。

例1: 次の2つの CPU-bound のプロセスが存在したとする。

プロセスA: nice値0
プロセスB: nice値1 (優先度が低い)

AのCPU時間 : BのCPU時間 == 1 : 0.9

◆ps コマンドでの実時間用の優先度の表示

# ps -o state,uid,pid,ppid,policy,pri,ni,rtprio,time,comm 
S   UID   PID  PPID POL PRI  NI RTPRIO     TIME COMMAND
S     0 29103 29041 TS   19   0      - 00:00:00 su
S     0 29110 29103 TS   19   0      - 00:00:00 bash
T     0 29226 29110 TS   19   0      - 00:00:00 emacs
T     0 29227 29110 TS   19   0      - 00:00:00 man
T     0 29234 29227 TS   19   0      - 00:00:00 less
R     0 29247 29110 TS   19   0      - 00:00:00 ps
# /bin/nice --10 ps -o state,uid,pid,ppid,policy,pri,ni,rtprio,time,comm 
S   UID   PID  PPID POL PRI  NI RTPRIO     TIME COMMAND
S     0 29103 29041 TS   19   0      - 00:00:00 su
S     0 29110 29103 TS   19   0      - 00:00:00 bash
T     0 29226 29110 TS   19   0      - 00:00:00 emacs
T     0 29227 29110 TS   19   0      - 00:00:00 man
T     0 29234 29227 TS   19   0      - 00:00:00 less
R     0 29248 29110 TS   29 -10      - 00:00:00 ps
# chrt 50 ps -o state,uid,pid,ppid,policy,pri,ni,rtprio,time,comm 
S   UID   PID  PPID POL PRI  NI RTPRIO     TIME COMMAND
S     0 29103 29041 TS   19   0      - 00:00:00 su
S     0 29110 29103 TS   19   0      - 00:00:00 bash
T     0 29226 29110 TS   19   0      - 00:00:00 emacs
T     0 29227 29110 TS   19   0      - 00:00:00 man
T     0 29234 29227 TS   19   0      - 00:00:00 less
R     0 29249 29110 RR   90   -     50 00:00:00 ps
#

ps コマンドで -o を与え、rtprio を指定する。
"-" の表示は、実時間のプロセスではない。
root (特権ユーザ) ならば、優先度を上げてプログラムを実行できる(nice --10)。
root (特権ユーザ) ならば、実時間の優先でプログラムを実行できる(chrtコマンド)。

◆スケジューリングを行うためのハードウェア

やりたいことの例: 今のプロセスを 50ミリ秒だけ実行して、50ミリ秒後に別のプロセスを実行したい。

目覚まし時計を使う。ある時間がたったら割り込みを発生させるハードウェアを用いる。例: 50ミリ秒後にセットして、プロセスを実行する。割り込みが発生したら、プロセスを切り替える。
定期的な割り込みを使う。例: 10ミリ秒間隔で、割り込みを掛けるようにしかける。プロセスの実行中に、 5 回割り込みが発生したら、プロセスを切り替える。

Unix では、定期的な割り込み(10ミリ秒から1ミリ秒に1回)を使う方法がよく使われる。 1回の割り込みを tick という。

■Linux task構造体とnice値

Linux のプロセスは、task 構造体で表現されている。

◆task_struct構造体

linux-3.6.8/include/linux/sched.h

1234:	struct task_struct {
1235:	        volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
...
1247:	        int prio, static_prio, normal_prio;
1248:	        unsigned int rt_priority;
1249:	        const struct sched_class *sched_class;
1250:	        struct sched_entity se;
1251:	        struct sched_rt_entity rt;
...
1274:	        unsigned int policy;
...
1592:	};

1178:	struct sched_entity {
...
1180:	        struct rb_node          run_node;
...
1182:	        unsigned int            on_rq;
...
1186:	        u64                     vruntime;
...
1202:	};

struct task_struct の中に、prio 等のフィールドやstruct sched_entity がある。

◆policy

Linux では、スケジューリングのポリシーが大きく2種類。通常の時分割と実時間。

linux-3.6.8/include/linux/sched.h
  36:	#define SCHED_NORMAL            0
  37:	#define SCHED_FIFO              1
  38:	#define SCHED_RR                2
  39:	#define SCHED_BATCH             3
  40:	/* SCHED_ISO: reserved but not implemented yet */
  41:	#define SCHED_IDLE              5

SCHED_NORMAL: 伝統的なプロセス。時分割(time sharing)
SCHED_BATCH: パッチ向け。一度CPUを割り当てたら横取りしない。
SCHED_IDLE: nice 19 よりも低い優先度。
SCHED_FIFO (first in first out): 実時間で FIFO
SCHED_RR (round robin): 実時間でラウンドロビン

◆prioとstatic_prio

static_prio

nice値を保持する。ただし、次のようなゲタを履かせている (NICE_TO_PRIO()参照)。

nice値の範囲 -20..19 を 0..39 にするために 20
実時間(realtime) のプロセスと区別するための 100 (MAX_RT_PRIO)

prio

スケジューリングに用いる優先度を保持する。

prio を見ると、通常のプロセスか実時間のプロセスかがわかる。 100 以上なら、通常のプロセス。通常のプロセスの prio は、100から140。

◆getpriority()システム・コール

linux-3.6.8/kernel/sys.c

 235:	/*
 236:	 * Ugh. To avoid negative return values, "getpriority()" will
 237:	 * not return the normal nice-value, but a negated value that
 238:	 * has been offset by 20 (ie it returns 40..1 instead of -20..19)
 239:	 * to stay compatible.
 240:	 */
 241:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 242:	{
 243:	        struct task_struct *g, *p;
 244:	        struct user_struct *user;
 245:	        const struct cred *cred = current_cred();
 246:	        long niceval, retval = -ESRCH;
 247:	        struct pid *pgrp;
 248:	        kuid_t uid;
 249:	
 250:	        if (which > PRIO_USER || which < PRIO_PROCESS)
 251:	                return -EINVAL;
...
 255:	        switch (which) {
 256:	                case PRIO_PROCESS:
 257:	                        if (who)
 258:	                                p = find_task_by_vpid(who);
 259:	                        else
 260:	                                p = current;
 261:	                        if (p) {
 262:	                                niceval = 20 - task_nice(p);
 263:	                                if (niceval > retval)
 264:	                                        retval = niceval;
 265:	                        }
 266:	                        break;
 267:	                case PRIO_PGRP:
...
 278:	                case PRIO_USER:
...
 297:	        }
...
 228:	out_unlock:
...
 232:	        return error;
 233:	}

linux-3.6.8/include/linux/sched.h
1610:	#define MAX_USER_RT_PRIO        100
1611:	#define MAX_RT_PRIO             MAX_USER_RT_PRIO
1612:	
1613:	#define MAX_PRIO                (MAX_RT_PRIO + 40)
1614:	#define DEFAULT_PRIO            (MAX_RT_PRIO + 20)

linux-3.6.8/kernel/sched/sched.h
  16:	#define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
  17:	#define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
  18:	#define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)

linux-3.6.8/kernel/sched/core.c
4169:	int task_nice(const struct task_struct *p)
4170:	{
4171:	        return TASK_NICE(p);
4172:	}

getpriority() は、which と who の 2引数。
which が PRIO_PROCESS なら、who は、pid。
who が 0 なら、自分自身(current)。
who が 0 以外なら find_task_by_vpid()でプロセスを探す。
プロセスが見つかれば、task_nice() で task_struct の static_prio の値を返す。この時、ゲタをはかせた分ゲタをはかせた分を引く。
さらに、システム・コールが負の値を返すとエラーの意味になるので、それを避けるために正の値に置換える。具体的には、-20,-19,-18,...17,18,19 を 40,39,38,...,3,2,1 に変換する。
正の値に置換えられた値は、ユーザ空間のライブラリで元にもどされる。

glibc-2.5/sysdeps/unix/sysv/linux/getpriority.c
  28:   #define PZERO 20
...
  35:   int
  36:   getpriority (enum __priority_which which, id_t who)
  37:   {
  38:     int res;
  39:
  40:     res = INLINE_SYSCALL (getpriority, 2, (int) which, who);
  41:     if (res >= 0)
  42:       res = PZERO - res;
  43:     return res;
  44:   }

◆se.load.weight

struct task_struct の static_prio は、struct task_struct の se.load.weight の値を決めるために使われる。


linux-3.6.8/kernel/sched/sched.h

 795:	/*
 796:	 * Nice levels are multiplicative, with a gentle 10% change for every
 797:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 798:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 799:	 * that remained on nice 0.
 800:	 *
 801:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
 802:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 803:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 804:	 * If a task goes up by ~10% and another task goes down by ~10% then
 805:	 * the relative distance between them is ~25%.)
 806:	 */
 807:	static const int prio_to_weight[40] = {
 808:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
 809:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
 810:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
 811:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 812:	 /*   0 */      1024,       820,       655,       526,       423,
 813:	 /*   5 */       335,       272,       215,       172,       137,
 814:	 /*  10 */       110,        87,        70,        56,        45,
 815:	 /*  15 */        36,        29,        23,        18,        15,
 816:	};
...

linux-3.6.8/kernel/sched/core.c

 695:	static void set_load_weight(struct task_struct *p)
 696:	{
 697:	        int prio = p->static_prio - MAX_RT_PRIO;
 698:	        struct load_weight *load = &p->se.load;
...
 709:	        load->weight = scale_load(prio_to_weight[prio]);
 710:	        load->inv_weight = prio_to_wmult[prio];
 711:	}

linux-3.6.8/include/linux/sched.h
 840:	# define scale_load(w)          (w)

struct task_struct の優先度 static_prio は、struct task_struct の struct sched_entity se の se.load.weight とその逆数se.load.inv_weight　に反映される。se.load.{weight,inv_weight} の値は、後に、vruntime の計算の重みづけに使われる。

■スケジューラとレディ・キュー

◆sched_class

オブジェクト指向のクラスと同じ意味。スケジューラのための手続きの集合。

sched_classの主要な手続き
名前	説明
enqueue_task	プロセスが実行可能(runnable)になった
dequeue_task	プロセスが実行可能ではなくなった
yield_task	CPUを譲る。dequeueしてenqueue
check_preempt_curr	実行可能になった時にCPUを横取りすべきかをチェック
pick_next_task	次に実行すべきプロセスを選ぶ
set_curr_task	スケジューリング・クラスが変更された
task_tick	タイマ割込み(tick)の時に呼ばれる
task_new	新しいプロセスが生成された

◆sched_class使い方

プロセスのクラスに応じて enqueue、 dequeue の操作を切り替える。

linux-3.6.8/kernel/sched/core.c

 713:	static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
 714:	{
 715:	        update_rq_clock(rq);
 716:	        sched_info_queued(p);
 717:	        p->sched_class->enqueue_task(rq, p, flags);
 718:	}
 719:	
 720:	static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 721:	{
 722:	        update_rq_clock(rq);
 723:	        sched_info_dequeued(p);
 724:	        p->sched_class->dequeue_task(rq, p, flags);
 725:	}

プロセスのクラスに応じて struct task_struct の sched_class の値が違う。
プロセスのクラスに応じて、enqueue_task(), dequeue_task() は別の関数が呼ばれる。

◆Linuxの主要なスケジューリング・クラス

fair_sched_class: 公平を目指す。task_struct の policy が SCHED_NORMAL の時に使われる。
rt_sched_class: 実時間を目指す。task_struct の policy が SCHED_FIFO と SCHED_RR の時に使われる。

◆スケジューラ・クラスの設定

linux-3.6.8/kernel/sched/core.c

4216:	static void
4217:	__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
4218:	{
4219:	        p->policy = policy;
4220:	        p->rt_priority = prio;
4221:	        p->normal_prio = normal_prio(p);
4222:	        /* we are holding p->pi_lock already */
4223:	        p->prio = rt_mutex_getprio(p);
4224:	        if (rt_prio(p->prio))
4225:	                p->sched_class = &rt_sched_class;
4226:	        else
4227:	                p->sched_class = &fair_sched_class;
4228:	        set_load_weight(p);
4229:	}

linux-3.6.8/include/linux/sched.h

1616:	static inline int rt_prio(int prio)
1617:	{
1618:	        if (unlikely(prio < MAX_RT_PRIO))
1619:	                return 1;
1620:	        return 0;
1621:	}

task_struct の sched_class は、 p->prio の値に応じて &rt_sched_class か &fair_sched_class のどちらかを指す。
if 文の中に入っている likely() や unlikely() は無視して良い。 (分岐予測による最適化に使われる。)

◆CFS(Completely Fair Scheduler)

CFS は、Linux のスケジューラの固有名詞。 fair を目指してはいるが、complete に fair かと言われると不明。

Linux CFS は、次の方法でスケジューリングを行なう。

各プロセスの se.vruntime (ナノ秒単位) が消費したCPU時間をもつ。
プロセスは、se.vruntime が小さい順にソートされたリストにつながれる。
スケジューラは、se.vruntime が最も小さいプロセス(リストの一番左) を実行する。
スケジューラは、実行した時間を現在実行しているプロセスの se.vruntime に加える。
ある程度、実行すると、現在実行中のプロセスのse.vruntime よりも、リストのものが小さくなる。そうなると、リストを作り直す。現在実行中のプロセスは、リストの先頭ではなくなる。
作り直したリストから se.vruntime が最も小さいプロセス(リストの一番左) を実行する。
ただし、あまり激しく切り替えると、キャッシュが効かなくなるので、ある granularity は、実行しつづける。

◆runqueues(リスト的な見方)

Linux における ready queue の1実装では、tasks_timeline を出発点とするリストと考えて良い。実際には、struct sched_entity se (struct task_structの途中) をつないでいく。

図? runqueueの構造

linux-3.6.8/kernel/sched/sched.h

 348:	struct rq {
...
 371:	        struct cfs_rq cfs;
 372:	        struct rt_rq rt;
...
 470:	};

 202:	struct cfs_rq {
...
 212:	        struct rb_root tasks_timeline;
 213:	        struct rb_node *rb_leftmost;
...
 272:	};

linux-3.6.8/kernel/sched/core.c

 112:	DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

(CPUごとに) runqueue がある。
runqueue には、CFS(Completely Fair Scheduler))のための構造体 cfs_rq (cfs run queue)がある。
cfs_rq には、tasks_timeline がある。
tasks_timeline は、プロセス(task_struct) の se (struct sched_entity) を通じて、プロセスのリストを持っている。

◆赤黒木(red-black tree (rbtree))

赤黒木(red-black tree) は、平衡二分探索木(self-balancing binary search tree)の一種。節は、赤と黒に分類される。

二分探索木とは、次のような二分木。

各節にキーがある。
左の部分木は、根よりも小さいキーだけをもつ二分探索木。
左の部分木は、根よりも小さいキーだけをもつ二分探索木。

平衡木(balanced tree)、または、高さ平衡木(height-balanced tree)は、任意の節で左右の高さの差が一定以下木。

Linux では、赤黒木をソートされた要素が並ぶリストを実現するために使っている。

◆Linux red-black treeの基本操作

型定義で、各要素に次の要素を含める。

struct rb_node node (rb_right, rb_left, rb_parent_color)
キーになるフィールド

検索

現在のノードとキーを比較
等しいなら見つかった
キーが小さいなら左の枝へ
キーが大きいなら右の枝へ
枝がなければキーは存在しない

挿入

まず検索する。現在のノードと挿入したいデータのキーを比較する。
キーが小さいなら左の枝を「親」にして検索を続ける。
キーが大きいなら右の枝を「親」にして検索を続ける。
キーが等しいならエラー(エラーにせず、重複を許すこともある)
子供がいない「親」が見つかる。
「親」から挿入したいデータへのリンクを作成する(rb_link_node())
平衡になるようにする(rebalancing, recoloring, rb_insert_color())

◆runqueues(red-black tree)

レディ・キューは、実際にはred-black tree による木構造になっている。 tasks_timeline は、木の根を差す。

図? runqueueの構造(red-black tree)

◆__enqueue_entity()

__enqueue_entity()は、CFS で木構造に要素を1個追加する関数である。

linux-3.6.8/kernel/sched/fair.c

 478:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 479:	{
 480:	        struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
 481:	        struct rb_node *parent = NULL;
 482:	        struct sched_entity *entry;
 483:	        int leftmost = 1;
 484:	
 485:	        /*
 486:	         * Find the right place in the rbtree:
 487:	         */
 488:	        while (*link) {
 489:	                parent = *link;
 490:	                entry = rb_entry(parent, struct sched_entity, run_node);
 491:	                /*
 492:	                 * We dont care about collisions. Nodes with
 493:	                 * the same key stay together.
 494:	                 */
 495:	                if (entity_before(se, entry)) {
 496:	                        link = &parent->rb_left;
 497:	                } else {
 498:	                        link = &parent->rb_right;
 499:	                        leftmost = 0;
 500:	                }
 501:	        }
 502:	
 503:	        /*
 504:	         * Maintain a cache of leftmost tree entries (it is frequently
 505:	         * used):
 506:	         */
 507:	        if (leftmost)
 508:	                cfs_rq->rb_leftmost = &se->run_node;
 509:	
 510:	        rb_link_node(&se->run_node, parent, link);
 511:	        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
 512:	}

 444:	static inline int entity_before(struct sched_entity *a,
 445:	                                struct sched_entity *b)
 446:	{
 447:	        return (s64)(a->vruntime - b->vruntime) < 0;
 448:	}

平衡二分探索木の一種、red-black tree に節を追加している。
キーは、vruntime。vruntime が小さいほど左に来る。
vruntime が現在のノードより小さければ、左(&parent->rb_left), 大きければ右(&parent->rb_right) に進む。
一番左なら、キャッシュとして cfs_rq->rb_leftmost にも保存。
最後に rb_insert_color() を呼び出して、バランスを回復する。

◆tickごとの仕事

scheduler_tick() は、tick ごとに定期的に呼び出される。 1 tick は、10 ミリ秒、4ミリ秒、1 ミリ秒等が一般的。

linux-3.6.8/kernel/sched/core.c
3214:	void scheduler_tick(void)
3215:	{
3216:	        int cpu = smp_processor_id();
3217:	        struct rq *rq = cpu_rq(cpu);
3218:	        struct task_struct *curr = rq->curr;
...
3225:	        curr->sched_class->task_tick(rq, curr, 0);
...
3234:	}

sched_class クラスの task_tick() を呼び出す。

◆entity_tick()

linux-3.6.8/kernel/sched/fair.c

4981:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
4982:	{
4983:	        struct cfs_rq *cfs_rq;
4984:	        struct sched_entity *se = &curr->se;
4985:	
4986:	        for_each_sched_entity(se) {
4987:	                cfs_rq = cfs_rq_of(se);
4988:	                entity_tick(cfs_rq, se, queued);
4989:	        }
4990:	}

1347:	static void
1348:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
1349:	{
...
1353:	        update_curr(cfs_rq);
...
1377:	        if (cfs_rq->nr_running > 1)
1378:	                check_preempt_tick(cfs_rq, curr);
1379:	}

 684:	static void update_curr(struct cfs_rq *cfs_rq)
 685:	{
 686:	        struct sched_entity *curr = cfs_rq->curr;
 687:	        u64 now = rq_of(cfs_rq)->clock_task;
 688:	        unsigned long delta_exec;
...
 698:	        delta_exec = (unsigned long)(now - curr->exec_start);
...
 702:	        __update_curr(cfs_rq, curr, delta_exec);
 703:	        curr->exec_start = now;
...
 714:	}

 663:	static inline void
 664:	__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 665:	              unsigned long delta_exec)
 666:	{
 667:	        unsigned long delta_exec_weighted;
...
 674:	        delta_exec_weighted = calc_delta_fair(delta_exec, curr);
...
 676:	        curr->vruntime += delta_exec_weighted;
...
 682:	}

task_tick_fair() は、tick ごとに定期的に呼び出される。
task_tick_fair() は、entity_tick() を呼ぶ。
entity_tick() は、update_curr() を呼ぶ。
update_curr() は、まず、現在の時刻を struct cfs_rq から得ている。
次に、前回の実行開始 exec_start と現在時刻の差　delta_exec　を求めている。
これを、引数に __update_curr() を呼び出している。
__update_curr() は、delta_exec　をさまざまな要素に加えている。
curr (現在実行中の)の vruntime については、重み付けをして加えている。重みの計算には、nice値(prio,se.load.weight)が使われる。

■課題3 プロセス、スケジューリング関連

★問題(301) nice値

例1: 次の2つの CPU-bound のプロセスが存在したとする。

プロセスA: nice値0 (標準)
プロセスB: nice値1 (優先度が低い)

19秒間実行した場合、プロセスAとプロセスBは、それぞれ何秒ずつ CPU時間が割り当てられると期待されるか。

★問題(302) 平衡二分探索木によるレディ・キューの実装

レディ・キューを実装する方法として、リスト構造を使う方法や配列を使う方法が考えられるが、Linux では、平衡二分探索木が使われている。レディ・キューを実装する方法として、平衡二分探索木を用いる方法の利点と問題点を、リスト構造、または、配列を使う方法と比較して簡単に説明しなさい。

★問題(303) 二分探索木によるレディ・キューの実装

以下の図は、4つの要素を持つリストを表している。各要素には、キーがあり、優先度を表しているものとする。

図? 4つの要素を持つリスト構造

このリストを表現した二分探索木を１つ作り、節と枝（矢印）を用いて図示しなさい。ただし、木はバランスをしていなくても良いものとする。

注意: 正しい二分探索木は、複数存在する。

Last updated: 2013/02/11 18:53:23

Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>