Linux内核设计与实现之进程的调度

pulbieup

9 i; S/ {& C& Q( k- i9 L主要内容：
$ A& L, S0 c3 W) D" |& [
什么是调度
调度实现原理
Linux上调度实现的方法
调度相关的系统调用
1. 什么是调度
) u/ z* t" L% W! D现在的操作系统都是多任务的，为了能让更多的任务能同时在系统上更好的运行，需要一个管理程序来管理计算机上同时运行的各个任务（也就是进程）。

这个管理程序就是调度程序，它的功能说起来很简单：
* j  K- v1 ~+ u, c" Z6 Y, V
决定哪些进程运行，哪些进程等待
决定每个进程运行多长时间
5 c, a9 |. o; B此外，为了获得更好的用户体验，运行中的进程还可以立即被其他更紧急的进程打断。

总之，调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程，进程切换过多，CPU的时间会浪费在切换上)；另一方面，保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。

" p! c, a4 k1 _2 |  V# t
3 X2 H6 J) {7 c7 x- m9 R& {0 }
2. 调度实现原理
- o0 A& `  [/ x- S% {- }) |前面说过，调度功能就是决定哪个进程运行以及进程运行多长时间。

, c8 D( n1 M. m# B8 a决定哪个进程运行以及运行多长时间都和进程的优先级有关。为了确定一个进程到底能持续运行多长时间，调度中还引入了时间片的概念。
$ L9 a5 d' a5 t! e
' D' I0 {6 v0 K0 {& w2.1 关于进程的优先级
进程的优先级有2种度量方法，一种是nice值，一种是实时优先级。
" K6 O/ `: V4 h: E- x+ D  w. ~
nice值的范围是-20～+19，值越大优先级越低，也就是说nice值为-20的进程优先级最大。

实时优先级的范围是0～99，与nice值的定义相反，实时优先级是值越大优先级越高。

1 c) L/ F8 J, J+ O. A实时进程都是一些对响应时间要求比较高的进程，因此系统中有实时优先级高的进程处于运行队列的话，它们会抢占一般的进程的运行时间。
0 v* G; T- a8 V


/ v' d- g( m6 P2 `进程的2种优先级会让人不好理解，到底哪个优先级更优先？一个进程同时有2种优先级怎么办？
& a% D  y, D) _
6 f# Q# B5 ^2 q- n) A其实linux的内核早就有了解决办法。
" a, r* X& q# k$ X8 h1 P" \
8 f$ O3 e5 L( i# b# Q对于第一个问题，到底哪个优先级更优先？

) k0 m$ d  l$ k; H. X/ P! t答案是实时优先级高于nice值，在内核中，实时优先级的范围是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定义参见 include/linux/sched.h

