参考教材：
Operating Systems: Three Easy Pieces
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
在线阅读：
http://pages.cs.wisc.edu/~remzi/OSTEP/
University of Wisconsin Madison 教授 Remzi Arpaci-Dusseau 认为课本应该是免费的。
————————————————————————————————————————
这是专业必修课《操作系统原理》的复习指引。
在本文的最后附有复习指导的高清截图。需要掌握的概念在文档截图中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
操作系统原理不是语言课，本复习指导对用到的编程语言的语法的讲解也不会很细致。如果不知道代码中的一些关键字或函数的具体用法，你应该自行查找相关资料。

十二 机械硬盘 RAID

1、机械硬盘（Hard disk drive，HDD）本身是按照扇区（sector）为最小单位进行存储的。以前，硬盘的扇区大小一般为512 Bytes；较新的硬盘则采用4 KB作为单个扇区的大小。但是4 KB扇区需要操作系统的支持，所以为了使硬盘在较老的OS上能够被识别，硬盘厂商通过固件（firmware）将4 KB大小的物理扇区模拟成512字节的逻辑扇区。

固件是安装在设备的硬件中的软件，和驱动（需要安装在操作系统内）没有明显的界限，但一般而言固件要更加接近于硬件底层。通常情况下，固件不允许被修改。
硬盘对扇区的读写是原子性的。如果读写过程中突然断电，未写入的数据就会丢失。

2、机械硬盘内部有若干个盘片（platter），它们是圆形的，一般由铝制成，表面极其光滑（你可以把报废的盘片拆下来当镜子用），双面都附有磁性材料来存储数据。盘片都被固定在主轴（spindle）上，随主轴一起转动。硬盘启动后，盘片的转速一般为5400 RPM（转 / 分）或7200 RPM。少数服务器硬盘转速达到10000 RPM甚至15000 RPM。当然，现在也比较少见了。因为高转速对加工的要求很高，而且转速过高可能导致盘片因为原子间提供的向心力不足而直接破碎。另外，高转速带来的发热量也是非常大的。盘片的直径多为2.5英寸或3.5英寸。以前有5.25英寸的硬盘，但是转速也不能做得过快。
其它规格都相同的情况下，转速越高，读写速率越快。7200 RPM的硬盘的读写速率一般高于5400 RPM的硬盘。
盘片被划分为大量的同心圆，每个同心圆称为一个磁道（track，有的软件也写作磁头，但不要将其把用于读取数据的磁头搞混）。单个盘片的磁道数量非常大，目前每张盘片的容量可以做到2 TB。
每张盘片的每一面各有一个磁头（disk head），与机械臂连接，被驱动电路控制，用于在不同的磁道、扇区进行读写。

如图。磁盘启动后，磁头会迅速移到盘片上方。在磁道间读写时，磁头的移动速度是非常快的。磁头通过空气动力学设计浮在盘片上方，距离盘片非常近。空气过滤片过滤空气中的灰尘。盘片对无尘的要求非常严格，所以不要自行拆开硬盘，否则这个硬盘很快就会报废。硬盘中的永磁铁的磁性非常大，如果你拆开了一个报废的硬盘，玩永磁铁的时候千万要小心，否则在磁铁与其它物体吸住的时候，你的手指很可能会马上变成肉泥。

3、收到读写扇区的命令后，磁盘会找到扇区所在的磁道，磁头会先从当前所在的位置移过去。这个过程需要的时间称为寻道时间（seek time）。具体来说，磁头从当前位置开始加速，然后保持一定的速度滑行，再减速，最后靠在正确的磁道上。为了使磁头能正确定位磁道，最后一步耗费的时间也是最多的。
然后，磁盘等待扇区转到磁头可以达到的位置。差不多到达这个位置以后，磁头就进行读写。这个等待的过程称为旋转延迟（rotational delay）。
这时候，传输数据的过程才正式开始。读一个扇区的速率自然是非常快的，因为要在扇区因为盘片的转动而离开磁头之前就将其读取完毕。
读写完毕后，磁头留在原位。因为过度频繁地移动磁头会耗损其寿命。
由此我们得出：磁盘IO的总时间 = 寻道时间 + 旋转延迟 + 传输时间。即
T_IO=T_S+T_R+T_t

4、现在的硬盘采用了磁道偏移（track skew）方式来划分磁道和扇区。下面的图中，右侧是采用了该技术的硬盘：

