操作系统 - 调度算法总结

1. 进程的调度算法

  1. 先到先服务调度算法:对短作业不友好,会加大短作业的等待时间,从而增加短作业的响应时间
  2. 短作业优先:对长作业不友好,造成长作业饥饿
  3. 高响应时间优先:优先级 = (等待时间+处理时间 )/处理时间, 当等待时间相同,短作业优先;当等待时间增大时,会增加长作业的优先级,兼顾了长作业和短作业。
  4. 时间片轮转调度算法:没有设置优先级;时间片的大小的设置,会造成不同的影响(时间片短了,大量的上下文切换;长了,增加短作业的等待时间,增加响应事件)
  5. 高优先级调度算法:会导致低优先级饥饿
  6. 多级队列反馈调度算法:比较均衡,综合了时间片轮转调度算法 + 高优先级调度算法的优点,和相互弥补了缺点。

2. 页置换算法

  1. 最佳置换算法: 置换将来最后被访问的页(理想中的调度,因为未来运行时间很难正确测量)
  2. 先到先出置换算法:将最先进入的页置换出去
  3. LRU置换算法:置换过去最先被访问的页
  4. 时钟置换算法:发生缺页中断,并内存不足时,开始遍历时钟,将其中访问标志位为1的变成0,直到访问到标志位为0的将其置换出去
  5. LFU置换算法:将最少被访问的页置换出去, 由于当其没有考虑时间的影响时,会造成将热数据页置换出内存(比如:当某个页过去一段时间被大量访问,但是在现在不怎么被访问成了冷数据,但是其访问量还是很大,而现在的热数据因为刚起步,访问量低,发生置换时,会造成热数据被置换,冷数据被保留。)

3. 磁盘寻道调度算法

  1. 先到先寻道: 效率差
  2. 短寻道时间优先:容易造成磁头在一个小的区域来回寻道,导致耗时长的寻道被饥饿。
  3. 扫描调度: 磁头从最里面扫描寻道到最外面,再从最外面扫描寻道到最里面,缺点:容易造成中间部分响应的概率更高, 中间部分占便宜。
  4. 循环扫描调度: 要求只从内部到外部的时候扫描数据, 扫描到最外面的时候,快速复位,让所有部分的响应的概率都相同
  5. look与c-look: look与扫描算法类似,只是其扫描的最外面边界,由磁盘的最外面改成了 一系列请求中最外面请求的位置 - c-look对标的是循环扫描,也是相同的改变。
经验分享 程序员 微信小程序 职场和发展