磁盘调度算法资料

磁盘调度算法先来先服务（ FCFS）最短寻道时间优先 （SSTF）扫描算法（SCAN）或电梯算法循环扫描算法（CSCAN）先来先服务（FCFS）按请求访问的先后次序来访问，而不考虑它们要访问的物理位置。（这种算法平均寻道时间较长，仅适合磁盘请求较少的场合）例：一个有40个磁道的磁盘，现在要求读取第11、1、36、16、34、9、12磁道上的数据，那么读取顺序为：第一步：磁头由第第一步：磁头由第11磁道移到第1磁道NN36 34 16 1211 9 10第一步：磁头由第第一步：磁头由第11磁道移到第1磁道NN36 34 16 1211 9 10N36 34 16 1211 9 10第二步：磁头由第1磁道移到第36磁道N36 34 16 1211 9 10第三步：磁头由第36磁道移到第16磁道第四步：磁头由第第四步：磁头由第16磁道移到第34磁道NN36 34 16 1211 9 10第四步：磁头由第第四步：磁头由第16磁道移到第34磁道NN36 34 16 1211 9 10第五步：磁头由第34磁道移到第9磁道第六步：磁头由第9磁道移到第12磁道最短寻道时间优先（SSTF）先访问离当前磁道最近的那个磁道,（即：让查找时间最短的那个作业先执行，而不考虑请求访问者到达的先后次序，这样就克服了先来先服务算法中的磁头移动过大的问题）例：一个有40个磁道的磁盘，现在要求读取第11、1、36、16、34、9、12磁道上的数据，那么读取顺序为：第一步：磁头开始时位于第11磁道，而离第11磁道最近的是第12磁道,所以把磁头由第11磁道移到第12磁道第二步：磁头此时位于第12磁道，而离第12磁道最近的是第9磁道,所以把磁头由第12磁道移到第9磁道第六步：磁头此时位于第第六步：磁头此时位于第34磁道，而离第34磁道最近的是第36磁道,第六步：磁头此时位于第第六步：磁头此时位于第34磁道，而离第34磁道最近的是第36磁道,第三步：磁头此时位于第第三步：磁头此时位于第9磁道，而离第9磁道最近的是第16磁道，所NN36 34 16 1211 9 10以把磁头由第9磁道移到第16磁道N36 34N36 3416 1211 9第四步：磁头此时位于第16磁道，而离第16磁道最近的是第1磁道,所以把磁头由第16磁道移到第1磁道N36 34N36 3416 1211 9第五步：磁头此时位于第1磁道，而离第1磁道最近的是第34磁道，所以把磁头由第1磁道移到第34磁道

