linux进程调度机制
前置
- 进程分类
- 实时进程(runtime)
- 跟用户交互需要及时相应
- 普通进行
- 不需要那么及时，如编码解码等
- 对于不同类型的进程应该采用不同的调度方法，实时进程序需要及时响应
- 实时进程(runtime)
- 上下文切换
- 发生进程调度时，保存当前进程的信息后(如程序计数器，变量，寄存器等context)才能加载另一个进程。这个过程就是上下文切换
调度算法
- FIFO
- 实现简单，但需要等待前面进程执行完才能执行后面的。what if前面是一个要执行很长时间的进程
- STF(Shortest Time First)
- 整体等待时间下降，但如果是长时间进程先到达时短时间进程还是需要等待
上面的调度算法都是非抢占的，一个执行完成才会执行下一个进程，都会导致个别进程需要长时间等待
- STCF(Shortest Time-to-Completion First)，短快优先
- 会抢占 。如p1需要100ms，当p1执行了10ms，p2到来只需要10ms，所有会先执行p2，再调度回p1
- 抢占：一个进程未必执行完才会执行另一个
- 但这样会执行时间长的进程可能会由于抢占而饥饿
- 会抢占 。如p1需要100ms，当p1执行了10ms，p2到来只需要10ms，所有会先执行p2，再调度回p1
- RR(Round robin)，轮循
- 每个进程执行一小段时间片然后切换
进程队列
- 全局队列
- 早期多核cpu下使用全局队列保存进程，因此调度时需要加锁，加锁机制导致这种方式性能很低。
- 局部队列
- 每个cpu有自己的队列，进程在多个队列中负载均衡
进程优先级
- 优先级越小优先级越高
- 用位图表示有优先级时从低到高找(find first)更快
- nice值
- linux中用户可以设置nice值来 影响优先级 (priority)，范围到
[-20, 19]ps -l，PRI字段可看到优先级，NI字段可看到nice值
- nice值越高优先级越低
- 简记：一个nice的人往往是谦虚礼貌的，吃饭都是说”你先吃你先吃”，结果最后这个nice的人饿着了
- 一个进程对别的进程越nice就越不会抢占cpu，得到的时间越少，优先级越低
- 可以通过
nice命令设置进程优先级，renice命令来修改nice值
- linux中用户可以设置nice值来 影响优先级 (priority)，范围到
- 静态优先级
- 选择权在用户，用户可以设置nice值来影响优先级
- 动态优先级
- 选择权在内核，内核根据一些机制调整优先级，如超时的进程会受到降低优先级的惩罚
linux调度器
O(n)调度器- 起初采用线性表遍历寻找最高优先级进程O(n)，效率很低
- O(1)调度器
- 时间片分配，优先级被映射成一定bitmap，在一个优先级上有进程则对应的bitmap会置1，cpu可以通过位运算快速取出优先级最高的进程
- CFS完全公平调度器
- 分时间片，每个进程相对公平
- vruntime，优先级高的进程虚拟时间增长慢，优先级低的进程虚拟时间增长快
- 如高优先级进程分到时间片10ms，而虚拟时间1ms
- 取红黑树中虚拟时间最短(优先级最高)的进程进行调度
O1调度
TODO https://zorro.gitbooks.io/poor-zorro-s-linux-book/content/linuxde-jin-cheng-you-xian-ji.html
O1调度的Linux2.6开始引入的，到Linux 2.6.23之后替换成了CFS。
使用两个队列，活动队列和过期(expire)队列
CFS
完全公平则每个进程占用cpu的时间应该是尽量相等的，linux中使用vruntime记录这个时间。因此CFS每次调度”vruntime最小”(为防止溢出带来的影响可能使用delta选取)的进程运行。一下是几种情况的总结：
- 创建进程
- 每个进程都是父进程fork产生的，fork让子进程继承父进程的vruntime
- 而父进程在执行执行fork时vruntime持续增加，从而子进程vruntime总是小于父进程，总是先于父进程调度
- 等待IO
- 部分进程等待IO/sleep，那当他们唤醒时vruntime将远远低于其他进程，所以保守的做法是进行进程唤醒时其vruntime等于最小vruntime
- CFS中的优先级
- nice值越低，vruntime增长越慢，调度几率越高
- vruntime溢出
- 如果64bit的无符号数(vruntime)溢出。则选择最小vruntime的规则将这个进程将一直运行很长时间
- 因此真正实现的选取”最小vruntime”应该是通过delta判断的
delta = (uint)(int t - int mt)
要做到完全公平，调度器要在一个较小的时间内把这n个进程调度执行一遍。这个较小的时间就是任意一个进程被调度的最大延迟时间，也叫做调度周期sched_latency_ns
CPU只要对所有进程维护一个累积占用CPU时间数，就可以衡量出每个进程目前占用的CPU时间总量是多还是少，这个数字记录在 vruntime 中。进程以vruntime为key放到一个红黑数组成的队列中，每次调度都选择最左子树上的那个进程，即vruntime最少的进程，这样就能保证所有进程相对公平。
CFS的优先级
虽说完全公平，但CFS还是需要支持优先级的。优先级是通过时间消耗(vruntime增长)的快慢来决定的。高优先级进程时间增长慢，低优先级进程时间增长快。如低优先级的进程实际运行了1s，vruntime是1s，而高优先级的进程实际已经运行了10s，而vruntime才是1s，这样高优先级的进程就更大概率在最左子树，得到调度。
调度并不在一个进程的vruntime大于最小vruntime的进程时发生，为了减少切换频率，CFS设计了sched_min_granularity_ns参数来设定进程执行之后的最小cpu占用时间。
新进程的vruntime值
当已经有多个进程执行的很长时间时，新起一个进程，并让它vruntime为0，这显然是不公平的。因为需要分配给它很多时间来追赶其他进程的vruntime。所有CFS对每个CPU的执行队列都维护了一个min_vruntime值，用于记录这个CPU执行队列的最小vruntime值。因此新进程vruntime不是直接设为0，而是以min_vruntime为基础进行调整。
需要考虑的因素很多，如子进程是否要先于父进程执行、还要防止进程不停的fork来获得很多的执行时间
TODO: https://zorro.gitbooks.io/poor-zorro-s-linux-book/content/linuxde-jin-cheng-you-xian-ji.html