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

					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/

■今日の大事な話

優先順位式スケジューリング
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  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
$

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,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
$

ps コマンドで -o を与え、rtprio を指定する。
"-" の表示は、実時間のプロセスではない。

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

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

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

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値を保持する。ただし、次のようなゲタを履かせている。

nice値の範囲 -20..19 を 0..39 にするために 20
実時間(realtime) のプロセスの優先度を上げるための 100 (MAX_RT_PRIO)

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);

getpriority() は、which と who の 2引数。
which が PRIO_PROCESS なら、who は、pid。
who が 0 なら、自分自身(current)。
who が 0 以外なら find_task_by_vpid()でプロセスを探す。
プロセスが見つかれば、task_struct の static_prio の値を返す。

◆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:	}

task_struct の sched_class は、&rt_sched_class か &rt_sched_class のどちらかを指す。

◆CFS(Completely Fair Scheduler)

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

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

◆runqueues(リスト的な見方)

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

図? 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:	}

(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個追加する関数である。

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:	}

平衡二分探索木の一種、red-black tree に節を追加している。
キーは、vruntime。vruntime が小さいほど左に来る。
最後に rb_insert_color() を呼び出して、バランスを回復する。

◆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:	}

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

◆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:	}

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値が使われる。

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

★問題(301) nice値

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

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

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

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

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

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

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

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

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

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

Last updated: 2010/12/21 16:48:18

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