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

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

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

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2011/2012-01-10
あるいは、次のページから手繰っていくこともできます。
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構造体

linux-3.1.3/include/linux/sched.h

1220:	struct task_struct {
1221:	        volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
...
1233:	        int prio, static_prio, normal_prio;
1234:	        unsigned int rt_priority;
1235:	        const struct sched_class *sched_class;
1236:	        struct sched_entity se;
1237:	        struct sched_rt_entity rt;
...
1257:	        unsigned int policy;
...
1572:	};

1169:	struct sched_entity {
...
1171:	        struct rb_node          run_node;
...
1173:	        unsigned int            on_rq;
...
1177:	        u64                     vruntime;
...
1193:	};

struct task_struct の中に、struct sched_entity がある。

◆policy

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

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

prio

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

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

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

linux-3.1.3/kernel/sys.c
 233:	/*
 234:	 * Ugh. To avoid negative return values, "getpriority()" will
 235:	 * not return the normal nice-value, but a negated value that
 236:	 * has been offset by 20 (ie it returns 40..1 instead of -20..19)
 237:	 * to stay compatible.
 238:	 */
 239:	SYSCALL_DEFINE2(getpriority, int, which, int, who)
 240:	{
 241:	        struct task_struct *g, *p;
 242:	        struct user_struct *user;
 243:	        const struct cred *cred = current_cred();
 244:	        long niceval, retval = -ESRCH;
 245:	        struct pid *pgrp;
 246:	
 247:	        if (which > PRIO_USER || which < PRIO_PROCESS)
 248:	                return -EINVAL;
...
 252:	        switch (which) {
 253:	                case PRIO_PROCESS:
 254:	                        if (who)
 255:	                                p = find_task_by_vpid(who);
 256:	                        else
 257:	                                p = current;
 258:	                        if (p) {
 259:	                                niceval = 20 - task_nice(p);
 260:	                                if (niceval > retval)
 261:	                                        retval = niceval;
 262:	                        }
 263:	                        break;
 264:	                case PRIO_PGRP:
...
 275:	                case PRIO_USER:
...
 293:	        }
 294:	out_unlock:
...
 298:	        return retval;
 299:	}

linux-3.1.3/include/linux/sched.h

1590:	#define MAX_USER_RT_PRIO        100
1591:	#define MAX_RT_PRIO             MAX_USER_RT_PRIO
1592:	
1593:	#define MAX_PRIO                (MAX_RT_PRIO + 40)
1594:	#define DEFAULT_PRIO            (MAX_RT_PRIO + 20)

linux-3.1.3/kernel/sched.c
  94:	#define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
  95:	#define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
  96:	#define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)
...
5016:	int task_nice(const struct task_struct *p)
5017:	{
5018:	        return TASK_NICE(p);
5019:	}
5020:	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 の値を決めるために使われる。

linux-3.1.3/kernel/sched.c

1405:	/*
1406:	 * Nice levels are multiplicative, with a gentle 10% change for every
1407:	 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
1408:	 * nice 1, it will get ~10% less CPU time than another CPU-bound task
1409:	 * that remained on nice 0.
1410:	 *
1411:	 * The "10% effect" is relative and cumulative: from _any_ nice level,
1412:	 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
1413:	 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
1414:	 * If a task goes up by ~10% and another task goes down by ~10% then
1415:	 * the relative distance between them is ~25%.)
1416:	 */
1417:	static const int prio_to_weight[40] = {
1418:	 /* -20 */     88761,     71755,     56483,     46273,     36291,
1419:	 /* -15 */     29154,     23254,     18705,     14949,     11916,
1420:	 /* -10 */      9548,      7620,      6100,      4904,      3906,
1421:	 /*  -5 */      3121,      2501,      1991,      1586,      1277,
1422:	 /*   0 */      1024,       820,       655,       526,       423,
1423:	 /*   5 */       335,       272,       215,       172,       137,
1424:	 /*  10 */       110,        87,        70,        56,        45,
1425:	 /*  15 */        36,        29,        23,        18,        15,
1426:	};
...
1768:	static void set_load_weight(struct task_struct *p)
1769:	{
1770:	        int prio = p->static_prio - MAX_RT_PRIO;
1771:	        struct load_weight *load = &p->se.load;
...
1782:	        load->weight = scale_load(prio_to_weight[prio]);
1783:	        load->inv_weight = prio_to_wmult[prio];
1784:	}

linux-3.1.3/include/linux/sched.h
 817:	# define scale_load(w)          (w)

優先度 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 が行われる。

linux-3.1.3/kernel/sched.c

