磁盘调度算法的常用磁盘调度算法

发布网友 发布时间：2022-04-29 16:54

我来回答

共2个回答

懂视网 时间：2022-04-12 00:30

2.3.5 磁盘调度和电梯算法 2010-12-14 09:39 杨冬青/吴愈青 等译 机械工业出版社 字号： T | T 综合评级： 想读(14)在读(4)已读(6)品书斋鉴(4) 已有24 人发表书评 《数据库系统实现（第2版）》第2章辅助存储管理，本章讲述我们需要知道的一个典型的计算机系

2.3.5 磁盘调度和电梯算法

2010-12-14 09:39 杨冬青/吴愈青 等译 机械工业出版社 字号：T | T

综合评级：

想读(14) 在读(4) 已读(6) 品书斋鉴(4) 已有24人发表书评

《数据库系统实现（第2版）》第2章辅助存储管理，本章讲述我们需要知道的一个典型的计算机系统如何进行存储管理。我们将回顾存储器层次，其设备的访问速度递减而存储空间却递增。我们将特别关注磁盘，研究磁盘上数据的组织形式对其访问速度的影响。我们还将学习提高磁盘可靠性的机制。本节为大家介绍磁盘调度和电梯算法。

AD：WOT2015 互联网运维与开发者大会 热销抢票

2.3.5 磁盘调度和电梯算法

提高磁盘系统吞吐率的另一个有效方法是让磁盘控制器在若干个请求中选择一个来首先执行。当系统需要按一定的顺序访问磁盘块的时候该方法无法使用，但若请求来自独立的进程，一般而言，这些请求都会得益于调度程序公平而审慎的调度。

调度大量块请求的一个简单而有效的方法被称为电梯算法（elevator algorithm）。我们把磁头看作是在做横跨磁盘的扫描，从柱面最内圈到最外圈，然后再返回来，正如电梯做垂直运动，从建筑物的底层到顶层，然后再返回来。当磁头通过柱面时，如果有一个或多个对该柱面上的块的请求，磁头就停下来。根据请求，所有这些块被读或写。然后磁头沿着其正在行进的同一方向继续移动，直至遇到下一个包含要访问块的柱面。当磁头到达其行进方向上的某一个位置时，在该位置的前方不再有访问请求，磁头就朝相反方向移动。

例2.6假设我们正在调度一个Megatron 747磁盘，我们回忆起该磁盘的平均寻道时间、旋转等待时间和传输时间分别为6.46、4.17和0.13（在本例中，所有时间均以ms计算）。假设某一时刻存在着对柱面8000、24000和56000的块访问请求。磁头正位于柱面8000。此外，还有3个对块的访问请求，在晚些时候到来，正如图2-6所概括的那样。例如，对柱面16000的块的访问请求在10ms时产生。

我们将假定，每个块访问导致0.13ms传输时间和4.17ms平均旋转等待时间，即无论寻道时间是多少，我们都需要为每一次块访问加上4.3ms。寻道时间可通过例2.2给出的Megatron 747的规则计算：1加上磁道数被4000除（1+磁道数/500）。让我们看看，如果通过电梯算法调度会发生什么情况。对柱面8000的第一个请求不需要寻道，因为磁头已经定位在那里。这样，在时间4.3ms处第一次访问将完成。对柱面16000的请求这时尚未到达，所以我们移动磁头到柱面24000，即我们在向数字最大的磁道方向扫描中所请求的下一“站”。从柱面8000到24000的寻道花费5ms，所以我们在时间9.3到达，并在另一个4.3ms内完成访问。这样，第二次访问在时间13.6完成。在这个时间之前，对柱面16000的请求已经到达，但是我们是在时间7.3经过那个柱面，并且在下一次经过之前不会回到那个位置。

这样，我们接下来移动到柱面56000，花费9ms用于寻道，4.3ms用于旋转和传输。这样，第三次访问在时间26.9完成。现在，对柱面64000的请求已经到达，所以我们继续向外圈行进。我们需要3ms寻道时间，所以本次访问完成时间是在26.9+3+8.3=34.2处。

在这个时刻，对柱面40000的请求已经产生，所以现在还有本次请求和柱面16000的请求。于是我们内圈行进，处理这两次请求。图2-7总结了各个请求处理的时间。

图2-6 6个块请求的到达时间

图2-7采用电梯算法的块访问完成时间

【责任编辑：云霞 TEL：（010）68476606】

热心网友 时间：2022-04-11 21:38

FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法。该算法的优点是具有公平性。如果只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则有望达到较好的性能；但如果有大量进程竞争使用磁盘，那么这种算法在性能上往往接近于随机调度。所以，实际磁盘调度中考虑一些更为复杂的调度算法。
1、算法思想：按访问请求到达的先后次序服务。
2、优点：简单，公平。
3、缺点：效率不高，相邻两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利。
4、例子：
假设磁盘访问序列：98，183，37，122，14，124，65，67。读写头起始位置：53。求：磁头服务序列和磁头移动总距离（道数）。
由题意和先来先服务算法的思想，得到下图所示的磁头移动轨迹。由此：
磁头服务序列为：98，183，37，122，14，124，65，67
磁头移动总距离=（98-53）+（183-98）+|37-183|+（122-37）+|14-122|+（124-14）+|65-124|+（67-65）=640（磁道） SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。
1、算法思想：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。
2、优点：改善了磁盘平均服务时间。
3、缺点：造成某些访问请求长期等待得不到服务。
4、例子：对上例的磁盘访问序列，可得磁头移动的轨迹如下图。 SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于磁头移动规律与电梯运行相似，故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如FCFS算法和SSTF算法好。
算法思想：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移 动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。如下图所示：
扫描算法（电梯算法）的磁头移动轨迹
2、优点：克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。 在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型的C-SCAN算法来避免这个问题。
釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK和C-LOOK调度。这是因为它们在朝一个给定方向移动前会查看是否有请求。注意，若无特别说明，也可以默认SCAN算法和C-SCAN算法为LOOK和C-LOOK调度。