北工大毕业生热血研究 揭密硬盘提速

    这两天看惯了美女、电影和PSP的内容，现在忽然来了这么一篇教材一样的文章，大家可能会感到有点奇怪吧。其实这件事说起来就要追溯到小编的大学本科时代了，那个时候我们专业的毕业设计中，除了课题和论文，还需要翻译一份国外的计算机相关文献。小编的毕业设计是操作系统方面的，所以就翻译了一本国外的操作系统教材中的磁盘调度策略章节。

 四本文档 小编告别了本科时代

    虽然节选自操作系统教材，但是本篇文章还是深入浅出的阐述了磁盘的调度策略。这些专业名词听起来虽然有点唬人，但是请相信我，本篇文章的内容并不深奥，大家看过之后就可以冒充高手去找别人喷。

    另外需要说明的是，由于那本教材出版时间比较早，所以其中描述硬盘的一些参数例如寻道时间等等，和现在的硬件发展水平相差比较远，不过那些基本的原理还是无所谓过时与否，大家在阅读的时候可以加以注意。<

12.1  绪论

    在多道程序设计的计算机系统中，导致系统执行效率降低的一个常见原因，就是旋转结构类存储设备的运行方案不当——例如磁盘和磁鼓等。本章引用了如何管理旋转类存储设备的文献，这50多个文献对于希望深入研究相关领域的朋友们来说是一个起点。

    在本章和下一章中我们将软盘、硬盘（使用磁介质存储技术的）、磁盘缓存、磁鼓、内存模拟磁盘、光盘等全都归入“磁盘或磁盘类”设备。我们将会讨论导致设备执行效率低下的原因、提高效率的方案，并且对各种管理磁盘的标准算法进行比较。

    我们将讨论各种影响系统设计师的决定的因素，设计师们会根据这些因素考虑是否要在系统中加入对磁盘的调度管理。另外我们还要说明在何种情况下没有必要使用这些调度策略。在下一章中，我们还将更多的考虑在不同磁盘设备中的信息组织方式，也就是文件系统管理。

12.2  可移动磁头的磁盘存储器操作

    图12.1是一个磁头可移动的硬盘的侧面图示。数据被按照连续的序列记录在这些带有磁介质的盘片上，这些盘片被连接在一个轴心上面，工作的时候以很高的速度旋转。

    数据的访问（也就是读或写），是由一串读/写磁头完成的，其中每个磁头负责一个盘片。读/写磁头只有在非常接近盘片的地方才能够进行读写操作，因此只有盘片相应的部分转到磁头的正下方（或者正上方）才能进行操作。这样，我们就引出了“延迟时间”（latency time）这个概念：即磁头从当前位置移动到指定位置所需的时间。

    磁头一旦固定了位置，随着盘片的旋转就会在上面划出一个圆形的磁道。每一个磁头都是和一个吊杆或者移动吊臂相连，可以随之向内圈或者外圈移动。当磁头随着吊臂到达一个新的位置的时候，就可以对这个位置的磁道进行读/写操作了。而此时，垂直的多个磁头也就形成了一个垂直的柱面。这些磁头被吊臂带到新位置，多个磁头形成柱面的过程就叫做“寻道操作” （seek operation）。

    综上所述，要想对指定的数据进行一次成功的访问，要经过以下几个必要的过程（图12.2）：首先要由吊臂将磁头带到指定的柱面；接着，磁头要等到相应的扇区旋转到它的下方（或者上方）才可以进行读/写操作（也就是要经过“延迟时间”）。最后，需要处理的任意长度的数据（最大值当然是这条磁道的最大容量）就要开始被写入/读出，在此期间经历的时间叫做“传输时间”（transmission time）。由于上面的每一个步骤都是机械运动的过程，因此总的加起来，处理指定的数据需要的时间是不可忽略的。<

