下面我们来讨论磁盘调度
前面我们说了I/O的特点
I/O的结构和I/O的数据传输
下面我们举一类
具体的设备的优化问题
这就是我们这里的磁盘调度
在具体讨论磁盘调度之前
我们有必要讨论一下
磁盘的工作机理和它的性能参数
这是一个磁盘的基本结构
它由若干个盘片和一个磁头组组成
磁头组上呢
每一个磁头上有一个读写头
分别对应着盘片的正反面
我们可以在这里读写相应的数据
中间这些盘片
是围绕着磁盘轴进行旋转的
在这个旋转的过程当中
我们要读写的数据
是分布在各个盘片上的
这里磁道 柱面和扇区
这是我们要找的
每一块数据所在的位置
你在这里要读写磁盘上的数据
首先必须移动磁头
到达指定的位置然后读写
那我们看到在这里花时间最长的
是这个磁头的移动
这就是我们这里的寻道时间
定位到指定的磁道所需要花的时间
然后再有一个是旋转延时
也就是说中间这个盘片
它是一直在匀速旋转的
这个旋转不会因为
我想读的位置不同而有所改变
所以我们在这里要想找到指定的扇区
必须是等待它旋转
那这样一来我们基本上是说
在这里从当前位置
旋转到你想要的那个位置
这中间时间是我们这里的旋转延时
有了这个之后
那我们基本可以说
这个旋转延时基本上是转半圈的情况
也就是说我在任何一个位置开始
读到我想要的那个位置
那通常情况下中间平均的延时
是要转半圈的时间
这是磁盘的结构
和它相应的几个影响参数
下面我们来具体分析一下
磁盘I/O它的时间都花在什么地方
首先第一个是我要读写某个设备
我要等的这个设备是可以访问的
等待设备可用这是一段时间
然后第二个是等待
我这个设备要想跟它进行交流的话
DMA通道或者是I/O通道它必须可用
这是一个时间
这两个时间基本上
跟你实际的设备操作关系不大
然后是寻道时间
这相当于磁头移到指定的磁道
然后是旋转延时
最后我到了指定地方之后
我还有一个数据读出的时间
后面这三个时间
都会有机械动作
所以我们在这里
计算这个传输时间的时候
基本上是把这三个时间加在一起
这三个时间
加上前面这个通道的等待时间
这是我设备忙的状态
这是我们给出来的传输时间的公式
这是我最后算出来的访问时间
它由三个部分组成
实际上这是我们已经简化过的
一个是寻道时间就是中间这一段
然后是旋转延时
第一个寻道时间
跟你磁头移动的距离是相关的
那它花的时间是最大的
第二个旋转延时
基本上是说我们转的速度它的倒数
就是你转一圈的时间
那我们在这儿
基本上是平均时间是转一圈的一半
就是2r分之一
然后再有一个数据读取的时间
这是传输时间 这里头这个时间
它这几个参数是什么意思呢
就是要读多少个字节
你这一圈磁道上有多少个比特
然后你的转速是啥样的
这三个数rN分之B
就是你这里头传输的延时
从这个分析我们可以知道
我们主要需要优化的是TS
这个寻道时间
为了寻道时间的优化
这就是我们这里磁盘调度所要干的事
那它通过优化磁盘访问的顺序
来达到提高磁盘访问性能的目标
访问顺序如何来影响这个寻道时间呢
实际上我们有这样几条依据
第一个寻道是磁盘上最耗费的时间
所以我们有必要对它进行优化
如果这时间很短 那优化的空间不大
那我们就没有必要在这里
来做这个优化
然后再有一个我必须在同一个磁盘上
同时会有多个I/O请求
如果一个磁盘上只有一个
那你不管怎么优化
你都要到指定位置的
同时有多个我可以调整这个顺序
就好比说图书馆的管理员要去书库取书
它同时有多本书要取的时候
它可以看看这几本分布的位置
我优化出一条线路来
如果说你只有一本的话
那相当于我就直接去 直接回
没有什么好优化的
再有一个是随机进行磁盘的I/O请求
那这时候它的性能是很差的
基于这样几条
我们可以通过优化这个顺序
来优化磁盘的访问性能
具体说起来呢
我们在这里给出这样几种优化算法
第一种是FIFO先进先出
它就是按照请求的顺序
来顺序的进行处理
这个算法它是公平的
但是它在很多情况下
它的性能是不好的
接近于你的随机访问
那我们用一个例子来说
它是在怎么访问
在这个例子给了一个访问的序列
并且约定了我磁头当前的位置
来按照FIFO的做法
看看它总共磁头移动的距离是多少
我们要优化的目标
就是这个移动的距离
当前位置是53
我第一个是98
第一个要移动53到98
这时候移动了45个单位的距离
这样的话一个一个移动下去
到最后
到这个地方我到67
我总共加在一起
它总和是640个单位
那我们看到这来回左移右移
实际上走了很多的冤枉路
这种做法呢它的性能是很差的
我们首先想到的第一个优化是什么
我就近
离的这后面这一段里
哪一个最近我按哪一个
这就是我们下一种做法
最短服务时间优先
在这里头呢
它依据磁头当前的位置
来找移动最少的那个I/O请求
所在的位置
这时候总是找最短寻道时间的
当前寻道最短的那个
那我们还是以刚才这个例子来说
在这个序列里头
我们仍然是这个序列
仍然是这个当前位置
我们看按最短寻道时间优先
它的结果是啥样的
我们在这儿53
离它最近的是哪个 是65
然后67 最后两个
然后67之后再往哪
37是离它最近的
然后这样一直走下去到最后
最后到哪 到这个地方 183
是它最后一个
这时候236和我们刚才的640
差不多差了接近3倍
那这时候我们看到这种做法
比刚才那个又有了很大的优化
原因在于刚才那个根本就没有考虑到
它的位置分布情况
这个做法是不是还可以优化呢
那我们再有第三种做法 扫描算法
它的做法是在一个方向上进行移动
一直到所有的访问全部完成
然后直到到达磁头的最后一个磁道
这种做法呢
它主要是因为我们在磁盘上
磁头是两个方向来回移动
哪些地方会是优待呢
中间那一部分会是优待
所以我沿一个方向走到头
然后再到另一个方向
这样一来的话
我换方向之后 再从那头扫回来
这种做法有点类似于
我们电梯里的控制算法
电梯的话
它是从最顶上到最底下
然后再从最底下到最顶上
这是我们这里的扫描算法
我们用扫描算法再来试一下
刚才那个序列
同样的序列 同样的起点
但这时候起头有一个方向的假定
我们在这儿
假定是往编号低的方向走
这时候我沿路扫到头
一直有多少个我就扫到那儿
这样一来的话基本上我转一圈
是从第一个到最后一个
200个单位这样的距离
也就是说极端的情况
如果说你是从最头上开始
不管你中间有多少个请求
它移动的距离就应该是不超过200
从这个角度来说这个算法呢
它的性能也是不错的
在我们这儿看到
它算出来和我们刚才那个
最短寻道时间优先的算法
的结果是一样的
这种做法它的特点是
我沿着一个方向走 顺序扫过去
这个地方我的判断会比较简单
不像刚才那个
我需要去找到底哪一个是最近的
每一次找的时候呢
都要来挨个去算一遍
我在这儿沿着一个方向就可以了
与此同时这种做法有一个问题
就是在于中间这些磁道
我会有更好的访问性能
而两头我到的时间会比较少
所以在这儿又有一种变化
叫做循环扫描
它仅在一个方向进行扫描
另一个方向呢是直接走到头
这种做法呢
它主要的目的是为了提高它的公平性
那我们看
刚才说你把从一个方向走到头
最外头那个地方
即使没有你要访问的I/O请求
你也要走到头
这个实际上是不合算的
所以在这儿就有一个C-Look
它和我们刚才说的扫描算法
唯一的区别就在于
它只是走到最后一个请求的位置
它不走到头 然后就折返了
其它的跟循环扫描算法是一样的
这样的话它就可以提高它的公平性
然后在这基础上我们还会再有两种优化
这就是N步扫描和双队列扫描算法
N步扫描算法实际上
想对付的问题是什么呢
是说由于我在扫描算法里头
我是考虑后面这些请求
哪个离我最近
如果说你总是在当前磁头
所在位置的边上有请求
在这个位置的请求就会优先响应
但这种优先响应
就会使另外一些请求
得不到访问的机会
这就是我们这里的磁头粘着现象
这时候呢
我们怎么来解决这个问题呢
你比如说在这里刚才我们说的
进程反复请求某一磁道的I/O操作
它就会长时间的停到这儿
对其它的后续的请求
等待延时就会非常长
为了减少这种某些情况速度很快
在另外一些情况下性能很差这种情况
有了N步扫描
它的做法是什么呢
它的做法是把磁盘请求
分成N个子队列
每次按照先进先出的顺序
来处理所有的子队列
也就说子队列我是按照先来后到的顺序
但是在每一个队列内部我用扫描算法
这就是我们这里的N步扫描算法
那这种算法呢又有一个小变种
就叫双队列扫描算法
它和前面的做法的区别是在于
我只分两个队列
某种角度上讲
你认为是N步扫描算法的一个简化
这种简化完了之后呢
我分成两个队列
交替使用扫描算法处理每一个队列
在处理一个队列的时候呢
当前新到达的请求就放在另外一个
没有进行处理那个队列里头
用这种办法呢
我就让这些请求有一个最长的等待时间
也就是说当前处理的这些
处理完了之后我再会去处理新的请求
从这个角度来讲呢
我的平均等待时间就会减少
这是我们对磁盘调度的一个简要介绍