在讲解具体的磁盘调度算法之前,我们先看看磁盘的结构,如下图所示:
磁盘调度算法的目的很简单,就是为了提高磁盘的访问性能,一般是通过优化磁盘的访问请求顺序来做到的。寻道的时间是磁盘访问最耗时的部分,如果请求顺序优化的得当,必然可以节省一些不必要的寻道时间,从而提高磁盘的访问性能。
为了下面的讲解,我们先假设有下面一个请求序列,每个数字代表磁道的位置:
98,183,37,122,14,124,65,67
初始磁头当前的位置是在第 53
磁道。
接下来,分别对以上的序列,作为每个调度算法的例子,那常见的磁盘调度算法有:
- 先来先服务算法
- 最短寻道时间优先算法
- 扫描算法
- 循环扫描算法
- LOOK 与 C-LOOK 算法
先来先服务算法
先来先服务(First-Come,First-Served,FCFS),顾名思义,先到来的请求,先被服务。
那按照这个序列的话:
98,183,37,122,14,124,65,67
那么,磁盘的写入顺序是从左到右,如下图:
先来先服务算法总共移动了 640
个磁道的距离,这么一看这种算法,比较简单粗暴,但是如果大量进程竞争使用磁盘,请求访问的磁道可能会很分散,那先来先服务算法在性能上就会显得很差,因为寻道时间过长。
最短寻道时间优先
最短寻道时间优先(Shortest Seek First,SSF)算法的工作方式是,优先选择从当前磁头位置所需寻道时间最短的请求,还是以这个序列为例子:
98,183,37,122,14,124,65,67
那么,那么根据距离磁头( 53 位置)最近的请求的算法,具体的请求则会是下列从左到右的顺序:
65,67,37,14,98,122,124,183
磁头移动的总距离是 236
磁道,相比先来先服务性能提高了不少。但这个算法可能存在某些请求的饥饿,因为本次例子我们是静态的序列,看不出问题,假设是一个动态的请求,如果后续来的请求都是小于 183 磁道的,那么 183 磁道可能永远不会被响应,于是就产生了饥饿现象,这里产生饥饿的原因是磁头在一小块区域来回移动。
扫描算法
最短寻道时间优先算法会产生饥饿的原因在于:磁头有可能再一个小区域内来回得移动。
为了防止这个问题,可以规定:磁头在一个方向上移动,访问所有未完成的请求,直到磁头到达该方向上的最后的磁道,才调换方向,这就是扫描(Scan)算法。
这种算法也叫做电梯算法,比如电梯保持按一个方向移动,直到在那个方向上没有请求为止,然后改变方向。
还是以这个序列为例子,磁头的初始位置是 53:
98,183,37,122,14,124,65,67
那么,假设扫描调度算先朝磁道号减少的方向移动,具体请求则会是下列从左到右的顺序:
37,14,0
,65,67,98,122,124,183
磁头先响应左边的请求,直到到达最左端( 0 磁道)后,才开始反向移动,响应右边的请求。
扫描调度算法性能较好,不会产生饥饿现象,但是存在这样的问题,中间部分的磁道会比较占便宜,中间部分相比其他部分响应的频率会比较多,也就是说每个磁道的响应频率存在差异。
循环扫描算法
扫描算法使得每个磁道响应的频率存在差异,那么要优化这个问题的话,可以总是按相同的方向进行扫描,使得每个磁道的响应频率基本一致。
循环扫描(Circular Scan, CSCAN )规定:只有磁头朝某个特定方向移动时,才处理磁道访问请求,而返回时直接快速移动至最靠边缘的磁道,也就是复位磁头,这个过程是很快的,并且返回中途不处理任何请求,该算法的特点,就是磁道只响应一个方向上的请求。
还是以这个序列为例子,磁头的初始位置是 53:
98,183,37,122,14,124,65,67
那么,假设循环扫描调度算先朝磁道增加的方向移动,具体请求会是下列从左到右的顺序:
65,67,98,122,124,183,199
,0
,14,37
磁头先响应了右边的请求,直到碰到了最右端的磁道 199,就立即回到磁盘的开始处(磁道 0),但这个返回的途中是不响应任何请求的,直到到达最开始的磁道后,才继续顺序响应右边的请求。
循环扫描算法相比于扫描算法,对于各个位置磁道响应频率相对比较平均。
LOOK 与 C-LOOK算法
我们前面说到的扫描算法和循环扫描算法,都是磁头移动到磁盘「最始端或最末端」才开始调换方向。
那这其实是可以优化的,优化的思路就是磁头在移动到「最远的请求」位置,然后立即反向移动。
那针对 SCAN 算法的优化则叫 LOOK 算法,它的工作方式,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中会响应请求。
而针 C-SCAN 算法的优化则叫 C-LOOK,它的工作方式,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中不会响应请求。
而针 C-SCAN 算法的优化则叫 C-LOOK,它的工作方式,磁头在每个方向上仅仅移动到最远的请求位置,然后立即反向移动,而不需要移动到磁盘的最始端或最末端,反向移动的途中不会响应请求。
好啦,我们的磁盘调度算法就讲解完了,记得多多掌握喔。
引用: