磁盘调度算法习题

news/2024/10/31 7:30:14/

注意(不论被访问的下一个磁道号是几,计算移动距离都是:大数减小数

一.磁盘共有200个柱面(0-199),它刚刚从92号磁道移到98号随道完成读写,假设此时系统中等待访问磁盘盘的磁道序列为190,97,90,45,150,32,162,108,112,80,试给出采用下列磁头移动算法的顺序并计算寻道距离。

  1. FCFS算法:(2)SSTF算法:(3)SCAN算法(4)C-SCAN算法

解析:1.FCFS,按照给的顺序,190 97 90 45 150 32 162 108 112 80

       寻道距离:190-98=92 190-97=93 97-90=7 90-45=45 150-45=105 150-32=118 162-32=130 162-108=54 112-108=4 112-80=32(总是相邻的两个,用大的减去小的最后在相加就是寻道距离)

92+93+7+45+105+118+130+54+4+32=680(磁头共移动680个磁道)

平均寻道长度:680/10=68

       2.SSTF:(要求访问的磁道与当前的磁头所在的磁道距离最近)就是先给从小到大排好序,然后按照括号里面的内容来做

所以顺序应该为97 90 80 108 112 150 162 190 45 32

寻道距离计算为(98-97)+(97-90)+(90-80)+(108-80)+(112-108)+(150-112)+(162-150)+(190-162)+(190-45)+(45-32)=286

平均寻道长度:286/10=28.6

3.SCAN:只有磁头移动到最外侧磁道的时候才能往内移动,移动到最内侧,才能往才移动。

       所以顺序为108 112 150 162 190 97 90 80 45 32其实这个算法也相当于排好从小到大的顺序,然后先到最大的(即最外侧),在从98左边的较小者97回到最小的(即最内侧))。

寻道距离:250(和上面算法一样)

平均寻道长度:250/10=25

       4.C-SCAN:磁头自里向外移动,移动到最外侧,磁头立即返回到最内侧访问。

       所以顺序为108 112 150 162 190 32 45 80 90 97(其实这个算法也相当于排好从小到大的顺序,然后先到最大的(即最外侧),在从左边最小的32回到98)。

寻道距离:295(和上面算法一样)

平均寻道长度:298/10=29.5

二. 假设一个磁盘有100个柱面,编号为0~99,在完成了磁道25处的请求后,磁头当前正在磁道43处服务。磁盘请求的柱面按38、6、40、2、20、22、10的次序到达磁盘驱动器,寻道时每移动一个柱面需要10ms,计算以下算法的总寻道时间:

(1)先来先服务算法

(2)最短寻道时间优先算法

(3)电梯调度算法。

【解答】

磁盘请求的柱面为38、6、40、2、20、22、10,FCFS算法就按照请求到达地次序依次响应。

被访问的下一个磁道号

移动的磁道数

38

43 38 = 5

6

38 6 = 32

40

40 6 = 34

2

40 2 = 38

20

20 2 = 18

22

22 20 = 2

10

22 10 = 12

故先来先服务算法的总寻道时间为10 ∗ ( 5 + 32 + 34 + 38 + 18 + 2 + 12 )

=1410ms

先将磁盘请求按磁道从小到大排个序:261020223840SSTF算法是先响应离自己(磁头所在磁道)最近的磁道上的请求。

当前在43,最近的是40

被访问的下一个磁道号

移动的磁道数

40

43 40 = 3

38

40 38 = 2

22

38 22 = 16

20

22 20 = 2

10

20 10 = 10

6

10 6 = 4

2

6 2 = 4

故最短寻道时间优先算法的总寻道时间为10 ∗ ( 3 + 2 + 16 + 2 + 10 + 4 + 4 )=410ms

还是先将磁盘请求按磁道从小到大排个序:2、6、10、20、22、38、40,题目说了磁头是完成了磁道25处的请求后,当前正在磁道43处服务,可知磁头的移动方向是向外,循环扫描算法是先依次服务完当前方向上的再转头。

但是此时所在磁道43处以外已经没有请求了,所以掉头扫描,和SSTF算法结果一样,总寻道时间为410ms

三. 若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。

(1)先来先服务算法;

(2)最短寻找时间优先算法。

答:

(1)40 → 20 → 44 → 40 → 4 → 80 → 12 → 76

