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

进程调度算法

也称 CPU 调度算法，当 CPU 空闲时，操作系统选择内存中某个就绪态进程，分配给其 CPU。调度算法影响的是等待时间，实际的 CPU 使用时间和 I/O 时间不会影响（和程序有关）

调度算法分类：

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

先来先服务调度算法：非抢占，按照队列中的顺序调度，可能导致饥饿
最短作业优先调度算法：非抢占，按照运行时间长度排序调度，会导致长作业进程饿死
高响应比优先调度算法：按照等待时间->服务时间-> 1
- 如果两个进程的「等待时间」相同时，「要求的服务时间」越短，优先级越高
- 如果两个进程「要求的服务时间」相同时，「等待时间」越长，优先级越高
- 避免长时间等待，同时优先处理短作业
时间片轮转调度算法：每个进程只运行一个时间片，改由下一个进程运行，当前进程进入队尾
最高优先级调度算法：按照设定进程的优先级（nice 值）排序，先处理重要的进程，低优先级可能被饿死
多级反馈队列调度算法

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

多级反馈队列

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

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

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

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

目的是为了提高磁盘的访问性能，优化磁盘访问顺序，常见的磁盘调度算法有：

先来先服务算法：随机访问效率不高，空转多
最短寻道时间优先算法：某个远的请求容易被饿死
扫描算法：每次单向移动完成所有未完成的请求，到达末尾换方向，两段扫描扫，中间扫描多
循环扫描算法：每次只单向扫描，到达末尾直接回到开始位置，回去途中不扫描，相对于扫描算法，更加平均
LOOK 与 C-LOOK 算法
- LOOK：磁头在移动到「最远的请求」位置，然后立即反向移动，中间处理请求，相较于扫描算法有优化
- C-LOOK：磁头在移动到「最远的请求」位置，立即移到另一端最远的请求出，中间不处理请求，相较于循环扫描算法有优化