" m# z9 ?# p9 d* D1611 #define MAX_USER_RT_PRIO        100
8 G5 m& G5 j/ x4 U- e2 Y1612 #define MAX_RT_PRIO             MAX_USER_RT_PRIO
. F0 l( q( O/ L3 H! Cnice值在内核中的范围是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO
; c) o* I: B" ~$ s: |2 g
8 n. g0 d$ G( L& H( a6 f3 y0 m! D1614 #define MAX_PRIO                (MAX_RT_PRIO + 40)
6 u  `4 k, }: R; J3 o

第二个问题，一个进程同时有2种优先级怎么办？
2 X* p* I+ \0 U$ H, I: z7 I
& @6 V: N1 d% J" C9 ^答案很简单，就是一个进程不可能有2个优先级。一个进程有了实时优先级就没有Nice值，有了Nice值就没有实时优先级。

我们可以通过以下命令查看进程的实时优先级和Nice值：(其中RTPRIO是实时优先级，NI是Nice值)
4 I5 m8 }/ K% S/ n2 O& V% I  M
2 t4 b8 Q7 q) p* o' d, O9 ^复制代码
$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
, F( [, L: y* l2 ^, ]" }0 g0 |S   UID   PID  PPID RTPRIO  NI     TIME COMMAND
" q8 @- j6 U7 @) ^$ FS     0     1     0      -   0 00:00:00 systemd
S     0     2     0      -   0 00:00:00 kthreadd
S     0     3     2      -   0 00:00:00 ksoftirqd/0
  t8 @% U/ ?7 K0 {9 ]% s; ]S     0     6     2     99   - 00:00:00 migration/0
9 x3 S+ J  D4 {# Z% C; FS     0     7     2     99   - 00:00:00 watchdog/0
( F# ~/ U) @, TS     0     8     2     99   - 00:00:00 migration/1
S     0    10     2      -   0 00:00:00 ksoftirqd/1
+ p( f& z9 ^( k0 r/ b/ ]S     0    12     2     99   - 00:00:00 watchdog/1
S     0    13     2     99   - 00:00:00 migration/2
  y* `" [' G. Y* FS     0    15     2      -   0 00:00:00 ksoftirqd/2
S     0    16     2     99   - 00:00:00 watchdog/2
+ d# k) h* I( z4 o) C$ i$ D4 FS     0    17     2     99   - 00:00:00 migration/3
S     0    19     2      -   0 00:00:00 ksoftirqd/3
; `* N/ s2 P% g1 a; i! jS     0    20     2     99   - 00:00:00 watchdog/3
S     0    21     2      - -20 00:00:00 cpuset
! ^+ J% a( L- f5 E8 o$ [S     0    22     2      - -20 00:00:00 khelper
4 o" \1 e5 V* E, H复制代码
- y3 j% {# {" z' X
: `! u  g+ ?4 L. @
2.2 关于时间片
有了优先级，可以决定谁先运行了。但是对于调度程序来说，并不是运行一次就结束了，还必须知道间隔多久进行下次调度。
" B5 D* ^6 k6 W% ^! y3 ]3 I
于是就有了时间片的概念。时间片是一个数值，表示一个进程被抢占前能持续运行的时间。

也可以认为是进程在下次调度发生前运行的时间(除非进程主动放弃CPU，或者有实时进程来抢占CPU)。

  x6 C6 l: B, g' x, ^# {( ]时间片的大小设置并不简单，设大了，系统响应变慢(调度周期长)；设小了，进程频繁切换带来的处理器消耗。默认的时间片一般是10ms

% ^: x  @  Q8 _" v* h3 X

2.3 调度实现原理（基于优先级和时间片）
下面举个直观的例子来说明：

, r! S% G) D4 P1 M/ Q* t" `( P假设系统中只有3个进程ProcessA(NI=+10)，ProcessB(NI=0)，ProcessC(NI=-10)，NI表示进程的nice值，时间片=10ms

1) 调度前，把进程优先级按一定的权重映射成时间片(这里假设优先级高一级相当于多5msCPU时间)。
# Y* B, @. X) u/ i
' `9 ]5 {9 |/ Y$ H9 P; T    假设ProcessA分配了一个时间片10ms，那么ProcessB的优先级比ProcessA高10(nice值越小优先级越高)，ProcessB应该分配10*5+10=60ms，以此类推，ProcessC分配20*5+10=110ms

2) 开始调度时，优先调度分配CPU时间多的进程。由于ProcessA(10ms),ProcessB(60ms),ProcessC(110ms)。显然先调度ProcessC

3) 10ms(一个时间片)后，再次调度时，ProcessA(10ms),ProcessB(60ms),ProcessC(100ms)。ProcessC刚运行了10ms，所以变成100ms。此时仍然先调度ProcessC

4) 再调度4次后(4个时间片)，ProcessA(10ms),ProcessB(60ms),ProcessC(60ms)。此时ProcessB和ProcessC的CPU时间一样，这时得看ProcessB和ProcessC谁在CPU运行队列的前面，假设ProcessB在前面，则调度ProcessB
' p, Q1 l! J1 F- \0 P% l
5) 10ms(一个时间片)后，ProcessA(10ms),ProcessB(50ms),ProcessC(60ms)。再次调度ProcessC
/ z7 b0 F( l, I0 J: c
6) ProcessB和ProcessC交替运行，直至ProcessA(10ms),ProcessB(10ms),ProcessC(10ms)。
* @& y# x, R- ~
    这时得看ProcessA，ProcessB，ProcessC谁在CPU运行队列的前面就先调度谁。这里假设调度ProcessA

