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

pulbieup

! |  ~6 L6 v8 H主要内容：
7 ]6 X/ }4 g4 \! P# ]% n
什么是调度
调度实现原理
Linux上调度实现的方法
9 |6 y9 N4 D' P- H调度相关的系统调用
1. 什么是调度
现在的操作系统都是多任务的，为了能让更多的任务能同时在系统上更好的运行，需要一个管理程序来管理计算机上同时运行的各个任务（也就是进程）。
. y* t. R8 H6 V1 {
这个管理程序就是调度程序，它的功能说起来很简单：
# {- [) D6 H. ]. c2 G
决定哪些进程运行，哪些进程等待
8 K+ s$ t3 x1 W" q1 {4 C/ k# t决定每个进程运行多长时间
此外，为了获得更好的用户体验，运行中的进程还可以立即被其他更紧急的进程打断。

总之，调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程，进程切换过多，CPU的时间会浪费在切换上)；另一方面，保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。
$ j& b; R6 s8 h$ s1 n5 T9 R: B) p% d
4 a" R% a; D: u! [% q3 J

/ ]% D* g8 r8 \/ n9 b) }2. 调度实现原理
# k; F+ {$ ~$ D" [$ }' F! z前面说过，调度功能就是决定哪个进程运行以及进程运行多长时间。