12.3  为什么需要磁盘调度

    在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。有些操作系统对于进程的请求使用简单的“先来先服务”（FCFS ：afirst-come-first-served）的策略，即先来的请求先被响应。FCFS策略看起来似乎是相当“公平”的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。

    FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间（图12.3）。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候FCFS也被看作是最简单的磁盘调度算法。

    每种磁盘调度算法包含一种挑选等待队列中最应该被响应的请求的规则，而挑选根据就是各个请求的相对位置关系。将请求队列按照这种规则重新排序，为的是将机械运动的路程降到最短。

    在相关文献中提到最多的两种磁盘调度是寻道优化和旋转（延迟）优化。由于寻道时间往往比延迟时间要高出一个数量级，因此绝大部分磁盘调度算法都把优化寻道时间作为首要目标。多数情况下优化延迟时间的作用是微乎其微的，除非是系统的负荷非常重的时候。

    在负荷不是很重的情况下（也就是说请求队列的长度不大），FCFS算法还算是可以接受的方案。而当负荷稍微重一些的时候，其他算法的优势就立刻表现出来了。

    尽管我们的目标是优化磁盘性能，但我们有时候却需要降低磁盘的处理速度。安装额外的硬盘虽然能够提高数据传输的速率，但却有可能超过一般个人电脑能够承受的范围。因此“过剩”的数据就要被存放在磁盘控制器的缓存里面了。此时，“交错”的作用就体现出来了：为了适当降低传输速率，连续的文件数据被分割成n-1个小块，以便于让处理器能够“跟上”。这就是“n路磁盘交错”的概念。不过磁盘的传输速率和减少寻道时间以及降低寻道距离相比较，后者在优化磁盘性能方面仍然起着主导的作用。<

12.4  磁盘调度策略应具有的特征

    上面已经提到，FCFS是一种相对公平的响应请求的策略。下面是一些评估调度策略优劣的指标：

    ·  吞吐量
    ·  平均响应时间
    ·  变化的响应时间（也就是可预见性）

    显而易见，一个调度策略应该尽量提供最大限度的增加吞吐量——每个单位时间能够处理的数据量。由于这些策略可以有效降低寻道时间，因此这时候的吞吐量一定会高于简单的使用FCFS策略的时候。另外一个调度策略应该做到的是降低平均响应时间（或者说是平均等待时间与平均处理时间之和）。同样，由于应用调度策略之后能够有效降低寻道时间，因此其平均响应时间必然比在应用FCFS的情况下要短。

    上面提到的标准是用来提升整体性能的，通常可能在个别请求开销上面起作用。调度策略往往能够在降低特定请求的服务级别时改善总体情况。

    衡量一种策略好坏的一个重要的尺度就是不同响应时间之间的不确定度。所谓不确定度就是数学上讲的个体样本与平均数之间的偏差程度。同样的，我们也用不确定度来衡量可预见性——不确定度越小说明可预见性越强。另外，有些请求会经历反复无常的服务水平。这种情况有时是令人难以忍受的，例如在通过迅速的服务可以帮助售票以及确认乘客是否能够按时到达的航空订票系统中。如果一种调度策略只是试图单纯的增大数据吞吐量而忽视了降低不确定度的话，那么就可能造成容易响应的请求全都被处理了，而不易响应的请求全都被忽略的结果。这是每一个设计者都应该注意的一点。

12.5  寻道的优化

    以下简单总结出了时下最流行的若干种寻道策略，在接下来的章节中我们将逐个对其进行详细讨论。

    · FCFS（First-come-first-served先请求先服务）：对等待队列不进行任何修改。

    · SSTF（Short-seek-time-first最短寻道请求优先）：磁盘的吊臂将移动到距离当前位置最近的请求位置（可以是向内或者向外），以便于缩短吊臂的移动路程。

    · SCAN（扫描）：吊臂在盘面上循环往复运动，在此过程中逐个响应队列里面的请求。当一个请求被完成之后则开始移动吊臂位置。

    · C-SCAN（Circular scan单向扫描）：吊臂朝着内圈的磁道进行单向的扫描。当最盘片里面位置的请求被完成之后，吊臂跳回到最外圈的请求位置上，再一次向内圈进行扫描。

    · N-Step scan（N-Step扫描）：吊臂像在“SCAN”策略里面一样运动，但在扫描过程中收到的同一位置的请求将被重新排序到一起，以便于下次扫描到该位置时将他们同时处理。

    · Eschenbach scheme（Eschenbach 策略）：吊臂的运动方式和“C-SCAN”策略的一样，但是对于某些特殊情况做了改进。我们知道，磁盘上面的每个柱面都是由一个个磁道组成的。每次吊臂运动到某个柱面的时候，实际上可以在该位置对柱面上所有磁道上的数据进行操作。因此我们把等待队列进行重新排序，把处于同一柱面上的位置请求放到一起进行处理。但是当这些请求的位置中有两个所处的扇区有覆盖的情况时，一次只能有一个请求得到响应。<

