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

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

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

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

■今日の大事な話

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

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

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

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

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

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

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

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

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

注意: 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  1013  4795  4793  0  76   0 -  1719 wait   pts/2    00:00:00 bash
0 S  1013  4905  4795  0  75   0 -  1503 -      pts/2    00:00:00 xterm
0 T  1013  5031  4795  2  76   0 -  3577 finish pts/2    00:00:00 emacs-x
0 R  1013  5034  4795  0  78   0 -   557 -      pts/2    00:00:00 ps
$ /bin/nice ps -l [←]
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
0 S  1013  4795  4793  0  75   0 -  1719 wait   pts/2    00:00:00 bash
0 S  1013  4905  4795  0  75   0 -  1503 -      pts/2    00:00:00 xterm
0 T  1013  5031  4795  0  76   0 -  3577 finish pts/2    00:00:00 emacs-x
0 R  1013  5040  4795  0  87  10 -   557 -      pts/2    00:00:00 ps
$ []

◆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
$ []

◆nice値の利用法

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

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

例1: 次の2つの CPU-bound のプロセスが存在したとする。 AのCPU時間 : BのCPU時間 == 1 : 0.9

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

$ ps -o state,uid,pid,ppid,rtprio,time,comm [←]
S   UID   PID  PPID RTPRIO     TIME COMMAND
S  1013  4795  4793      - 00:00:00 bash
S  1013  4905  4795      - 00:00:00 xterm
T  1013  5031  4795      - 00:00:00 emacs-x
R  1013  5343  4795      - 00:00:00 ps
$ []

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

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

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

■Linux task構造体とnice値

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

◆task_struct構造体

include/linux/sched.h
1163:	struct task_struct {
1164:	        volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
...
1178:	        int prio, static_prio, normal_prio;
1179:	        unsigned int rt_priority;
1180:	        const struct sched_class *sched_class;
1181:	        struct sched_entity se;
1182:	        struct sched_rt_entity rt;
...
1202:	        unsigned int policy;
...
1497:	};
...
1119:	struct sched_entity {
...
1121:	        struct rb_node          run_node;
...
1123:	        unsigned int            on_rq;
...
1127:	        u64                     vruntime;
...
1143:	};
struct task_struct の中に、struct sched_entity がある。

◆policy

Linux では、スケジューリングのポリシーが大きく2種類。通常の時分割と実時間。
  35:	#define SCHED_NORMAL            0
  36:	#define SCHED_FIFO              1
  37:	#define SCHED_RR                2
  38:	#define SCHED_BATCH             3
  39:	/* SCHED_ISO: reserved but not implemented yet */
  40:	#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値を保持する。 ただし、次のようなゲタを履かせている。
prio
スケジューリングに用いる優先度を保持する。
prio を見ると、通常のプロセスか実時間のプロセスかがわかる。 100 以上なら、通常のプロセス。通常のプロセスの prio は、100から140。

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

xkernel/sys.c 

 210:	/*
 211:	 * Ugh. To avoid negative return values, "getpriority()" will
 212:	 * not return the normal nice-value, but a negated value that
 213:	 * has been offset by 20 (ie it returns 40..1 instead of -20..19)
 214:	 * to stay compatible.
 215:	 */
 216:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 217:	{
 218:	        struct task_struct *g, *p;
 219:	        struct user_struct *user;
 220:	        const struct cred *cred = current_cred();
 221:	        long niceval, retval = -ESRCH;
 222:	        struct pid *pgrp;
 223:	
 224:	        if (which > PRIO_USER || which < PRIO_PROCESS)
 225:	                return -EINVAL;
...
 229:	        switch (which) {
 230:	                case PRIO_PROCESS:
 231:	                        if (who)
 232:	                                p = find_task_by_vpid(who);
 233:	                        else
 234:	                                p = current;
 235:	                        if (p) {
 236:	                                niceval = 20 - task_nice(p);
 237:	                                if (niceval > retval)
 238:	                                        retval = niceval;
 239:	                        }
 240:	                        break;
 241:	                case PRIO_PGRP:
...
 252:	                case PRIO_USER:
...
 270:	        }
...
 275:	        return retval;
 276:	}

