EDA365电子论坛网

标题: Linux内核设计与实现之进程的调度 [打印本页]
作者: pulbieup    时间: 2020-10-16 09:51
标题: Linux内核设计与实现之进程的调度
1 w( ^9 G3 A! c4 ~3 i  i1 ?
主要内容：5 C+ M* o6 I4 P# \* L
, s+ n+ E0 {* @- O. z5 X3 {4 i% i
什么是调度5 M( d* ~$ f: }* e, l. d
调度实现原理7 x6 E! \* ?9 l( t: w  h" i6 c
Linux上调度实现的方法
, q: n, }" o$ L& T调度相关的系统调用
& o  }1 s& ~6 i/ c+ F: [1. 什么是调度8 G% c) C0 U. J+ ?8 ~& p
现在的操作系统都是多任务的，为了能让更多的任务能同时在系统上更好的运行，需要一个管理程序来管理计算机上同时运行的各个任务（也就是进程）。
' I% _+ {, z% D9 _* }, Y# o! P* j
+ S' `$ i- [* g6 p( Q这个管理程序就是调度程序，它的功能说起来很简单：
0 O  \. a. Z: i6 i. J
+ n- B3 `! p8 f+ q( |3 v决定哪些进程运行，哪些进程等待5 ]# C3 m6 M* g7 r- z0 ?# g
决定每个进程运行多长时间
, N6 T( C9 k) ~7 Y  |- a此外，为了获得更好的用户体验，运行中的进程还可以立即被其他更紧急的进程打断。- m0 P) k/ g% I4 d/ q# c2 U

4 q: M% E6 f0 L7 P2 d. W$ a9 U- w总之，调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CPU(即尽量少的切换进程，进程切换过多，CPU的时间会浪费在切换上)；另一方面，保证各个进程能公平的使用CPU(即防止一个进程长时间独占CPU的情况)。9 [% Z/ l% k  z  G& o8 D

0 D+ G0 y% Z6 z" z& L  ? " _' J7 Q* t+ W4 Y; N. n  o  l' g9 s

+ o0 `. l) J2 b, a1 U! ^4 ^2. 调度实现原理0 u& Q; Z5 _. V! C1 N8 y
前面说过，调度功能就是决定哪个进程运行以及进程运行多长时间。  u6 q$ ~/ E/ w

' U2 @2 |' \" T& k; u, U1 k决定哪个进程运行以及运行多长时间都和进程的优先级有关。为了确定一个进程到底能持续运行多长时间，调度中还引入了时间片的概念。
: [% r' d! G0 Z2 I6 J, L% M  T+ d, B/ }$ s3 N
2.1 关于进程的优先级
/ V* p/ A5 G6 W: i3 ~* V进程的优先级有2种度量方法，一种是nice值，一种是实时优先级。9 ^0 K' |. l' u# r, ~
& O9 n1 T* e- }8 A! e
nice值的范围是-20～+19，值越大优先级越低，也就是说nice值为-20的进程优先级最大。
' t7 K; B& S+ m$ h1 @6 \- p
5 K5 G6 e$ H! E( C4 o- e实时优先级的范围是0～99，与nice值的定义相反，实时优先级是值越大优先级越高。  T. l+ _& N; l2 x" N9 d
% F# S8 y! K& d6 Z3 B
实时进程都是一些对响应时间要求比较高的进程，因此系统中有实时优先级高的进程处于运行队列的话，它们会抢占一般的进程的运行时间。/ B! c: f& t' `% ^: W0 G

. p% \  {  m. a! W4 _$ x6 n
& r8 p( H9 J  c5 Q; F4 q& l  ]' W& h, Q6 c9 M7 x& X1 n  i
进程的2种优先级会让人不好理解，到底哪个优先级更优先？一个进程同时有2种优先级怎么办？' `4 t+ K0 b1 I3 F5 T5 u
- M" n) _7 }3 G% o- I
其实linux的内核早就有了解决办法。
) r7 S- r" ~, y- {' M# x) _5 \6 A7 y! a5 g. _
对于第一个问题，到底哪个优先级更优先？
  q  T  {; _" s
. I! v. r2 r% D# l0 ^8 e0 `- s4 B答案是实时优先级高于nice值，在内核中，实时优先级的范围是 0～MAX_RT_PRIO-1 MAX_RT_PRIO的定义参见 include/linux/sched.h2 w+ _2 u: ?( Y4 a
' n5 ^7 I+ U: G- d* h
1611 #define MAX_USER_RT_PRIO        100
; I. n. @" @" h( |1612 #define MAX_RT_PRIO             MAX_USER_RT_PRIO
7 V. i! l* x+ D% k* c, J. enice值在内核中的范围是 MAX_RT_PRIO～MAX_RT_PRIO+40 即 MAX_RT_PRIO～MAX_PRIO
6 ]2 m; l  `+ R! n4 o" J9 K( e% x" u) X+ ]
1614 #define MAX_PRIO                (MAX_RT_PRIO + 40)
% H3 |" C: t& O- ?  N7 R; B& ?
# B3 M/ |+ v6 _$ J# l7 }2 F
7 F4 l0 a& o- y6 O6 A) G, D6 K% _第二个问题，一个进程同时有2种优先级怎么办？7 ]2 b0 Y, q1 H3 J5 Q

' w6 e: _- k! w. b& A9 a答案很简单，就是一个进程不可能有2个优先级。一个进程有了实时优先级就没有Nice值，有了Nice值就没有实时优先级。7 q* t3 m, M; S* \0 @$ s: r

, {8 N" u, R1 r) }. f4 M我们可以通过以下命令查看进程的实时优先级和Nice值：(其中RTPRIO是实时优先级，NI是Nice值)
* d3 B* O+ x4 d  F3 `* I2 P5 M, {& u1 N1 }; x) F
复制代码% u2 k) c: g- ~% b# T/ @/ n
$ ps -eo state,uid,pid,ppid,rtprio,ni,time,comm
, [) ]+ H* k# w5 c" T+ r) T: H/ b2 v. N% lS   UID   PID  PPID RTPRIO  NI     TIME COMMAND$ |# {1 K4 H" e- X2 d
S     0     1     0      -   0 00:00:00 systemd* Y/ f! F& D7 v7 d
S     0     2     0      -   0 00:00:00 kthreadd$ V! o- G. q4 m( u# E5 l
S     0     3     2      -   0 00:00:00 ksoftirqd/0" y6 Y3 Q8 g2 S- l& X
S     0     6     2     99   - 00:00:00 migration/0
8 Y& V8 e  W$ F9 iS     0     7     2     99   - 00:00:00 watchdog/0
6 K) t7 m$ L+ {8 q2 K. ~S     0     8     2     99   - 00:00:00 migration/1
1 ^$ `3 j3 ]* C+ ]S     0    10     2      -   0 00:00:00 ksoftirqd/1
9 q. S9 h* f; Q! nS     0    12     2     99   - 00:00:00 watchdog/1
3 _! Q( Y  V! |) |S     0    13     2     99   - 00:00:00 migration/2
: Z' O$ r% l2 _S     0    15     2      -   0 00:00:00 ksoftirqd/2' ~2 B" C) M# C2 B* {  @$ B. t! ]. p
S     0    16     2     99   - 00:00:00 watchdog/2( B  y0 l: |; h. {$ B3 P; v; e& S6 w
S     0    17     2     99   - 00:00:00 migration/3
' B2 w$ Q' t2 G; e. T; Z% ~1 |S     0    19     2      -   0 00:00:00 ksoftirqd/3
  V' q' d/ j9 ZS     0    20     2     99   - 00:00:00 watchdog/3
$ Z2 w6 V) l' |: ~! f, Z/ y  Z. }" J4 ^S     0    21     2      - -20 00:00:00 cpuset
6 Q3 w) t5 K' \  s5 L4 P1 D; RS     0    22     2      - -20 00:00:00 khelper! v- f; o: ~5 K: U; b
复制代码1 d/ ^7 U$ I  R3 ]/ b

9 h7 a* @7 I3 }9 @9 w: H& j4 t* T0 y  j- r  D
2.2 关于时间片, k+ y; V5 A- w9 s+ z
有了优先级，可以决定谁先运行了。但是对于调度程序来说，并不是运行一次就结束了，还必须知道间隔多久进行下次调度。
- O& s# v& U1 d  p, o7 N0 w8 X/ M% G  [5 a
于是就有了时间片的概念。时间片是一个数值，表示一个进程被抢占前能持续运行的时间。
; d; g* L/ q" K$ H; w/ W/ V. D0 s7 `2 Q
7 @: m9 K4 d, I& q: ?也可以认为是进程在下次调度发生前运行的时间(除非进程主动放弃CPU，或者有实时进程来抢占CPU)。' Q; E! x7 f7 E. Q

: O4 j% i; ?$ ?) {6 f) o, a时间片的大小设置并不简单，设大了，系统响应变慢(调度周期长)；设小了，进程频繁切换带来的处理器消耗。默认的时间片一般是10ms/ t+ s3 S5 I5 u% `8 p

. j; [# Q# k. p5 g - |, D, Q) k2 l7 [2 `

