公众号「码农小奎」 操作系统—进程调度算法
上一篇谈论了进程是什么，以及多进程系统中CPU需要在进程之间来回切换。
那么CPU到底如何进行上下文切换，假如进程A需要的运算时间长，而进程B虽然运算时间短，但用户急于获得进程B的响应。
这时候，进程切换如何兼顾效率与公平就显得很重要了。
其实如果只考虑最大化一个方面，那算法实现相对比较简单，但想兼顾两个方面难度就瞬间提升了。
在谈论算法之前，先来看看什么是调度吧。
调度
每个进程当然都希望自己能够被CPU快速执行，但是CPU就那一个，现在进程动辄上百。条件不允许进程独享CPU。
只能靠操作系统实现一系列调度策略，CPU要照顾好每一个进程。（CPU：我好难）
之前说过进程有三种基本状态，每一次状态的切换其实也意味着进程发生了切换，也就是操作系统进行了一次进程调度。
调度发生的时机：
进程的基本状态在「运行-阻塞-就绪」之前来回变动，而每一次状态更迭会触发一次进程调度。
- 就绪态->运行态：当进程创建完毕后就会进入就绪队列，等待操作系统选择队列中的进程执行。
- 运行态->阻塞态：当进程发生IO事件时，进程进入阻塞队列，此时操作系统会从就绪队列中选择一个进程执行。
- 运行态->结束态：当进程执行完毕退出后，操作系统会从就绪队列中选择一个进程执行。
当进程发生状态更迭的时候，操作系统会考虑是否把CPU执行权让位给其他进程，而选择什么时机让位，怎么让位，选择哪个进程上位，这就是所谓的进程调度策略。
进程调度策略有很多，根据如何处理时钟的周期性中断把进程调度算法分为两大类：
补充：所谓时钟中断，是指硬件上CPU的每秒数字脉冲的震荡次数，代表CPU的主频，每一次周期的到来，对应着一次CPU运算。也就是说，时钟频率越高，CPU单位时间内的运算量越大。硬件发烧友常说的“超频”来提升CPU性能，就是这个原理。
- 非抢占式调度算法不理会时钟中断，只有在进程被阻塞或退出时，才会调度另一个进程。
- 抢占式调度算法会让每个进程运行一个周期，而在周期结束时，如果该进程仍在运行，则会把它挂起，然后操作系统从就绪队列中选择一个进程执行。每一次周期的末端发生一次中断，CPU给每个进程执行一小会，称为时间片机制。
在谈论具体算法之前，还需要了解进程调度算法的衡量指标，这样才能理解算法为什么这么考虑。
- CPU利用率：如果进程发生了IO请求，那此时CPU是空闲的，进程因等待硬盘返回数据而阻塞。频繁的IO请求势必会降低CPU利用率，所以这时候调度程序会从就绪队列中选择一个进程执行。
- 系统吞吐率：是指CPU单位时间内完成的任务数量。如果一个进程的执行耗费时间很长，一直占用着CPU，那对后续的短作业进程是不公平的，造成进程的就绪队列堆积堵塞，
- 周转时间：是指进程的运行时间加上进程的等待时间，假如进程只需1s执行完，却等待了5s，这种周转时间的过长是我们不希望发生的。
- 等待时间：是指进程在就绪队列中的等待时长，如果一个进程一直等不到CPU的执行权，称为进程“饿死”。
- 响应时间：交互式系统中考虑的权重比非常高的一个指标，是指用户点击鼠标或键盘后，到进程给出响应的时间，当然是越快越好。
明白了这些指标之后，就知道调度算法的具体优化方向了，接下来谈论具体的调度算法。
进程调度算法
进程调度算法有很多，它们不是同一时期出现的，而是根据需要不断发展而来的，下面根据历史发展的顺序讲述进程调度算法。
- 先来先服务调度算法
一种简单存粹的算法，先来先服务(First Come First Served, FCFS)，顾名思义，就是传统的先来后来，调度程序从就绪队列里选择一个进程，直到该进程执行结束或被阻塞，才接着从就绪队列里选择一个进程。
听起来很公平，实际上当一个长作业先运行，那么后面的短作业等待时间就很长。就好像你排队买饭，明明队伍就三个人，结果第一个人帮5个舍友带饭，那对于后面排队的人来说等待时间太长了。
- 最短作业优先调度算法
最短作业优先(Shortest Job First, SJF)，也很好理解，就是选择执行时间短的进程先运行。还是拿上面那个例子来说，相当于让帮忙带饭的那个人排到最后去，谁买的饭越少谁先来。
同样问题又来了，如果短作业很多，就绪队列里送来源源不断的短作业，那长作业按这种策略一直得不到CPU执行权，进程会“饿死”。
2. 高响应比优先算法
前面的先来先服务算法对长作业有利，最短作业优先算法对短作业有利。却都达不到对长作业和短作业调度的平衡。
高响应比主要按照优先权对进程调度，
优先权=(等待时间 + 要求服务时间) / 要求服务时间
由公式可以发现，两个进程如果服务时间一样，那么谁等待时间长谁优先。
而如果等待时间一致，则谁要求服务时间短谁优先。
3. 时间片轮转调度算法
公平且纯粹的时间片轮转调度(Round Robin，RR)，给每个进程分配一个时间片，CPU轮流切换进程执行。
如果一个时间片结束，该进程还没执行完，则挂起，切换另一个进程执行。
或者在一个时间片结束前该进程已经结束或阻塞，则立即切换另一个进程执行。
4. 最高优先级调度算法
前面那个时间片轮转调度过于公平，实际上进程的任务的紧急程度是不一样的，有些进程可以在后台慢慢运算，而有些进程急于给用户响应。
所以在时间片轮转的基础上，加上了优先级，调度程既希望给每个进程轮转调度，又希望每次轮转尽可能选择高优先级的进程
5. 多级反馈队列调度算法
多级反馈队列(Multilevel Feedback Queue)，关键词多级，反馈。
「多级」就是就绪队列不再是一个，而是多个，每个队列优先级不同，时间片也不同。
「反馈」意味着这个算法是动态的，根据当前进程的变化而变化。
看看这个机制是怎么工作的：
- 有多个队列，每个队列优先级不同，队列优先级越高，时间片越短。
- 新来的进程会先进入最高优先级队列，如果在一级队列的时间片内没有执行完，该进程会被向下送入二级队列，以此类推，直至进程执行完成。
- 只有高级队列为空时，才执行低级队列中的进程。假如正在执行低级队列中的进程，此时高级队列中来了新进程，则停止运行当前进程，转而运行高级队列中的进程。
可以发现，这个算法兼顾了公平和效率。首先，短作业进入高级队列可以很快被执行完毕而不会进入低级队列，保证了短作业响应速度。其次，长作业可能在高级队列的时间片内执行不完，会被移入低级队列，虽然低级队列的优先权低，但时间片长，也就是说，低级队列被选中执行的概率相对小，但如果选中则执行的时间长。
END
进程状态的每一次切换都意味着发生了一次进程调度。
而进程调度的策略至关重要，调度算法指标总结来说就是公平与效率的取舍。
各种调度算法各有优势，在不同场景不同系统选择适当的调度策略。
欢迎关注「码农小奎」，更多技术想和你分享。
本文转载自: 掘金