磁盘的驱动调度.ppt

72磁盘的驱动调度磁盘的驱动方式不同，从磁盘上获得信息的时间也不同，影响信息获得的时间还有数据在磁盘上的分布。721磁盘的结构“磁头号”。“柱面号”。“扇区号”。,磁盘的结构如下图所示。,执行一次输入输出所花的时间有：寻找时间、延迟时间、传送时间,假定用T表示每个柱面上的磁道数，用S表示每个盘面上的扇区数，则第i柱面，j磁头，k扇区所对应的块号b可有如下公式确定：b=k+S*(j+i*T)在上述的假定下，每个柱面上有S*T个磁盘块，为了计算第P块在磁盘上的位置，可以令D=S*T,设M=PD,N=PmodD。于是，第P块在磁盘上的位置为：柱面号=M磁头号=NS扇区号=NmodS,722磁盘的驱动调度为了使寻找时间和延迟时间尽可能小，系统往往采用一定的调度策略来决定各等待访问者的执行次序，这项工作称磁盘的“驱动调度”，采用的调度算法称“驱动调度算法”。对磁盘来说，驱动调度有“移臂调度”和“旋转调度”两部分组成。一、移臂调度常用的移臂调度算法有：先来先服务算法最短寻找时间优先算法电梯调度算法单向扫描算法。,在例子中假设柱面的编号从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个柱面的距离。,调度算法比较：除了“先来先服务”调度算法外，其余三种调度算法都是根据欲访问的柱面位置来进行调度的。在调度过程中可能有新的请求访问者加入，这些新的请求访问者加入时，如果读写磁头已经超过了它们所要访问的柱面位置，则只能在以后的调度中被选择执行。在多道程序设计系统中，在等待访问磁盘的若干请求访问者中，有些请求访问者可能要求访问的柱面号相同，但各自要求访问同一柱面上的不同磁道，或访问同一柱面同一磁道上不同扇区。所以，在进行移臂调度时，按照某种算法把移动臂定位到某个柱面后，应让等待访问这个柱面的各个访问者的输入输出操作都完成后再改变移动臂的位置。,二、旋转调度根据延迟时间来决定执行次序的调度称为“旋转调度”。应分析下列情况：(1)若干等待访问者请求访问同一磁道上的不同扇区。(2)若干等待访问者请求访问不同磁道上的不同扇区。(3)若干等待访问者请求访问不同磁道上相同扇区。,例如，有4个访问5号柱面的请求访问者，它们的访问要求如下表所示。,对它们进行旋转调度后，它们的执行次序可能是，或，。,三、信息的优化分布例如，某系统对磁盘初始化时把每条盘面分成8个扇区，今有8条逻辑记录被存放在同一条磁道上供处理程序使用，处理程序要求顺序处理这8条记录，每次请求从磁盘上读一条记录，然后对读出的记录要花5毫秒的时间进行处理，以后再读下一条记录进行处理，直至8条记录都处理结束。假定磁盘转速为20毫秒周，现把这8条逻辑记录依次存放在磁道上，如下图(a)所示。显然，读一条记录要花25毫秒的时间。当花了25毫秒的时间读出第1条记录并花5毫秒时间进行处理后，读写磁头已经在第4条记录的位置，为了顺序处理第2条记录，必须等待磁盘把第2条记录旋转到读写磁头位置下面，即要有15毫秒的延迟时间。于是，处理这8条记录所要花费的时间为：8*(25十5)十7*15=165(ms)。,(a)(b),如果我们