6 q, {6 O8 p5 G1 H( U. Q2.3 调度实现原理（基于优先级和时间片）
2 ^0 |  y  a3 x下面举个直观的例子来说明：
2 O5 ~6 Q' z, f# c8 x8 V
# ]1 X0 i/ c( Q. Z2 T* T6 O+ S假设系统中只有3个进程ProcessA(NI=+10)，ProcessB(NI=0)，ProcessC(NI=-10)，NI表示进程的nice值，时间片=10ms
5 c2 N0 H1 u: t9 `2 M% B3 ^2 r% H  S( k: L0 a; _; \
1) 调度前，把进程优先级按一定的权重映射成时间片(这里假设优先级高一级相当于多5msCPU时间)。
/ t" r1 v6 T: }* R9 }' Y! C5 x9 m% I* n1 h
    假设ProcessA分配了一个时间片10ms，那么ProcessB的优先级比ProcessA高10(nice值越小优先级越高)，ProcessB应该分配10*5+10=60ms，以此类推，ProcessC分配20*5+10=110ms5 i# E0 J" h2 R0 r' e& |& d3 ~

( w. \. U& }% B6 p2) 开始调度时，优先调度分配CPU时间多的进程。由于ProcessA(10ms),ProcessB(60ms),ProcessC(110ms)。显然先调度ProcessC
: `8 J$ m6 H0 V) A% i3 P$ K% ~0 m9 \7 c) I  `
3) 10ms(一个时间片)后，再次调度时，ProcessA(10ms),ProcessB(60ms),ProcessC(100ms)。ProcessC刚运行了10ms，所以变成100ms。此时仍然先调度ProcessC4 O6 E0 S$ k; V2 q& n! L4 f4 c

6 _8 r9 C' M5 Y' Z( Y+ }4) 再调度4次后(4个时间片)，ProcessA(10ms),ProcessB(60ms),ProcessC(60ms)。此时ProcessB和ProcessC的CPU时间一样，这时得看ProcessB和ProcessC谁在CPU运行队列的前面，假设ProcessB在前面，则调度ProcessB/ w$ }8 D7 U1 o& x- k1 h
! K, F, o  T- U
5) 10ms(一个时间片)后，ProcessA(10ms),ProcessB(50ms),ProcessC(60ms)。再次调度ProcessC
& p! K. G% A+ F' }# F- V& o$ k/ s# ]: x' Z- p
6) ProcessB和ProcessC交替运行，直至ProcessA(10ms),ProcessB(10ms),ProcessC(10ms)。5 O  }6 P0 V8 {: {9 v- ]5 e/ a

: D! }+ Y/ U2 ^1 O4 {2 b    这时得看ProcessA，ProcessB，ProcessC谁在CPU运行队列的前面就先调度谁。这里假设调度ProcessA
4 o' b) Z) j  Y5 J1 V" b9 }8 g6 y( I/ \4 s" U' D) J* ]; ?
7) 10ms(一个时间片)后，ProcessA(时间片用完后退出),ProcessB(10ms),ProcessC(10ms)。4 {6 j. S% b4 F3 Z: U* @2 Z8 F

( r# I& {$ v, e! l9 T8) 再过2个时间片，ProcessB和ProcessC也运行完退出。
# C5 [) k, Q5 f7 j' m6 R! D/ ^5 L6 O" I0 d$ v
这个例子很简单，主要是为了说明调度的原理，实际的调度算法虽然不会这么简单，但是基本的实现原理也是类似的：3 x, M! q/ A: P' o
9 H& w7 W$ t: V0 N  b
1）确定每个进程能占用多少CPU时间(这里确定CPU时间的算法有很多，根据不同的需求会不一样)
) [! B3 S7 W) y* u  _9 Q/ l: X7 P% S8 D( a& m
2）占用CPU时间多的先运行' w* ]9 q9 \  b+ p2 Y
1 b. r9 Y4 j1 A: F
3）运行完后，扣除运行进程的CPU时间，再回到 1）
$ a5 O! y* Z4 Z' H3 `( X' U6 q" R3 b
: O! o5 ?% F' @, K# c( ?

7 C& T1 x1 b6 ~4 Z0 b9 J3. Linux上调度实现的方法0 R  ^6 R2 H1 c( J* x! R9 T8 u) N
Linux上的调度算法是不断发展的，在2.6.23内核以后，采用了“完全公平调度算法”，简称CFS。
: S. a. e& W; [0 ]' _6 j! d  t$ l& g" j6 K+ E; t' A
CFS算法在分配每个进程的CPU时间时，不是分配给它们一个绝对的CPU时间，而是根据进程的优先级分配给它们一个占用CPU时间的百分比。. r; _, v8 u) o3 e: M4 ^2 P: a
+ H0 I. @: e8 \8 R. m' M
比如ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分别占用CPU的百分比为：ProcessA(10%)，ProcessB(30%)，ProcessC(60%)6 O! N4 x+ N* U' _
, c; V9 _- [6 |  I* \8 c9 _( D8 Y% F
因为总共是100%，ProcessB的优先级是ProcessA的3倍，ProcessC的优先级是ProcessA的6倍。
# m4 R3 ~' V  ]0 X' O- U; y1 ?+ N( Q: [) ^* u5 G' M
$ [3 M5 [$ c  T9 L2 x! M

" C8 Y) w0 w) `' [$ P3 o0 BLinux上的CFS算法主要有以下步骤：(还是以ProcessA(10%)，ProcessB(30%)，ProcessC(60%)为例)
$ B* _( r+ z2 t" N, r( F9 L, U1 E$ o/ }* |' L, R
1)计算每个进程的vruntime(注1)，通过update_curr()函数更新进程的vruntime。
& j4 @* J; G9 y7 m; V5 z# U8 c( T4 R8 q2 f; e
2)选择具有最小vruntime的进程投入运行。（注2）
! I2 J# W4 {0 f% S6 L
+ e; ^! E+ m1 x0 M) C5 B* @; H$ P2 j3)进程运行完后，更新进程的vruntime，转入步骤2) （注3）7 p3 y7 w  c2 y1 K9 N" q( O0 i( a