注意对比两张图的扇区11和12、23和24的相对位置有什么不同。这种方式能使顺序读取的过程中，磁头切换下一条磁道读取时，能够直接从下一个扇区开始读。如果不使用该方式划分磁道和扇区，磁头在切换下一个磁道时，下一个编号的扇区已经在切换磁道的过程中随着盘片的旋转而离开了磁头的位置。若要继续读取此扇区，只能再等盘片转一圈。
这两张图只是为了便于理解而绘制的。事实上，在较新的硬盘中，外侧的磁道拥有的扇区数要更多。现在说的“每磁道扇区数”是一个换算出来的平均值。
机械硬盘都会具有缓存（以前叫做磁道缓冲区（track buffer））。读取数据时，被读取的数据连同附近的数据一起被读入缓存中，以此加快访问速率。在写入数据时，数据也会先写入到缓存，之后再由硬盘正式写入到盘片上。
磁盘在写入时，有两种方式，分别是write back和write through。使用前者时，只要写入的数据全部交给了磁盘（即使有数据还在缓存内），就报告写入已经完毕；使用后者时，只有数据真正写入到盘片上，才报告写入完毕。Write back方式看上去写入速率更高，但如果在磁盘将缓存中的数据写入的过程中断电，未写入盘片的数据将丢失。缓存加快读写速率的原理在第6章第10点已经讲过了。

5、简单学习了磁盘读写的基本步骤之后，很容易想到：顺序读取的速率一定远远高于随机读取，因为随机读取意味着要耗费大量时间在寻道和旋转延迟上。如果频繁请求小文件的随机读写，性能会降低得非常难看。在编写代码的时候也要注意，如果可能，尽量将小的IO凑在一起一次性进行。
由下面的几张图片可以看出顺序读写和小文件读写的性能差距。如果是小文件随机读写，性能就更低了（Pic via Anandtech）。并且，小文件大概率是在硬盘上随机分布的。

6、理论上，平均寻道时间是最大寻道时间的约1 / 3。下面我们来证明这个结论。
设磁道从0编号到N，N→+∞（一个磁盘具有非常多的磁道数量）。从任意一个磁道x寻道至y需要走过的路程近似用
|x – y| 个长度单位表示。于是所有的寻道轨迹的路程之和就是

由乘法原理，共有N2种不同的寻道请求。因此上式除以N2就得到平均的寻道路程。设寻道的平均速率是不变的，那么平均寻道时间与最大寻道时间的比值就由两种情况下磁头走过的路程决定了。
因为N很大，所以上面的式子可以近似为积分式

我们先算内层积分。去掉绝对值，得：

上式已经可以直接解出，结果为：

化简并代入原积分式，得：

这个积分式也可以直接解出，结果为：

如果访问是完全随机的，那么N越大，N2次寻道中磁头走过的总路程就越接近该值。将其除以N2，就得到平均寻道路程为1 / 3倍的N。最大寻道路程自然就是从盘片的最外沿到最内沿，路程为N。结论得证。

7、一系列IO请求产生（或累积）后，磁盘调度器（disk scheduler）负责调度这些磁盘IO请求。与进程 / 线程调度不同，我们一般无法得知进程 / 线程何时结束，但可以根据需要访问的位置和磁头的当前位置算出磁盘的寻道时间和延迟。因此磁盘调度器倾向于选择最短作业优先（SJF）调度算法。
最短寻道时间优先（shortest seek time first，SSTF），或最短寻道优先（shortest seek first，SSF），是很早就产生的磁盘IO调度方法。目标磁道离磁头的当前位置最近的IO请求会被最先处理。
但SSTF并不是万能的，因为磁盘的几何结构并不为操作系统所知，操作系统只把磁盘当成一个由块组成的一维连续结构。不过这个问题非常容易解决，OS容易实现最近块优先（nearest block first，NBF）算法，让离访问过的块最近的IO请求最先被处理。
而且，SSTF容易让部分请求长期饥饿，因为硬盘总是最先响应离当前磁头位置更近的寻道请求。

