磁盘调度算法寻道问题

磁盘调度算法

磁盘调度算法比较常见的有以下四种:

  1. 先来先服务算法(FCFS)
  2. 最短寻道时间优先算法(SSTF)
  3. 扫描算法(SCAN)
  4. 循环扫描算法(CSCAN)

先来先服务算法(FCFS,First Come First Served)

  根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单,且每个进程的请求都能依次地得到处理,不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化,致使平均寻道时间可能较长。

初始位置

100

磁道编号

移动距离

55

45

58

3

39

19

18

21

90

72

160

70

150

10

38

112

184

146

平均寻道长度

55.3

  与后面即将讲到的几种调度算法相比,其平均寻道距离较大,故FCFS算法仅适用于请求磁盘I/O的进程数目较少的场合。 


最短寻道时间优先(SSTF,Shortest Seek Time First)

  要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。可以得到比较好的吞吐量,但不能保证平均寻道时间最短。

初始位置

100

磁道编号

移动距离

90

10

58

32

55

3

39

16

38

1

18

20

150

132

160

10

184

24

平均寻道长度

27.5

  对用户的服务请求的响应机会不是均等的,因而导致响应时间的变化幅度很大。在服务请求很多的情况下,对内外边缘磁道的请求将会无限期的被延迟,有些请求的响应时间将不可预期。  SSTF算法虽然能获得较好的寻道性能,但却可能导致某个进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达,且其所要访问的磁道与磁头当前所在磁道的距离较近,这种新进程的I/O请求必然优先满足。


扫描算法(SCAN)

  不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道既在当前磁道之外,又是距离最近的。这样自里向外地访问,直至再无更外的磁道需要访问时,才将磁臂换向为自外向里移动。这时,同样也是每次选择这样的进程来调度,即要访问的磁道在当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现象。

初始位置

100

磁道编号

移动距离

150

50

160

10

184

24

90

94

58

32

55

3

39

16

38

1

18

20

平均寻道长度

27.5

  由于在这种算法中磁头移动的规律颇似电梯的运行,因而又常称之为电梯调度算法。


循环扫描算法(CSCAN)

  SCAN算法既能获得较好的寻道性能,又能防止“饥饿”现象,故被广泛用于大、中、小型机器和网络中的磁盘调度。但SCAN也存在这样的问题:当磁头刚从里向外移动而越过了某一磁道时,恰好又有一进程请求访问此磁道,这时,该进程必须等待,待磁头继续从里向外,然后再从外向里扫描完所有要访问的磁道后,才处理该进程的请求,致使该进程的请求被大大地推迟。

  为了减少这种延迟,CSCAN算法规定磁头单向移动,例如,只是自里向外移动,当磁头移到最外的磁道并访问后,磁头立即返回到最里的欲访问的磁道,亦即将最小磁道号紧接着最大磁道号构成循环,进行循环扫描。   采用循环扫描方式后,上述请求进程的请求延迟将从原来的2T减为T + Smax,其中,T为由里向外或由外向里单向扫描完要访问的磁道所需的寻道时间,而Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道(或相反)的寻道时间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

毫秒级检测!你见过带GPU加速的树莓派吗?

47310
来自专栏IT派

干掉照片中那些讨厌的家伙!Mask R-CNN助你一键“除”人!

【导读】:看过英剧《黑镜》吗?圣诞特别版《白色圣诞节》中有这样一个场景:其中一个未来科技有自由屏蔽人像的功能,可以让你屏蔽任何一个不想看见或不喜欢的人,然后留下...

870
来自专栏逍遥剑客的游戏开发

WoWModelViewer分析

1745
来自专栏小巫技术博客

A008-drawable资源

关于drawable资源笔者之前有写过两篇文章: Android-自定义图像资源的使用(1) Android-自定义图像资源的使用(2) 这里笔者就不做过多的赘...

732
来自专栏用户2442861的专栏

Caffe中LMDB的使用

http://rayz0620.github.io/2015/05/25/lmdb_in_caffe/

951
来自专栏python爬虫日记

python下调用pytesseract识别某网站验证码

pytesseract最新版本0.1.6,网址:https://pypi.python.org/pypi/pytesseract

1473
来自专栏AI科技大本营的专栏

不会用Photoshop抠图?Mask R-CNN助你一键“除”人

翻译 | 林椿眄 编辑 | 费棋 【AI科技大本营导读】:看过英剧《黑镜》吗?圣诞特别版《白色圣诞节》中有这样一个场景:其中一个未来科技有自由屏蔽人像的功能,可...

3937
来自专栏ATYUN订阅号

自定义对象检测问题:使用TensorFlow追踪星球大战中的千年隼号宇宙飞船

大多数的大型科技公司(如IBM,谷歌,微软,亚马逊)都有易于使用的视觉识别API。一些规模较小的公司也提供类似的产品,如Clarifai。但没有公司能够提供对象...

3685
来自专栏ios 技术积累

ios 百度地图标注遮挡问题

在项目中遇到一个问题,百度地图标注很多而且密集的时候,当我们点击其中一个标注的时候如图

881
来自专栏人工智能

Tensorflow on Spark爬坑指南

北京 上海巡回站 | NVIDIA DLI深度学习培训 2018年1月26/1月12日 ? NVIDIA 深度学习学院 带你快速进入火热的DL领域 正文共107...

2956

扫码关注云+社区