操作系统：驱动调度算法

驱动调度

磁盘属于共享型设备

• 系统在任一时刻只允许一个访问者启动磁盘执行操作，其余的访问者必须等待
• 一次输入/输出操作结束后，再释放一个等待访问者

提高系统效率

• 系统根据移动臂的当前位置选择寻找时间和延迟时间尽可能小的那个访问者优先得到服务
• 降低若干个访问者执行输入/输出操作的总时间（平均服务时间），增加单位时间内输入/输出操作的次数

“寻找时间”是机械运动时间，通常在几十毫秒时间量级
设法减小寻找时间是提高磁盘传输效率的关键

驱动调度：系统采用一定的调度策略来决定各个请求访问磁盘者的执行次序

驱动调度先进行“移臂调度”，减少寻找时间，再进行“旋转调度”，减少延迟时间 。

移臂调度：

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

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

先来先服务调度算法FCFS

• 算法简单且公平
• 只是根据访问者提出访问请求的先后次序进行调度，并不考虑访问者所要求访问的物理位置

缺点：

• 未对寻道进行优化，磁臂来回地移动，使寻道时间比较长。

先来先服务算法仅适合于磁盘I/O请求数目较少的场合

例如，现在读写磁头正在53号柱面上执行输入/输出操作，而访问者请求访问的柱面顺序为：98，183，37，122，14，124，65，67。

读写磁头总共移动了640个柱面的距离。

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

• 总是从若干请求访问者中挑选与当前磁头所在的磁道距离最近，使每次寻道时间最短的那个请求进行调度，而不管访问者到达的先后次序
• 与先来先服务算法相比，大幅度地减少了寻找时间，缩短了为各请求访问者服务的平均时间，提高了系统效率

缺点：

• 并未考虑访问者到来的先后次序
• 可能存在某进程的请求距离当前磁头较远，致使被大大的推迟，发生“饥饿”现象

例如，现在读写磁头正在53号柱面上执行输入/输出操作，而访问者请求访问的柱面顺序为：98，183，37，122，14，124，65，67。

读写磁头总共的移动距离为236个柱面

单向扫描调度算法

• 不论访问者的先后次序，总是从0号柱面开始向里扫描，依次选择所遇到的请求访问者；
• 移动臂到达盘面的最后一个柱面时，立即带动读/写磁头快速返回到0号柱面，返回时不为任何请求访问者服务，返回0号柱面后再次进行扫描

缺点：

• 算法虽然考虑了移动臂的移动距离问题，由于存在一趟空扫描，系统的效率并未得到大的提高

读写磁头总共的移动距离为382个柱面

双向扫描算法

• 从0号柱面开始向里扫描，依次选择所遇到的请求访问者；移动臂到达最后一个柱面时，调转方向从最后一个柱面向外扫描，依次选择所遇到的请求访问者
• 解决了单向扫描算法中的一趟空扫描问题，减少了寻找时间，提高了系统的访问效率

缺点：

• 在每次扫描过程中必须从最外磁道扫描到最内磁道，有可能存在部分空扫描

读写磁头总共的移动距离为382个柱面

电梯调度算法

• “电梯调度”算法不仅考虑到请求访问者的磁头与当前磁头之间的距离，更优先考虑的是磁头当前的移动方向。
• 总是从移动臂当前位置开始，沿着移动臂的移动方向选择距离当前移动臂最近的那个访问者进行调度，若沿移动臂的移动方向再无访问请求时，则改变移动臂的方向再选择

目的

• 尽量减少移动臂移动时所花的时间

• 若当前移动臂由里向外移动时，读写磁头共移动了208个柱面的距离，
• 若当前移动臂由外向里移动时，则读写磁头共移动了299个柱面的距离

电梯调度算法和最短寻找时间优先算法对比

“电梯调度”与“最短寻找时间优先”，都是以尽量减少移动臂移动时所花的时间为目标。

• 最短寻找时间优先不考虑移动臂的当前移动方向，总是选择距离当前读/写磁头最近的那个柱面的访问者，可能会导致某个进程发生“饥饿”现象，移动臂来回改变移动方向频率高。
• 电梯调度算法沿着移动臂的移动方向选择距离当前读/写磁头最近的那个柱面的访问者，仅当沿着移动臂的移动方向无等待访问者时，才改变移动臂的方向，改变频率相对较慢。是一种简单、实用且高效的调度算法，能获得较好的寻道性能，又能防止“饥饿”现象，实现时需要增加开销，除了要记住读写磁头的当前位置外，还必须记住移动臂的移动方向被广泛应用于大、中、小型计算机和网络的磁盘调度

旋转调度

旋转调度分析：

• 在一次移臂调度将移动臂定位到某一柱面后，允许进行多次旋转调度
• 旋转调度是指选择延迟时间最短的请求访问者执行的调度策略
  （1）若干等待访问者请求访问同一磁道上的不同扇区
  （2）若干等待访问者请求访问不同磁道上的不同编号的扇区
  （3）若干等待访问者请求访问不同磁道上具有相同编号的扇区

影响I/O操作时间的因素
记录在磁道上的排列方式会影响I/O操作的时间

例如，某系统，在对磁盘初始化时，把每个盘面分成8个扇区，有8个逻辑记录被存放在同一个磁道上供处理程序使用。

处理程序要求顺序处理这8个记录，每次请求从磁盘上读一个记录，然后对读出的记录要花5ms的时间进行处理，以后再读下一个记录进行处理，直至8个记录全部处理结束。假定磁盘的转速为20ms/周，现把这8个逻辑记录依次存放在磁道上

在不知道当前磁头位置的情况下，处理这8个记录所要花费的时间为：
8×(2.5+5)+10+7×15=175(ms)
如果把这8个逻辑记录在磁道上的位置重新安排一下，当读出一个记录并处理后，读/写磁头正好位于顺序处理的下一个记录位置，可立即读出该记录，不必花费等待延迟时间。于是，处理这8个记录所要花费的时间为：
10+8×(2.5+5)=70(ms)

• 记录的优化分布有利于减少延迟时间，从而缩短了输入/输出操作的时间
• 对于一些能预知处理要求的信息采用优化分布可以提高系统的效率
• 扇区的编号方式也会影响I/O操作的时间
• 一般常将盘面扇区交替编号，磁盘组中不同盘面错开命名(原因：磁头都固定值一个磁臂上)