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

pulbieup

5 Q  K" S& H% F7 @: W) U主要内容：
. w; m4 z4 M& f( }" i9 q
$ y. K" }2 H/ w什么是调度
, O! |" }' W  ~调度实现原理
/ O0 s6 A# v" J* TLinux上调度实现的方法
4 G* y) h) Q  g# @# z调度相关的系统调用
1. 什么是调度
! B  v! h3 Z# p3 H9 F0 f现在的操作系统都是多任务的，为了能让更多的任务能同时在系统上更好的运行，需要一个管理程序来管理计算机上同时运行的各个任务（也就是进程）。
( w3 g  @" ?5 w9 p: I4 l/ t! q
* q9 ~: C, a6 V4 W0 E- h; L4 i# s6 Z这个管理程序就是调度程序，它的功能说起来很简单：
  B+ T' V. J2 I# g3 D' V
0 x* @: a" O- ]9 W7 K4 s决定哪些进程运行，哪些进程等待
决定每个进程运行多长时间
此外，为了获得更好的用户体验，运行中的进程还可以立即被其他更紧急的进程打断。
0 Q. u1 q. m8 d9 ?. Z1 W
总之，调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程，进程切换过多，CPU的时间会浪费在切换上)；另一方面，保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。
! y5 p6 J. `6 @) {1 ^- p, m" y


9 o/ l1 h# K9 f( [0 D9 s* a2. 调度实现原理
: X; c: Z% U% Y6 j+ G" c9 Q前面说过，调度功能就是决定哪个进程运行以及进程运行多长时间。
/ l& W8 e! V# D
决定哪个进程运行以及运行多长时间都和进程的优先级有关。为了确定一个进程到底能持续运行多长时间，调度中还引入了时间片的概念。
- F- _$ V, U. g" U/ j8 Q
" o; I& O, ]3 n1 s  m! p# Y2.1 关于进程的优先级
( p, z  y5 t4 K+ I7 L1 F4 ?: d进程的优先级有2种度量方法，一种是nice值，一种是实时优先级。
! G, f9 E: z& T9 D2 F  r: ]
nice值的范围是-20～+19，值越大优先级越低，也就是说nice值为-20的进程优先级最大。
: `" x+ v" r; p; J5 x: k
实时优先级的范围是0～99，与nice值的定义相反，实时优先级是值越大优先级越高。

实时进程都是一些对响应时间要求比较高的进程，因此系统中有实时优先级高的进程处于运行队列的话，它们会抢占一般的进程的运行时间。

, [2 t+ t) N' X$ ?+ W- t6 v

, B! B9 h. E$ n& s, E7 _& G1 C进程的2种优先级会让人不好理解，到底哪个优先级更优先？一个进程同时有2种优先级怎么办？

其实linux的内核早就有了解决办法。
0 W- O' J  [4 Y
8 r" Y# N3 C3 k' N7 k对于第一个问题，到底哪个优先级更优先？
/ a/ V7 c" [8 M
答案是实时优先级高于nice值，在内核中，实时优先级的范围是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定义参见 include/linux/sched.h

& j+ m$ @0 v, W5 ]% W1611 #define MAX_USER_RT_PRIO        100
1612 #define MAX_RT_PRIO             MAX_USER_RT_PRIO
nice值在内核中的范围是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO

1614 #define MAX_PRIO                (MAX_RT_PRIO + 40)

0 B) j# I3 z: t) g6 h# M
7 n3 v' @6 e1 _+ k9 B第二个问题，一个进程同时有2种优先级怎么办？

- x# d/ N: s9 F0 q( e, k答案很简单，就是一个进程不可能有2个优先级。一个进程有了实时优先级就没有Nice值，有了Nice值就没有实时优先级。

我们可以通过以下命令查看进程的实时优先级和Nice值：(其中RTPRIO是实时优先级，NI是Nice值)

