Chapter4 - 磁盘管理

0x00 概述

磁盘存储器不仅容量大，存取速度快，且可以实现随机存取，是实现虚拟存储系统所必需的硬件。

磁盘存储管理的主要任务是：

为文件分配必要的存储空间
提高磁盘存储空间的利用率
提高对磁盘的I/O速度，以改善文件系统的性能
采取必要的冗余措施，确保文件系统的可靠性

0x01 磁盘工作原理

1. 磁盘结构

在磁盘设备中，可包含一个或多个盘片，每片分两面。
每个面上都有一个磁头，且每面又可分成若干条磁道。
在每条磁道上可存储相同数目的二进制位，每英寸中所存储的位数称为磁盘密度。
- 显然，内层磁道的密度较外层磁道的密度高
每条磁道又分成若干个扇区，每个扇区的大小相当于一个盘块
- 0扇区是最外层煮面的第一个磁道的第一个扇区
磁盘的顺序首先是磁道不同的扇区，然后是同一柱面的不同磁道，最后是由外向内的不同柱面。
- 即磁盘大小：柱面数 x 一个柱面上的磁道数（盘片*2） x 每条磁道上的扇区数 x 每个扇区的大小

补充：

对于磁盘，每个磁道的扇区数并不是常量。
绝大多数磁盘都有一些缺陷扇区，因此映射必须用磁盘上的其他空闲扇区来替代这些缺陷扇区。

2. 磁盘缺陷

硬盘的实际扇区数比硬盘标签上标定的大，其中

一部分用于存储硬盘的固件。
一部分是用户存储数据的区域，即工作区，也就是硬盘标定容量的扇区。
剩下的为保留区。

几个概念：

P表，又称永久缺陷列表
- 用于记录硬盘生产过程中产生的缺陷。
- 读到该扇区将直接跳过。
G表：又称为增长缺陷列表
- 用于记录硬盘使用过程中由于磁介质性能变弱而引起的缺陷
- 读到坏扇区将转读原保留区。

3. 磁盘的组织

1）主引导扇区(MBR)

硬盘的0柱面，0磁头，1扇区成为主引导扇区（也称主引导记录MBR），该记录占用512个字节，用于硬盘启动时将系统控制权转给用户指定的、在分区表中登记了某个操作系统分区。

MBR包含三部分内容

0~446字节为启动代码及数据；
447-510字节（64个字节）则是分区表（DPT）
- 分区表由四个分区项组成，每个分区项16字节，记录了启动时需要的分区参数。
最后两个字节AA和55被成为幻数（Magic Number）
- BIOS读取MBR时会检查是否有这两个幻术，若无则认为该硬盘未分区。

硬盘分区有三种：主磁盘分区、扩展磁盘分区、逻辑分区。

由于MBR的限制，最多只能有4个分区。

一个硬盘主分区至少有1个，最多4个；
- 主分区只能有一个是激活的（active），其余为inactive，且操作系统必须装载主分区上面。
分出主分区后，其余的部分可以分成扩展分区，扩展分区可以没有，但最多1个；
- 扩展分区不能直接使用，必须分成若干逻辑分区。
主分区+扩展分区总共不能超过4个，所有的逻辑分区都是扩展分区的一部分。

2）硬盘分区表(DPT)

从偏移01BEH开始到偏移01FDH结束的64字节，包含四个分区，每个分区16字节，其内容与含义如下：

第0个字节是自举标志，其值为80H时表示该分区是当前活动分区
第4个字节是分区类型

3）分区引导扇区(DBR)

DBR是由硬盘的MBR装载的程序段。
DBR装入内存后，即开始执行该引导程序段，其主要功能是完成操作系统的自举并将控制权交给操作系统。
每个分区都有引导扇区，但只有被设为活动分区的DBR才会被MBR装入内存运行。

4）磁盘地址与块号的转换

磁盘地址（CHS）：Cylinder, Head, Sector
块号：又称逻辑块号（LBA）, Logic Block Address，逻辑块是最小的传输单位**。

4. 磁盘访问时间

磁盘的访问时间，包括以下三部分。

