2012年12月25日 情報科学類 オペレーティングシステム II 筑波大学 システム情報工学研究科 コンピュータサイエンス専攻, 電子・情報工学系 新城 靖 <yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2012/2012-12-25
あるいは、次のページから手繰っていくこともできます。
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 1000 28765 28759 0 80 0 - 1363 wait pts/0 00:00:00 bash
0 T 1000 28825 28765 0 80 0 - 1270 signal pts/0 00:00:00 man
0 T 1000 28832 28825 0 80 0 - 1183 signal pts/0 00:00:00 less
0 T 1000 28833 28765 0 80 0 - 7606 signal pts/0 00:00:00 emacs
0 R 1000 28836 28765 0 80 0 - 1216 - pts/0 00:00:00 ps
$ /bin/nice ps -l
F S UID PID PPID C PRI NI ADDR SZ WCHAN TTY TIME CMD
0 S 1000 28765 28759 0 80 0 - 1363 wait pts/0 00:00:00 bash
0 T 1000 28825 28765 0 80 0 - 1270 signal pts/0 00:00:00 man
0 T 1000 28832 28825 0 80 0 - 1183 signal pts/0 00:00:00 less
0 T 1000 28833 28765 0 80 0 - 7606 signal pts/0 00:00:00 emacs
0 R 1000 28837 28765 0 90 10 - 1216 - pts/0 00:00:00 ps
$ /bin/nice -19 ps -l
F S UID PID PPID C PRI NI ADDR SZ WCHAN TTY TIME CMD
0 S 1000 28765 28759 0 80 0 - 1363 wait pts/0 00:00:00 bash
0 T 1000 28825 28765 0 80 0 - 1270 signal pts/0 00:00:00 man
0 T 1000 28832 28825 0 80 0 - 1183 signal pts/0 00:00:00 less
0 T 1000 28833 28765 0 80 0 - 7606 signal pts/0 00:00:00 emacs
0 R 1000 28841 28765 0 99 19 - 1216 - pts/0 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,policy,pri,ni,rtprio,time,comm
S UID PID PPID POL PRI NI RTPRIO TIME COMMAND
S 0 29103 29041 TS 19 0 - 00:00:00 su
S 0 29110 29103 TS 19 0 - 00:00:00 bash
T 0 29226 29110 TS 19 0 - 00:00:00 emacs
T 0 29227 29110 TS 19 0 - 00:00:00 man
T 0 29234 29227 TS 19 0 - 00:00:00 less
R 0 29247 29110 TS 19 0 - 00:00:00 ps
# /bin/nice --10 ps -o state,uid,pid,ppid,policy,pri,ni,rtprio,time,comm
S UID PID PPID POL PRI NI RTPRIO TIME COMMAND
S 0 29103 29041 TS 19 0 - 00:00:00 su
S 0 29110 29103 TS 19 0 - 00:00:00 bash
T 0 29226 29110 TS 19 0 - 00:00:00 emacs
T 0 29227 29110 TS 19 0 - 00:00:00 man
T 0 29234 29227 TS 19 0 - 00:00:00 less
R 0 29248 29110 TS 29 -10 - 00:00:00 ps
# chrt 50 ps -o state,uid,pid,ppid,policy,pri,ni,rtprio,time,comm
S UID PID PPID POL PRI NI RTPRIO TIME COMMAND
S 0 29103 29041 TS 19 0 - 00:00:00 su
S 0 29110 29103 TS 19 0 - 00:00:00 bash
T 0 29226 29110 TS 19 0 - 00:00:00 emacs
T 0 29227 29110 TS 19 0 - 00:00:00 man
T 0 29234 29227 TS 19 0 - 00:00:00 less
R 0 29249 29110 RR 90 - 50 00:00:00 ps
#
"-"
の表示は、実時間のプロセスではない。
linux-3.6.8/include/linux/sched.h 1234: struct task_struct { 1235: volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ ... 1247: int prio, static_prio, normal_prio; 1248: unsigned int rt_priority; 1249: const struct sched_class *sched_class; 1250: struct sched_entity se; 1251: struct sched_rt_entity rt; ... 1274: unsigned int policy; ... 1592: }; 1178: struct sched_entity { ... 1180: struct rb_node run_node; ... 1182: unsigned int on_rq; ... 1186: u64 vruntime; ... 1202: };struct task_struct の中に、prio 等のフィールドやstruct sched_entity が ある。
linux-3.6.8/include/linux/sched.h 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
linux-3.6.8/kernel/sys.c 235: /* 236: * Ugh. To avoid negative return values, "getpriority()" will 237: * not return the normal nice-value, but a negated value that 238: * has been offset by 20 (ie it returns 40..1 instead of -20..19) 239: * to stay compatible. 240: */ 241: SYSCALL_DEFINE2(getpriority, int, which, int, who) 242: { 243: struct task_struct *g, *p; 244: struct user_struct *user; 245: const struct cred *cred = current_cred(); 246: long niceval, retval = -ESRCH; 247: struct pid *pgrp; 248: kuid_t uid; 249: 250: if (which > PRIO_USER || which < PRIO_PROCESS) 251: return -EINVAL; ... 255: switch (which) { 256: case PRIO_PROCESS: 257: if (who) 258: p = find_task_by_vpid(who); 259: else 260: p = current; 261: if (p) { 262: niceval = 20 - task_nice(p); 263: if (niceval > retval) 264: retval = niceval; 265: } 266: break; 267: case PRIO_PGRP: ... 278: case PRIO_USER: ... 297: } ... 228: out_unlock: ... 232: return error; 233: } linux-3.6.8/include/linux/sched.h 1610: #define MAX_USER_RT_PRIO 100 1611: #define MAX_RT_PRIO MAX_USER_RT_PRIO 1612: 1613: #define MAX_PRIO (MAX_RT_PRIO + 40) 1614: #define DEFAULT_PRIO (MAX_RT_PRIO + 20) linux-3.6.8/kernel/sched/sched.h 16: #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20) 17: #define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20) 18: #define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio) linux-3.6.8/kernel/sched/core.c 4169: int task_nice(const struct task_struct *p) 4170: { 4171: return TASK_NICE(p); 4172: }
glibc-2.5/sysdeps/unix/sysv/linux/getpriority.c 28: #define PZERO 20 ... 35: int 36: getpriority (enum __priority_which which, id_t who) 37: { 38: int res; 39: 40: res = INLINE_SYSCALL (getpriority, 2, (int) which, who); 41: if (res >= 0) 42: res = PZERO - res; 43: return res; 44: }
linux-3.6.8/kernel/sched/sched.h 795: /* 796: * Nice levels are multiplicative, with a gentle 10% change for every 797: * nice level changed. I.e. when a CPU-bound task goes from nice 0 to 798: * nice 1, it will get ~10% less CPU time than another CPU-bound task 799: * that remained on nice 0. 800: * 801: * The "10% effect" is relative and cumulative: from _any_ nice level, 802: * if you go up 1 level, it's -10% CPU usage, if you go down 1 level 803: * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25. 804: * If a task goes up by ~10% and another task goes down by ~10% then 805: * the relative distance between them is ~25%.) 806: */ 807: static const int prio_to_weight[40] = { 808: /* -20 */ 88761, 71755, 56483, 46273, 36291, 809: /* -15 */ 29154, 23254, 18705, 14949, 11916, 810: /* -10 */ 9548, 7620, 6100, 4904, 3906, 811: /* -5 */ 3121, 2501, 1991, 1586, 1277, 812: /* 0 */ 1024, 820, 655, 526, 423, 813: /* 5 */ 335, 272, 215, 172, 137, 814: /* 10 */ 110, 87, 70, 56, 45, 815: /* 15 */ 36, 29, 23, 18, 15, 816: }; ... linux-3.6.8/kernel/sched/core.c 695: static void set_load_weight(struct task_struct *p) 696: { 697: int prio = p->static_prio - MAX_RT_PRIO; 698: struct load_weight *load = &p->se.load; ... 709: load->weight = scale_load(prio_to_weight[prio]); 710: load->inv_weight = prio_to_wmult[prio]; 711: } linux-3.6.8/include/linux/sched.h 840: # define scale_load(w) (w)struct task_struct の優先度 static_prio は、struct task_struct の 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 | 新しいプロセスが生成された |
linux-3.6.8/kernel/sched/core.c 713: static void enqueue_task(struct rq *rq, struct task_struct *p, int flags) 714: { 715: update_rq_clock(rq); 716: sched_info_queued(p); 717: p->sched_class->enqueue_task(rq, p, flags); 718: } 719: 720: static void dequeue_task(struct rq *rq, struct task_struct *p, int flags) 721: { 722: update_rq_clock(rq); 723: sched_info_dequeued(p); 724: p->sched_class->dequeue_task(rq, p, flags); 725: }
linux-3.6.8/kernel/sched/core.c 4216: static void 4217: __setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio) 4218: { 4219: p->policy = policy; 4220: p->rt_priority = prio; 4221: p->normal_prio = normal_prio(p); 4222: /* we are holding p->pi_lock already */ 4223: p->prio = rt_mutex_getprio(p); 4224: if (rt_prio(p->prio)) 4225: p->sched_class = &rt_sched_class; 4226: else 4227: p->sched_class = &fair_sched_class; 4228: set_load_weight(p); 4229: } linux-3.6.8/include/linux/sched.h 1616: static inline int rt_prio(int prio) 1617: { 1618: if (unlikely(prio < MAX_RT_PRIO)) 1619: return 1; 1620: return 0; 1621: }
p->prio
の値に応じて
&rt_sched_class
か
&fair_sched_class
のどちらかを指す。
Linux CFS は、次の方法でスケジューリングを行なう。
図? runqueueの構造
linux-3.6.8/kernel/sched/sched.h 348: struct rq { ... 371: struct cfs_rq cfs; 372: struct rt_rq rt; ... 470: }; 202: struct cfs_rq { ... 212: struct rb_root tasks_timeline; 213: struct rb_node *rb_leftmost; ... 272: }; linux-3.6.8/kernel/sched/core.c 112: DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
図? runqueueの構造(red-black tree)
linux-3.6.8/kernel/sched/fair.c 478: static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 479: { 480: struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; 481: struct rb_node *parent = NULL; 482: struct sched_entity *entry; 483: int leftmost = 1; 484: 485: /* 486: * Find the right place in the rbtree: 487: */ 488: while (*link) { 489: parent = *link; 490: entry = rb_entry(parent, struct sched_entity, run_node); 491: /* 492: * We dont care about collisions. Nodes with 493: * the same key stay together. 494: */ 495: if (entity_before(se, entry)) { 496: link = &parent->rb_left; 497: } else { 498: link = &parent->rb_right; 499: leftmost = 0; 500: } 501: } 502: 503: /* 504: * Maintain a cache of leftmost tree entries (it is frequently 505: * used): 506: */ 507: if (leftmost) 508: cfs_rq->rb_leftmost = &se->run_node; 509: 510: rb_link_node(&se->run_node, parent, link); 511: rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline); 512: } 444: static inline int entity_before(struct sched_entity *a, 445: struct sched_entity *b) 446: { 447: return (s64)(a->vruntime - b->vruntime) < 0; 448: }
&parent->rb_left
), 大きければ右(&parent->rb_right
) に進む。
cfs_rq->rb_leftmost
にも保存。
linux-3.6.8/kernel/sched/core.c 3214: void scheduler_tick(void) 3215: { 3216: int cpu = smp_processor_id(); 3217: struct rq *rq = cpu_rq(cpu); 3218: struct task_struct *curr = rq->curr; ... 3225: curr->sched_class->task_tick(rq, curr, 0); ... 3234: }
linux-3.6.8/kernel/sched/fair.c 4981: static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) 4982: { 4983: struct cfs_rq *cfs_rq; 4984: struct sched_entity *se = &curr->se; 4985: 4986: for_each_sched_entity(se) { 4987: cfs_rq = cfs_rq_of(se); 4988: entity_tick(cfs_rq, se, queued); 4989: } 4990: } 1347: static void 1348: entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) 1349: { ... 1353: update_curr(cfs_rq); ... 1377: if (cfs_rq->nr_running > 1) 1378: check_preempt_tick(cfs_rq, curr); 1379: } 684: static void update_curr(struct cfs_rq *cfs_rq) 685: { 686: struct sched_entity *curr = cfs_rq->curr; 687: u64 now = rq_of(cfs_rq)->clock_task; 688: unsigned long delta_exec; ... 698: delta_exec = (unsigned long)(now - curr->exec_start); ... 702: __update_curr(cfs_rq, curr, delta_exec); 703: curr->exec_start = now; ... 714: } 663: static inline void 664: __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, 665: unsigned long delta_exec) 666: { 667: unsigned long delta_exec_weighted; ... 674: delta_exec_weighted = calc_delta_fair(delta_exec, curr); ... 676: curr->vruntime += delta_exec_weighted; ... 682: }
図? 4つの要素を持つリスト構造
このリストを表現した二分探索木を1つ作り、節と枝(矢印)を用いて図示し なさい。ただし、木はバランスをしていなくても良いものとする。注意: 正しい二分探索木は、複数存在する。