操作系统磁盘的驱动调度ppt课件

1、62 磁盘的驱动调度磁盘的驱动调度 磁盘的驱动方式不同，从磁盘上获得信磁盘的驱动方式不同，从磁盘上获得信息的时间也不同，影响信息获得的时间还有息的时间也不同，影响信息获得的时间还有数据在磁盘上的分布。数据在磁盘上的分布。621 磁盘的结构磁盘的结构 “磁头号磁头号”。 “柱面号柱面号” 。 “扇区号扇区号”。磁盘的结构如下图所示。执行一次输入输出所花的时间有：寻找时间、延迟时间、传送时间 假定用T表示每个柱面上的磁道数，用S表示每个盘面上的扇区数，则第i柱面，j磁头，k扇区所对应的块号b可有如下公式确定： b=k+S*(j+i*T) 在上述的假定下，每个柱面上有S*T个磁盘块，为了计算第P块在

2、磁盘上的位置，可以令D=S*T,设M=PD,N=P mod D。于是，第P块在磁盘上的位置为：柱面号=M磁头号=NS扇区号=N mod S622 磁盘的驱动调度磁盘的驱动调度 为了使寻找时间和延迟时间尽可能小，系统往往采用为了使寻找时间和延迟时间尽可能小，系统往往采用一定的调度策略来决定各等待访问者的执行次序，这项工一定的调度策略来决定各等待访问者的执行次序，这项工作称磁盘的作称磁盘的“驱动调度驱动调度”，采用的调度算法称，采用的调度算法称“驱动调度驱动调度算法算法”。对磁盘来说，驱动调度有。对磁盘来说，驱动调度有“移臂调度和移臂调度和“旋转旋转调度两部分组成。调度两部分组成。一、移臂调度一、

3、移臂调度 常用的移臂调度算法有：常用的移臂调度算法有： 先来先服务算法先来先服务算法 最短寻找时间优先算法最短寻找时间优先算法 电梯调度算法电梯调度算法 单向扫描算法。单向扫描算法。 在例子中假设柱面的编号从0到199。例如，如果现在读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98，183，37，122，14，124，65，67。 1先来先服务调度算法 当53号柱面上的操作结束后，访问柱面的次序为98，183，37，122，14，124，65，67。 读写磁头总共移动了640个柱面的距离。2最短寻找时间优先调度算法最短寻找时间优先调度算法 现在当现在当53号柱面的操

4、作结束后，访问次序为号柱面的操作结束后，访问次序为65、67、37、14，98，122，124，183。 读写磁头总共移动了读写磁头总共移动了236个柱面的距离。个柱面的距离。3. 电梯调度算法电梯调度算法 由于该算法是与移动臂的方向有关，所以，应分两种由于该算法是与移动臂的方向有关，所以，应分两种情况来讨论。情况来讨论。(1)移动臂是向外移的。当前正在移动臂是向外移的。当前正在53号柱面执行操作的读写号柱面执行操作的读写磁头是移动臂由里向外磁头是移动臂由里向外(向向0号柱面方向号柱面方向)带到带到53号柱面的位号柱面的位置，因此，当访问置，因此，当访问53号柱面的操作结束后，依次访问的次号柱

5、面的操作结束后，依次访问的次序为序为37、14，65，67，98，122，124，183。读写磁头共移。读写磁头共移动了动了208个柱面的距离。个柱面的距离。(2)移动臂是向里移的。当前正在移动臂是向里移的。当前正在53号柱面执行操作的读写号柱面执行操作的读写磁头是移动臂由外向里磁头是移动臂由外向里(向柱面号增大方向向柱面号增大方向)带到带到53号柱面号柱面的位置，因此，当访问的位置，因此，当访问53号柱面的操作结束后，依次访问号柱面的操作结束后，依次访问的次序为的次序为65、67，98，122，124，183、37，14柱面的访问柱面的访问者服务。读写磁头共移动了者服务。读写磁头共移动了29