8、电梯调度，也称SCAN，它的基本思想很简单：不断地由盘片外圈移至内圈，再由内圈移至外圈，如此往复，很像建筑物里的电梯那样反复升降。磁头完整地从外圈移至内圈或从内圈移至外圈一次，称为一次扫描。这个算法总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。如果某个请求在最近一次的扫描中已经处理过，它将不被立即处理。
SCAN算法有很多变体。F-SCAN在扫描进行的过程中冻结请求队列，在扫描期间到来的请求全部被延后至下一轮扫描再处理。这确保了每个IO请求的饥饿时间都不长。
C-SCAN的C代表Circular（循环）。这种算法只从外圈向内圈扫描。一轮扫描完毕后，磁头重新回到最外圈。这种算法对靠近内圈和外圈的IO请求更公平一点。双向的往复扫描可能让部分外圈和内圈的IO请求饥饿时间较长。
举个生活中的简单例子，你就能更好地体会电梯算法的优势了：假如电梯里只有你一人，你从30楼下到1楼，有个人从10楼进来了，按了15楼。如果电梯总是去往最近的楼层，那么它就会先到15楼。如果15楼又有个人上来了，他按了13楼，电梯就到13楼；13楼又有个人上来了，他按了18楼，电梯就又上升到18楼……当轮到你到达1楼的时候，时间已经不知道过去多久了。

9、不过，SCAN和SSTF并没有考虑盘片的旋转造成的影响。在介绍最短定位时间优先（shortest positioning time first，SPTF，或最短访问时间优先，shortest access time first，SATF）之前，先举一个例子：

现在在扇区30。一堆磁盘IO请求过来了，一个是16，一个是8。先处理哪个呢？我们进行分类讨论。
如果寻道时间比旋转延迟长得多，使用SSTF及其变种更佳，先访问扇区16；但如果旋转延迟比寻道时间长，访问8则更优。因为如果访问16则意味着要等盘片转上差不多一圈才能访问到它。
但在较新的机械硬盘中，寻道和旋转时间一般差不多（当然在有些情况下有区别），于是SPTF算法就能更好发挥性能了。但这个方法更难被操作系统实现，因为操作系统并不能知道磁道边界在哪里，也不知道此时磁头在哪个位置，所以这个算法通常由磁盘自行实现。

10、以往，操作系统负责全部的磁盘调度。而现代系统中，磁盘负责大部分的调度。操作系统通常只简单告诉磁盘它认为的一些最优位置，磁盘便接手剩余的调度决策。
OS也负责将邻近位置的磁盘IO合并。这可以减少IO请求的数量，减轻硬盘控制芯片的压力，并且还能提升读写速率。
此外，OS如何知道当IO数量非常少的时候要等待多久？有的OS选择令磁盘连续工作（work-conserving），于是一有磁盘IO到来就立刻让磁盘进行读写；而相对的是预期磁盘调度（anticipatory disk scheduling），当IO请求非常少时，先等待一定时间，以便在收集到更多的IO请求后做出一个更优的调度方案，也可以将邻近区域的磁盘IO请求合并，提升性能。能力足够的同学可以查阅相关的论文或Linux内核代码。

11、我们总是希望硬盘能够更大、更快。一张4K的BD最大容量至少为66 GB，有的盘还更大，把这些电影抓到硬盘里，只需要几十部，一块5 TB的移动硬盘就差不多要满了；也许你还下载了很多数字音乐，它们甚至是Hi-Res或DSD规格的；你还在B站或者YouTube下载了很多很有趣的视频；你还会拿相机或摄像机拍摄很多高质量的照片和录像；你写了很多小说和歌曲，画了很多漫画……这些无不对存储容量、速率和可靠性上提出了更高的要求。
廉价磁盘冗余阵列（Redundant Array of Inexpensive Disks，RAID）一词在1980年代末由UC Berkeley的一组研究人员引入。这个时间前后，许多研究者也不约而同地产生了相似的思想。
从外部看，RAID是一块磁盘，可以作为整体进行读写。但RAID实际上具有多个磁盘，还可以有内存，以及专门管理这些磁盘的处理器。硬RAID已经很接近一个计算机系统，只不过其主要任务是管理磁盘。

12、为计算机添加新的功能时，应该尽量做到透明，也就是说OS基本不用作多少改动就可以让新功能正常运行。RAID是一个非常好的例子。因为你基本上完全可以把RAID当作一块磁盘来用，在OS层面上几乎不需要进行什么更改。把一块磁盘换成一个RAID，不用改动一行代码；在RAID安装完毕后，原有的OS和应用程序可以直接继续运行。透明增强了硬件的可部署性（deployability），用户无需担心软件不与新硬件兼容。

