2.3.5 磁盘调度和电梯算法

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采用电梯算法的块访问完成时间

让我们与诸如“先到达先服务”这样更朴素的方法来比较电梯算法的性能。假设头三个请求的顺序是8000、24000、56000，头三个请求完全以同样的方式处理。然而，在那一点，我们要到柱面16000去，因为那是第四个请求要到达的柱面。这个请求的寻道时间是11.0ms，因为我们从柱面56000行进到16000，行程超过了跨越磁盘的一半。第五次请求是对柱面64000，要求一个13ms的寻道时间，最后一次请求是对柱面40000，其寻道时间是7。图2-8概括了由“先到达先服务”调度法所产生的活动。两种算法相差14ms，看起来可能并不是很显著，但是请注意，在这个简单的例子中，请求数较少，而且假设在到达六个请求中的第四个之前两种算法没有区别。

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

回书目   上一节   下一节