1 X) F; X* A: K4 i4 C - E) X& @/ F! {  m; _  b

, @. T4 c: M7 E注1. 这里的vruntime是进程虚拟运行的时间的总和。vruntime定义在：kernel/sched_fair.c 文件的 struct sched_entity 中。
+ o- J" `0 F: E  c6 |/ e' ^- L% F7 j  l1 z  O) q! W

+ n/ [+ f  r3 u2 Z- F  W7 t, n5 V% p
注2. 这里有点不好理解，根据vruntime来选择要运行的进程，似乎和每个进程所占的CPU时间百分比没有关系了。, q) K8 ]5 [6 J7 R3 a! r

( Q/ z9 k! V% w, F& N  O: c1）比如先运行ProcessC，(vr是vruntime的缩写)，则10ms后：ProcessA(vr=0)，ProcessB(vr=0)，ProcessC(vr=10)" K2 P9 g) B/ a

5 n! j' y; J$ N* y( Y2）那么下次调度只能运行ProcessA或者ProcessB。(因为会选择具有最小vruntime的进程)
4 M1 r' u2 K* Z/ ~9 x$ R' \/ `; w7 c. Y7 z/ D7 g
长时间来看的话，ProcessA、ProcessB、ProcessC是公平的交替运行的，和优先级没有关系。
9 \' d6 G. _; ]* y* W" V% D, q
- S, q' X* z( [9 y7 Y  E而实际上vruntime并不是实际的运行时间，它是实际运行时间进行加权运算后的结果。, R# p! g/ q5 J% _& e

9 B  Q4 ^: S% T比如上面3个进程中ProcessA(10%)只分配了CPU总的处理时间的10%，那么ProcessA运行10ms的话，它的vruntime会增加100ms。, m. g7 Z) S# Z/ I$ S( o
* i4 q6 k) A+ k7 A- H9 I
以此类推，ProcessB运行10ms的话，它的vruntime会增加(100/3)ms,ProcessC运行10ms的话，它的vruntime会增加(100/6)ms。
# z0 A8 }- X6 `. t% f) H2 ?& \3 s( `$ X7 b6 X/ a
实际的运行时，由于ProcessC的vruntime增加的最慢，所以它会获得最多的CPU处理时间。
8 F$ g9 i4 Q6 A8 H8 L1 r6 K+ Y. W4 ]
上面的加权算法是我自己为了理解方便简化的，Linux对vruntime的加权方法还得去看源码^-^7 Z8 y3 O( E! G' }+ ?1 |
3 ^  c, W( ~; }! c8 E$ z
5 z4 ~3 E  K4 z% P$ H1 Z
) C& m2 p% i6 I7 v' n) L0 u
注3.Linux为了能快速的找到具有最小vruntime，将所有的进程的存储在一个红黑树中。这样树的最左边的叶子节点就是具有最小vruntime的进程，新的进程加入或有旧的进程退出时都会更新这棵树。. O" A7 X/ K2 `1 P2 M+ G# B

" h% A  ~5 g5 k9 C ' n4 X& b1 _. v5 C! Z7 ?
% D2 W) e+ w6 }9 ^4 d$ F
其实Linux上的调度器是以模块方式提供的，每个调度器有不同的优先级，所以可以同时存在多种调度算法。
" X9 {, p4 C  x
' k; a6 b5 G# o5 Y5 ]& L每个进程可以选择自己的调度器，Linux调度时，首先按调度器的优先级选择一个调度器，再选择这个调度器下的进程。
6 ?" P2 j4 V2 j; O, g4 r. B/ O$ B  V  ~
; k2 @: ~" b7 {$ Y- g5 y
; f' j: ]* ?5 s" E# u+ K  c
4. 调度相关的系统调用
" f, V$ N" F1 u0 D( s' y调度相关的系统调用主要有2类：
3 ~. X8 H. a, d
$ v% W8 B" T$ h  ?! T8 f. B" U5 O1) 与调度策略和进程优先级相关 (就是上面的提到的各种参数，优先级，时间片等等) - 下表中的前8个4 L% D* c( E; X1 O
. e8 s4 C  V8 H; z9 B
2) 与处理器相关 - 下表中的最后3个
3 S; l% V7 e% F2 m4 U# }
系统调用
描述
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()
暂时让出处理器
+ M0 a/ U1 |; R% Q" S
  p  G6 T% [2 c$ ^. m- u4 o

; ]) J4 w/ b# _* Z
' Y* o! p! ~) r% z$ ^8 g; [$ X+ M, u, o  ^+ i& l

4 [# @  X- P" U! [5 j
作者: NingW    时间: 2020-10-16 11:00
Linux内核设计与实现之进程的调度



欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/) Powered by Discuz! X3.2