磁盘

1. 磁盘调度算法

读写一个磁盘的时间需要三个因素决定：

对大多数磁盘而言，寻道时间占主导地位，所以减少平均寻道时间可以充分地改善系统性能够。

先来先服务算法(FCFS)

即按照接受请求的顺序完成请求。
最短寻道优先算法(SSF)

下一次总是处理与当前磁头距离最近的请求以使寻道时间最小化。但当正在处理请求时，可能不断有其他请求到达，如果磁盘负载很重，可能到时磁盘臂大部分时间停留在磁盘中部区域，而两端区域将一直等待，出现饥饿现象。
电梯调度算法

需要保存一个二进制位来记录当前移动方向，当一个请求处理完成后，磁盘检查该位，并处理当前移动方向上的另一个请求，如果该方向上没有请求，则方向取反，并移向最近位置。该算法的优良特性是，任意的一组给定请求，磁盘臂移动总次数的上界是固定的，即为柱面数两倍。

在磁盘制造时会有瑕疵，而这些瑕疵可能会引入坏扇区，也就是说，扇区不能正确地读回刚刚写到其上的值。

在控制器中进行处理

磁盘在从工厂出厂前要进行测试，并将一个坏扇区列表写在磁盘上，对于每一个坏扇区，将用一个备用扇区替换它。用两种方法可用来替换。
- 将备用扇区之一重映射为坏扇区(该方式在重写前导码时很简便)。
- 将所有扇区向上移动一个扇区(该方式会提供更好的性能，因为磁道可以再旋转一周中读出)。
驱动器安装后在正常工作期间可能出现错误。如果控制器发现在某个扇区遇到重复性错误(一次错误可能是因为有灰尘等导致的)，可以再该扇区完全坏掉前切换到一个备用扇区，一般采用重映射的方法，因为移动扇区需要复制所有数据。
在操作系统中进行处理

如果控制器不具有重映射扇区的能力，就需要操作系统处理重映射，那么必须确保坏扇区不出现在任何文件中，并且不出现在空闲列表或位图中。可以创建一个包含所有坏扇区的秘密文件，并且不被加入文件系统，这样用户就不会意外读到。

磁盘有时会出现错误，好扇区可能变成坏扇区，整个驱动器也可能死掉。为了对写操作期间崩溃提供保护，一个磁盘应该做到：当一个写命令发给它时，磁盘要么正确写数据，要么什么也不做，让现有数据完整留下。这样的系统就被称为稳定存储器。

稳定存储器使用一对完全相同的磁盘，对应的块一同工作以形成一个无差错的块。当不存在错误时，两个驱动器上对应块是相同的，并定义了以下三种操作：

稳定写

稳定写首先将块写到驱动器1上，然后将其读回以校验写正确。如果写的不正确，那么就再次写并重读，一直到n次或正常为止。经过n次失败后，就将该块重映射到一个备用块上，并且重复写和读直到成功为止，无论尝试多少备用块。在对驱动器1写成功后，对驱动器2上的对应块进行写和重读，重复操作直到成功为止。如果不存在CPU崩溃，那么当稳定写之后，块被正确写到两个驱动器，并在两个驱动器上得到校验。
稳定读

稳定读首先从驱动器1读取块。如果这一操作产生错误ECC(包含冗余信息，可以恢复读错误)，则再次尝试读操作，一直到n次，如果这些操作都给出了错误的ECC，则从驱动器2上读取相应数据块(这里存在假设，在一定合理时间间隔内，相同块在两个驱动器上自发变坏的可能性忽略不计)。
崩溃恢复

崩溃之后，回复程序扫描两个磁盘，比较对应块。如果一对块都是好的并且相同，就什么也不做。如果一个ECC错误，那么坏块则用好块覆盖。如果一对块都是好的但是内容不同，那么将驱动器1的块写到驱动器2上。

以上方法可行是基于CPU不会崩溃的情况，因为稳定写总能写下两个有效副本。但如果稳定写期间出现CPU崩溃，则根据崩溃发生的精确时间，有5种可能，如图所示。

[操作系统] 磁盘

在a中，CPU崩溃发生在写块的两个副本前。恢复时，不需要修改而旧的值将继续存在。

在b中，CPU崩溃发生在写驱动器1期间，破坏了该块内容。但恢复程序能检测出这一错误，并将驱动器2写到驱动器1，以消除崩溃影响，并且恢复旧状态。

在c中，CPU崩溃发生在写两个驱动器之间。此时恢复程序将驱动器1复制到驱动器2，写成功。

在d中，CPU崩溃发生在写驱动器2期间，破坏了该块内容。类似于b，恢复程序同样能检测出错误，并消除影响，不同的是，两个块都将有新值。

在e中，恢复程序不需要修改，无影响。

在很多计算机中，使用非易失性RAM记录要写的块。如果无法使用非易失性RAM，可用以下方法模拟。在稳定写开始时，用将要被稳定写的块的编号覆盖驱动器1上的一个固定块，然后读回该块并校验，该块正确后，对驱动器2上对应块进行写与读校验。当稳定写完成后，用一个无效块编号覆盖这两个固定块，并校验。

参考书目：现代操作系统第三版