1786:	static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
1787:	{
...
1790:	        p->sched_class->enqueue_task(rq, p, flags);
1791:	}

1793:	static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
1794:	{
...
1797:	        p->sched_class->dequeue_task(rq, p, flags);
1798:	}

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

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

◆スケジューラの設定

linux-3.1.3/kernel/sched.c

5050:	static void
5051:	__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
5052:	{
5053:	        p->policy = policy;
5054:	        p->rt_priority = prio;
5055:	        p->normal_prio = normal_prio(p);
5056:	        /* we are holding p->pi_lock already */
5057:	        p->prio = rt_mutex_getprio(p);
5058:	        if (rt_prio(p->prio))
5059:	                p->sched_class = &rt_sched_class;
5060:	        else
5061:	                p->sched_class = &fair_sched_class;
5062:	        set_load_weight(p);
5063:	}

linux-3.1.3/include/linux/sched.h
1596:	static inline int rt_prio(int prio)
1597:	{
1598:	        if (unlikely(prio < MAX_RT_PRIO))
1599:	                return 1;
1600:	        return 0;
1601:	}

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

◆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の構造


linux-3.1.3/kernel/sched.c
 456:	struct rq {
...
 479:	        struct cfs_rq cfs;
 480:	        struct rt_rq rt;
...
 575:	};
...
 312:	struct cfs_rq {
...
 322:	        struct rb_root tasks_timeline;
 323:	        struct rb_node *rb_leftmost;
 324:	
 325:	        struct list_head tasks;
...
 381:	};
...
 577:	static 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.1.3/kernel/sched_fair.c
 352:	static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 353:	{
 354:	        struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
 355:	        struct rb_node *parent = NULL;
 356:	        struct sched_entity *entry;
 357:	        int leftmost = 1;
...
 362:	        while (*link) {
 363:	                parent = *link;
 364:	                entry = rb_entry(parent, struct sched_entity, run_node);
...
 369:	                if (entity_before(se, entry)) {
 370:	                        link = &parent->rb_left;
 371:	                } else {
 372:	                        link = &parent->rb_right;
 373:	                        leftmost = 0;
 374:	                }
 375:	        }
...
 381:	        if (leftmost)
 382:	                cfs_rq->rb_leftmost = &se->run_node;
 383:	
 384:	        rb_link_node(&se->run_node, parent, link);
 385:	        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
 386:	}
...
 318:	static inline int entity_before(struct sched_entity *a,
 319:	                                struct sched_entity *b)
 320:	{
 321:	        return (s64)(a->vruntime - b->vruntime) < 0;
 322:	}

平衡二分探索木の一種、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 ミリ秒から1 ミリ秒。

linux-3.1.3/kernel/sched.c
4102:	void scheduler_tick(void)
4103:	{
4104:	        int cpu = smp_processor_id();
4105:	        struct rq *rq = cpu_rq(cpu);
4106:	        struct task_struct *curr = rq->curr;
...
4113:	        curr->sched_class->task_tick(rq, curr, 0);
...
4122:	}

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

◆entity_tick()

linux-3.1.3/kernel/sched_fair.c

4126:	static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
4127:	{
4128:	        struct cfs_rq *cfs_rq;
4129:	        struct sched_entity *se = &curr->se;
4130:	
4131:	        for_each_sched_entity(se) {
4132:	                cfs_rq = cfs_rq_of(se);
4133:	                entity_tick(cfs_rq, se, queued);
4134:	        }
4135:	}

1206:	static void
1207:	entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
1208:	{
...
1212:	        update_curr(cfs_rq);
...
1238:	}

 558:	static void update_curr(struct cfs_rq *cfs_rq)
 559:	{
 560:	        struct sched_entity *curr = cfs_rq->curr;
 561:	        u64 now = rq_of(cfs_rq)->clock_task;
 562:	        unsigned long delta_exec;
...
 572:	        delta_exec = (unsigned long)(now - curr->exec_start);
...
 576:	        __update_curr(cfs_rq, curr, delta_exec);
 577:	        curr->exec_start = now;
...
 586:	}

 537:	static inline void
 538:	__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 539:	              unsigned long delta_exec)
 540:	{
 541:	        unsigned long delta_exec_weighted;
...
 548:	        delta_exec_weighted = calc_delta_fair(delta_exec, curr);
...
 550:	        curr->vruntime += delta_exec_weighted;
 551:	        update_min_vruntime(cfs_rq);
...
 556:	}

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つの要素を持つリスト構造

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

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

Last updated: 2012/01/08 22:18:49

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