操作系统-调度算法

本文最后更新于：1 年前

[TOC]

进程调度算法

先来先服务

不利于短作业

短作业优先

不利于长作业

高响应比优先

权衡：优先权=（等待时间+要求服务时间）/要求服务时间

时间片轮转

  • 如果时间⽚设得太短会导致过多的进程上下⽂切换，降低了 CPU 效率；

  • 如果设得太⻓⼜可能引起对短作业进程的响应时间变⻓。

  • ⼀般来说，时间⽚设为 20ms~50ms 通常是⼀个⽐较合理的折中值。

最高优先级

  • 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运⾏时间优先级都不会变化；

  • 动态优先级：根据进程的动态变化调整优先级，⽐如如果进程运⾏时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升⾼其优先级，也就是随着时间的推移增加等待进程的优先级。
    该算法也有两种处理优先级⾼的⽅法，⾮抢占式和抢占式：

  • ⾮抢占式：当就绪队列中出现优先级⾼的进程，运⾏完当前进程，再选择优先级⾼的进程。

  • 抢占式：当就绪队列中出现优先级⾼的进程，当前进程挂起，调度优先级⾼的进程运⾏。

  • 但是依然有缺点，可能会导致低优先级的进程永远不会运⾏。

多级反馈队列

是「时间⽚轮转算法」和「最⾼优先级算法」的综合和发展。

image-20210801222105298

  • 设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从⾼到低，同时优先级越⾼时间⽚越短；
  • 新的进程会被放⼊到第⼀级队列的末尾，按先来先服务的原则排队等待被调度，如果在第⼀级队列规定的时间⽚没运⾏完成，则将其转⼊到第⼆级队列的末尾，以此类推，直⾄完成；
  • 当较⾼优先级的队列为空，才调度较低优先级的队列中的进程运⾏。如果进程运⾏时，有新进程进⼊较⾼优先级的队列，则停⽌当前运⾏的进程并将其移⼊到原队列末尾，接着让较⾼优先级的进程运⾏；
  • 可以发现，对于短作业可能可以在第⼀级队列很快被处理完。对于⻓作业，如果在第⼀级队列处理不完，可以移⼊下次队列等待被执⾏，虽然等待的时间变⻓了，但是运⾏时间也变更⻓了，所以该算法很好的兼顾了⻓短作业，同时有较好的响应时间。

页面置换算法

最佳页面（OPT）

淘汰以后最长时间不用的。
无法实现，不能预知未来，可以用来评价其他算法。

先进先出（FIFO）

淘汰最早进入的。

最久未使用（LRU）

时钟页面置换（CLOCK）

  • LRU 开销比较大。难以实现。
  • 该算法的思路是，把所有的⻚⾯都保存在⼀个类似钟⾯的「环形链表」中，⼀个表针指向最⽼的⻚⾯。
  • 当发⽣缺⻚中断时，算法⾸先检查表针指向的⻚⾯：
  • 如果它的访问位位是 0 就淘汰该⻚⾯，并把新的⻚⾯插⼊这个位置，然后把表针前移⼀个位置；
  • 如果访问位是 1 就清除访问位，并把表针前移⼀个位置，重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌。

最不常用

设置访问计数器。

磁盘调度算法

先来先服务

最短寻道时间

找最近的。
会产生饥饿现象。

扫描算法（Scan）

磁头在⼀个⽅向上移动，访问所有未完成的请求，直到磁头到达该⽅向上的最后的磁道，才调换⽅向，这就是扫描（Scan）算法。

问题：中间磁道比较优先级高。

循环扫描（CSCAN）

只有磁头朝某个特定⽅向移动时，才处理磁道访问请求，⽽返回时直接快速移动⾄最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应⼀个⽅向上的请求。

LOOK 与 CLOOK

扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换⽅向。
优化的思路就是磁头在移动到「最远的请求」位置，然后⽴即反向移动。