8 B* j# i0 U" x. y+ q) ~7) 10ms(一个时间片)后，ProcessA(时间片用完后退出),ProcessB(10ms),ProcessC(10ms)。
8 @, j- }6 S* k1 k3 M" V- w
' v: I7 e( ~$ Z" v4 ?8) 再过2个时间片，ProcessB和ProcessC也运行完退出。
5 M8 l- U9 ?4 x3 \5 `, N* h0 ~
. F/ u) ]; ]* J1 q! ]! P& v3 C这个例子很简单，主要是为了说明调度的原理，实际的调度算法虽然不会这么简单，但是基本的实现原理也是类似的：

6 c3 t- d% i( w" ?1）确定每个进程能占用多少CPU时间(这里确定CPU时间的算法有很多，根据不同的需求会不一样)
9 L1 e' H% p" G; Y* N# M
& d8 ?$ a& r4 t; k6 T: D7 U2）占用CPU时间多的先运行

3）运行完后，扣除运行进程的CPU时间，再回到 1）
8 L  H7 z& l) r: Y! ]
% {. |9 D" z$ s" j
6 W- s9 S5 Z2 c1 P) P5 ]
3. Linux上调度实现的方法
; ^1 j* D, [  F. Z* PLinux上的调度算法是不断发展的，在2.6.23内核以后，采用了“完全公平调度算法”，简称CFS。
( ~, W* x* o  e: @( ?2 ]) u$ z* d; S
CFS算法在分配每个进程的CPU时间时，不是分配给它们一个绝对的CPU时间，而是根据进程的优先级分配给它们一个占用CPU时间的百分比。
, _% j. A; m8 r# `" Y8 p
/ C& _! f' j2 y1 o比如ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分别占用CPU的百分比为：ProcessA(10%)，ProcessB(30%)，ProcessC(60%)
# L! x' a& A& J  M$ B8 @- j
+ A& J4 E" S# x. v, ~! P% y因为总共是100%，ProcessB的优先级是ProcessA的3倍，ProcessC的优先级是ProcessA的6倍。
* y6 h! \1 J- x8 N8 @8 \& S% a
% H! m- C8 M' n/ u! A8 A2 K/ B$ D0 n
! y  b# L' f" X4 F3 K! W3 c
2 W+ f. ]: P' B1 A. vLinux上的CFS算法主要有以下步骤：(还是以ProcessA(10%)，ProcessB(30%)，ProcessC(60%)为例)

1)计算每个进程的vruntime(注1)，通过update_curr()函数更新进程的vruntime。
& p8 t. _+ N5 i- W# x& [
+ n% {, x% w+ M7 O8 v2)选择具有最小vruntime的进程投入运行。（注2）

3)进程运行完后，更新进程的vruntime，转入步骤2) （注3）

" d1 ~5 |* Y8 Q0 C; C
' i, k! w- E4 V8 ]
注1. 这里的vruntime是进程虚拟运行的时间的总和。vruntime定义在：kernel/sched_fair.c 文件的 struct sched_entity 中。
$ g; Q* v1 C$ t0 J/ B+ x
4 n. a0 A  d0 L$ D+ g- q: D# U( h; m0 B7 E

* o; m; M/ W3 L/ ?. Y8 ]) _0 e7 |注2. 这里有点不好理解，根据vruntime来选择要运行的进程，似乎和每个进程所占的CPU时间百分比没有关系了。
+ Q& t3 e; Y& u+ l
' k4 n4 A9 i, w. K) i* u9 ]7 k; g+ r1）比如先运行ProcessC，(vr是vruntime的缩写)，则10ms后：ProcessA(vr=0)，ProcessB(vr=0)，ProcessC(vr=10)