include/linux/sched.h:

1515:	#define MAX_USER_RT_PRIO        100
1516:	#define MAX_RT_PRIO             MAX_USER_RT_PRIO
1517:	
1518:	#define MAX_PRIO                (MAX_RT_PRIO + 40)
1519:	#define DEFAULT_PRIO            (MAX_RT_PRIO + 20)

kernel/sched.c
  90:	#define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
  91:	#define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
  92:	#define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)
...
4509:	int task_nice(const struct task_struct *p)
4510:	{
4511:	        return TASK_NICE(p);
4512:	}
4513:	EXPORT_SYMBOL(task_nice);

◆se.load.weight

static_prio は、se.load.weight の値を決めるために使われる。
kernel/sched.c

1370:	/*
1371:	 * Nice levels are multiplicative, with a gentle 10% change for every
1372:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
1373:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
1374:	 * that remained on nice 0.
1375:	 *
1376:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
1377:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
1378:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
1379:	 * If a task goes up by ~10% and another task goes down by ~10% then
1380:	 * the relative distance between them is ~25%.)
1381:	 */
1382:	static const int prio_to_weight[40] = {
1383:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
1384:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
1385:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
1386:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
1387:	 /*   0 */      1024,       820,       655,       526,       423,
1388:	 /*   5 */       335,       272,       215,       172,       137,
1389:	 /*  10 */       110,        87,        70,        56,        45,
1390:	 /*  15 */        36,        29,        23,        18,        15,
1391:	};

1859:	static void set_load_weight(struct task_struct *p)
1860:	{
...
1876:	        p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
1877:	        p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
1878:	}
優先度 static_prio は、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 が行われる。
kernel/sched.c
1880:	static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
1881:	{
...
1884:	        p->sched_class->enqueue_task(rq, p, flags);
1885:	        p->se.on_rq = 1;
1886:	}
1887:	
1888:	static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
1889:	{
...
1892:	        p->sched_class->dequeue_task(rq, p, flags);
1893:	        p->se.on_rq = 0;
1894:	}

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

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

◆スケジューラの設定

kernel/sched.c
4543:	static void
4544:	__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
4545:	{
4546:	        BUG_ON(p->se.on_rq);
4547:	
4548:	        p->policy = policy;
4549:	        p->rt_priority = prio;
4550:	        p->normal_prio = normal_prio(p);
4551:	        /* we are holding p->pi_lock already */
4552:	        p->prio = rt_mutex_getprio(p);
4553:	        if (rt_prio(p->prio))
4554:	                p->sched_class = &rt_sched_class;
4555:	        else
4556:	                p->sched_class = &fair_sched_class;
4557:	        set_load_weight(p);
4558:	}

◆CFS(Completely Fair Scheduler)

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

◆runqueues(リスト的な見方)

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

runqueue、tasks_timeline、se.vruntime

図? runqueueの構造


kernel/sched.c
 449:	struct rq {
...
 472:	        struct cfs_rq cfs;
 473:	        struct rt_rq rt;
...
 556:	};
...
 313:	struct cfs_rq {
...
 320:	        struct rb_root tasks_timeline;
 321:	        struct rb_node *rb_leftmost;
...
 323:	        struct list_head tasks;
...
 373:	};
...
 558:	static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
...
7592:	static void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq)
7593:	{
7594:	        cfs_rq->tasks_timeline = RB_ROOT;
...
7600:	}

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

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

二分探索木とは、次のような二分木。 平衡木(balanced tree)、または、高さ平衡木(height-balanced tree)は、任意 の節で左右の高さの差が一定以下木。

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

◆Linux red-black treeの基本操作

型定義で、各要素に次の要素を含める。 検索
  1. 現在のノードとキーを比較
  2. 等しいなら見つかった
  3. キーが小さいなら左の枝へ
  4. キーが大きいなら右の枝へ
  5. 枝がなければキーは存在しない
挿入
  1. 現在のノードとデータのキーを比較
  2. キーが小さいなら左の枝を「親」
  3. キーが大きいなら右の枝を「親」
  4. キーが等しいならエラー(重複)
  5. 「親」からデータへのリンクを作成する(rb_link_node())
  6. 平衡になるようにする(rebalancing, recoloring, rb_insert_color())

