操作系统 磁盘的驱动调度&考试重点.doc

卷面共70分， 选择10道，每个1分；判断10道，每个1分；大题6道，50分
大题重点
第三章
PV操作
银行家算法判断是否安全，能否分配
第四章
进程调度算法（先来先服务，短作业优先， 优先级算法，最高响应比优先）
第五章
页面置换算法(FIFO，LRU, OPT)
逻辑地址与物理地址转换
第八章
磁盘调度算法（先来先服务，短距离优先， 电梯调度， 单向扫描调度）
优化分布
6．2 磁盘的驱动调度
磁盘的驱动方式不同，从磁盘上获得信息的时间也不同，影响信息获得的时间还有数据在磁盘上的分布。
6．2．1 磁盘的结构
“磁头号”。
“柱面号” 。
“扇区号”。

执行一次输入输出所花的时间有：
寻找时间、延迟时间、传送时间

假定用T表示每个柱面上的磁道数，用S表示每个盘面上的扇区数，则第i柱面，j磁头，k扇区所对应的块号b可有如下公式确定：
b=k+S*(j+i*T)
在上述的假定下，每个柱面上有S*T个磁盘块，为了计算第P块在磁盘上的位置，可以令D=S*T,设M=[P／D],N=P mod D。于是，第P块在磁盘上的位置为：
柱面号=M
磁头号=[N／S]
扇区号=N mod S
6．2．2 磁盘的驱动调度
为了使寻找时间和延迟时间尽可能小，系统往往采用一定的调度策略来决定各等待访问者的执行次序，这项工作称磁盘的“驱动调度”，采用的调度算法称“驱动调度算法”。对磁盘来说，驱动调度有“移臂调度”和“旋转调度”两部分组成。
一、移臂调度
常用的移臂调度算法有：
先来先服务算法
最短寻找时间优先算法
电梯调度算法
单向扫描算法。
在例子中假设柱面的编号从0到199。例如，如果现在读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98，183，37，122，14，124，65，67。 1．先来先服务调度算法
当53号柱面上的操作结束后，访问柱面的次序为98，183，37，122，14，124，65，67。
读写磁头总共移动了640个柱面的距离。
2．最短寻找时间优先调度算法
现在当53号柱面的操作结束后，访问次序为65、67、37、14，98，122，124，183。
读写磁头总共移动了236个柱面的距离。
3. 电梯调度算法
由于该算法是与移动臂的方向有关，所以，应分两种情况来讨论。
(1)移动臂是向外移的。当前正在53号柱面执行操作的读写磁头是移动臂由里向外(向0号柱面方向)带到53号柱面的位置，因此，当访问53号柱面的操作结束后，依次访问的次序为37、14，65，67，98，122，124，183。读写磁头共移动了208个柱面的距离。
(2)移动臂是向里移的。当前正在53号柱面执行操作的读写磁头是移动臂由外向里(向柱面号增大方向)带到53号柱面的位置，因此，当访问53号柱面的操作结束后，依次访问的次序为65、67，98，122，124，183、37，14柱面的访问者服务。读写磁头共移动了299个柱面的距离。
“电梯调度”与“最短寻找时间优先”的比较：
相同：都是尽量减少移动臂移动时所化的时间；
不同：“最短寻找时间优先”不考虑臂的移动方向；
“电梯调度”考虑臂的移动方向。
优点：电梯调度算法是一种简单、实用且高效的调度算法。
缺点：由于移动臂改变方向是机械动作，速度相对较慢。
在实现时除了要记住读写磁头的当前位置外，还必须记住移动臂的移动方向。
4．单向扫描调度算法
执行次序为65，67，98，122，124，183、14，37。除了移动臂由里向外返回（从199返回到0）所用的时间外，读写磁头还需移动183个柱面的距离。
更正为从183直接返回到14，移动总距离为(183-53)+(183-14)+(37-14)=130+169+23=322个柱面
调度算法比较：除了“先来先服务”调度算法外，其余三种调度算法都是根据欲访问的柱面位置来进行调度的。在调度过程中可能有新的请求访问者加入，这些新的请求访问者加入时，如果读写磁头已经超过了它们所要访问的柱面位置，则只能在以后的调度中被选择执行。
在多道程序设计系统中，在等待访问磁盘的若干请求访问者中，有些请求访问者可能要求访问的柱面号相同，但各自要求访问同一柱面上的不同磁道，或访问同一柱面同一磁道上不同扇区。所以，在进行移臂调度时，按照某种算法把移动臂定位到某个柱面后，应让等待访问这个柱面的各个访问者的输入输出操作都完成后再改变移动臂的位置。
二、旋转调度
根据延迟时间来决定执行次序的调度称为“旋转调度”。
应分析下列情况：
(1)若干等待访问者请求访问同一磁道上的不同扇区。
(2)若干等待访问者请求访问不同磁道上的不同扇区。
(3)若干等待访问者请求访问不同磁道上相同扇区。
例如，有4个访问5号柱面的请求访问者，它们的访问要求如下表所示。

对它们进行旋转调度后，它们的执行次序可能是①，②，④，③，或①，③，④，②。
三、信息的优化分布
例如，某系统对磁盘初始化时把每条盘面分成8个扇区，今有8条逻辑记录被存放在同一条磁道上供处理程序使用，处理程序要求顺序处理这8条记录，每次请求从磁盘上读一条记录，然后对读出的记录要花5毫秒的时间进行处理，以后再读下一条记录进行处理，直至8条记录都处理结束。假定磁盘转速为20毫秒／周，现把这8条逻辑记录依次存放在磁道上，如下图 (a)所示。
显然，读一条记录要花2．5毫秒的时间。当花了2．5毫秒的时间读出第1条记录并花5毫秒时间进行处理后，读写磁头已经在第4条记录的位置，为了顺序处理第2条记录，必须等待磁盘把第2条记录旋转到读写磁头位置下面，即要有15毫秒的延迟时间。于是，处理这8条记录所要花费的时间为 ： 8*(2．5十5)十7*15=165(ms)。

如果我们把这8条逻辑记录在磁道上的位置重新安排一下， (b)是这8条逻辑记录的最优分布。处理这8个记录所要花费的时间为： 8*(2.5+5)=60(ms)。 可见记录的优化分布有利于减少延迟时间，从而缩短了输入输出操作的时间。