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/
表示 | 説明 |
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
$
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
$
$ 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
$
"-"
の表示は、実時間のプロセスではない。
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 がある。
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
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);
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 の計算の重みづけに使われる。
名前 | 説明 |
---|---|
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 | 新しいプロセスが生成された |
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: }
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: }
図? 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: }
図? runqueueの構造(red-black tree)
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: }
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: }
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: }
図? 4つの要素を持つリスト構造
同じ優先度を持つ要素を、二分探索木を用いて保持するとどうなるか。節と枝 (矢印)を用いて図示しなさい。ただし、木はバランスをしていなくても良い ものとする。注意: 答えは1つではない。