愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

操作系统之磁盘驱动调度

磁盘是典型的共享设备,所以多道程序环境下,会存在同时有多个I/O请求的情况。微观上,磁盘一次只能服务一个I/O请求,因此,决定如何服务这些I/O请求,便产生了磁盘驱动调度算法

一、磁盘I/O操作的时间组成

1、着陆区:磁盘没有I/O操作空闲时,是停放在靠近磁盘最内圈的接触启/停区,也称为着陆区,着陆区不存放任何数据
2、因为磁盘的物理块地址由柱面号、磁头号、扇区号组成。所以在一次磁盘I/O操作中,时间的组成部分如下:

  • 寻道时间Ts: 所谓寻道,就是将磁头移到指定的柱面。而移动前,当前磁头可能是静止的,也有可能是往某一个方向移动,那么就存在一个启动时间s0;此外,磁头移到指定柱面后,不能立即读写,需要一个稳定时间s1;再者,寻道时间也应该和柱面的位置有关系,因此两个柱面间的平均移动时间为m,总共需要移动n个柱面,花费的时间为m×n;因此Ts = s0 + s1 + m×n
  • 旋转延迟时间Tr: 磁头在指定柱面中,对应扇区要旋转到磁头的下方才能开始读写数据,所以存在一个旋转延迟时间Tr。记r为旋转一周的平均时间,那么有平均旋转延迟时间Tr = r/2
  • 传输时间Tt: 因为磁盘都是以物理块为读写单位的,而一次读写的物理块大小相等。所以各I/O请求操作的Tt相等

综上所述,一次磁盘I/O操作的访问时间为Ta = Ts + Tr + Tt

二、磁盘驱动调度算法

通常不考虑Tt,把磁盘驱动调度分为移臂调度旋转调度,但是由于旋转的时间远远小于移臂的时间,所以通常情况下考虑移臂调度
以下例子基于:55、72、100、88、93、66,磁盘位于90柱面,假设共有150个柱面

1、先来先服务算法(FCFS)

先来先服务算法中,对一组I/O操作,按照先来后到的顺序进行服务。该算法具有较好的公平性,但是可能导致频繁地改变磁头的方向。
服务顺序如:90 -> 55 -> 72 -> 100 -> 88 -> 93 -> 66

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

调度时优先选择离当前磁盘最近柱面的一个I/O操作请求。
服务顺序如:90 -> 88 -> 93 -> 100 -> 72 -> 66 -> 55
缺点:可能存在饥饿现象

3、扫描算法(SCAN)

磁头从着陆区启动后,由内向外扫描到最外层,再由外向内到最内层。扫描过程中总是选择离 当前磁头方向 最近的柱面
服务顺序如(往变小的方向):90 -> 88 -> 72 -> 66 -> 55 -> 0 -> 93 -> 100
优点:可以减少磁盘方向的改变;缺点:造成磁头的空移动(如55后已经没有更小的了,但是还是需要到0之后再改变方向返回)

4、电梯算法(Elevator Algorithm)

允许磁头中途改变方向,是对SCAN算法的一种改进;若服务过程中,当前方向上无新的I/O请求,而相反方向上有I/O请求,那么可以立即改变方向。
服务顺序如:90 -> 88 -> 72 -> 66 -> 55 -> 93 -> 100
缺点:如果磁头改变方向后,有新的反方向IO请求加入,会对这些新的IO请求不公平

5、循环扫描算法(C-SCAN)

又称为单向扫描算法,在到达最外层后,迅速改变方向,并从最内层重新开始扫描。
服务顺序如:90 -> 88 -> 72 -> 66 -> 55 -> 100 -> 93

三、磁臂黏着现象

为了减少磁头的移动距离,通常情况下是当柱面上的每个IO请求都处理完毕后,才决定将磁头移到下一个柱面。如果当前柱面上不断地有新的请求加入,磁头就会长时间地停留在该柱面上,导致其他请求得不到及时的服务。这种情况,称为磁臂黏着现象
解决办法:

  • 建立N个磁盘请求队列
  • 算法一次只处理一个队列,只有当这个队列处理完成后,才选择下一个队列
  • 如果有新的IO请求,则只能加入其它的或者新的队列中