6、9个柱面的距离。个柱面的距离。 “电梯调度与“最短寻找时间优先的比较： 一样：都是尽量减少移动臂移动时所化的时间； 不同：“最短寻找时间优先不考虑臂的移动方向； “电梯调度考虑臂的移动方向。 优点：电梯调度算法是一种简单、实用且高效的调度算法。 缺陷：由于移动臂改变方向是机械动作，速度相对较慢。 在实现时除了要记住读写磁头的当前位置外，还必须记住移动臂的移动方向。4单向扫描调度算法单向扫描调度算法 执行次序为执行次序为65，67，98，122，124，183、14，37。除了。除了移动臂由里向外返回从移动臂由里向外返回从199返回到返回到0所用的时间外，读写所用的时间外，读写磁头还需移动磁头还

7、需移动183个柱面的距离。个柱面的距离。调度算法比较：除了调度算法比较：除了“先来先服务调度算法外，其余先来先服务调度算法外，其余三种调度算法都是根据欲访问的柱面位置来进行调度的。三种调度算法都是根据欲访问的柱面位置来进行调度的。在调度过程中可能有新的请求访问者加入，这些新的请在调度过程中可能有新的请求访问者加入，这些新的请求访问者加入时，如果读写磁头已经超过了它们所要访求访问者加入时，如果读写磁头已经超过了它们所要访问的柱面位置，则只能在以后的调度中被选择执行。问的柱面位置，则只能在以后的调度中被选择执行。 在多道程序设计系统中，在等待访问磁盘的若干请在多道程序设计系统中，在等待访问磁盘的若

8、干请求访问者中，有些请求访问者可能要求访问的柱面号相求访问者中，有些请求访问者可能要求访问的柱面号相同，但各自要求访问同一柱面上的不同磁道，或访问同同，但各自要求访问同一柱面上的不同磁道，或访问同一柱面同一磁道上不同扇区。所以，在进行移臂调度时，一柱面同一磁道上不同扇区。所以，在进行移臂调度时，按照某种算法把移动臂定位到某个柱面后，应让等待访按照某种算法把移动臂定位到某个柱面后，应让等待访问这个柱面的各个访问者的输入输出操作都完成后再改问这个柱面的各个访问者的输入输出操作都完成后再改变移动臂的位置。变移动臂的位置。二、旋转调度二、旋转调度 根据延迟时间来决定执行次序的调度称为根据延迟时间来决定

9、执行次序的调度称为“旋转调度旋转调度”。应分析下列情况：应分析下列情况：(1)若干等待访问者请求访问同一磁道上的不同扇区。若干等待访问者请求访问同一磁道上的不同扇区。(2)若干等待访问者请求访问不同磁道上的不同扇区。若干等待访问者请求访问不同磁道上的不同扇区。(3)若干等待访问者请求访问不同磁道上相同扇区。若干等待访问者请求访问不同磁道上相同扇区。例如，有4个访问5号柱面的请求访问者，它们的访问要求如下表所示。对它们进行旋转调度后，它们的执行次序可能是，或，。请求次序柱面号磁头号扇区号541515545528三、信息的优化分布三、信息的优化分布例如，某系统对磁盘初始化时把每条盘面分成例如，某系

10、统对磁盘初始化时把每条盘面分成8个扇区，今有个扇区，今有8条逻辑记录被存放在同一条磁道上供处理程序使用，处理程条逻辑记录被存放在同一条磁道上供处理程序使用，处理程序要求顺序处理这序要求顺序处理这8条记录，每次请求从磁盘上读一条记录，条记录，每次请求从磁盘上读一条记录，然后对读出的记录要花然后对读出的记录要花5毫秒的时间进行处理，以后再读下一毫秒的时间进行处理，以后再读下一条记录进行处理，直至条记录进行处理，直至8条记录都处理结束。假定磁盘转速为条记录都处理结束。假定磁盘转速为20毫秒周，现把这毫秒周，现把这8条逻辑记录依次存放在磁道上，如下图条逻辑记录依次存放在磁道上，如下图 (a)所示。所示。 显然，读一条记录要花显然，读一条记录要花25毫秒的时间。当花了毫秒的时间。当花了25毫毫秒的时间读出第秒的时间读出第1条记录并花条记录并花5毫秒时间进行处理后，读写磁毫秒时间进行处理后，读写磁头已经在第头已经在第4条记录的位置，为了顺序处理第条记录的位置，为了顺序处理第2条记录，必须条记录，必须等待磁盘把第等待磁盘把第2条记录旋转到读写磁头位置下面，即要有条记录旋转到读写磁头位置下面，即要有15毫毫秒的延迟时间。于是，处理这秒的延迟时间。于是，处理这8条