Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
$B%W%m%;%9!"%9%1%8%e!<%j%s%04XO"(B

$B%W%m%;%9!"%9%1%8%e!<%j%s%04XO"(B

					2012$BG/(B01$B7n(B10$BF|(B
$B>pJs2J3XN`(B $B%*%Z%l!<%F%#%s%0%7%9%F%`(B II

                                       $BC^GHBg3X(B $B%7%9%F%`>pJs9)3X8&5f2J(B 
                                       $B%3%s%T%e!<%?%5%$%(%s%9@l96(B, $BEE;R!&>pJs9)3X7O(B
                                       $B?7>k(B $BLw(B
                                       <yas@is.tsukuba.ac.jp>

$B$3$N%Z!<%8$O!" http://www.coins.tsukuba.ac.jp/~yas/coins/os2-2011/2012-01-10
$B$"$k$$$O!" http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

$B"#:#F|$NBg;v$JOC(B

$BM%@h=g0L<0%9%1%8%e!<%j%s%0(B
nice$BCM$N0UL#(B
$B%9%1%8%e!<%i(B
$BLZ9=B$$K$h$k%l%G%#!&%-%e!<$N
$B"#I|=,(B($B%*%Z%l!<%F%#%s%0%7%9%F%`(B I$B$NHO0O(B)

$B"!%9%1%8%e!<%j%s%0$NL\I8(B
- CPU $B;HMQN($r>e$2$k!#(B
- $B%9%k!<%W%C%H(B($BC10L;~4VJU$j$N;E;vNL(B)$B$r>e$2$k!#(B
- $B%?!<%s%"%i%&%s%I;~4V(B($B%W%m%;%9$r@8@.$7$F$+$i40N;$9$k$^$G(B)$B$rC;$/$9$k!#(B
- $B%l%G%#!&%-%e!<$G$NBT$A;~4V$rC;$/$9$k!#(B
- $B1~Ez;~4V$rC;$/$9$k!#(B
- $B%W%m%;%9$K8xJ?$J(B CPU $B;~4V$r3d$jEv$F$k!#(B
- ($B
  $BA4It$OF1;~$K$O@.$jN)$?$J$$!#(B
  $B"!%9%1%8%e!<%j%s%0!&%"%k%4%j%:%`(B
  - FCFS (Firt-Come, First-Served), FIFO (First-In First-Out)
  - $B:GC;%8%g%VM%@h(B(Shortest Job First)
  - $BM%@hEY%9%1%8%e!<%j%s%0!#522n>uBV(B(starvation)$B$r5/$3$9!#(B aging $B$GM%@hEY$r>e$2$k!#(B
  - Round-Robin$B!#;~4V9o$_(B(time slice)$B$4$H$K@Z$jBX$($k!#(B
  $B"!M%@h=g0L<0%9%1%8%e!<%j%s%0(B(OS$B0lHL(B)
  - $B%W%m%;%9$4$H$KM%@hEY$r3d$jEv$F$k!#(B
  - OS $B$O!" $B%W%m%;%9$NM%@hEY$O!"MxMQ$7$?(BCPU$B;q8;$dF~=PNO$N%Q%?%s$GF0E*$KJQ99$9$k!#(B
  $B"!%l%G%#!&%-%e!<(B(OS$B0lHL(B)
  $B%l%G%#!&%-%e!<$O!"%l%G%#>uBV$N%W%m%;%9$N%j%9%H!#M%@hEY$N=g$KJB$s$G$$$l(B $B$P!"(BCPU $B$O%j%9%H$N@hF,$+$iMWAG$r
  $B"#%W%m%;%9!&%9%1%8%e!<%j%s%04XO"$N(BAPI
  $B"!(BUnix$B$K$*$1$k%W%m%;%9$K4X$9$k%7%9%F%`!&%3!<%k(B
  
  nice(), getpriority(), setpriority(): nice$BCM(B($BM%@hEY(B)$B$NA`:n!#CM$,>.$5$$J}$,M%@hEY$,9b$$!#(B $B0lHL%f!<%6$O!"CM$rBg$-$/$9$k$3$H$@$1$G$-$k!#(B $BCM$NHO0O$O!"(B-20$B$+$i(B19$B$,IaDL!#(B
  sched_getscheduler(), sched_setscheduler(): POSIX $B(B)$B!#(B
  sched_get_priority_max()$B!"(Bsched_get_priority_min(): $B3F%]%j%7!<$G$NM%@hEY$N:GBg$H:G>.$rI=$9@0?tCM!#%7%9%F%`$K$h$C$F@0?tCM$,(B $B0[$J$k!#?t;z$,Bg$-$$J}$,!"M%@hEY$,9b$$!#(Bmin < max $B$K$J$C$F(B $B$$$k!#(B
  $BCm0U(B: Linux $B$=$N$b$N$O!"/$7CY$l$F$b0UL#$,$"$k!J%=%U%H%j%"%k%?%$%`!K$K$O!";H$($k$3$H$,$"$k!#(B
  $B"!(Bps -l$B%3%^%s%I(B
  ps -l $B$N7k2L$N$&$A!" $BI=<((B $B@bL@(B NI Nice$B!#M%@hEY$rI=$9CM!#(B
  $ 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 $B%3%^%s%I$N(B NI $B$K$O!"(Bnice$BCM$,I=<($5$l$k!#(B
  nice $BCM$rJQ99$7$F%W%m%;%9$r@8@.$9$k$K$O!"(Bnice $B%3%^%s%I$,;H$($k!#%G(B $B%U%)%k%H$G(B 10 $B$K@_Dj$5$l$k!#(B
  
  $B"!(Bgetpriority-pid.c
  
  1: /* 2: getpriority-pid.c -- $BM%@hEY$NI=<((B 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 $
  
  $B%7%'%k$N(B PID $B$O!"(B$$ $B$H$$$&JQ?t$G;2>H$G$-$k!#(B
  PID $B$H$7$F(B 0 $B$r;XDj$9$k$H!"<+J,<+?H(B($B%7%'%k$+$i7Q>5(B)$B$,I=<($5$l$k!#(B
  nice $B%3%^%s%I$GCM$rBg$-$/$G$-$k!#:GBg(B20$B!#(B ($BFC8"%f!<%6$O!"CM$r>.$5$/$G$-$k!#(B)
  
  $B"!(Bnice$BCM$NMxMQK!(B
  $BM%@hEY$ND4@0J}K!(B
  
  $B ($BBPOCE*$J=hM}$GF~=PNO$GBT$A$,B?$$%W%m%;%9$NM%@hEY$r>e$2$k!#(B)
  nice$BCM$N87L)$J!V0UL#!W$O!"(BUnix $B$N$B"!(BLinux(CFS)$B$G$NDL>o$N%W%m%;%9(B($BHs
  
  nice$BCM$,(B1$BA}$($k$H!"AjBPE*$K(B10%$B$@$1(BCPU$B;~4V$N3dEv$F$,>/$J$/$J$k$h$&$K$9$k!#(B
  $BNc(B1: $B
- $B%W%m%;%9(BA: nice$BCM(B0
- $B%W%m%;%9(BB: nice$BCM(B1 ($BM%@hEY$,Dc$$(B)
A$B$N(BCPU$B;~4V(B : B$B$N(BCPU$B;~4V(B == 1 : 0.9
$B"!(Bps $B%3%^%s%I$G$N
```
$ 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
$ 
```
- "-" $B$NI=<($O!"
  $B"!%9%1%8%e!<%j%s%0$r9T$&$?$a$N%O!<%I%&%'%"(B
  $B$d$j$?$$$3$H$NNc(B: $B:#$N%W%m%;%9$r(B 50$B%_%jIC$@$1
  - $BL\3P$^$7;~7W$r;H$&!#$"$k;~4V$,$?$C$?$i3d$j9~$_$rH/@8$5$;$k%O!<%I%&%'(B $B%"$rMQ$$$k!#(B $BNc(B: 50$B%_%jIC8e$K%;%C%H$7$F!"%W%m%;%9$r $BDj4|E*$J3d$j9~$_$r;H$&!#(B $BNc(B: 10$B%_%jIC4V3V$G!"3d$j9~$_$r3]$1$k$h$&$K$7$+$1$k!#%W%m%;%9$N Unix $B$G$O!"Dj4|E*$J3d$j9~$_(B(10$B%_%jIC$+$i(B1$B%_%jIC$K(B1$B2s(B)$B$r;H$&J}K!$,$h$/;H$o$l$k!#(B 1$B2s$N3d$j9~$_$r(B tick $B$H$$$&!#(B
    $B"#(BLinux task$B9=B$BN$H(Bnice$BCM(B
    Linux $B$N%W%m%;%9$O!"(Btask $B9=B$BN$GI=8=$5$l$F$$$k!#(B
    $B"!(Btask_struct$B9=B$BN(B
    
    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 $B$NCf$K!"(Bstruct sched_entity $B$,$"$k!#(B
    $B"!(Bpolicy
    Linux $B$G$O!"%9%1%8%e!<%j%s%0$N%]%j%7!<$,Bg$-$/(B2$Bo$N;~J,3d$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
    
    SCHED_NORMAL
    $BEAE}E*$J%W%m%;%9!#;~J,3d(B(time sharing)
    SCHED_BATCH
    $B%Q%C%A8~$1!#0lEY(BCPU$B$r3d$jEv$F$?$i2# SCHED_IDLE
    nice 19 $B$h$j$bDc$$M%@hEY!#(B
    SCHED_FIFO (first in first out)
    $B SCHED_RR (round robin)
    $B
    $B"!(Bprio$B$H(Bstatic_prio
    
    static_prio
    nice$BCM$rJ];}$9$k!#(B $B$?$@$7!"
    nice$BCM$NHO0O(B -20..19 $B$r(B 0..39 $B$K$9$k$?$a$K(B 20
    $Be$2$k$?$a$N(B 100 (MAX_RT_PRIO)
  prio
  $B%9%1%8%e!<%j%s%0$KMQ$$$kM%@hEY$rJ];}$9$k!#(B prio $B$r8+$k$H!"DL>o$N%W%m%;%9$+e$J$i!"DL>o$N%W%m%;%9!#DL>o$N%W%m%;%9$N(B prio $B$O!"(B100$B$+$i(B140$B!#(B
  $B"!(Bgetpriority()$B%7%9%F%`!&%3!<%k(B
  
  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() $B$O!"(Bwhich $B$H(B who $B$N(B 2$B0z?t!#(B
  which $B$,(B PRIO_PROCESS $B$J$i!"(Bwho $B$O!"(Bpid$B!#(B
  who $B$,(B 0 $B$J$i!"<+J,<+?H(B(current)$B!#(B
  who $B$,(B 0 $B0J30$J$i(B find_task_by_vpid()$B$G%W%m%;%9$rC5$9!#(B
  $B%W%m%;%9$,8+$D$+$l$P!"(Btask_struct $B$N(B static_prio $B$NCM$rJV$9!#(B
  
  $B"!(Bse.load.weight
  static_prio $B$O!"(Bse.load.weight $B$NCM$r7h$a$k$?$a$K;H$o$l$k!#(B
  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)
  $BM%@hEY(B static_prio $B$O!"(Bstruct sched_entity se $B$N(B se.load.weight $B$H$=$N5U?t(B se.load.inv_weight$B!!$KH?1G$5$l$k!#(Bse.load.{weight,inv_weight} $B$NCM$O!"(B $B8e$K!"(Bvruntime $B$N7W;;$N=E$_$E$1$K;H$o$l$k!#(B
  $B"#%9%1%8%e!<%i$H%l%G%#!&%-%e!<(B
  
  $B"!(Bsched_class
  $B%*%V%8%'%/%H;X8~$N%/%i%9$HF1$80UL#!#(B $B%9%1%8%e!<%i$N$?$a$N sched_class$B$N $BL>A0(B $B@bL@(B enqueue_task $B%W%m%;%9$, dequeue_task $B%W%m%;%9$, yield_task CPU$B$r>y$k!#(Bdequeue$B$7$F(Benqueue check_preempt_curr $B pick_next_task $B set_curr_task $B%9%1%8%e!<%j%s%0!&%/%i%9$,JQ99$5$l$?(B task_tick $B%?%$%^3d9~$_(B(tick)$B$N;~$K8F$P$l$k(B task_new $B?7$7$$%W%m%;%9$,@8@.$5$l$?(B
  $B"!(Bsched_class$B;H$$J}(B
  $B%/%i%9$K1~$8$F(B enqueue, dequeue $B$,9T$o$l$k!#(B
  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: }
  
  $B"!(BLinux$B$N%9%1%8%e!<%j%s%0!&%/%i%9(B
  
  fair_sched_class
  $B8xJ?$rL\;X$9!#(Btask_struct $B$N(B policy $B$,(B SCHED_NORMAL $B$N;~$K;H$o$l$k!#(B
  rt_sched_class
  $B
  $B"!%9%1%8%e!<%i$N@_Dj(B
  
  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 $B$N(B sched_class $B$O!"(B p->prio $B$NCM$K1~$8$F(B &rt_sched_class $B$+(B &fair_sched_class $B$N$I$A$i$+$r;X$9!#(B
  if $BJ8$NCf$KF~$C$F$$$k(B likely() $B$d(B unlikely() $B$OL5;k$7$FNI$$!#(B ($BJ,4tM=B,$K$h$k:GE,2=$K;H$o$l$k!#(B)
  
  $B"!(BCFS(Completely Fair Scheduler)
  CFS $B$O!"(BLinux $B$N%9%1%8%e!<%i$N8GM-L>;l!#(B fair $B$rL\;X$7$F$O$$$k$,!"K\Ev$K(B complete $B$+$H8@$o$l$k$HITL@!#(B
  
  $B3F%W%m%;%9$N(B se.vruntime ($B%J%NICC10L(B) $B$,>CHq$7$?(BCPU$B;~4V$r$b$D!#(B
  $B%W%m%;%9$O!"(Bse.vruntime $B$,>.$5$$=g$K%=!<%H$5$l$?%j%9%H$K$D$J$,$l$k!#(B
  $B%9%1%8%e!<%i$O!"(Bse.vruntime $B$,:G$b>.$5$$%W%m%;%9(B($B%j%9%H$N0lHV:8(B) $B$r $B$"$kDxEY!".$5$/$J$k!#$=$&$J$k$H!"%j%9%H$+$i$=$N%W%m%;%9$r $B$?$@$7!"$"$^$j7c$7$/@Z$jBX$($k$H!"%-%c%C%7%e$,8z$+$J$/$J$k$N$G!"$"(B $B$k(B granularity $B$O!"
  $B"!(Brunqueues($B%j%9%HE*$J8+J}(B)
  Linux $B$K$*$1$k(B ready queue $B$N(B1$B
  
  $B?^(B? runqueue$B$N9=B$(B
  
  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$B$4$H$K(B) runqueue $B$,$"$k!#(B
  runqueue $B$K$O!"(BCFS(Completely Fair Scheduler))$B$N$?$a$N9=B$BN(B cfs_rq (cfs run queue)$B$,$"$k!#(B
  cfs_rq $B$K$O!"(Btasks_timeline $B$,$"$k!#(B
  tasks_timeline $B$O!"%W%m%;%9(B(task_struct) $B$N(B se (struct sched_entity) $B$rDL$8$F!"%W%m%;%9$N%j%9%H$r;}$C$F$$$k!#(B
  
  $B"!@V9uLZ(B(red-black tree (rbtree))
  $B@V9uLZ(B(red-black tree) $B$O!"J?9UFsJ,C5:wLZ(B(self-balancing binary search tree)$B$N0l
  $BFsJ,C5:wLZ$H$O!"
  $B3F@a$K%-!<$,$"$k!#(B
  $B:8$NItJ,LZ$O!":,$h$j$b>.$5$$%-!<$@$1$r$b$DFsJ,C5:wLZ!#(B
  $B:8$NItJ,LZ$O!":,$h$j$b>.$5$$%-!<$@$1$r$b$DFsJ,C5:wLZ!#(B
  $BJ?9ULZ(B(balanced tree)$B!"$^$?$O!"9b$5J?9ULZ(B(height-balanced tree)$B$O!"G$0U(B $B$N@a$G:81&$N9b$5$N:9$,0lDj0J2
  Linux $B$G$O!"@V9uLZ$r%=!<%H$5$l$?MWAG$,JB$V%j%9%H$r$B"!(BLinux red-black tree$B$N4pK\A`:n(B $B7?Dj5A$G!"3FMWAG$K
  struct rb_node node (rb_right, rb_left, rb_parent_color)
  $B%-!<$K$J$k%U%#!<%k%I(B
$B8!:w(B
1. $B8=:_$N%N!<%I$H%-!<$rHf3S(B
2. $BEy$7$$$J$i8+$D$+$C$?(B
3. $B%-!<$,>.$5$$$J$i:8$N;^$X(B
4. $B%-!<$,Bg$-$$$J$i1&$N;^$X(B
5. $B;^$,$J$1$l$P%-!<$OB8:_$7$J$$(B
$BA^F~(B
1. $B8=:_$N%N!<%I$H%G!<%?$N%-!<$rHf3S(B
2. $B%-!<$,>.$5$$$J$i:8$N;^$r!V?F!W(B
3. $B%-!<$,Bg$-$$$J$i1&$N;^$r!V?F!W(B
4. $B%-!<$,Ey$7$$$J$i%(%i!<(B($B=EJ#(B)
5. $B!V?F!W$+$i%G!<%?$X$N%j%s%/$r:n@.$9$k(B(rb_link_node())
6. $BJ?9U$K$J$k$h$&$K$9$k(B(rebalancing, recoloring, rb_insert_color())
$B"!(Brunqueues(red-black tree)
$B%l%G%#!&%-%e!<$O!"
$B?^(B? runqueue$B$N9=B$(B(red-black tree)

$B"!(B__enqueue_entity()
__enqueue_entity()$B$O!"(BCFS $B$GLZ9=B$$KMWAG$r(B1$B8DDI2C$9$k4X?t$G$"$k!#(B
```
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:	}
```
- $BJ?9UFsJ,C5:wLZ$N0l $B%-!<$O!"(Bvruntime$B!#(Bvruntime $B$,>.$5$$$[$I:8$KMh$k!#(B
- vruntime $B$,8=:_$N%N!<%I$h$j>.$5$1$l$P!":8(B(&parent->rb_left), $BBg$-$1$l$P1&(B(&parent->rb_right) $B$K?J$`!#(B
- $B0lHV:8$J$i!"%-%c%C%7%e$H$7$F(B cfs_rq->rb_leftmost $B$K$bJ]B8!#(B
- $B:G8e$K(B rb_insert_color() $B$r8F$S=P$7$F!"%P%i%s%9$r2sI|$9$k!#(B
$B"!(Btick$B$4$H$N;E;v(B
scheduler_tick() $B$O!"(Btick $B$4$H$KDj4|E*$K8F$S=P$5$l$k!#(B 1 tick $B$O!"(B10 $B%_%jIC$+$i(B1 $B%_%jIC!#(B
```
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 $B%/%i%9$N(B task_tick() $B$r8F$S=P$9!#(B
$B"!(Bentity_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() $B$O!"(Btick $B$4$H$KDj4|E*$K8F$S=P$5$l$k!#(B
- task_tick_fair() $B$O!"(Bentity_tick() $B$r8F$V!#(B
- entity_tick() $B$O!"(Bupdate_curr() $B$r8F$V!#(B
- update_curr() $B$O!"$^$:!"8=:_$N;~9o$r(B struct cfs_rq $B$+$iF@$F$$$k!#(B
- $B $B$3$l$r!"0z?t$K(B __update_curr() $B$r8F$S=P$7$F$$$k!#(B
- __update_curr() $B$O!"(Bdelta_exec$B!!$r$5$^$6$^$JMWAG$K2C$($F$$$k!#(B
- curr ($B8=:_
  $B"#%/%$%:(B3 $B%W%m%;%9!"%9%1%8%e!<%j%s%04XO"(B
  
  $B!zLdBj(B(301) nice$BCM(B
  $BNc(B1: $B
- $B%W%m%;%9(BA: nice$BCM(B0 ($BI8=`(B)
- $B%W%m%;%9(BB: nice$BCM(B1 ($BM%@hEY$,Dc$$(B)
19$BIC4Vl9g!"%W%m%;%9(BA$B$H%W%m%;%9(BB$B$O!"$=$l$>$l2?IC$:$D(B CPU$B;~4V$,3d$jEv$F$i$l$k$H4|BT$5$l$k$+!#(B
$B!zLdBj(B(302) $BJ?9UFsJ,C5:wLZ$K$h$k%l%G%#!&%-%e!<$N
$B%l%G%#!&%-%e!<$r $B!zLdBj(B(303) $BFsJ,C5:wLZ$K$h$k%l%G%#!&%-%e!<$N $B0J2<$N?^$O!"(B4$B$D$NMWAG$r;}$D%j%9%H$rI=$7$F$$$k!#3FMWAG$K$O!"%-!<$,$"$j!"(B $BM%@hEY$rI=$7$F$$$k$b$N$H$9$k!#(B

$B?^(B? 4$B$D$NMWAG$r;}$D%j%9%H9=B$(B
$B$3$N%j%9%H$rI=8=$7$?FsJ,C5:wLZ$r#1$D:n$j!"@a$H;^!JLp0u!K$rMQ$$$F?^<($7(B $B$J$5$$!#$?$@$7!"LZ$O%P%i%s%9$r$7$F$$$J$/$F$bNI$$$b$N$H$9$k!#(B
$BCm0U(B: $B@5$7$$FsJ,C5:wLZ$O!"J#?tB8:_$9$k!#(B
Last updated: 2012/01/08 22:18:49

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