5 ?, d7 x4 x# f0 a' B  o0 Y决定哪个进程运行以及运行多长时间都和进程的优先级有关。为了确定一个进程到底能持续运行多长时间，调度中还引入了时间片的概念。
( M1 c6 G: D" e! C
! M$ l3 ~+ W( u4 N* A' S2.1 关于进程的优先级
7 B1 V0 |/ ~9 x. W进程的优先级有2种度量方法，一种是nice值，一种是实时优先级。

nice值的范围是-20～+19，值越大优先级越低，也就是说nice值为-20的进程优先级最大。

- t5 _; M: Y: y% f( `实时优先级的范围是0～99，与nice值的定义相反，实时优先级是值越大优先级越高。
: r( J' o$ j" G' ^1 C5 K; G" A5 `
实时进程都是一些对响应时间要求比较高的进程，因此系统中有实时优先级高的进程处于运行队列的话，它们会抢占一般的进程的运行时间。



进程的2种优先级会让人不好理解，到底哪个优先级更优先？一个进程同时有2种优先级怎么办？
: |) `) |% J, Y  m9 b, K9 W
其实linux的内核早就有了解决办法。
" V4 v: c" h0 W- b
0 d/ t4 h! R& A3 q: z" U对于第一个问题，到底哪个优先级更优先？

6 g* y& R  \9 H* t7 o答案是实时优先级高于nice值，在内核中，实时优先级的范围是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定义参见 include/linux/sched.h

: i" I0 ~% y8 o' J( s3 {1611 #define MAX_USER_RT_PRIO        100
0 P+ a+ {& C; J- i3 a1612 #define MAX_RT_PRIO             MAX_USER_RT_PRIO
nice值在内核中的范围是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO
0 Q) j, I/ W7 e) ~
1614 #define MAX_PRIO                (MAX_RT_PRIO + 40)
3 X8 h* `( {# l3 u+ Q; ?) m$ W
4 f3 N9 I4 T, u5 z. h, O5 h* s
# m4 S% X) s8 @+ B! x7 Y第二个问题，一个进程同时有2种优先级怎么办？
. x5 D0 D' P8 _. r, f- p
8 y. H5 H- [! `$ a答案很简单，就是一个进程不可能有2个优先级。一个进程有了实时优先级就没有Nice值，有了Nice值就没有实时优先级。
$ k& O/ H+ Y& Z. B
8 [, T8 b% }4 ?# k我们可以通过以下命令查看进程的实时优先级和Nice值：(其中RTPRIO是实时优先级，NI是Nice值)

复制代码
, R" S8 \& l" \* g  F% k: W$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
S   UID   PID  PPID RTPRIO  NI     TIME COMMAND
; U# a1 w. k: D3 IS     0     1     0      -   0 00:00:00 systemd
5 {! t, }( z3 a# QS     0     2     0      -   0 00:00:00 kthreadd
S     0     3     2      -   0 00:00:00 ksoftirqd/0
. u/ s: y4 C7 J8 b2 x& WS     0     6     2     99   - 00:00:00 migration/0
S     0     7     2     99   - 00:00:00 watchdog/0
4 I, I7 g' K5 R0 N' HS     0     8     2     99   - 00:00:00 migration/1
2 r3 B5 O* @- ~8 XS     0    10     2      -   0 00:00:00 ksoftirqd/1
3 U, c0 B. {, O0 iS     0    12     2     99   - 00:00:00 watchdog/1
3 c. ]9 w2 ]) MS     0    13     2     99   - 00:00:00 migration/2
S     0    15     2      -   0 00:00:00 ksoftirqd/2
- n5 r9 K" R8 D) N* i3 O# aS     0    16     2     99   - 00:00:00 watchdog/2
/ V! o: H% [) S) \& }S     0    17     2     99   - 00:00:00 migration/3
8 [/ b' n. r/ n% DS     0    19     2      -   0 00:00:00 ksoftirqd/3
# s* M* y$ {4 n% i2 o$ h% XS     0    20     2     99   - 00:00:00 watchdog/3
# a1 a# z$ J2 D+ o0 s3 f, }+ h6 x0 L" c! [S     0    21     2      - -20 00:00:00 cpuset
S     0    22     2      - -20 00:00:00 khelper
+ {0 a' j: v4 s" E4 \" v3 W复制代码
+ f- Z: h% I+ J4 d
- [8 P% m" H0 R' b0 y
2.2 关于时间片
有了优先级，可以决定谁先运行了。但是对于调度程序来说，并不是运行一次就结束了，还必须知道间隔多久进行下次调度。

/ B$ z. v0 W) j8 V) j9 U于是就有了时间片的概念。时间片是一个数值，表示一个进程被抢占前能持续运行的时间。
  X8 M. {+ B/ V9 s1 }
也可以认为是进程在下次调度发生前运行的时间(除非进程主动放弃CPU，或者有实时进程来抢占CPU)。

时间片的大小设置并不简单，设大了，系统响应变慢(调度周期长)；设小了，进程频繁切换带来的处理器消耗。默认的时间片一般是10ms
$ O7 `( E8 j5 m* P5 s& a


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

7 a$ k# Y% z; T* h" _2 r: ?% h) {  B假设系统中只有3个进程ProcessA(NI=+10)，ProcessB(NI=0)，ProcessC(NI=-10)，NI表示进程的nice值，时间片=10ms

  U3 f$ c% H3 t# n# T5 d+ S1) 调度前，把进程优先级按一定的权重映射成时间片(这里假设优先级高一级相当于多5msCPU时间)。
9 q0 ^% }. W- E) i' a; |
    假设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

+ t5 ^; m  l# ]6 R* b7 D, f) \3) 10ms(一个时间片)后，再次调度时，ProcessA(10ms),ProcessB(60ms),ProcessC(100ms)。ProcessC刚运行了10ms，所以变成100ms。此时仍然先调度ProcessC
7 J; S. R5 n. ~
4) 再调度4次后(4个时间片)，ProcessA(10ms),ProcessB(60ms),ProcessC(60ms)。此时ProcessB和ProcessC的CPU时间一样，这时得看ProcessB和ProcessC谁在CPU运行队列的前面，假设ProcessB在前面，则调度ProcessB
% R7 ~" N2 F7 {; p! m4 [/ I
5) 10ms(一个时间片)后，ProcessA(10ms),ProcessB(50ms),ProcessC(60ms)。再次调度ProcessC

, v% ^/ C  Z, G8 }( |8 w! M/ U; j6) ProcessB和ProcessC交替运行，直至ProcessA(10ms),ProcessB(10ms),ProcessC(10ms)。
) N5 P1 }! J" f3 Y  X
    这时得看ProcessA，ProcessB，ProcessC谁在CPU运行队列的前面就先调度谁。这里假设调度ProcessA