( m9 _; Q5 Q8 U9 Y5 n2）那么下次调度只能运行ProcessA或者ProcessB。(因为会选择具有最小vruntime的进程)

长时间来看的话，ProcessA、ProcessB、ProcessC是公平的交替运行的，和优先级没有关系。
* J3 X8 Q. a5 ~
3 P# i1 N4 h8 |' F$ \5 I而实际上vruntime并不是实际的运行时间，它是实际运行时间进行加权运算后的结果。
9 i& ?, w, E% k( B- }) U
* Y" W6 w$ T: |& p2 C9 Y比如上面3个进程中ProcessA(10%)只分配了CPU总的处理时间的10%，那么ProcessA运行10ms的话，它的vruntime会增加100ms。
* n9 v2 |- ~( {( P
  B  @" a9 H2 R6 v1 L0 w以此类推，ProcessB运行10ms的话，它的vruntime会增加(100/3)ms,ProcessC运行10ms的话，它的vruntime会增加(100/6)ms。
* s2 m8 D( f1 w/ ^4 O8 j
+ F$ q  s" c2 H实际的运行时，由于ProcessC的vruntime增加的最慢，所以它会获得最多的CPU处理时间。
1 q5 R9 A$ B# ~. z0 k9 `
上面的加权算法是我自己为了理解方便简化的，Linux对vruntime的加权方法还得去看源码^-^
+ \. Z2 Z' ?5 m0 q6 D; U+ J8 T
. s4 K2 e! ?4 ]$ Z6 z
9 |4 V9 [3 ^1 E/ K) T$ d. X1 O
注3.Linux为了能快速的找到具有最小vruntime，将所有的进程的存储在一个红黑树中。这样树的最左边的叶子节点就是具有最小vruntime的进程，新的进程加入或有旧的进程退出时都会更新这棵树。
  q$ k  S4 p. }8 `
, Q2 m& T# ~* c9 b: @% T
* j% R2 ]; c/ J2 h0 l; H' |+ |
其实Linux上的调度器是以模块方式提供的，每个调度器有不同的优先级，所以可以同时存在多种调度算法。

每个进程可以选择自己的调度器，Linux调度时，首先按调度器的优先级选择一个调度器，再选择这个调度器下的进程。


) O3 D& b: `6 r9 b, M
" c3 J7 r! Y7 g) x4. 调度相关的系统调用
8 H6 H& Y; u. A( j6 F( A$ t调度相关的系统调用主要有2类：

" k: [5 `- t6 z9 Q/ ~1) 与调度策略和进程优先级相关 (就是上面的提到的各种参数，优先级，时间片等等) - 下表中的前8个
) `8 H$ G5 S) q" c
2) 与处理器相关 - 下表中的最后3个

系统调用	描述
nice()	设置进程的nice值
sched_setscheduler()	设置进程的调度策略，即设置进程采取何种调度算法
sched_getscheduler()	获取进程的调度算法
sched_setparam()	设置进程的实时优先级
sched_getparam()	获取进程的实时优先级
sched_get_priority_max()	获取实时优先级的最大值，由于用户权限的问题，非root用户并不能设置实时优先级为99
sched_get_priority_min()	获取实时优先级的最小值，理由与上面类似
sched_rr_get_interval()	获取进程的时间片
sched_setaffinity()	设置进程的处理亲和力，其实就是保存在task_struct中的cpu_allowed这个掩码标志。该掩码的每一位对应一个系统中可用的处理器，默认所有位都被设置，即该进程可以再系统中所有处理器上执行。 用户可以通过此函数设置不同的掩码，使得进程只能在系统中某一个或某几个处理器上运行。
sched_getaffinity()	获取进程的处理亲和力
sched_yield()	暂时让出处理器

9 j' v/ `" K8 E1 y" M


" T7 b9 c6 _2 l  r5 v# H' f" P/ v

NingW

Linux内核设计与实现之进程的调度