调度算法

进程调度

先来先服务

先来先服务(FCFS)算法每次运行就绪队列中最先进入的进程，直到进程退出或被阻塞，之后继续从队列中选择第一个进程接着运行

问题：
当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业

适用场景：
FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统

最短作业优先

最短作业优先(SJF)调度算法优先选择运行时间最短的进程来运行，有助于提高系统的吞吐量

问题：
对长作业不利，当就绪队列有非常多的短作业时会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行

高响应比优先

高响应比优先 (HRRN)调度算法权衡了短作业和长作业，每次进行进程调度时，先计算响应比优先级，然后把响应比优先级最高的进程投入运行

• 两个进程的等待时间相同时，要求的服务时间越短，优先级越高，这样短作业的进程容易被选中运行
• 两个进程要求的服务时间相同时，等待时间越长，优先级就越高，兼顾到了长作业进程，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会

问题：
实际情况下进程的要求服务时间无法确定，因此高响应比优先调度算法属于理想型算法

时间片轮转

时间片轮转(RR)调度算法是最古老、最简单、最公平且使用最广的算法
每个进程被分配一个时间段，称为时间片，允许该进程在该时间段中运行

• 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换

问题：
时间片的长度难以确定：

• 太短会导致过多的进程上下文切换，降低 CPU 效率
• 太长可能引起对短作业进程的响应时间变长

通常时间片设为 20ms~50ms

最高优先级

最高优先级(\HPF)调度算法从就绪队列中选择最高优先级的进程进行运行

进程的优先级可以分为：

• 静态优先级：创建进程时候优先级已确定，然后整个运行时间优先级都不会变化
• 动态优先级：根据进程运行情况动态调整优先级，比如进程运行时间增加，则降低其优先级，进程等待时间(就绪队列的等待时间)增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级

该算法也有两种处理优先级高的方法：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行

问题：
HPF 算法可能会导致低优先级的进程永远不会运行

多级反馈队列

多级反馈队列(Multilevel Feedback Queue)调度算法是「时间片轮转算法」和「最高优先级算法」的结合

多级 - 有多个优先级从高到低的队列，优先级越高时间片越短
反馈 - 如果有新的进程加入比当前进程优先级更高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列

1. 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度
2. 如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成
3. 如果进程在其时间片内主动释放 CPU，则优先级不变

问题

• 饥饿：如果系统有过多交互型工作，就会不断加入优先级高队列占用 CPU，导致位于优先级低队列的长工作永远无法得到 CPU
• 愚弄调度程序：用户控制进程在时间片用完之前，调用一个 I/O 操作(比如访问一个无关的文件)，从而主动释放 CPU，如此便可以始终保持在高优先级，占用更多的 CPU 时间，极端情况下(比如每运行 99%的时间片时间就主动放弃一次 CPU)可以几乎独占 CPU

解决方法：

• priority boost 机制，一段时间后将所有任务都提升到最高优先级队列，防止一直来新的任务让低优先级的长任务饿死
• 一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次 CPU)，就降低其优先级，移入低一级队列

内存页面置换

最佳页面置换算法

最佳页面置换算法(OPT)选择在「未来」最长时间不访问的页面进行置换

该算法计算内存中每个逻辑页面的下一次访问时间，然后比较，选择未来最长时间不访问的页面进行置换

属于理想算法，现实无法实现

先进先出置换算法

先进先出置换算法(FIFO)选择在内存驻留时间最长的页面进行置换

问题：

• 经常访问或者需要长期存在的页面会被频繁调入调出 - 较早调入的页往往是经常被访问或者需要长期存在的页，这些页会被反复调入和调出
• 存在 Belady 现象 - 被置换的页面并不是进程不会访问的，有时就会出现分配的页面数增多但缺页率反而提高的异常现象，出现该异常的原因是因为 FIFO 算法只考虑了页面进入内存的顺序，而没有考虑页面访问的频率和紧迫性

最近最久未使用置换算法

最近最久未使用置换算法(LRU)选择最长时间没有被访问的页面进行置换

问题：
开销大，需要在内存中维护一个所有页面的链表，且每次访问内存时必须更新整个链表

时钟页面置换算法

时钟页面置换算法(Lock)把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面

当发生缺页中断时检查表针指向的页面：

• 如果访问位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置
• 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止

最不常用置换算法

最不常用置换算法(LFU)选择访问次数最少的页面进行置换

实现方式：
对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器累加 1，发生缺页中断时淘汰计数器值最小的那个页面

问题：

• 计数器硬件成本较高
• 对计数器进行查找耗时
• LFU 算法只考虑频率问题而忽略时间问题，过去时间里高访问频率的停用页面置换优先可能低于当前频繁访问的页面
  • 可以定期减少访问的次数，加大旧页面被置换的概率

磁盘调度

磁盘调度算法通过优化磁盘的访问请求顺序提高磁盘的访问性能

寻道的时间是磁盘访问最耗时的部分

先来先服务算法

先来先服务算法按请求顺序访问磁道

最短寻道时间优先算法

最短寻道时间优先(SSF)算法优先选择从当前磁头位置所需寻道时间最短的请求

问题：
可能出现饥饿问题，对于动态请求磁头始终在一小块区域来回移动，远处请求始终未响应

扫描算法

扫描算法(Scan)下磁头在一个方向上移动并访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，调换方向访问之前的请求

问题：
中间部分的磁道相比其他部分响应频率更高

循环扫描算法

循环扫描算法(CSCAN)在扫描算法基础上规定磁道只响应一个方向上的请求
只有磁头朝特定方向移动时才处理磁道访问请求，返回时直接快速移动至最靠边缘的磁道(复位磁头)，该过程速度快

LOOK 与 C-LOOK 算法

扫描算法需要移动到磁盘的最始端或最末端
LOOK 算法下磁头在移动到「最远的请求」位置，然后立即反向移动
C-LOOK 算法下磁头在反向移动的情况下不响应请求