操作系统中涉及的各种调度算法

在每本介绍操作系统的书中，各类调度算法都占据了很大的篇幅，仅从此处我们可以看出
各类调度算法的重要性。而这些调度算法除了在操作系统的各部分使用外，我们也可以将
它们背后蕴含的逻辑用在其他地方，下面是对操作系统中设计的各类调度算法的一个系统
性的总结：

适用于作业与进程的调度算法：

1.先来先服务(FCFS)算法

(1)对于作业，FCFS算法总是从后备作业队列中选择最先进入该队列的一个或多个作业，将
它们调入内存，分配资源，创建进程并放入就绪队列
对于进程，FCFS算法总是选择最先进入就绪队列的进程，将处理器分配给它
(2)FCFS算法属于不可剥夺算法，对所用进程都是公平的
(3)FCFS算法简单，但效率低，有利于CPU忙型作业而不利于I/O忙型作业

2.短作业优先(SJF)调度算法

(1)对于作业，SJF算法选择一个或多个估计运行时间最短的作业调入内存
对于进程，SJF算法从就绪队列中选择一个估计运行时间最短的进程将处理器分配给它
(2)对长作业不利，可能造成 饥饿 现象
(3)SJF调度算法的平均等待时间、平均周转时间最短
(4)SJF调度算法使用的是对未来的估计，难以实现或者不能保证准确

3.优先级调度算法

(1)使用优先级表示作业或进程的紧迫程度，选择优先级最高的作用或进程调入内存或分配
处理器(注意：优先级常用数字表示，但并不一定数字越大优先级越高，需要看具体定义)
(2)根据高优先级进程能否抢占低优先级进程可将该调度算法分为：
非剥夺式优先级调度算法：当一个进程在处理器运行时，即使有一个更高优先级的进程进
入就绪队列，该高优先级的进程也必须等待低优先级进程退出处理器才能获取处理器
剥夺式优先级调度算法：当一个进程在处理器运行时，当有一个更高优先级的进程进入
就绪队列后，暂停正在运行的进程而将处理器分配给高优先级的进程
(3)根据进程优先级能否改变分为：
静态优先级：优先级在进程创建时确定，在进程整个运行期中保持不变
动态优先级：根据进程运行状况动态调整进程优先级
(4)优先级调度算法可能会导致 饥饿
(5)一般系统进程优先级大于用户进程，交互型进程大于非交互型进程，I/O进程大于计算型进程

4.高响应比优先调度算法

(1)主要用于作业调度，是FCFS与SJF的综合平衡，同时考虑了每个进程的等待时间与估计运行
时间，在每次作业调度时，先计算各作业响应比，选择响应比最高的作业调入内存
(2)响应比 = (等待时间 + 要求服务时间) / 要求服务时间
(3)高响应比优先算法克服了饥饿状态，兼顾了长作业

5.时间片轮转调度算法

(1)时间片轮转调度算法主要适用于分时系统
(2)类似于FCFS算法，但每个进程仅能运行一个时间片，当进程时间片用完后，无论该进程是否
完成，必须释放处理器给就绪队列中的下一个进程，而自身进入就绪队列末尾排队，属于剥
夺式调度算法
(3)时间片的大小对算法性能影响很大，过大的时间片使得每个进程在一个时间片中运行完成，
也就使该算法退化为FCFS，过小的时间片，会使得花费在调度上的时间过多
(4)时间片的选择通常由系统响应时间、就绪队列中进程数目、系统的处理能力共同决定

6.多级反馈队列调度算法

(1)多级反馈队列调度算法是时间片轮转调度算法与优先级调度算法的综合，通过动态调整优先
级与时间片的大小，该算法可兼顾多个方面，且不必估计进程运行时间
(2)多级反馈队列调度算法的实现通过设置多个就绪队列，每个队列的优先级不同，高优先级队
列中每个进程分配的时间片越小，每个进程最先进入优先级最高的就绪队列末尾，当该就绪
队列中进程在属于该就绪队列的时间片中未运行完后，进入下一个优先级低一级的就绪队列
中等待执行。系统总是爱高优先级队列为空时才执行下一优先级就绪队列中的进程
(3)多级反馈队列调度算法对于终端型作业用户，短作业优先；对于短批处理作业用户，周转时
间较短；对于长批处理作业用户，不会产生饥饿现象

页面置换算法

1.最佳(OPT)置换算法

(1)选择以后不会被使用或最长时间内不再被访问的页面换出，以保证最低的缺页率
(2)由于是对未来的预测，该算法无法实现，但OPT常被用于评价其他算法

2.先进先出(FIFO)页面置换算法

(1)选择最先进入内存的页面(在内存中滞留时间最长度的页面)换出
(2)FIFO实现简单，但该算法可能出现当所分配的物理块越多页面故障数不增反减的现象，称为
Belady异常

3.最近最久未使用(LRU)置换算法

(1)选择最近最长时间未被访问的页面换出，该算法认为过去一段时间未被访问的页面在将来也
不会被访问，采用过去预测将来
(2)LRU算法性能较好，但需要寄存器和栈的硬件支持，属于堆栈类算法，不会出现 Belady异常
(3)LRU性能接近OPT，但实现困难，且开销大

4.时钟(CLOCK)置换算法

(1)简单的CLOCk算法为每帧关联一个附加位，称为使用位。当页面首次装入内存时，该位为 1，
当该页面随后又被访问时，也将使用位置为 1，将被换出的帧根据进入内存时间先后形成一
个循环缓冲区，有一个指针与该缓冲区相关联，最初该指针指向第一个进入内存的帧，当要
选择某一帧换出时，该指针循环扫描该缓冲区，将其遇到的第一个使用位为0的帧换出，该指
针指向被换出帧的下一个帧，被该指针扫过的帧，使用位从1变为0
(2)CLOCK算法性能比较接近LRU算法
(3)为每个帧继续添加附加位，用于标识各个状态，形成各个改进的CLOCK算法

磁盘调度算法：

1.先来先服务(FCFS)

(1)最简单的磁盘调度算法，根据进程访问磁盘的先后顺序进行调度
(2)FCFS具有公平性，在少量进程访问簇聚的文件扇区时有较好性能，但若大量进程竞争使用磁盘
则性能接近随机调度

2.最短寻找时间优先(SSTF)

(1)SSTF选择与当前磁头距离最近的磁道，以便每次寻找时间最短
(2)SSTF可能产生饥饿现象

3.扫描算法(SCAN)

(1)SCAN算法在当前磁头移动方向上选择与当前磁头距离最近的请求作为下一次服务对象
(2)SCAN算法对最近扫描过的区域不公平，在访问的局部性方面不如FCFS、SSTF

4.循环扫描算法(C-SCAN)

(1)C-SCAN在SCAN算法的基础上规定磁头单向移动提供服务，回返时直接快速移动到起始端
(2)SCAN与C-SCAN的改进：磁头移动只需要达到最远端的一个请求即可返回，不需要达到磁盘端点，称
为LOOK调度和C-LOOK调度
(3)SCAN与C-SCAN在磁盘负载较大时比较占优势