13、当文件系统向RAID发起一个（逻辑）IO请求时，RAID本身要确定需要访问的内容位于哪些磁盘，然后向相应的磁盘发起（物理）IO。RAID的实现是很复杂的：微控制器需要对磁盘正确操作，DRAM负责暂存常用的数据块，有时还要对数据进行校验。

14、评价一个RAID的常见指标有：
（1）容量。同样容量的磁盘，实现不同的RAID后，剩余的可用容量是不同的。
（2）可靠性。这个RAID系统最多能容忍多少磁盘同时损坏？
（3）性能。性能的重要性就不用多说了。

15、RAID 0将数据分散存储在各个磁盘上。假设将一个文件分成很多份（前16份编号0到15），由4块硬盘组件RAID 0，那么它的分布是这样的：

可以看出，数据按照RR（round-robin）的方式分配到各个磁盘。在上表中横跨一整行的每部分数据都称为一个条带（stripe）。RAID将数据按照块（chunk）划分，同一块被写入一个磁盘。如果将块大小（chunk size）扩大两倍，数据的分布就变成这样：

块大小为2的整数次方倍，一般为32 KB或64 KB，其它值亦可。
块大小是影响RAID性能的重要因素。块大小较小时，文件被打散成更多份，于是在访问单个文件的时候，需要访问的部分具有更大的几率位于不同磁盘，使得并发度更高；但是如果要在文件中定位，也需要更多的时间。块大小较大时，情况相反：访问单个文件的时候，需要访问的部分具有更大的几率位于更少的磁盘甚至都位于同一个磁盘，使得并发度更低乃至和单个磁盘的读写性能没有区别；但如果要在文件中定位，则需要更少的时间。块大小需要根据应用场景和硬盘本身的特点来决定，不存在一个普遍适用的值。
下面我们从第14点说的三个指标入手，来评估RAID 0。
在容量上，RAID 0做得很完美：RAID 0的总容量是各个硬盘的容量之和。但是要注意：如果使用不同容量的磁盘来组成 RAID-0时，由于数据是一直等量依序放置到不同磁盘中，当小容量的磁盘用完后，所有的数据都将被写入到剩余的磁盘去。此时的性能就变差了。在性能上，RAID 0也很优秀：有几块磁盘组成RAID 0，读写性能最高就能达到单块磁盘的几倍。当然，数据不大于块大小的时候，它就只能落在一个磁盘上，读写性能就没有提升了。但是，RAID 0不具备任何冗余。如果组成RAID 0中的任何一块磁盘损坏，基本就意味着存储在这个阵列上的全部数据都丢失了，因为所有文件都是被尽可能高度分散并存储的，只有在非损坏磁盘上的那些不大于块大小的小文件能够逃过一劫。
在读写的时候，各块硬盘的工作状态不一定相同，有的盘可能恰好在这时具有更大的寻道时间和旋转延迟。这部分延迟会导致RAID的实际读写速率要比理论上慢一点。

16、RAID 1将数据镜像（mirror）存储，每个磁盘都是另一块磁盘的镜像：

当然，这只是其中一种数据组织方式。你还可以在RAID 1的基础上将数据条带化存储。RAID-10（RAID 1+0）先将数据复制为镜像，再进行条带存储；而RAID-01（RAID 0+1）先条带化，再镜像化。
读取数据时，RAID 1可以从多个磁盘镜像中读取；而写入的时候，必须向每个镜像盘统一写入相同内容，以确保冗余性。
由于RAID 1是完全的镜像，因此可用容量为总容量除以副本数量。一般同一个数据只存储2份，只有十分关键的数据才会启用多个镜像存储。以两份副本为例，RAID 1最多可以容忍一半的盘损坏，当然前提是没有任何两块互为镜像的盘同时损坏；点背的时候，虽然只坏了两块盘，但坏的正好是互为镜像的盘，那这部分数据就确确实实丢失了。

17、RAID 4则带有奇偶校验（parity check）。相比完全镜像的RAID 1，RAID 4存储同样内容需要花费的磁盘数量少得多，但冗余度就没有那么高。

数据依然是条带分布的，每个条带都配有专门的一块磁盘作为校验盘。
校验位的数据是通过奇偶校验得出的。如果有n个二进制位参与奇偶校验，则从左往右共做(n – 1)次异或运算。由异或的性质得：参与运算的位中，若1的个数是奇数，则校验位为1；若1的个数是偶数，则校验位为0。校验时，每块磁盘对应块中的对应位一同进行异或，结果写在校验盘中对应的位。
下图以4块盘各自的位于磁盘最前面的一个数据块的前4位为例。在4磁盘1校验盘的结构下，可以看出数据块是在各个非校验磁盘中交错分布的；图中展示的四个数据块的第0、1、2、3位分别有3、1、1、2个1，校验位为1、1、1、0。