/ x* x0 Z) A8 H, g$ i复制代码
$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
7 }& e$ {0 T% r; _- V( ^" K1 |/ |S   UID   PID  PPID RTPRIO  NI     TIME COMMAND
S     0     1     0      -   0 00:00:00 systemd
S     0     2     0      -   0 00:00:00 kthreadd
, ?' ~) E$ }4 o( ?S     0     3     2      -   0 00:00:00 ksoftirqd/0
( L- D. q9 X9 q# i, x2 B5 H* D8 M2 _S     0     6     2     99   - 00:00:00 migration/0
5 F" e$ r% V' f3 fS     0     7     2     99   - 00:00:00 watchdog/0
- [4 W% S* a( g" y" f. P! qS     0     8     2     99   - 00:00:00 migration/1
2 E4 Z% X  f3 F' c' n/ _, tS     0    10     2      -   0 00:00:00 ksoftirqd/1
S     0    12     2     99   - 00:00:00 watchdog/1
+ W% a2 z4 O0 m0 pS     0    13     2     99   - 00:00:00 migration/2
8 u( `* ?' i1 p% Z+ T$ U6 e/ p: pS     0    15     2      -   0 00:00:00 ksoftirqd/2
S     0    16     2     99   - 00:00:00 watchdog/2
S     0    17     2     99   - 00:00:00 migration/3
S     0    19     2      -   0 00:00:00 ksoftirqd/3
S     0    20     2     99   - 00:00:00 watchdog/3
S     0    21     2      - -20 00:00:00 cpuset
+ ]$ f  A& ?$ X$ d" B6 oS     0    22     2      - -20 00:00:00 khelper
" W$ ^  J/ s* _+ q: I0 S: R) L复制代码
; A4 x' Q- y$ m2 h( f8 G2 s# ?, {5 I6 S

2.2 关于时间片
有了优先级，可以决定谁先运行了。但是对于调度程序来说，并不是运行一次就结束了，还必须知道间隔多久进行下次调度。
8 p! }5 ]% y# G8 F  V* q
于是就有了时间片的概念。时间片是一个数值，表示一个进程被抢占前能持续运行的时间。

也可以认为是进程在下次调度发生前运行的时间(除非进程主动放弃CPU，或者有实时进程来抢占CPU)。
! w4 c' Y" H6 ^
时间片的大小设置并不简单，设大了，系统响应变慢(调度周期长)；设小了，进程频繁切换带来的处理器消耗。默认的时间片一般是10ms


: t2 r- ~3 w- F6 m( X2 s
4 C4 L' |$ c( {; Q: Q6 I& d2.3 调度实现原理（基于优先级和时间片）
下面举个直观的例子来说明：

假设系统中只有3个进程ProcessA(NI=+10)，ProcessB(NI=0)，ProcessC(NI=-10)，NI表示进程的nice值，时间片=10ms
( y% X  w3 ?  @  _  H: r! q
' O/ F" M# f4 p) Z1) 调度前，把进程优先级按一定的权重映射成时间片(这里假设优先级高一级相当于多5msCPU时间)。

6 m/ g: J- v; q8 m+ v% p, O2 L    假设ProcessA分配了一个时间片10ms，那么ProcessB的优先级比ProcessA高10(nice值越小优先级越高)，ProcessB应该分配10*5+10=60ms，以此类推，ProcessC分配20*5+10=110ms
4 a9 Z4 y: q0 R( k9 u; P
' e% `4 `7 q! F$ i; L' m- ^% R2) 开始调度时，优先调度分配CPU时间多的进程。由于ProcessA(10ms),ProcessB(60ms),ProcessC(110ms)。显然先调度ProcessC
  {7 j4 Y! u$ w
3) 10ms(一个时间片)后，再次调度时，ProcessA(10ms),ProcessB(60ms),ProcessC(100ms)。ProcessC刚运行了10ms，所以变成100ms。此时仍然先调度ProcessC
* Q7 v+ Q* s" R
4) 再调度4次后(4个时间片)，ProcessA(10ms),ProcessB(60ms),ProcessC(60ms)。此时ProcessB和ProcessC的CPU时间一样，这时得看ProcessB和ProcessC谁在CPU运行队列的前面，假设ProcessB在前面，则调度ProcessB

5) 10ms(一个时间片)后，ProcessA(10ms),ProcessB(50ms),ProcessC(60ms)。再次调度ProcessC
0 |" t+ X2 X; b) g
6) ProcessB和ProcessC交替运行，直至ProcessA(10ms),ProcessB(10ms),ProcessC(10ms)。
, k8 Z3 j+ ~9 q: P
    这时得看ProcessA，ProcessB，ProcessC谁在CPU运行队列的前面就先调度谁。这里假设调度ProcessA

* f: K0 {2 W$ v* g$ @% [2 y# T7) 10ms(一个时间片)后，ProcessA(时间片用完后退出),ProcessB(10ms),ProcessC(10ms)。

8) 再过2个时间片，ProcessB和ProcessC也运行完退出。
1 I. P3 n" N8 \5 v! H
这个例子很简单，主要是为了说明调度的原理，实际的调度算法虽然不会这么简单，但是基本的实现原理也是类似的：

, b3 R7 R9 v  g4 U% x5 E, A: u1）确定每个进程能占用多少CPU时间(这里确定CPU时间的算法有很多，根据不同的需求会不一样)
/ w* z5 s) i5 G% d9 t
' @" V. D5 x! o3 P4 |0 c6 {) x! M! y2）占用CPU时间多的先运行

3）运行完后，扣除运行进程的CPU时间，再回到 1）
) }7 I2 a+ v9 a" n/ h7 W


; \: \; a! L" B1 Y* V3. Linux上调度实现的方法
Linux上的调度算法是不断发展的，在2.6.23内核以后，采用了“完全公平调度算法”，简称CFS。
( N5 o+ J% w- l' E. F
& D* b4 T  [; V! tCFS算法在分配每个进程的CPU时间时，不是分配给它们一个绝对的CPU时间，而是根据进程的优先级分配给它们一个占用CPU时间的百分比。

6 P7 W' h; o! T# Z% ^2 {比如ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分别占用CPU的百分比为：ProcessA(10%)，ProcessB(30%)，ProcessC(60%)

2 L- c# H) N# L& l+ G5 x' i因为总共是100%，ProcessB的优先级是ProcessA的3倍，ProcessC的优先级是ProcessA的6倍。
+ Y3 ^+ W4 D! r. U
8 V  u; Q7 u3 ~) W$ I
1 c: d2 Q2 s4 \, G  n
Linux上的CFS算法主要有以下步骤：(还是以ProcessA(10%)，ProcessB(30%)，ProcessC(60%)为例)
% l# p4 d' ?  J+ D+ V
7 E' b6 G; Q3 m  k2 G  X  u' ]1)计算每个进程的vruntime(注1)，通过update_curr()函数更新进程的vruntime。

2)选择具有最小vruntime的进程投入运行。（注2）
; f+ V9 J7 T0 P  C" u, q9 F( G
- A- ]9 v0 G+ k% O' g8 d3 N3)进程运行完后，更新进程的vruntime，转入步骤2) （注3）
2 r. z2 x6 E+ h


注1. 这里的vruntime是进程虚拟运行的时间的总和。vruntime定义在：kernel/sched_fair.c 文件的 struct sched_entity 中。
1 @. S, L. T  Z" c, H8 {7 k
# {' ?6 ?; a. o( M4 n0 F
' l* y$ \1 S% q& d0 V; s
注2. 这里有点不好理解，根据vruntime来选择要运行的进程，似乎和每个进程所占的CPU时间百分比没有关系了。
- |5 W5 j0 o- b
4 }* W9 R4 }1 m0 [9 v  {: a* i1）比如先运行ProcessC，(vr是vruntime的缩写)，则10ms后：ProcessA(vr=0)，ProcessB(vr=0)，ProcessC(vr=10)

! q+ l5 c/ s( w* f: T8 F2）那么下次调度只能运行ProcessA或者ProcessB。(因为会选择具有最小vruntime的进程)
7 s# L2 G7 k! ]9 }
! z1 g# A- @" A5 I6 `" h9 q- C3 j长时间来看的话，ProcessA、ProcessB、ProcessC是公平的交替运行的，和优先级没有关系。
& B2 p8 ], o# v1 v4 X
, g5 r# P: Q* ?* e5 |6 v' h" l0 S$ R而实际上vruntime并不是实际的运行时间，它是实际运行时间进行加权运算后的结果。
9 D8 n- q6 G( B% Y
; O1 @7 j. I  Z0 \5 \5 E0 T0 D2 x) }比如上面3个进程中ProcessA(10%)只分配了CPU总的处理时间的10%，那么ProcessA运行10ms的话，它的vruntime会增加100ms。

# B4 |5 f; a  m4 j1 \# e0 r1 T以此类推，ProcessB运行10ms的话，它的vruntime会增加(100/3)ms,ProcessC运行10ms的话，它的vruntime会增加(100/6)ms。

实际的运行时，由于ProcessC的vruntime增加的最慢，所以它会获得最多的CPU处理时间。
- t+ R% }1 L7 t/ ~$ L
$ ^9 k, X+ Z+ |* ?6 h1 }/ P上面的加权算法是我自己为了理解方便简化的，Linux对vruntime的加权方法还得去看源码^-^
6 Q$ d% d6 `6 D


注3.Linux为了能快速的找到具有最小vruntime，将所有的进程的存储在一个红黑树中。这样树的最左边的叶子节点就是具有最小vruntime的进程，新的进程加入或有旧的进程退出时都会更新这棵树。
0 N" F2 V6 Z  f1 \9 _. a* \0 g7 g

& G$ U. K! |- M' h
1 x  A- Z* U" X) ]& l8 d其实Linux上的调度器是以模块方式提供的，每个调度器有不同的优先级，所以可以同时存在多种调度算法。

每个进程可以选择自己的调度器，Linux调度时，首先按调度器的优先级选择一个调度器，再选择这个调度器下的进程。
2 @7 h+ T& ^. e6 n1 y4 u% _
9 C7 N% Q7 f5 [# _& ?0 _; V
: a( O: l) ~  Z; k) E3 a+ M
4. 调度相关的系统调用
调度相关的系统调用主要有2类：

1 z- Q; x5 e) J2 N  Q( ]1) 与调度策略和进程优先级相关 (就是上面的提到的各种参数，优先级，时间片等等) - 下表中的前8个
& c5 ]* f9 [4 g8 ?6 u2 \% N
; w$ x- |: F- Q, \5 e, k8 U2) 与处理器相关 - 下表中的最后3个
8 b/ S* }3 \6 b  ~0 b3 T! w# k6 X  ]

系统调用	描述
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()	暂时让出处理器

$ g: p" C7 w1 ]3 u- W" A4 l  K
9 O* M+ v6 ^2 A

% A0 p2 u6 ~% B% z
& p+ s. y$ Z1 N( @

NingW

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