12.5.1  FCFS（First-come-first-served先请求先服务）调度策略

    在FCFS策略中，先接受的请求先得到响应。看起来这种策略很“公平”：先来的先排队，大家的位置都是固定的，谁也不许“插队”。由于一个具有更高优先级的请求的到来，其它任何一个请求在队列中的位置都不能改变。当一个请求完成之后，FCFS会严格的驱动吊臂到下一个请求的位置，即使再下一个请求的位置就是当前位置。

    通常情况下，队列中请求的地址可能分布在磁盘表面的各个位置，而应用FCFS策略完成这些请求之后的结果，会带有一种很典型的随机性。FCFS策略完全忽视队列中各个请求地址之间的位置关系，所以也就根本不对队列进行任何优化。

    FCFS策略在磁盘负担较轻的情况下是可以接受的。但是随着负担的增加，FCFS策略立刻会导致磁盘设备负担的急剧增大，响应速度也会大大降低。尽管应用FCFS策略之后，响应时间的不确定度确实不大，但是这一理论数字对于早就处于“水深火热之中”的硬盘来说，根本就是于事无补的。<

12.5.2   SSTF（Short-seek-time-first最短寻道请求优先）调度策略

    在SSTF策略中，最基本的规则是：距离最近的请求被下一个服务，不管这个请求在队列中的位置如何，以尽量降低寻道时间。SSTF是一种“柱面定向”的策略，这一点将在后面的练习中体现。

    SSTF策略对于不同请求的响应可能区别非常大。这种策略比较趋向于优先处理盘片中间部分的请求，而可能会比较“冷落”内圈和外圈边缘的请求。（图12.5）

    SSTF策略相比FCFS有更大的吞吐量，而且在负担适当增加的情况下，平均响应时间会有降低的趋势。但是SSTF策略的一个重大缺陷就是响应时间的不确定度很高，究其原因就是刚才提到的盘片中间磁道和边缘磁道被响应的速度差别很大所造成的。在极端条件下，甚至会发生盘片边缘请求的“饥饿”。考虑到SSTF策略在吞吐量以及评价响应时间上面的重大进步，不确定度的增加也就变得可以接受了。SSTF策略在主要看重吞吐量的批处理系统中非常适用；然而响应时间的较高不确定度（或者说是不可预见性）对于交互式系统来说则是无法接受的。<

12.5.3  SCAN（扫描）调度策略

    Denning开发的SCAN策略克服了SSTF的高不确定度这一缺点。

    SCAN策略的工作原理和SSTF有类似之处，但是SCAN并不是以最短的寻道时间作为确定下一个响应的唯一标准。比如，假设吊臂正在向着盘片的外圈移动，那么下一个被响应的请求就是这个方向上的最近请求。只有已经达到最外圈，或者当前方向上没有请求了的情况下，吊臂才会“掉头”走向反方向。由于SCAN的感觉很像是在坐电梯，因此有时候它也被称作“电梯算法”——电梯也是顺着一个方向走，直到走到头或者那个方向上没有乘客之后再折回反方向。我们在后面的练习中将会深入比较SCAN策略和电梯算法的异同。SCAN策略也是其他很多类似策略的基础。

    SCAN的某些方面表现和SSTF非常相像：他们都改进了吞吐量和平均响应时间，但SCAN对于不同请求的响应区别不大，因此也就降低了不确定度。和SSTF类似，SCAN也是一种“柱面定向”的策略，这个问题也将在练习中出现。

    由于应用SCAN策略时，吊臂做的是一种振动运动，这也就决定了磁头访问盘片中间磁道的几率比访问边缘的要稍微大一些，但是绝对没有SSTF那么严重。<

