什么是电梯调度算法?假设原来磁盘请求队列已经有请求磁道号为 99, 87,134,66,磁头正从外向里移动(从80移动到了99,磁盘编号是从外到里由小到大编号), 此时768盘块(对应的磁道号为76)加入磁盘的请求队列中,根据电梯调度算法,则接下来磁头移动向哪个磁道?假设每个磁道的移动时间为1ms,则访问76号磁道上的数据还需要多长时间?
时间: 2024-04-01 14:32:15 浏览: 159
电梯调度算法是磁盘调度算法的一种,其基本思想是尽可能地减少磁盘磁头的移动距离,以提高磁盘I/O操作的效率。电梯调度算法可以分为向上扫描算法和向下扫描算法两种。
在向上扫描算法中,磁头按照磁道号从小到大的顺序依次访问磁盘请求队列中的磁道,直到最大磁道号,然后改变方向,按照磁道号从大到小的顺序依次访问磁盘请求队列中的磁道,直到最小磁道号。在向下扫描算法中,则反之。
在本题中,磁头从80移动到了99,此时向上扫描算法会继续向上访问134,然后改变方向,向下访问66和87,最后访问76。因此,接下来磁头移动到76号磁道。
访问76号磁道上的数据需要移动3个磁道,即从99到76需要移动23个盘块,因为每个磁道的移动时间为1ms,所以访问76号磁道上的数据需要23ms。
相关问题
假设磁盘有400个磁道,磁盘请求队列中是一些随机的1/O请求,它们按照到达的次序分别处于110、116、78、36、180、320、300、76、368号磁道上,当前磁头在200号磁道上,并向磁道号增加的方向上移动,请给出按下列算法进行磁盘调度时满足请求的磁头移动的次序。 (1)最短寻道时间优先调度(SSTF) (2)扫描算法(电梯调度算法SCAN) (3)循环扫描算法(CSCAN)
好的,我会回答你的问题。下面分别介绍三种磁盘调度算法的实现过程和磁头移动次序。
1. 最短寻道时间优先调度(SSTF)
SSTF算法会选择距离当前磁头最近的请求进行服务。首先,我们需要计算当前磁头和每个请求的距离,然后按照距离从小到大的顺序依次服务请求。
按照这个算法,服务请求的顺序为:180、116、110、76、78、36、300、320、368。
磁头移动的次序为:200 → 180 → 116 → 110 → 76 → 78 → 36 → 300 → 320 → 368,总共移动了640个磁道。
2. 扫描算法(电梯调度算法SCAN)
SCAN算法会按照磁头移动的方向服务请求,直到服务到最边缘,然后改变移动方向服务请求。
按照这个算法,服务请求的顺序为:180、116、110、78、76、36、300、320、368。
磁头移动的次序为:200 → 180 → 116 → 110 → 78 → 76 → 36 → 300 → 320 → 368 → 400 → 0,总共移动了1040个磁道。
3. 循环扫描算法(CSCAN)
CSCAN算法和SCAN算法类似,但是在到达最边缘后,会直接移动到另一端继续服务请求。
按照这个算法,服务请求的顺序为:180、116、110、78、76、36、368、320、300。
磁头移动的次序为:200 → 180 → 116 → 110 → 78 → 76 → 36 → 368 → 400 → 0 → 320 → 300,总共移动了1048个磁道。
综上所述,三种算法中,SSTF算法的磁头移动次数最少,为640个磁道。
简答题:假设有11个进程先后提出磁盘I/O请求,当前磁头正在100号磁道处,并预向磁道序号增加的方向移动。请求队列的顺序为36、145、120、78、82、140、20、42、165、55、60,分别用FCFS调度算法、SSTF调度算法和SCAN调度算法这3种调度算法完成上述请求,写出磁道的访问顺序和每次磁头移动的距离,并计算出平均移动磁道数。
首先,为了方便计算,我们假设磁盘的磁道数为200。
1. FCFS调度算法
按照先来先服务的原则,依次处理请求队列中的进程。
访问顺序:100 → 36 → 145 → 120 → 78 → 82 → 140 → 20 → 42 → 165 → 55 → 60
磁头移动距离:64 + 109 + 25 + 42 + 42 + 58 + 58 + 120 + 22 + 123 + 105 + 5 = 770
平均移动磁道数:770 / 11 = 70
2. SSTF调度算法
每次选取离当前磁头位置最近的请求进行处理。
访问顺序:100 → 78 → 82 → 55 → 60 → 42 → 36 → 20 → 120 → 140 → 145 → 165
磁头移动距离:22 + 4 + 24 + 27 + 5 + 18 + 16 + 16 + 20 + 25 + 5 = 182
平均移动磁道数:182 / 11 = 16.55(保留两位小数)
3. SCAN调度算法
磁头按照预定方向移动,扫描所有未处理的请求,到达磁盘的一端后返回另一端,继续扫描未处理的请求。
访问顺序:100 → 120 → 140 → 145 → 165 → 200 → 36 → 42 → 55 → 60 → 78 → 82 → 20
磁头移动距离:20 + 20 + 5 + 25 + 35 + 35 + 164 + 6 + 13 + 5 + 18 + 4 + 62 = 412
平均移动磁道数:412 / 11 = 37.45(保留两位小数)
综上所述,SSTF调度算法的平均移动磁道数最小,是最优的算法。
阅读全文