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

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

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

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

■今日の大事な話

task_struct 構造体
nice値の意味
スケジューラ
木構造によるレディ・キューの実装

■current

印刷資料は、先週配布済み。

■プロセスを表現する構造体/スケジューリング関連

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

fork(): プロセスのコピーを作る。
execve(): プログラムを入れ替える。プロセスとしては同一。
exit(): プロセスの終了する。
wait(), waitpid(), wait3(), wait4()。プロセスの終了を待つ。
nice(),getpriority(),setpriority() : nice値(優先度)の操作。値が小さい方が優先度が高い。一般ユーザは、値を大きくすることだけできる。値の範囲は、-20から19が普通。

◆ps -lコマンド

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

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

% ps l 
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
0  1013  5463  5462  15   0  91484  3636 rt_sig Ss   pts/3      0:00 -tcsh
0  1013  8378  5463  15   0  51236  2648 -      S    pts/3      0:00 xterm
0  1013  8380  8378  15   0  91188  3208 -      Ss+  pts/4      0:00 -csh
0  1013  9172  5463  16   0   8368   748 -      R+   pts/3      0:00 ps l
% /bin/nice  ps l 
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
0  1013  5463  5462  15   0  91484  3636 rt_sig Ss   pts/3      0:00 -tcsh
0  1013  8378  5463  15   0  51236  2648 -      S    pts/3      0:00 xterm
0  1013  8380  8378  15   0  91188  3208 -      Ss+  pts/4      0:00 -csh
0  1013  9175  5463  26  10   8368   748 -      RN+  pts/3      0:00 ps l
%

◆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 $$ 
5463
% ./getpriority-pid $$ 
pid==5463, priority==0
% ./getpriority-pid 0 
pid==0, priority==0
% /bin/nice -20 ./getpriority-pid 0 
pid==0, priority==19
%

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

■Linux task構造体とnice値

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

◆task_struct構造体

include/linux/sched.h
1166: struct task_struct {
1167:         volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
...
1181:         int prio, static_prio, normal_prio;
1182:         unsigned int rt_priority;
1183:         const struct sched_class *sched_class;
1184:         struct sched_entity se;
1185:         struct sched_rt_entity rt;
...
1206:         unsigned int policy;
...
1483: };

1089: struct sched_entity {
...
1091:         struct rb_node          run_node;
...
1093:         unsigned int            on_rq;
...
1097:         u64                     vruntime;
...
1148: };

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

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

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

◆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。

◆通常のプロセス(非実時間プロセス)でのnice値の利用法

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

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

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

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

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

kernel/sys.c 

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

include/linux/sched.h:
1501: #define MAX_USER_RT_PRIO        100
1502: #define MAX_RT_PRIO             MAX_USER_RT_PRIO
1503: 
1504: #define MAX_PRIO                (MAX_RT_PRIO + 40)
1505: #define DEFAULT_PRIO            (MAX_RT_PRIO + 20)

kernel/sched.c
  89: #define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
  90: #define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
  91: #define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)
...
6044: int task_nice(const struct task_struct *p)
6045: {
6046:         return TASK_NICE(p);
6047: }
6048: 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 の値を決めるために使われる。

1368: static const int prio_to_weight[40] = {
1369:  /* -20 */     88761,     71755,     56483,     46273,     36291,
1370:  /* -15 */     29154,     23254,     18705,     14949,     11916,
1371:  /* -10 */      9548,      7620,      6100,      4904,      3906,
1372:  /*  -5 */      3121,      2501,      1991,      1586,      1277,
1373:  /*   0 */      1024,       820,       655,       526,       423,
1374:  /*   5 */       335,       272,       215,       172,       137,
1375:  /*  10 */       110,        87,        70,        56,        45,
1376:  /*  15 */        36,        29,        23,        18,        15,
1377: };

1757: static void set_load_weight(struct task_struct *p)
1758: {
...
1774:         p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
1775:         p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
1776: }

優先度 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	新しいプロセスが生成された

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

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

◆sched_class使い方

クラスに応じて enqueue, dequeue が行われる。

1784: static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)
1785: {
...
1790:         p->sched_class->enqueue_task(rq, p, wakeup);
1791:         p->se.on_rq = 1;
1792: }
1793: 
1794: static void dequeue_task(struct rq *rq, struct task_struct *p, int sleep)
1795: {
...
1808:         p->sched_class->dequeue_task(rq, p, sleep);
1809:         p->se.on_rq = 0;
1810: }

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

fair_sched_class: 公平を目指す。
rt_sched_class: 実時間を目指す

◆スケジューラの設定