距离:(20)(24)(4)(36)(76)(68)(64) 共移动292柱面

(2)40 → 44 → 20 → 12 → 4 → 76 → 80(先按大小排列4 12 20 40 44 76 80,发现40离40近,所以这里没写了,因为等会计算寻道距离也是0,然后下一个44离40近,在下一个44离20近,在下一个20离12近。。。。。。。)

距离:(4)(24)(8)(8)(72)(4) 共移动120柱面

四.【2018腾讯秋招题目】若磁头当前位置为100磁道,磁头由外向内移动,现有一磁盘读写请求队列(共12个):23,376,205,132,19,61,190,398,29,4,18,40。若采用先来先服务、最短寻道时间优先算法,试计算出平均寻道长度各为多少?

答:

(1)算法思想:

FCFS算法(先来先服务)的思想是根据磁盘读写请求的先后次序来访问。

SSTF算法(最短寻道时间优先)的思想是每次总是寻找离当前柱面(或磁道)最近的优先访问。

(2)平均寻道分析

采用FCFS处理次序为:100-23-376-205-132-19-61-190-398-29-4-18-40,因此磁头移动磁道总数为(100-23)+(376-23)+(376-205)+ (205-132)+(132-19)+(61-19)+(190-61)+(398-190)+(398-29)+(29-4)+(18-4)+(40-18) = 1596。总柱面数(即寻道距离)为:1596,因此平均寻道长度为1596/12=133。

采用SSTF处理次序为:100-132-190-205-61-40-29-23-19-18-4-376-398,因此磁头移动磁道总数为(132-100)+(190-132)+(205-190)+(205-61)+(61-40)+(40-29)+(29-23)+(23-19)+(19-18)+(18-4)+(376-4)+(398-376)=700。总柱面数为:700,因此平均寻道长度为700/12≈58.3。

五.假定一磁盘有200个柱面,编号为0—199,在完成了磁道125处的请求后,当前正在磁道143处为一个请求服务。若请求队列的先后顺序为86,147,91,177,94,150,102,175,130试分别采用FCFS(先来先服务)、SSTF(最短寻道时间优先)、SCAN(扫描)算法和CSCAN(循环扫描)完成上述请求,写出磁头移动的顺序,并计算存取臂移动总量(单位为磁道数)。

【解答】

采用FCFS算法调度时,磁头移动顺序为:

143→86→147→91→177→94→150→102→175→130

磁头移动总量是565(柱面)

采用SSTF算法调度时,磁头移动顺序为:

143→147→150→130→102→94→91→86→175→177

磁头移动总量是162(柱面)

采用SCAN算法调度时,磁头移动顺序为:

143→147→150→175→177→130→102→94→91→86

磁头移动总量是125(柱面)

采用CSCAN算法调度时,磁头移动顺序为:

143-147-150-175-177-86-91-94-102-130

采用FCFS算法调度时(当前143) 被访问的下一个磁道号 移动距离 (磁道数) 57 61  56  86 83  56  48  73  45。总移动量:565

采用SSTF算法调度时(当前143) 被访问的下一个磁道号 移动距离 (磁道数)

4  3  20  28 8  3  5  89  2。总移动量:162

采用SCAN算法调度时(当前143) 被访问的下一个磁道号 移动距离 (磁道数)

4  3  25  2  47  28  8  3  5。总移动量:125

采用CSCAN算法调度时(当前143) 被访问的下一个磁道号 移动距离 (磁道数)  4  3  25  2  91 5  3 8  28。总移动量:169

三、一个磁盘驱动器有150个柱面,考虑一个磁盘队列,它按照到达时间顺序分别是35,52,37,17,80,120,135,104如果读写磁头最初位于柱面90,请使用FCFS,SSTF,SCAN,CSCAN算法求总寻道长度和平均寻道长度.

答:

FCFS

磁头移动顺序:直接按题目的顺序来做

90 -> 35 -> 52 -> 37 -> 17 -> 80 -> 120 -> 135 -> 104

总寻道长度 = (90-35) + (52-35) + (52-37) + ... + (135-120) + (135-104) = 256

平均寻道长度 = 总长/移动次数

256/8 = 32

SSTF

磁头移动顺序: 先按从小到大排序,在每次寻找两个磁道距离最近的