在非校验磁盘中，数据的组织方式与RAID 0一样。而校验盘不负责数据的存储，因此RAID 4的可用容量是非校验磁盘的总容量之和。RAID 4最多允许非校验盘中损坏1块，这1块的数据可以由其它非校验盘和校验盘中的信息重构出来：校验位描述了参与异或运算的1是奇数个还是偶数个。而参与运算的位数又是已知的，所以可以直接推断出缺失的数据。但如果非校验盘损坏了超过1块，就无法重构数据了。
下面分析RAID 4的性能。对顺序读取，其情况与RAID 0类似，最高性能为单盘顺序读取性能×非校验磁盘个数。但是如果要读取的内容正好都落在同一块磁盘，性能就没有提升。在顺序写入的时候，写入的同时需要修改相应的校验位，但位运算比磁盘的机械动作快得多，而且对校验盘的读写与对非校验盘的读写相对独立，不会拖慢数据读写，所以最高速率也能达到单盘顺序写入性能×非校验磁盘个数。
在随机读取时，其性能也与RAID 0类似：有几块非校验磁盘组成RAID 4，读写性能最高就能达到单块磁盘的几倍。当然，数据不大于块大小的时候，它就只能落在一个磁盘上，读写性能就没有提升了。但在随机写入时，情况就比较棘手了：由于写入数据较小，因此有很多或者全部需要进行写入的条带中，不是所有的位置都会被写入。但写入新数据可能会导致校验位改变，因此在写入某一条带上的块时，需要一并读取同一条带上其它数据块的未修改数据，并重新计算新的校验码。当非校验盘的块数很多时，造成的性能影响也非常大。
有一种方式可以减小这种性能影响。在写入数据块之前，把这一块的旧数据读出来，然后比对各个位要写入的数据是否与这一位的原数据不同。如果是，就意味着校验位要改变。如果不是，这一位校验位保持不变。于是，写入一个块的数据在非校验盘上实际需要的操作就是一次读一次写。更坑爹的是，由于在非校验盘每写入一个块，都要把校验盘对应的位修改一次，因此校验盘会卡住整个写入进程，导致对非校验盘的写入必须等一个块写完并修改相应的校验位后再写入下一个块而不能并发。因此，随机写入的性能等于：单盘随机写入性能÷2。
（这里我觉得有点不对劲。因为这种写入策略非常蠢，实际上应该可以把一个条带上多个块的随机写入操作合并，并发地写入，一次性修改校验位。这里我再去求证一下。RAID 2 / 3 / 4没有RAID 0 / 1 / 5 / 10常用，这里大家先不管它。）

18、为了（至少部分）解决校验式RAID的小数据读写性能大打折扣的问题，RAID 5应运而生。RAID 5的校验数据的分布是这样的：

RAID 5的很多地方和RAID 4很像。RAID 5同样只允许1块盘失效，顺序读写性能和RAID 4是一样的。RAID 5的随机读取性能要好一点，因为在校验数据占有的比例相同的情况下，可以多用一块盘进行读写（校验数据不再由专门的一块不参与读写的磁盘进行存储）。相比RAID 4，RAID 5的随机写入性能的增长令人印象深刻。RAID 5的随机写操作可以并发。其随机写入的速率是：单盘随机写入性能×磁盘块数÷4，除以一个因子4是因为采用奇偶校验的RAID的每个写操作实际上都要进行4个操作：一次是写入数据本身，一次是读写入位置的旧数据，一次是读所属的校验块，一次是写入新的校验块。
（RAID 5的随机写入性能这里也存疑。）

19、还有其它级别的RAID，比如RAID 2、RAID 3和RAID 6等。RAID 6最多允许2块盘损坏。在RAID中的磁盘发生故障时，RAID控制器必须立刻探测到并发出告警。用户接到警报后，需要及时进行重建。有时候，RAID系统会有一个热备盘（hot spare disk）。如果RAID里其中一个盘坏了，这个热备盘就会顶替RAID里的那个坏盘，同时把坏盘上面的数据原样做出来并存储在热备盘中。于是RAID系统允许同时损坏的盘数就多了1块。