12.5.4  N-Step SCAN（N-Step扫描）调度策略

    N-Step SCAN是一种比较有意思的SCAN的扩展。在这种策略中，吊臂像SCAN里面一样往复运动，除非在一次扫描开始之后，请求的数量不变了。那些在扫描过程中提出的请求将会被重新优化排序，为回程的扫描做好准备（图12.7）。在每次的扫描中，前N个请求被响应（按照优化的顺序交给磁头去处理）。

    N-Step SCAN提供了很好的吞吐量以及平均反应时间方面的性能。它比SSTF与普通SCAN更难得的是同样保持了较低的响应时间不确定度。N-Step SCAN还避免了在大量处于同一柱面的产生请求到来的时候，出现延迟时间意外延长的可能。这些全都有赖于对请求的重新排序，以便于为磁头回程扫描做好准备。<

12.5.5  C-SCAN（单向扫描）调度策略

    另外一个SCAN的有趣的改版就是C-SCAN（单向扫描）。C-SCAN避免了过于优先处理盘片中间部分的请求，而可能会比较“冷落”内圈和外圈边缘的请求的情况。

    在C-SCAN策略中，吊臂从最外圈的磁道向最内圈的移动，同时按照“最近先服务”的标准来响应队列中的请求。当吊臂完成一次由外而内的扫描后，会立刻跳转（不响应请求）到最接近外圈的请求位置，紧接着开始下一个由外而内的扫描过程。在正在扫描时收到的请求将会在下次扫描中被响应（图12.8）。因此，C-SCAN策略也从根本上杜绝了盘片边缘与中部的请求响应速度不一致的问题，因此它的不确定度也很理想。

    一些文献中的模拟测试显示，衡量一个策略的效率需要分为大致两种环境分别讨论：在系统负担比较轻的时候，SCAN策略是非常好的方案；在负担适中或者较重的时候，C-SCAN表现最好——特别是在负担较重的时候，为旋转优化过的C-SCAN是首选方案。<

12.5.6  Eschenbach scheme（Eschenbach 调度策略）

    有关这个策略可以参看图12.9，这个策略最初是为航空订票系统设计的，考虑的是系统负担极重的情况。并且这也是第一个不仅考虑优化寻道时间，更考虑了优化延迟时间的策略。然而刚刚讨论的为旋转优化过的C-SCAN策略被证明了在任何条件下的效率都优于Eschenbach 策略。

12.6  旋转优化

    在重负荷的条件下，对某个特殊柱面的访问几率会增加，因此这个时候对旋转优化就变得和寻道优化一样有用起来了。事实上，旋转优化策略在磁鼓等磁头固定的设备上面已经应用很多年了。

    对寻道优化的SSTF策略进行推广就得到了旋转优化的SLTF（shortest-latency-time-first最短延迟请求优先）。当吊臂移动到一个新位置的时候，在这个柱面上可能会有很多请求等待。SLTF策略则开始判断这些请求中延迟时间最小的，并且响应之。这个策略已经被证明是非常接近理想状态的方案，并且相对比较容易实现。旋转优化有时候也被归在“扇区排列”的范畴，因为本质上它确实是按照请求扇区的相互位置关系来优化响应顺序的。<

12.7  系统整体考虑

    在什么情况下有必要应用磁盘的调度策略？什么情况下使用了磁盘调度策略反而会降低系统整体性能？这些问题需要在集成了磁盘调度策略的系统里面得到解释。在接下来的文章中我们将开始讨论哪些有关的情况会影响到设计师的决定。

12.7.1  磁盘存储资源是有限的

    磁盘性能已经被证明是系统整体性能的瓶颈，因此一些专家建议增加磁盘的数量以改善这一情况。但是这么做也未必能够治本，因为增加数量有限的磁盘数量在大量的磁盘操作请求面前仍然是杯水车薪。一旦出现这种情况，磁盘调度管理也就成了最为行之有效的提升性能、消除瓶颈的手段。