90 -> 80 -> 104 -> 120 -> 135 -> 52 -> 37 -> 35 -> 17

总寻道长度:略(这里不写了,纯计算)

平均寻道长度: 略(这里不写了,纯计算)

SCAN:

磁头移动顺序: 先按从小到大排序

移动顺序分两种

1.向左移动完(向内侧)再往右边(外侧)最近优先寻道!

90-> 80 -> 52 -> 37 -> 35 -> 17 -> 104 -> 120 -> 135

//2.向右(外侧)移动完再往左边(向内侧)最近优先寻道!

90 -> 104 -> 120 -> 135 -> 80 -> 52 -> 37 -> 35 -> 17

总寻道长度:略(这里不写了,纯计算)

平均寻道长度: 略(这里不写了,纯计算)

CSCAN

磁头移动顺序: 先按从小到大排序

移动顺序分两种

1.向左移动完再往右边最远优先寻道!

90-> 80 -> 52 -> 37 -> 35 -> 17 -> 135 -> 120 ->104

2.向右移动完再往左边最远优先寻道!

90 -> 104 -> 120 -> 135 -> 17 -> 35 -> 37 -> 52 -> 80


http://www.ppmy.cn/news/40672.html

相关文章

Python 判断闰年、Python 平方根

Python 判断闰年 以下实例用于判断用户输入的年份是否为闰年: # -*- coding: UTF-8 -*-# Filename : test.py # author by : www.w3cschool.cnyear int(input("输入一个年份: ")) if (year % 4) 0:if (year % 100) 0:if (year % 400) 0:print("…

REVA首届世界巡回交流会——澳门站 亚太峰会!

近日金融相关媒体报道:REVA亚太峰会将定于2023年5月8日—5月10日在澳门举行为期三天的会议交流,本次峰会由REVA主办,这一次的亚太峰会是疫情放开后国内外互联网市场交流的良好契机,也加速推动着国家和地区间互联网的经济、技术交流与合作。此次首战澳门亚太峰会会议,将拉开Reva…

Python结合OpenAI的GPT-3 API做数据分析

本文使用了OpenAI的GPT-3 API来生成数据分析报告。GPT-3是一种基于深度学习的自然语言处理模型,可以生成高质量的自然语言文本。在本示例中,我使用GPT-3来分析给定的CSV文件中的数据,并生成相应的报告。 以下是完整的Python代码示例&#xf…

使用Comparator 对List<Map>格式不严格字段排序

public static void main( String[] args ){String col1 "time";String col2 "num";//双数据源的集合ArrayList<Map> lists produceData(col1, col2);//对双数据源集合惊醒排序 这里2个字段的灵活配置升序降序SortBy2Cols(lists,col1,OrderType.D…

第九章 且慢,弄清索引之阻碍让SQL飞

参考《收获&#xff0c;不止SQL优化》作者: 梁敬彬 / 梁敬弘 一、 索引的不足之处 二、 索引的取舍 三、 结合案例 四、 习题 习题1&#xff1a; &#xff08;1&#xff09; SQL写法导致&#xff1a;列上加函数、列隐式类型转换、HINT固定全表扫描 &#xff08;2&#xff09; S…

OpenCV实战(14)——图像线条提取

OpenCV实战(14)——图像线条提取 0. 前言1. 检测图像轮廓1.1 图像轮廓1.2 使用 Canny 算子检测图像轮廓2. 使用霍夫变换检测图像中的线条2.1 线条的表示2.2 霍夫变换检测直线2.3 概率霍夫变换2.4 霍夫变换与概率霍夫变换对比2.5 霍夫变换检测圆3. 完整代码小结系列链接0. 前言…

【第二节】- Idea本地调试提交Flink程序

1、下载Flink tar包: 解压,查看对应的flink.sh脚本: #!/usr/bin/env bash ################################################################################ # Licensed to the Apache Software Foundation (ASF) under one # or more contributor license agreements…

华为OD机试-密室逃生游戏-2022Q4 A卷-Py/Java/JS

小强正在参加《密室逃生》游戏,当前关卡要求找到符合给定密码K(升序的不重复小写字母组成)的箱子, 并给出箱子编号,箱子编号为1~N。 每个箱子中都有一个字符串s,字符串由大写字母、小写字母、数字、标点符号、空格组成, 需要在这些字符串中找到所有的字母,忽略大小写后…