磁盘调度算法寻道问题

磁盘调度算法

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

  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 条评论
登录 后参与评论

相关文章

来自专栏java初学

磁盘调度算法寻道问题

2826
来自专栏calmound

KMP专题

POJ 2406 Power Strings http://poj.org/problem?id=2406 题意:找出s字符窜由多少个重复子窜循环构成 分析:K...

2958
来自专栏章鱼的慢慢技术路

2013年第四届蓝桥杯C/C++B组省赛题目解析

1433
来自专栏人工智能头条

TensorFlow架构与设计:图模块

1824
来自专栏测试开发架构之路

C语言程序设计50例(二)(经典收藏)

【程序11】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月    后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总...

35010
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

2186
来自专栏前端布道

JavaScript 浮点数陷阱及解法

众所周知,JavaScript 浮点数运算时经常遇到会 0.000000001 和 0.999999999 这样奇怪的结果,如 0.1+0.2=0.300000...

923
来自专栏数据结构与算法

P1774 最接近神的人_NOI导刊2010提高(02)

题目描述 破解了符文之语,小FF开启了通往地下的道路。当他走到最底层时,发现正前方有一扇巨石门,门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“...

2576
来自专栏木子昭的博客

机器学习三剑客之PandasPandas的两大核心数据结构Panda数据读取(以csv为例)数据处理Pandas的分组和聚合(重要)

Pandas是基于Numpy开发出的,专门用于数据分析的开源Python库 Pandas的两大核心数据结构 Series(一维数据) 允许索引重复...

2756
来自专栏机器学习从入门到成神

计算机系统的层次存储结构详解

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

811

扫码关注云+社区