寻道时间 Ts
- 把磁头从当前位置移动到指定磁道上所经历的时间，*Ts = m * n + s*
- 即，启动磁盘的时间s与磁头移动n条磁道所花费的时间之和
- 其中m是一常量，与磁盘驱动器的速度有关。
  - 对于一般磁盘，m = 0.3
  - 对于高速磁盘，m <= 0.1
旋转延迟时间 Tr
- 把磁头从当前磁道移动到指定扇区下所经历的时间，Tr = 1/(2r)
- 对于硬盘，典型的旋转速度为 3600r/min，每转需16.7ms，平均旋转延迟时间Tr为8.3ms。
- 对于软盘，旋转速度为300或600r/min，平均旋转延迟时间Tr为50~100ms。
传输时间 Tt
- Tt是指把数据从磁盘读出，或向磁盘写入数据所经历的时间，Tt = b / (rN)
- Tt的大小与每次所读/写的字节数b，旋转速度r以及磁道上的字节数N有关
- 典型的N值为一个扇区：512Byte，旋转速度为3600RPM ~ 15000RPM，故硬盘1s可传输的数据为2MB ~ 50MB

访问时间

寻道时间 + 旋转延迟时间 + 传输时间，即 Ta = Ts + 1/(2r) + b/(rN) 。

0x02 磁盘调度（重点）

1. 磁盘调度算法

1）先来先服务算法（FCFS）

按访问请求到达的先后次序服务。

2）最短寻道时间优先算法（SSTF，Shortest Seek Time First）

优先选择距当前磁头最近的访问请求进行服务。

3）扫描算法（SCAN）

当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务。

克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向
由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型的C-SCAN算法可避免这个问题。

4）循环扫描算法（CSCAN）

当磁头到达最后一个柱面后，快速返回0号柱面；返回时不为任何的等待访问者服务，返回后再次进行扫描。

5）LOOK 和 C-LOOK

SCAN与C-SCAN磁头总是严格地遵循从盘面的一端到另一端，显然，磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。这种形式的SCAN与C-SCAN算法称为LOOK 和 C-LOOK调度。

2. 算法比较

0x03 磁盘空间管理

1）位图法

用一串二进制位反应磁盘空间中分配使用情况，每个物理块对应一位，分配的物理块为0，否则为1。

2）空闲表法

将所有空闲块记录在一个表中，即空闲表；

主要记录两项内容：起始块号，块数

3）空闲链表法

把所有空闲块链成一个表，但链会很长。

4）成组链接法

把空白物理块分成组，在通过指针把组与组之间链接起来。

成组链接法的优点：

空白块号登记不占用额外空间；
节省时间；
采用后进先出的栈结构思想

0x04 廉价冗余磁盘阵列（RAID）

考虑可靠性，具有N个磁盘的磁盘组中某些磁盘比特定磁盘具有较高的出错率。假设单个磁盘的平均损坏时间为100000小时，具有100个磁盘的阵列中某些磁盘的平均损坏时间为100000/100小时，大约是41.66天。这样高的数据丢失率是不能接受的。

解决可靠性问题的方法是引入冗余技术存储一般不需要的额外的信息，可以在磁盘损坏时用来恢复丢失的信息。

廉价冗余磁盘阵列（Redundant Arrays of Inexpensive Disks, RAID）

其基本思想就是把多个相对便宜的硬盘组合起来，成为一个硬盘阵列组，使性能达到甚至超过一个价格昂贵、容量巨大的硬盘。
根据选择的版本不同，RAID比单颗硬盘有以下一个或多个方面的好处：
- 增强数据集成度，增强容错功能，增加处理量或容量。
- 另外，磁盘阵列对于电脑来说，看起来就像一个单独的硬盘或逻辑存储单元

磁盘阵列中针对不同的应用使用不同的技术，称为 RAID level。每一 level 代表一种技术，不同 level 并不代表技术的高低。

RAID0：无差错控制的带区组

条带化（Stripe）存储，RAID0需要两个以上的磁盘来组成带区组，数据分为数据块保存在不同的驱动器上。

由于数据分布在不同驱动器上，所以数据吞吐率大大提高，驱动器的负载也比较平衡。

理论上说，有N个磁盘组成的RAID0是单个磁盘读写速度的N倍。

