Ruemmler 和 Wilkes [RW92]，以及 Anderson、Dykes 和 Riedel [ADR03]在他们 的优秀论文中提供了许多这方面的细节。
关键问题：如何存储和访问磁盘上的数据
现代HDD如何存储数据？接口是什么？数据是如何安排和访问的？磁盘调度如何提高性能？
接口
我们先来了解一个磁盘的接口。所有磁盘的基本接口都很简单。磁盘由大量的扇区组成(512字节块)，每个扇区都可以读取或写入。在具有n个扇区的磁盘上，扇区从0到n-1编号。因此，我们可以将磁盘视为一组扇区，0到n-1是磁盘的地址空间(address space)。
多扇区操作是可能的。实际上，许多文件系统一次读取或写入4KB(或更多)。但是，在更新磁盘时，磁盘的制造商唯一保证的时单个512字节（一个扇区）的写入时原子的(atomic, 即它完整地完成或者根本不会完成)。因此，如果发生不合时宜的掉电，则只能完成较大写入的一部分(有时称为不完整写入(torn write))。
大多数磁盘的客户端都会做一些假设，但是这些假设并没有在接口中制定。Schlosser和Ganger称这是磁盘的“不成文合同”。具体来说，通常可以假设访问磁盘的地址空间内两个相邻的块会比两个相隔更远的块速度更快。人们通常也会假设访问连续块(即顺序读取或写入)是最快的访问模式，并且通常比任何更随机的访问模式快得多。
基本几何形状
盘片(platter)
盘片(platter)是一个圆形坚硬的表面，通过引入磁性变化来永久存储数据。磁盘可能有一个或者多个盘片。每个盘片都有两面，每面都称为表面，是两块独立的盘面，如下图b可以体现。这些盘面通常由一些硬质材料(如铝)制成，然后涂上一层薄薄的磁性层，即使驱动器断点，驱动器也能持久存储数据位。
主轴(spindle)
所有盘片都围绕主轴(spindle)连接在一起，主轴连接到电机，以一个恒定(固定)的速度旋转盘片(当驱动器接通电源时)。旋转速率通常以每分钟转速(Rotations Per Minute, RPM)来测量，典型的现代值在7200~15000RPM，我们一般会对单次旋转时间比较敏感，如10000RPM旋转的驱动器意味着一次旋转大约需要6ms。(10000/60 =166.666, 1/1.666 = 0.006s, 1秒 = 1000毫秒，即6毫米左右)
磁道(track)
在盘片上，会有很多圆形轨道用于存储数据，磁盘的表面被分成若干个同心圆，每一个同心圆划分出的圆弧就是一条磁道(track)，一个表面包含数以千计的磁道布满，数百个磁道只有头发的宽度。
磁头(disk head)
磁头有时候也会被叫做探头，探针(读写头)，它是位于机械臂尾端的元件，它其实并不会直接接触盘面，而是会在盘面上方一层薄薄的气垫上。它很脆弱，因此在使用硬盘时，不要在读写磁盘时移动或者扰乱其表面
机械臂(disk arm)
机械臂是位于盘面附近一个物理器件，它有点类似于人的手臂，由若干个关节组成，可以在磁盘的盘面上面移动，包括了机械臂臂身、关节、电机等部件。它们协同工作，通过精密的机械设计和电子控制，可以实现非常精确的磁道定位，从而实现对磁盘上数据的精确读写。它的尾端有一个磁头，当发生读写的时候，会通过移动机械臂来定位到具体的磁道。
需要注意的是，在多个盘面的磁盘驱动器上，机械臂的末端可能会有多个独立的读写头，它们可以相互独立工作，从而达到并行的读取。不过这会对机械臂的设计和控制要求更高，会更复杂和精密，因为需要同时控制多个磁头的位置和方向。
简单的磁盘驱动器
让我们来构建一个简单的磁道模型，来学习磁盘是如何工作的了。简单起见，我们先学习单一磁道的磁盘，如下图。
这个磁道只有12个扇区，每个扇区的大小是512字节(典型的扇区大小，回忆一下)，因此用0到11的数字来表示。这里的单个盘片围绕主轴旋转，电机连接到主轴。此外，还有一个机械臂和磁头，如下所见。
单磁道延迟：旋转延迟
要理解如何在单道磁盘上处理请求，请想象我们现在收到读取块0的请求。磁盘应该如何处理该请求？
在我们简单磁盘中，磁盘不需要做太多工作，因为只有一个磁道，所以不需要寻道。具体来说，它需要等待期望的扇区旋转到磁头下。这种等待在现代驱动器中经常发生。并且是I/O服务时间的重要组成部分，对于这种等待，它有一个专业术语：旋转延迟(rotational delay，有时称为 rotation delay，尽管听起来很奇怪)。
在这个例子中，如果完整的旋转延迟是R，当前磁头位于6号扇区的位置，假设我们要读取扇区0，那么磁盘必然产生大约为R/2的旋转延迟。对于这个磁道来说，最坏的情况就是请求5号扇区，这需要一次接近完整的旋转延迟，才能服务这个请求。
多磁道：寻道时间
为了读取某个目标扇区的内容，机械臂首先将磁头定位到包含目标扇区的磁道上。移动机械臂所需的事件称为寻道时间。寻道时间依赖于磁头之前所在的位置和机械臂在盘面上移动的速度。现代的磁盘平均寻道时间是通过对几千次随机扇区的寻道求平均值来测量的，通常为3~9ms。一次寻道的最大时间 可以高达20ms。
现在我们再来看看多磁道的磁盘，现代的磁盘在一个盘面上多达数百万计的磁道。因此，我们来看看更具有现实感的盘面，如下图所示，这个盘面有3条磁道，其中最内侧的磁道包含24-35扇区，下一个磁道包含12-23扇区，最外面的磁道包含0-11扇区。
我们来理解一下，尝试访问指定扇区的请求。例如访问扇区11，为了处理这个请求，驱动器必须先将机械臂移动到正确的磁道(在这个例子中，是最外面的磁道)，即寻道(seek)过程。寻道，以及旋转等待，是最昂贵的磁盘操作之一。
应该指出的是，寻道有许多阶段：首先是机械臂移动时的加速阶段。然后随着机械臂全速移动而惯性滑动。然后随着机械臂减速而减速。最后，在磁头小心地放置在正确的磁道上停下来。停放时间(settling time)通过不小，例如0.5~2ms，因为驱动器必须确定找到正确的磁道(想象一下，如果它只是移动到附近)。这个过程有点类似于在停车位停车的操作。
寻道完成之后，机械臂将磁头定位到了正确的磁道上，如上图右侧。此时盘面在正常继续旋转，在这个例子中，大约旋转了3个扇区。因此，扇区9即将通过磁头下方，因此我们需要等待短暂的旋转延迟。
当扇区11经过磁头时，I/O的最后阶段将发生，称为传输(transfer)，数据从表面读取或者写入表面。因此，我们得到了完成的I/O时间图：首先寻道，然后等待转动延迟，最后传输。
磁盘控制器
目前我们知道，现在的磁盘构造复杂，有多个盘面，每个盘面上还有很多扇区。为了对操作系统隐藏这样的复杂性，现代磁盘将它们的构造呈现为一个简单的视图，—个B个扇区大小的逻辑块的序列，编号为 0，1，… ，B-1。
磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。
当操作系统想要执行一个I/O操作时，例如读一个磁盘扇区的数据到主存，操作系统会发送—个命令到磁盘控制器，让它读某个逻辑块号。控制器上的固件执行一个快速表査找，将一个逻辑块号翻译成一个三元组(盘面，磁道，扇区），这个三元组唯一地标识了对应的物理扇区。控制器上的硬件会解释这个三元组，将读/写头移动到适当的柱面，等待扇区移动到读/写头下，将读/写头感知到的位放到控制器上的一个小缓冲区中，然后将它们复制到主存中。
格式化磁盘的容量
磁盘控制器必须对磁盘进行格式化，然后才能在该磁盘上存储数据。格式化包括用标识扇区的信息填写扇区之间的间隙，标识出表面有故障的盘面并且不使用它们，以及在每个区中预留出一组柱面作为备用，如果区中一个或多个柱面在磁盘使用过程中坏掉了，就可以使用这些备用的柱面。因为存在着这些备用的柱面，所以磁盘制造商所说的格式化容量比最大容量要小。
磁盘缓存
现代的磁盘还有一个重要的组成部分，即它的缓存(cache)，由于历史原因，有时候也被称为缓冲区(track buffer)。该缓存不会很大(通常大约8MB或16MB)，驱动器可以使用这些内存来保存磁盘读取或者写入的数据(有点类似于小区楼下的丰巢或收发室)。当磁盘读取扇区时，驱动器可能会先将读取到的数据放到缓冲区中。这样的话，驱动器就可以快速响应对同一磁道的请求(有点类似于外卖骑手的车尾的外卖架，对于同一家店铺的外卖，骑手会先将第一份外卖放入外卖架，然后再将这家店的其它外卖一起放入外卖架。或者也可以类比成小区楼下的菜鸟驿站)。
有了缓冲区之后，那么操作系统往磁盘写入数据时，就会有些纠结了。有两种方式，一种方式是将其先放入缓冲区，等磁盘有空时再实际写入。还有一种方式是不存入缓冲区，而是直接的进行写入。前者称为写回(write back)，后者称为直写(write through)。
使用写回方式的话，看起来会觉得磁盘的处理速度“很快”，但是也有危险，即并没有实际的写入到磁盘中。如果文件系统或者应用程序要求数据按照特定顺序写入磁盘以保证正确性，写回可能会导致问题。
计算I/O时间
我们现在开始来分析一下磁盘的性能。具体来说，我们现在可以将一次完整的I/O时间分成3个组成部分
但通常我们习惯用类似 90MB/s这样的方式来表示I/O速率()，如下图所示，它很容易，只需要将传输大小除以所花时间：
为了更好的感受I/O时间，我们一会会通过测试两个我们感兴趣的工作负载情况。
第一个是4K随机工作负载(random)：这个测试会对磁盘的随机位置发出小的(例如4KB)读取请求，这是测试磁盘性能最重要的一项指标。
还有一个是顺序工作负载(sequential)：会从磁盘连续读取大量的扇区，这些扇区是连续的，不会跳过，顺序访问的速度在拷贝文件，全文搜索的时候比较重要。
同时，为了理解随机和顺序工作负载之间的性能差异，我们通过测试两块希捷不同的现代磁盘。第一个是 Ceetah15K.5，是高性能SCSI驱动器。第二个是Barracuda，是一个为容量而生的驱动器。这两个磁盘的特性完全不同，并且从很多方面总结了磁盘驱动器市场的两个重要部分。首先是“高性能”磁盘市场，磁盘的设计尽可能快，提供低寻道时间，并快速传输数据。其次是“容量”市场，每字节成本是最重要的方面。因此，磁盘的速度较慢，但将尽可能多的数据放到可用空间中。两块硬盘的数据如下所示：
ㅤ | Cheetah 15K.5 | Barracuda |
容量 | 300GB | 1TB |
RPM | 15000 | 7200 |
平均寻道时间 | 4ms | 9ms |
最大传输速度 | 125MB/s | 105MB/s |
磁盘 | 4 | 4 |
缓存 | 16MB | 16/32MB |
连接方式 | SCSI | SATA |
首先我们来测试一下随机访问的性能。假设每次读取4kb的随机位置，我们来看一下每次读取大概需要多长时间
- 寻道时间使用制造商报告的时间
4ms
- 旋转时间等于 60 /15000= 0.004s；0.004 *1000 = 4ms(一次完整旋转的时间)，那么平均时间就是4/2=
2ms
- 传输时间是 传输大小(4kb)乘以峰值传输速率(125MB/s)
4 / (125 *1024) 转成字节 = 0.00003125s
0.00003125 * 1000 * 1000 =
31.25us因此得到：寻道= 4ms，旋转=2ms，传输=30us
得到以上三个条件后，将这三个条件相加就是4kb的I/O时间，我们现在就知道Cheetah硬盘进行一次4kb的读写大约需要6ms左右。因此，我们可以再次计算得到随机访问时I/O的速度。套用上面的公式，就是用4kb除以6ms，在进行计算之前我们先做一下转换，更方便阅读，我们需要得到类似 90mb/s 这样的结果。
我们先将4kb转换成字节(byte)，即是4096byte。然后再把6ms转成s，得到0.006s。接着再用4096/0.006 = 682666.6666666666 byte，接着再把这个结果转成kb，682666.6666666666byte / 1024 = 666.6666666666666kb，因此得到666.66kb/s，转成MB的话大概是
0.66MB/s，对Barracuda进行同样的计算，它的时间约为13.2ms，因此4k随机速率是0.31MB/s。我们再来计算一下顺序工作负载。这里我们假定只需要一次寻道和旋转，随后就是很长的传输。简单起见，我们测试的传输大小是100MB。因此Barracuda 和 Cheetah的时间分别是800ms (100/125=0.8s == 800ms)和950ms。
ㅤ | Cheetah | Barracuda |
随机 | 0.66MB/s | 0.31MB/s |
顺序 | 125MB/s | 105MB/s |
通过上表我们也发现了，随机负载和顺序负载的性能差距很大，对于Cheetah磁盘来说，性能差距差不多是200倍，而对于Barracuda来说，性能差距差不多是300倍
我们还发现了，高端“性能”磁盘和低端“容量”磁盘的性能差异很大。出于这个原因(和其它原因)，大家往往愿意为前者支付更高的价格，同时尽可能便宜地获得后者。
提示：顺序地使用磁盘
尽可能以顺序方式将数据传输到磁盘，并从磁盘传输数据。如果顺序不可行，至少应考虑以大块传输数据：越大越好。如果 I/O 是以小而随机方式完成的，则 I/O 性能将受到显著影响。而且，用户也会痛苦。而且，你也会痛苦，因为你知道正是你不小心的随机 I/O 让你痛苦。
磁盘调度
由于一次I/O的时间成本很高，因此，为了尽可能让让磁盘的效率更好。操作系统的I/O子系统会在实际的I/O请求被发送到磁盘时，先对这些请求做一些排序处理。它会对这些请求进行调度，决定下个该先发送哪个请求。
还记得我们之前我们学习进程调度的时候，每一个进程的耗时时间我们预先是没法知道的。但是磁盘调度，我们可以很好的猜测“任务”(即磁盘请求)需要请求多长时间，因此会尽量让耗时最少的请求优先调度。因此，磁盘调度程序会尝试遵循SJF(最短任务优先)的原则(principle of SJF, shortest job first)。
SSTF: 最短寻道时间优先
一种早期的磁盘调度方法被称为最短寻道时间优先(Shortest-Seek-Time-First, SSTF)(也称为最短寻道优先，Shortest-Seek-First，SSF)。
SSTF按磁道对I/O请求队列排序，选择在最近磁道上的请求先完成。例如，假设磁头当前位置在内圈磁道上，并且接收到请求扇区21(中间磁道)和扇区2(外圈磁道)，那么磁盘会先对扇区21请求，等待它完成，然后对2发出请求。
在我们这个例子中，SSTF的运作很良好，首先寻找中间磁道，然后寻找外侧磁道。但是SSTF不是万能的，有以下两个问题。
第一个问题是，操作系统是无法利用驱动器的几何结构的，操作系统只能看到一系列的块。但这个问题比较容易解决。操作系统可以简单地实现最近块优先(Nearest-Block-First, NBF)，而不是SSTF，然后用最近块地址来调度请求。
第二个问题更为严重：饥饿(starvation)。想象一下，假设我们频繁的请求离磁头距离较近的磁道(如频繁请求 32,25,27扇区)，此时如果还有处于外侧磁盘中的请求将会被饿死，因此磁头根本没有时间来处理处于外圈磁道的请求。
关键问题：如何处理磁盘饥饿
我们实现类SSTF调度，但避免饥饿？
电梯(又称SCAN或C-SCAN)
这个问题的答案是很久以前得到的，并且相对较简单。该算法最初称为SCAN，简单地以跨越磁道的顺序来服务磁盘的请求。我们将一次完整的跨越盘面上所有磁道称为扫一遍。因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，他就不会立即处理(不会反方向扫，从不回头)，而是排队等待下次扫一遍。这个最简单的电梯只能单向扫描，一次扫描结束后会继续回到起始位置(最外侧或者最内侧磁道)，重新进行扫描。
SCAN有许多变种，所有的这些变种都是一样的。例如，Coffman等人引入了
F-SCAN，即Forward-SCAN(正向扫描算法)，它在扫描一遍时冻结请求队列以保证新加入进来的请求不能插队。它的思路很简单。它有两个队列，A和B队列，每次接收到一批请求后，都会将这些请求按磁盘进行排序，排序后再放入其中一个队列中(假设是A队列)，然后磁盘就会根据A队列的请求进行扫描。此时如果收到新的请求，则会将这些请求放入到B队列中。等A队列的所有请求服务完，磁盘会以相同的方式去扫描B队列。从而避免了饥饿问题，延迟了迟到(但更近)的请求。还有一种SCAN的变体是
C-SCAN,即循环SCAN(Circular SCAN)的缩写。它不是单方向的扫描，该算法会从外圈扫描到内圈，然后内存再扫描到外圈，如此循环。由于这个算法和电梯的运行方式很类似，又是被称为电梯(elevator)算法，电梯要么向上要么向下，而不是根据那层楼更近来服务请求。如果你从10楼想下降到1楼，有人在3楼上来按下4楼，那么电梯就会上升到4楼，因为3→4比3→1更近! 如你所见，电梯算法在现实中使用时，可以方式电梯发生战斗。在磁盘中，它就防止了饥饿。
但SCAN极其变种也并不是最好的调度技术。特别是SCAN(甚至SSTF)实际上并没有严格遵循SJF的原则。具体来说，它们忽视了旋转时间，具体来说，即在磁头移动到下一磁道时，可能要请求的扇区刚刚从磁头下路过，因此需要在在等待一次完整的旋转时间。
关键问题：如何计算磁盘旋转开销
如何同时考虑寻道和旋转，实现更接近SJF的算法？
SPTF: 最短定位时间优先
在讨论最短定位时间优先调度(Shortest Positioning Time First SPTF 有时也被称为最短接入时间优先，Shortest Access Time First SATF)之前，我们先通过一个小例子来更详细的了解问题。
在这个例子中，磁头当前定位在内圈磁道扇区30的位置。因此，调度程序需要决定：下一个请求应该是是扇区16(中间磁道)还是扇区8(外侧磁道)。接下来应该服务哪个请求？
答案当然是“视情况而定”。在工程中，事实证明视情况而定几乎可以回答所有问题。这反映了取舍是工程师生活的一部分。这样的格言也很好，例如，当你不知道老板问题的答案时，也许可以试试这句话。然而，知道为什么视情况认定就更好了，我们在这里要讨论这一点。
这个例子的情况是选择时间和寻道时间的纠结。如果在我们的例子中，寻道时间会比旋转延迟更久，那么SSTF(和变体)的调度则更优。但是，想象一下，如果寻道时间比旋转延迟更快。那么在我们的例子中，寻道远一点的，在外圈磁道的服务扇区8，会比寻道近一点的，在中间磁道的扇区16更优。后者必须旋转很长的时间才能移到磁头下。
在现代磁盘中，正如上面所看到的，寻道和旋转的延迟相当(当然，视具体的请求而定)，因此SPTF(最短定位时间优先)是有用的，它提高的性能。然而，它在操作系统中实现起来更加困难，操作系统不请求磁道的边界在哪(即一个磁道上包含的x-y扇区)，也不知道磁头当前的位置(旋转到了哪里)。因此，SPTF通常在磁盘内部执行。
提示：总是视情况而定(LIVNY定律)
正如我们的同事Miron Livny总是说的那样,几乎任何问题都可以用"视情况而定"来回答。但是,要谨慎使用,因为如果你以这种方式回答太多问题,人们就不会再问你问题。例如,有人问:"想去吃午饭吗?"你回答:"视情况而定。你是一个人来吗?"
其它调度问题
在这个基本的磁盘操作，调度和相关的简要描述中，还有很多问题我们没有讨论。其中一个问题及时：在现代系统上执行磁盘调度的地方在哪里？在较早的系统时，操作系统自身完成了所有的调度。在查看一系列I/O请求后，操作系统会选择最好的那个，将其发送到磁盘。当该请求完成时，将选择下一个，如此反复。磁盘当前比较简单，生活也是ヽ(^o^)丿。在现代系统中，操作系统的I/O子系统会负责主要调度。
在现代系统中，磁盘可以接受多个分离的请求(即磁盘可以接受任意扇区的氢气，而不需要I/O子系统预先对请求分配)。磁盘内部现在有复杂的调度程序(它们可以准确的实现SPTF。在磁盘内部，所有的相关细节都可以得到，包括精确地磁头位置)。因此，操作系统通常会选择它认为最好的几个请求(如上面例子中的16)，并将它们全部发送到磁盘。磁盘会通过磁头的位置和详细的磁道布局信息等内部信息，以最佳可能(SPTE)顺序服务于这些请求。
磁盘调度程序另一个相关任务是I/O合并(I/O merging)。例如，设想一系列请求读取块33,8,34。如上例子图所示。在这种情况下，调度程序会将块33和块34的请求合并(merge)为一个请求。最后发送给磁盘时都是基于合并后的请求。合并在操作系统级别尤其重要，因为它减少了发送到磁盘的请求数量，从而降低了时间开销。
调度程序最后一个问题：在想磁盘真正发出I/O之前，操作系统需要等待多久？有些人可能天真的认为，操作系统每收到一个磁盘I/O都会立即向磁盘发出请求。这种方法被称为工作保全(work-conserving)，因为如果有请求要服务，磁盘将永远不会闲下来。然而，对预期磁盘调度的研究表明，有时最好等待一段时间，即所谓的非工作保全(non-work-conserving)方法。通过等待，新的和“更好”的请求可能会到达磁盘，从而整体效率提高。当然，决定何时等待以及等待多久可能非常棘手。这方面可以参考对应的研究论文或者查看Linux内核实现。