# F1 i$ X+ S/ x( i. r/ [: @- G0 n
- `# }" ?2 \6 e0 D1 a7) 10ms(一个时间片)后，ProcessA(时间片用完后退出),ProcessB(10ms),ProcessC(10ms)。

  u  ~( m6 q" s# }/ j7 u9 ?! n8) 再过2个时间片，ProcessB和ProcessC也运行完退出。

这个例子很简单，主要是为了说明调度的原理，实际的调度算法虽然不会这么简单，但是基本的实现原理也是类似的：

1）确定每个进程能占用多少CPU时间(这里确定CPU时间的算法有很多，根据不同的需求会不一样)
3 q8 c/ i4 @1 e3 I, J" G
2）占用CPU时间多的先运行

! y) i9 R4 E/ |  p7 w9 b7 z3）运行完后，扣除运行进程的CPU时间，再回到 1）
, K& Q( F# z# ]! i) S. ?

$ X# Y: S# _# r
6 q, w! g, q  t3. Linux上调度实现的方法
) h" E9 J) n1 ^7 VLinux上的调度算法是不断发展的，在2.6.23内核以后，采用了“完全公平调度算法”，简称CFS。
! n/ h9 L. x9 g
3 [( n' E: ?7 a8 nCFS算法在分配每个进程的CPU时间时，不是分配给它们一个绝对的CPU时间，而是根据进程的优先级分配给它们一个占用CPU时间的百分比。

7 H( y# u6 \2 c) R- L% v: y比如ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分别占用CPU的百分比为：ProcessA(10%)，ProcessB(30%)，ProcessC(60%)
* w* I, G+ }" @' V3 m
因为总共是100%，ProcessB的优先级是ProcessA的3倍，ProcessC的优先级是ProcessA的6倍。
; |$ k7 B/ N4 w( l' C2 p+ i
* @: o8 C. _9 Y* E, m7 ~6 x
" F- d/ l/ l- L2 ~6 J2 z+ a2 b
" f$ e6 L* Q, @7 ^Linux上的CFS算法主要有以下步骤：(还是以ProcessA(10%)，ProcessB(30%)，ProcessC(60%)为例)
2 d9 @/ s; N, D8 w
/ }9 d3 M; Z" c5 T2 ]1)计算每个进程的vruntime(注1)，通过update_curr()函数更新进程的vruntime。

- V& Z# Q2 C/ ]. O% Z0 V2)选择具有最小vruntime的进程投入运行。（注2）

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


+ x7 h5 h, P+ w- e7 x
4 c( F, R$ ~3 f注1. 这里的vruntime是进程虚拟运行的时间的总和。vruntime定义在：kernel/sched_fair.c 文件的 struct sched_entity 中。

, C3 A- n! B2 y, U8 k
6 I" c: X3 n- m
注2. 这里有点不好理解，根据vruntime来选择要运行的进程，似乎和每个进程所占的CPU时间百分比没有关系了。

4 R/ f7 u2 I# D. k, L1）比如先运行ProcessC，(vr是vruntime的缩写)，则10ms后：ProcessA(vr=0)，ProcessB(vr=0)，ProcessC(vr=10)

2）那么下次调度只能运行ProcessA或者ProcessB。(因为会选择具有最小vruntime的进程)
, m: ?* _& \# B% b2 M* ^# a
5 B/ g9 X4 A0 s长时间来看的话，ProcessA、ProcessB、ProcessC是公平的交替运行的，和优先级没有关系。

而实际上vruntime并不是实际的运行时间，它是实际运行时间进行加权运算后的结果。
0 ^+ x) W4 ~. N1 f/ E7 l
比如上面3个进程中ProcessA(10%)只分配了CPU总的处理时间的10%，那么ProcessA运行10ms的话，它的vruntime会增加100ms。
+ S2 D0 J- @4 }" J* i, ?$ n
以此类推，ProcessB运行10ms的话，它的vruntime会增加(100/3)ms,ProcessC运行10ms的话，它的vruntime会增加(100/6)ms。

, R& Z( e& p" I3 |9 Y$ x0 i. e实际的运行时，由于ProcessC的vruntime增加的最慢，所以它会获得最多的CPU处理时间。

上面的加权算法是我自己为了理解方便简化的，Linux对vruntime的加权方法还得去看源码^-^
7 n' H2 M" \: |0 K4 {9 w
7 C1 V" Q: x1 u  ?  }/ [
5 q. h6 E' g- J6 |! x
! g- v4 b2 n2 r1 r$ y注3.Linux为了能快速的找到具有最小vruntime，将所有的进程的存储在一个红黑树中。这样树的最左边的叶子节点就是具有最小vruntime的进程，新的进程加入或有旧的进程退出时都会更新这棵树。
3 v$ ?: L6 h) Y

$ H4 V4 t# G! w* C0 c; B1 L
2 l- h4 O% U0 p' t% E  S其实Linux上的调度器是以模块方式提供的，每个调度器有不同的优先级，所以可以同时存在多种调度算法。

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



6 z8 V- O$ O, u! m3 S% b4 q4. 调度相关的系统调用
4 J; E2 S/ D' X调度相关的系统调用主要有2类：
2 y4 D# _' m; q0 A6 }8 Z0 e
1) 与调度策略和进程优先级相关 (就是上面的提到的各种参数，优先级，时间片等等) - 下表中的前8个
# J5 T6 u. w$ E4 n
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()	暂时让出处理器

NingW

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