◆runqueues(red-black tree)

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

runqueue、tasks_timeline、se.vruntime、red-black tree

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

◆__enqueue_entity()

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

 328:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 329:	{
 330:	        struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
 331:	        struct rb_node *parent = NULL;
 332:	        struct sched_entity *entry;
 333:	        s64 key = entity_key(cfs_rq, se);
 334:	        int leftmost = 1;
 335:	
 336:	        /*
 337:	         * Find the right place in the rbtree:
 338:	         */
 339:	        while (*link) {
 340:	                parent = *link;
 341:	                entry = rb_entry(parent, struct sched_entity, run_node);
 342:	                /*
 343:	                 * We dont care about collisions. Nodes with
 344:	                 * the same key stay together.
 345:	                 */
 346:	                if (key < entity_key(cfs_rq, entry)) {
 347:	                        link = &parent->rb_left;
 348:	                } else {
 349:	                        link = &parent->rb_right;
 350:	                        leftmost = 0;
 351:	                }
 352:	        }
 353:	
 354:	        /*
 355:	         * Maintain a cache of leftmost tree entries (it is frequently
 356:	         * used):
 357:	         */
 358:	        if (leftmost)
 359:	                cfs_rq->rb_leftmost = &se->run_node;
 360:	
 361:	        rb_link_node(&se->run_node, parent, link);
 362:	        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
 363:	}
...
 299:	static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
 300:	{
 301:	        return se->vruntime - cfs_rq->min_vruntime;
 302:	}

◆tickごとの仕事

scheduler_tick() は、tick ごとに定期的に呼び出される。 1 tick は、10 ミリ秒から1 ミリ秒。

kernel/sched.c
3573:	void scheduler_tick(void)
3574:	{
3575:	        int cpu = smp_processor_id();
3576:	        struct rq *rq = cpu_rq(cpu);
3577:	        struct task_struct *curr = rq->curr;
...
3584:	        curr->sched_class->task_tick(rq, curr, 0);
...
3593:	}

◆entity_tick()

kernel/sched_fair.c

3726:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
3727:	{
3728:	        struct cfs_rq *cfs_rq;
3729:	        struct sched_entity *se = &curr->se;
3730:	
3731:	        for_each_sched_entity(se) {
3732:	                cfs_rq = cfs_rq_of(se);
3733:	                entity_tick(cfs_rq, se, queued);
3734:	        }
3735:	}
...

 951:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
 952:	{
...
 956:	        update_curr(cfs_rq);
...
 975:	        if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
 976:	                check_preempt_tick(cfs_rq, curr);
 977:	}
...
 519:	static void update_curr(struct cfs_rq *cfs_rq)
 520:	{
 521:	        struct sched_entity *curr = cfs_rq->curr;
 522:	        u64 now = rq_of(cfs_rq)->clock;
 523:	        unsigned long delta_exec;
...
 533:	        delta_exec = (unsigned long)(now - curr->exec_start);
...
 537:	        __update_curr(cfs_rq, curr, delta_exec);
 538:	        curr->exec_start = now;
...
 547:	}
...

 503:	__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 504:	              unsigned long delta_exec)
 505:	{
 506:	        unsigned long delta_exec_weighted;
...
 511:	        curr->sum_exec_runtime += delta_exec;
...
 513:	        delta_exec_weighted = calc_delta_fair(delta_exec, curr);
 514:	
 515:	        curr->vruntime += delta_exec_weighted;
 516:	        update_min_vruntime(cfs_rq);
 517:	}

■クイズ3 プロセス、スケジューリング関連

★問題(301) nice値

例1: 次の2つの CPU-bound のプロセスが存在したとする。 19秒間実行した場合、プロセスAとプロセスBは、それぞれ何秒ずつ CPU時間が割り当てられると期待されるか。

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

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

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

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

head、next、next、next

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

同じ優先度を持つ要素を、二分探索木を用いて保持するとどうなるか。節と枝 (矢印)を用いて図示しなさい。ただし、木はバランスをしていなくても良い ものとする。

注意: 答えは1つではない。


Last updated: 2010/12/21 16:48:18
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>