磁盘调度

6.5 磁盘调度

几乎所有计算机都使用磁盘来存储信息。从存储角度看，与内存比较起来，硬盘有三个主要的优点：

⑴可用的存储容量非常大。

⑵每位的价格非常低。

⑶电源关掉后信息不会丢失。

 

6.5.1 磁盘的操作时间

启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：

寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。

延迟时间——指定扇区旋转到磁头下所需的时间。

传送时间——由磁头进程读写完成信息传送的时间。

其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。图6-8是访问磁盘的操作时间示意图。

为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。

6.5.2 磁盘的驱动调度

磁盘是一种高速旋转的存储设备。移动臂上的磁头在沿着知己盘片的直径方向移动，同时对指定的磁道上的扇面中的数据进行读写操作。

磁盘的调度策略称为“驱动调度”。磁盘驱动调度由“移臂调度”和“旋转高度”。两部分组成。

1、  移臂调度

根据访问者指定的柱面位置来决定执行次序的调度，称为“移臂调度”。移臂调度的目的是尽可能地减少操作中的寻找时间。

在磁盘盘面上，0磁道在盘面的外部；号数越大，磁道越靠近盘片的中心。磁盘在关机时，硬盘磁头停放在最内圈柱面。

常用的移臂调度算法有先来先服务算法、最短寻找时间优先算法、电梯调度算法和单向扫描算法。

⑴先来先服务调度算法

最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面，如图6-9所示。

从图6-9中可以看到，采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。

⑵最短寻找时间优先调度算法

最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199，如图6-10所示。

从图6-10中可以看到，采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。

⑶电梯调度算法

“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。

我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨论。

①     移动臂由里向外移动

开始时，，在50号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是32号柱面。所以应先为32号柱面的访问者服务，然后是为15号柱面的访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是61、99、130、148、159、199，如图6-11所示。

②     移动臂由外向里移动

开始时，正在50号柱面执行操作的读写磁头的移动臂是由外向里（即向柱面号增大的内圈方向）趋向61号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是61号柱面。所以，应先为61号柱面服务，然后按移动臂由外向里移动的方向，依次为99、130、148、159、199柱面的访问者服务。当201号柱面的操作结束后，向里移动的方向已经无访问等待者，所以改变移动臂的前进方向，由里向外依次为32、15柱面的访问者服务，如图6-12所示。

“电 梯调度”与“最短寻找时间优先”都是要尽量减少移动臂时所花的时间。所不同的是：“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写磁头最近的 那个柱面，这种选择可能导致移动臂来回改变移动方向；“电梯调度”是沿着臂的移动方向去选择离当前读写词头最近的哪个柱面的访问者，仅当沿移动臂的前进移 动方向无访问等待者时，才改变移动臂的前进方向。由于移动臂改变方向是机械动作，速度相对较慢，所以，电梯调度算法是一种简单、使用且高效的调度算法。

但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。

⑷单向扫描调度算法

单项扫描调度算法的基本思想是，不考虑访问者等待的先后次序，总是从0号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后，立即快速返回到0号柱面，返回时不为任何的访问者等待服务。在返回到0号柱面后，再次进行扫描。

对上述相同的例子采用单向扫描调度算法的执行次序如图6-13所示。

在图6-13中，由于该例中已假定读写的当前位置在50号柱面，所以，指示了从50号柱面继续向里扫描，依次为61、99、130、148、159、199各柱面的访问者服务，此时移动臂已经是最内的柱面，于是立即返回到0号柱面，重新扫描，依次为15、32号柱面的访问者服务。

除了“先来先服务”调度算法外，其余三种调度算法都是根据欲访问的柱面位置来继续调度的。在调度过程中可能有新的请求访问者加入。在这些新的请求访问者加入时，如果读写已经超过了它们所要访问的柱面位置，则只能在以后的调度中被选择执行。

在 多道程序设计系统中，在等待访问磁盘的若干访问者请求中，可能要求访问的柱面号相同，但在同一柱面上的不同磁道，或访问同一柱面中同一磁道上的不同扇区。 所以，在进行移动调度时，在按照某种短法把移动臂定位到某个柱面后，应该在等待访问这个柱面的各个访问者的输入输出操作都完成之后，再改变移动臂的位置。

2、  旋转调度

对在同一个柱面中多个访问者的读写请求，需要有调度算法，用来确定为这些访问等待者服务的次序。

在移动臂定位后有若干个访问者等待访问该柱面的情况下，若从减少输入输出操作总时间为目标出发，显然应该优先选择延迟时间最短的访问者去执行。根据延迟时间来决定执行次序的调度称为“旋转调度”。

进行旋转调度时应分析下列情况：

⑴若干访问等待者请求访问同一磁道上的不同扇区。

⑵若干访问等待者亲切访问不同磁道上的不同编号的扇区。

⑶若干访问等待者亲切访问不同磁道上的、具体相同编号的扇区。

对于前两种情况，旋转调度总是为首先到达读写磁头位置下的扇区进行读写操作。

对于第三种情况，由于这些扇区编号相同，又在同一个柱面上，所以它们同时到达读写磁头的位置下。这时旋转调度可任意选择一个读写磁头进行读写操作。

3、  信息的优化分布

记录在磁道上的排列方式也会影响磁盘的输入输出操作的时间。现在举一个假想的简单例子给予说明。

假设某个系统在磁盘初始化时把磁盘的盘面分呈个扇区，今有8个逻辑记录被存放在同一个磁道上的这8个扇区中，供处理程序使用。处理程序要求顺序处理这8个记录，从1至8。每次处理程序请求从磁盘上读出一个逻辑记录，然后程序对每个读出的记录花费10毫秒的时间进行运算处理，接着再读出下一个记录进行类似的处理，直至这8个记录都处理结束。假定磁盘转速为40毫秒/周，8个逻辑记录依次存放在磁道上，如图6-15（a）所示。