RAID0不计算校验码，因而没有冗余校验功能，也没有数据差错控制，因此它并不能算是真正的RAID结构。

RAID1：镜像结构

它是镜象（Mirror）磁盘冗余阵列，将每一数据块重复存入镜像磁盘，以改善磁盘机的可靠性。

镜像盘也称为拷贝盘，相当于一个不断进行备份操作的磁盘。

优势：
- 当原始数据繁忙时，可直接从镜像拷贝中读取数据，因此RAID 1可以提高读取性能。
- 当一个磁盘失效时，系统可以自动切换到镜像磁盘上读写，而不需要重组失效的数据，提供了很高的数据安全性和可用性。
缺点：
- RAID 1的硬盘容量利用率只有50%，是所有RAID级别中最低的，因而单位成本也最高。

RAID2：带海明码校验

RAID 2是采用海明码（Hamming Code）纠错冗余的磁盘阵列，将数据位交叉写入几个磁盘中，并利用几个磁盘驱动器进行按位的出错检查，冗余度比RAID1小。

特点：
- 并行存取，各个驱动器同步工作。
- 使用海明编码来进行错误检测和纠正，数据传输率高。
- 需要多个磁盘来存放海明校验码信息，冗余磁盘数量与数据磁盘数量的对数成正比。
- 这种阵列的数据读写操作涉及阵列中的每一个磁盘，影响小文件的传输率，因此它适合大量顺序数据访问。
- 是一种在多磁盘易出错环境中的有效选择，并未被广泛应用，目前还没有商业化产品

RAID3：带奇偶校验的并行传送

RAID 3采用奇偶校验冗余的磁盘阵列，阵列中只有一个共享校验盘，将数据按位交叉写到几个磁盘上，用一个校验盘检查数据错误，数据条带存储单位为字节。

基本思想：
- 将磁盘分组，读写要访问组中所有盘，每组中有一个盘作为校验盘。
- 简单理解：先将分布在各个数据盘上的一组数据加起来，将和存放在冗余盘上。一旦某一个盘出错，只要将冗余盘上的和减去所有正确盘上的数据，得到的差就是出错的盘上的数据。

特点
- 它同RAID 2非常类似，都是将数据条块化分布于不同的硬盘上，区别在于RAID 3使用简单的奇偶校验，并用单块磁盘存放奇偶校验信息。
- RAID 3对于大量的连续数据可提供很好的传输率，但对于随机数据来说，奇偶盘会成为写操作的瓶颈。

RAID4：带奇偶校验码的独立磁盘结构

RAID 4也是用一个校验盘，但和RAID 3不一样。RAID 4是以扇区作为数据分段，各磁盘相同位置的分段形成一个校验磁盘分段，放在校验盘。

特点：
- 冗余代价与RAID3相同
- 访问数据的方法与RAID3不同
- 在RAID3中，一次磁盘访问将对磁盘阵列中的所有磁盘进行操作。
- RAID4出现的原因：希望使用较少的磁盘参与操作，以使磁盘阵列可以并行进行多个数据的磁盘操作

RAID5：分布式奇偶校验的独立磁盘结构

RAID 5 避免了 RAID 4 的瓶颈，校验数据分布式存储，数据条带存储单位为块。

RAID 5不单独指定的奇偶盘，而是在所有磁盘上交叉地存取数据及奇偶校验信息。在RAID 5上，读/写指针可同时对阵列设备进行操作，提供了更高的数据流量。

特点
- RAID 5更适合于小数据块和随机读写的数据。
- RAID 3与RAID 5相比，最主要的区别在于RAID 3每进行一次数据传输就需涉及到所有的阵列盘；而对于RAID 5来说，大部分数据传输只对一块磁盘操作，并可进行并行操作。
- 在RAID 5中有“写损失”，即每一次写操作将产生四个实际的读/写操作，其中两次读旧的数据及奇偶信息，两次写新的数据及奇偶信息。
- 当进行恢复时，如我们需要恢复图中的A0，这里就必须需要B0、C0、D0加0 parity才能计算并得出A0，进行数据恢复。所以当有两块盘坏掉的时候，整个RAID的数据失效。