所以把磁头由第34磁道移到第36磁道N36 34N36 3416 1211 9扫描算法（SCAN）又叫“电梯算法”是具有方向性的“最短寻道时间优先”。像电梯一样，沿磁头的移动方向去访问离当前磁头最近的那个磁道，只有当沿磁头方向再无请求访问时，才改变磁头的移动方向。（即：如果离当前磁头最近的磁道在左边，则先把左边的所有磁道都访问完，再改变方向，访问右边的所有磁道；如果离当前磁头最近的磁道在右边，则先把右边的所有磁道都访问完，再改变方向，访问左边的所有磁道。 ）例：一个有40个磁道的磁盘，现在要求读取第11、1、36、16、34、9、12磁道上的数据，那么读取顺序为：第一步：磁头开始时位于第11磁道，而离第11磁道最近的是第12磁道,所以把磁头由第11磁道移到第12磁道N36 34 16 1211 9 10第二步：此时磁头的移动方向是向左，所以要先把左边的所有磁道都访第二步：此时磁头的移动方向是向左，所以要先把左边的所有磁道都访第二步：此时磁头的移动方向是向左，所以要先把左边的所有磁道都访第二步：此时磁头的移动方向是向左，所以要先把左边的所有磁道都访问完，才改变方向，访问右边的所有磁道。在左边方向上，离第 12磁道最近的是第16磁道，所以把磁头由第12磁道移到第16磁道N36 34N36 3416 1211 9第三步：此时在左边方向上，离第16磁道最近的是第34磁道，所以把磁头由第16磁道移到第34磁道N36 34 16 1211 9 10第四步：此时在左边方向上，离第34磁道最近的是第36磁道，所以把磁头由第34磁道移到第36磁道N36 34N36 3416 1211 9第五步：此时在左边方向上，已再无要访问的磁道了，所以改变磁头的移动方向，开始访问右边的所有磁道。此时，在右边方向上，离第36磁道最近的是第9磁道，所以把磁头由第36磁道移到第9磁道N36 3416 1211 9N36 3416 1211 9第六步：此时，在右边方向上，离第9磁道最近的是第1磁道，所以把磁头由第9磁道移到第1磁道36341612113634161211第二步：此时磁头位于第第二步：此时磁头位于第90磁道，在向右方向上，离第90磁道最近的循环扫描算法（CSCAN）相当于：单方向的电梯算法。磁头只向一个方向移动（要么是从左到右，要么是从右到左），例如，磁头只从左到右移动，那么从当前位置出发，向右先访问离当前磁头位置最近的磁道，然后继续向右访问离当前磁头位置最近的磁道，直到把右边所有的磁道都访问完，然后磁头返回到最左边，继续向右访问。题目：一个有200个磁道的磁盘，磁头开始位置位于第100磁道，现在要求读取第50、90、30、120磁道上的数据，移动方向为从左到右，那么读取顺序为：第一步：磁头开始时位于第100磁道，在向右方向上，离第100磁道最近的是第90磁道，所以把磁头由第100磁道移到第90磁道。N120 100 90 50 300是第50磁道，所以把磁头由第90磁道移到第50磁道N120 1009050N120 1009050300第二步：此时磁头位于第50磁道，在向右方向上，离第50磁道最近的是第30磁道，所以把磁头由第50磁道移到第30磁道N120 1009050N120 1009050300第三步：此时磁头位于第30磁道，在向右的方向上，已再无需要访问的磁道了，于是磁头返回到最左边，继续向右访问。此时，离最左端磁道最近的是第120磁道，所以把磁头由最左端磁道移到第 120磁道N120 100 90 50 300.在以下磁盘调度中，算法可能出现饥饿现象。【★★】A.电梯调度 B.最短寻道时间优先C.循环扫描算法 D.先来先服务解：最短寻道时间优先调度算法可能出现饥饿现象，其他算法不会。本题答案为B。.在以下磁盘调度中，算法可能会随时改变磁头的运动方向。A.电梯调度 B.先来先服务C.循环扫描算法 D.都不会解：先来先服务调度算法可能会随时改变磁头的运动方向，因为先来的请求可能在当前磁头位置的左边或右边。本题答案为Bo ---.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个破道访问请求序列为35、45、12、68、100、180、170、195。采用SCAN调度（电梯调度）算法得到的磁道访问序列是。110、170、180、195、68、45>35、12 .4110、68、45、35、12、170、180、195C110、170、180、195、12、35、45、68D.12、35、45、68、110、170、180、195本题为2009年全国考研题・解：采用SCAN调度算法的结果如图18.19所示。本题答案为A。27,设磁盘的I/O请求队列中的柱面号为19、376、205、134、18、56、193、396、29、3、19、40,磁头的起始位置为100,若采用SCAN（电梯调度）算法（磁头的运行方向是向内的），则磁头移动个磁道。【★★】A.2O5 B.480 C.490 D.512解：对SCAN算法,寻道顺序为：100、56、40、29、19、18、3、134、193、205、376、396,移动磁道次数分别为44、16、11、10、1、15、131、59、12、171、20,总数为490.本题答案为Co —28,娴盘的I/O请求队列中的柱面号为55、58、39、18、90、160、150、38、184,磁头艇始位置为100,若采用SSTF（最短寻道时间优先）算法,则磁头移动一个磁道。【★★】A8 B.184 C.200 D.248解：对SSTF算法，寻道顺序为：100、90、58、55、39、38、18、150、160、184,移动磁道次数分别为10、32、3、16、1、20、132、10、24,总数为248。本题答案为D。29.如果当前读写磁头正在53号柱面上执行输入输出操作，依次有4个等待者分别要访问的柱面号为98、37、124、65,当采用调度算法时下一次读写磁头才可能到达37号柱面。【★★】A.先来先服务B,最短寻找时间优先 Sc.电梯调度（初始磁头移动方向向着小磁道方向） JJMD,循环扫描算法（磁头移动方向向着大磁道方向） J解：若采用先来先服务调度算法，卜.•个应为98c若采用最短寻找时间优先调度算法，离53号柱面最近的是65。若采用电梯调度算法（在初始磁头移动方向向着小磁道方同时），卜•一个应为37。若循环扫描算法（磁头移动方向向着大磁道方向），下一个应为65o本题答案为Co38.假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。【★★★★】（1）请说明在上述条件下如何进行磁盘块的空闲状态管理。 ［工，（2）设某单面磁盘的旋转速度为每分钟6000转,每个磁道有100个扇区,相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处,并沿蓑磁道号增大的方向移动（如图18.21所示），磁道号的请求队列为50,90,30,1记一再请求M列中的每个磁道需要读取］个随机分布的扇区，则读完这幅区点病要多少时间?要求给出计算过程。随机分布的某扇区0号磁道磁头运行方向100号磁道图18.21 一个磁盘结构（3）如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，也说明理由。 .一M；本题为2010年全国考研题.- 解：（1）使用位小图法表示磁盘的空闲状态，每一位表示一个磁道块是否为空闲,共需要16384/32=512个字=512x4个字节=2KB,正好可放在系统提供的内存中。（2）采用CSCAN调度算法，访问磁道的顺序为120、30、50、90,则移动磁道长度力20+90+20+40=170,总的移动磁丽间万而而行菽每分钟6000转，则平均旋转