12.7.2  多任务的程度

    随着多任务程度的增加，磁盘的负担以及请求的随机性都有上升的趋势。因此，磁盘调度策略在不常见多任务的批处理系统中难以发挥作用；而在有适当多任务的分时操作系统中经常是很有效的；尤其在每分钟有上千条请求的信息交换系统中，磁盘调度策略经常能够收到意想不到的效果。例如，对于一个大型局域网内的文件服务器来说，可能要同时服务上百个用户，这时调度策略就成为非常必要的环节了。

12.7.3  多磁盘子系统

    出于模块化以及经济上面的考虑，在硬件系统中一个磁盘控制器往往要支配多个磁盘。而这些控制器需要轮流和输入输出通道进行通信，最终把磁盘上面的数据传递给中央系统。而一个通道可以支持多个磁盘控制器，每个磁盘控制器又带有多个磁盘，这样就形成了一个树型结构（图12.10）。

    我们看到在这种结构中，输入输出通道并不是与磁盘直接相连的。因此系统设计师们在设计磁盘调度策略的时候需要首先进行调查分析，以研究这种系统的瓶颈所在。有时候瓶颈出在控制器的任务饱和上面，或者是通道的阻塞上。这些情况是比较容易被观察到的，因为不管是用软件还是硬件监测这些通道和控制器，都是可以实时进行的。如果某个控制器的负担经常饱和，那么设计师就要考虑减少这个控制器下属的磁盘数量了。如果是通道阻塞的情况，那么就要试着让其他通道对这个通道进行分流处理。或者追加入新的通道。这些硬件上面的重组对于消除系统瓶颈是非常必要的。

    为了降低通道的负担，很多磁盘系统中都集成了一种被称作“rotational position sensing （RPS 旋转位置探测）”的技术。这一技术能够降低磁盘系统在查找数据时候的繁忙时间。当一条请求到达后，RPS能够另通道空闲，直到磁头开始读取响应数据为止。RPS同样支持多任务的请求，以充分利用硬件资源。

12.7.4  请求的不均匀分布

    相关文献中的多数分析工作，都是建立在假设请求是平均分布在盘片各个位置的。因此这种分析的结论在那些请求分布并不平均的系统中并不适用。这种不均匀请求分布的情况在某些系统中是很常见的，人们也研究过它会造成什么样的结果。Lynch在一项研究中认为，绝大多数的请求地址都是和刚刚处理的地址处于同一柱面。

    造成请求非常集中于相同位置的一个重要原因就是对大尺寸文件以及连续文件进行的读写操作。当操作系统对用户提出的连续文件请求开辟磁盘空间时，往往习惯于使用相同的磁道（尽管现在很多个人操作系统已经支持交错处理）。当一个磁道空间用完之后，系统将追加相邻磁道的空间来存放多余的数据。因此对于处理这样的连续文件来说，寻道时间几乎是零。即使需要寻道操作，也只不过是吊臂移动到相邻的柱面上，这点时间是非常短暂的。显然，这种情况对于磁盘调度策略来说是非常理想的。
在某些系统中，当发现损坏磁道的时候，就需要分配交错磁道进行替换。这样一来，这些交错磁道的位置就难以确定了，而其所需的寻道时间更是无法预测。

12.7.5  文件组织技术

    经过实践应用的文件组织技术，例如ISAM（index sequential access method索引顺序存取法）可能会导致长寻道时间操作的增加。ISAM的接口可能包含多个磁盘的请求。在某些情况下，一个完整的ISAM操作可能需要从主索引记录开始，经过柱面索引记录，然后再转换为最后的真实操作地址。这样一来，每个完整的响应过程可能会包含多个寻道延迟。由于从主索引记录和柱面索引记录都存放在盘片上面（而且远离真正的数据位置），因此这样一来，我们就要为这些寻道操作付出昂贵的时间代价。尽管对于软件设计人员来说ISAM非常方便，但是对于硬件系统来说，这实在是令人头痛的。<