计算机磁盘调度算法汇总

磁盘调度在多道程序设计的计算机系统中,各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快,因此我们有必要为每个磁盘设备建立一个等待队列,常用的磁盘调度算法有以下四种:

  • 先来先服务算法(FCFS)
  • 最短寻道时间优先算法(SSTF)
  • 扫描算法(SCAN)
  • 循环扫描算法(CSCAN)

先来先服务算法(FCFS)

系统按照作业到达的先后次序来进行调度,或者说它优先考虑在系统中等待时间最长的作业,而不管该作业所需执行时间的长短,从后备作业队列中选择几个最先进入该队列的作业,将它们调入内存,为它们分配资源和创建进程。然后把它放入就绪队列。当进程调度中才有FCFS算法时,每次调度是从就绪的进程队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后,进程调度程序才将处理机分配给其他进程。

  • 算法思想:按访问请求到达的先后次序服务
  • 优点:简单,公平
  • 缺点:效率不高,相邻两次请求可能会造成最内到最外的柱面寻道,使磁头反复移动,增加了服务时间,对机械也不利

最短寻道时间优先算法(SSTF)

SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。

  • 算法思想:优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先
  • 优点:改善了磁盘平均服务时间
  • 缺点:造成某些访问请求长期等待得不到服务

扫描算法(SCAN)

SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于磁头移动规律与电梯运行相似,故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平,因此,它在访问局部性方面不如FCFS算法和SSTF算法好。

  • 算法思想:当设备无访问请求时,磁头不动;当有访问请求时,磁头按一个方向移动,在移动过程中对遇到的访问请求进行服务,然后判断该方向上是否还有访问请求,如果有则继续扫描;否则改变移动方向,并为经过的访问请求服务,如此反复。
  • 优点:克服了最短寻道优先的缺点,既考虑了距离,同时又考虑了方向

循环扫描算法(CSCAN)

在扫描算法的基础上规定磁头单向移动来提供服务,回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求,所以使用改进型的C-SCAN算法来避免这个问题。CSCAN算法规定磁头单向移动,例如,只是自里向外移动,当磁头移到最外面的磁道并访问后,磁头立即返回到最里面的欲访问磁道,亦即将最小磁道号紧接着最大磁道号构成循环,进行循环扫描。

综合比较

人已赞赏
WordPress主题

Cosy - 多功能资讯自媒体博客主题

2020-8-11 10:46:45

计算机理论

Deepin操作系统的安装部署

2020-7-26 21:44:23

⚠️
恩月阁文章由星九进行编写或整理,部分内容来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
若无意中侵害到您的权益,请发送邮件至 xingjiu@nuue.cn 或点击右侧 私信:星九 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索