6.1 进程调度/页面置换/磁盘调度算法

进程调度算法

进程调度算法也称 CPU 调度算法。

当 CPU 空闲时，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU。

抢占式调度：进程正在运行的时，可以被打断，使其把 CPU 让给其他进程。有以下两种情况
- 当进程从运行状态转到就绪状态；
- 当进程从等待状态转到就绪状态；（这种是因为进程有优先级，这个时候如果这个进程优先级高，会立刻抢占执行）
非抢占式调度：当进程正在运行时，它就会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把 CPU 让给其他进程。有以下两种情况：
- 当进程从运行状态转到等待状态；
- 当进程从运行状态转到终止状态；

调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），而不能影响进程真在使用 CPU 的时间和 I/O 时间。

接下来，说说常见的调度算法：

先来先服务调度算法
- 进程在就绪队列中排队，每个进程运行退出或者阻塞之后，才会从队列中选第一个接着运行
- 可能出现长作业一直不停止，导致进程饥饿
最短作业优先调度算法
- 优先选择运行时间最短的进程来运行
- 会导致长作业进程饿死
高响应比优先调度算法
- 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，优先级越高
- 如果两个进程「要求的服务时间」相同时，「等待时间」越长，优先级越高
- 避免长时间等待，同时优先处理短作业
时间片轮转调度算法
- 每个进程只运行一个时间片，运行结束释放CPU
- 每个进程在就绪队列中排队
- 时间片长度不好平衡
最高优先级调度算法
- 通过设定进程的优先级，优先处理重要的进程
- 可能会导致低优先级的进程永远不会运行。
多级反馈队列调度算法

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

多级反馈队列

来看看，它是如何工作的：

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

缺页异常（缺页中断）：当 CPU 访问的页面不在物理内存时（虚拟页表的状态为为无效），便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。置换入内存后重新执行导致缺页中断的命令。

如果置换时找不到空闲页的话，就说明此时内存已满了，这时候，就需要「页面置换算法」选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，然后把该被置换出去的页表项的状态改成「无效的」，最后把正在访问的页面装入到这个物理页中。

这里提一下，页表项有

页面置换算法的功能是，当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，目标是尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种：

最佳页面置换算法（OPT）
- 置换在「未来」最长时间不访问的页面
- 是最理想算法，无法实际实现，无法预知每个页面在「下一次」访问前的等待时间。
先进先出置换算法（FIFO）
- 选择在内存驻留时间很长的页面进行中置换
最近最久未使用的置换算法（LRU）
- 选择最长时间（LRU）没有被访问的页面进行置换
- 每次访问更新整个链表，开销大，实际使用少
时钟页面置换算法（Lock）
- 把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。
- 缺页中断，会检查当前指向的页面的访问位
  - 是 1 就清除访问位，并把表针前移一个位置，知道找到一个0
  - 是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置
最不常用置换算法（LFU）
- 当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰
- 需要找到访问次数最小页面，复杂度较高，且不能仅仅依靠次数一个指标作为评判标准

磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。

寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。

常见的磁盘调度算法有：

先来先服务算法
- 先来的地址先定位
- 对于随机访问效率不高
最短寻道时间优先算法
- 根据距离磁头最近的请求先定位
- 可能存在某些请求的饥饿，一些远的请求可能一直不会处理
扫描算法算法
- 磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向。
- 两侧的请求可能比较少，所以中间磁道扫描次数会更多
循环扫描算法
- 只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
- 循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。
LOOK 与 C-LOOK 算法
- LOOK：磁头在移动到「最远的请求」位置，然后立即反向移动，中间处理请求，相较于扫描算法有优化
- C-LOOK：磁头在移动到「最远的请求」位置，立即移到另一端最远的请求出，中间不处理请求，相较于循环扫描算法有优化