task_struct の policy が SCHED_NORMAL の時には、fair_sched_class で指定された通常のスケジューラが、SCHED_FIFO と SCHED_RR の時には、実時間用のスケジューラが動作する。

kernel/sched.c
6078: static void
6079: __setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
6080: {
6081:         BUG_ON(p->se.on_rq);
6082: 
6083:         p->policy = policy;
6084:         switch (p->policy) {
6085:         case SCHED_NORMAL:
6086:         case SCHED_BATCH:
6087:         case SCHED_IDLE:
6088:                 p->sched_class = &fair_sched_class;
6089:                 break;
6090:         case SCHED_FIFO:
6091:         case SCHED_RR:
6092:                 p->sched_class = &rt_sched_class;
6093:                 break;
6094:         }
6095: 
6096:         p->rt_priority = prio;
6097:         p->normal_prio = normal_prio(p);
6098:         /* we are holding p->pi_lock already */
6099:         p->prio = rt_mutex_getprio(p);
6100:         set_load_weight(p);
6101: }

◆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
 565: struct rq {
...
 586:         struct cfs_rq cfs;
 587:         struct rt_rq rt;
...
 664: };

 420: struct cfs_rq {
...
 427:         struct rb_root tasks_timeline;
 428:         struct rb_node *rb_leftmost;
 429: 
 430:         struct list_head tasks;
...
 480: };
...
 666: static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
...
9068: static void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq)
9069: {
9070:         cfs_rq->tasks_timeline = RB_ROOT;
...
9076: }

(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
 304: static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 305: {
 306:         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
 307:         struct rb_node *parent = NULL;
 308:         struct sched_entity *entry;
 309:         s64 key = entity_key(cfs_rq, se);
 310:         int leftmost = 1;
 311: 
 312:         /*
 313:          * Find the right place in the rbtree:
 314:          */
 315:         while (*link) {
 316:                 parent = *link;
 317:                 entry = rb_entry(parent, struct sched_entity, run_node);
 318:                 /*
 319:                  * We dont care about collisions. Nodes with
 320:                  * the same key stay together.
 321:                  */
 322:                 if (key < entity_key(cfs_rq, entry)) {
 323:                         link = &parent->rb_left;
 324:                 } else {
 325:                         link = &parent->rb_right;
 326:                         leftmost = 0;
 327:                 }
 328:         }
 329: 
 330:         /*
 331:          * Maintain a cache of leftmost tree entries (it is frequently
 332:          * used):
 333:          */
 334:         if (leftmost)
 335:                 cfs_rq->rb_leftmost = &se->run_node;
 336: 
 337:         rb_link_node(&se->run_node, parent, link);
 338:         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
 339: }
...
 275: static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
 276: {
 277:         return se->vruntime - cfs_rq->min_vruntime;
 278: }

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

◆tickごとの仕事

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


kernel/sched.c
1079: static enum hrtimer_restart hrtick(struct hrtimer *timer)
1080: {
1081:         struct rq *rq = container_of(timer, struct rq, hrtick_timer);
...
1086:         update_rq_clock(rq);
1087:         rq->curr->sched_class->task_tick(rq, rq->curr, 1);
...
1091: }

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

◆entity_tick()

kernel/sched_fair.c
1697: static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
1698: {
1699:         struct cfs_rq *cfs_rq;
1700:         struct sched_entity *se = &curr->se;
1701: 
1702:         for_each_sched_entity(se) {
1703:                 cfs_rq = cfs_rq_of(se);
1704:                 entity_tick(cfs_rq, se, queued);
1705:         }
1706: }
...
 866: entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
 867: {
 871:         update_curr(cfs_rq);
...
 890:         if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
 891:                 check_preempt_tick(cfs_rq, curr);
 892: }
...
 484: static void update_curr(struct cfs_rq *cfs_rq)
 485: {
 486:         struct sched_entity *curr = cfs_rq->curr;
 487:         u64 now = rq_of(cfs_rq)->clock;
 488:         unsigned long delta_exec;
...
 498:         delta_exec = (unsigned long)(now - curr->exec_start);
...
 502:         __update_curr(cfs_rq, curr, delta_exec);
 503:         curr->exec_start = now;
 511: }
...
 469: static inline void
 470: __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 471:               unsigned long delta_exec)
 472: {
 473:         unsigned long delta_exec_weighted;
 474: 
 475:         schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
 476: 
 477:         curr->sum_exec_runtime += delta_exec;
 478:         schedstat_add(cfs_rq, exec_clock, delta_exec);
 479:         delta_exec_weighted = calc_delta_fair(delta_exec, curr);
 480:         curr->vruntime += delta_exec_weighted;
 481:         update_min_vruntime(cfs_rq);
 482: }

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/01/25 17:48:22

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