磁盘

磁盘的结构

磁盘设备可包括一个或多个物理盘片，每个磁盘片分一个或两个存储面(Surface)。每个盘面对应一个磁头，所有的磁头都是连在同一个磁臂上的，因此所有磁头只能“共进退”，所有盘面中相对位置相同的磁道组成柱面。

每个盘面上有若干个磁道(Track)，磁道之间留有必要的间隙(Gap)。在每条磁道上可存储相同数目的二进制位，磁盘密度即每英寸中所存储的位数，显然是内层磁道的密度较外层磁道的密度高。每条磁道又被从逻辑上划分成若干个扇区(Sectors)，软盘大约为 8 至 32 个扇区，硬盘则可多达数百个。一个扇区称为一个盘块(或数据块)，各扇区之间保留一定的间隙(Gap)。

在磁盘中读/写数据时，需要把“磁头”移动到想要读/写的扇区所在的磁道，磁盘会转起来让目标扇区从磁头下面划过，才能完成对扇区的读/写操作。可用(柱面号，盘面号，扇区号）来定位任意一个“磁盘块”，读取的过程是：

1. 根据“柱面号”移动磁臂，让磁头指向指定柱面；
2. 激活指定盘面对应的磁头；
3. 磁盘旋转的过程中，指定的扇区会从磁头下面划过。

   磁盘的类型

   对于磁盘可以从不同的角度进行分类，最常见的有：将磁盘分成硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头（移动头）磁盘等。

磁盘的管理

磁盘初始化

为了在磁盘上存储数据，必须先将磁盘初始化，初始化的过程如下：

1. 进行低级格式化(物理格式化)：将磁盘的各个磁道划分为扇区，一个扇区通常可分为头、数据区域(如 512B 大小)、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码；
2. 磁盘分区：每个分区由若干柱面组成，在逻辑上每个分区是一个独立的逻辑磁盘；
3. 逻辑格式化：创建文件系统，包括创建文件系统的根目录、初始化存储空间管理所用的数据结构(如位示图、空闲分区表）。

计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序完成的，初始化程序可以放在 ROM(只读存储器）中，开机时计算机先运行“自举装入程序”，通过执行该程序就可找到引导块，并将完整的“自举程序”读入内存完成初始化。

坏块的管理

坏了、无法正常使用的扇区就是坏块，属于硬件故障，操作系统是无法修复的。所以应该将坏块标记出来，以免错误地使用到它。对于简单的磁盘，可以在逻辑格式化时(建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如在 FAT 表上标明。对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件）会维护一个坏块链表，在磁盘出厂前进行低级格式化时就将坏块链进行初始化。保留一些“备用扇区”，用于替换坏块，这种方案称为扇区备用，这种方式坏块对操作系统透明。

磁盘访问时间

磁盘设备在工作时以恒定速率旋转，为了读或写，磁头必须能移动到所指定的磁道上，并等待所指定的扇区的开始位置旋转到磁头下，然后再开始读或写数据。故可把对磁盘的访问时间分成以下三部分：

寻道时间

寻道时间 Ts 指把磁臂(磁头)移动到指定磁道上所经历的时间，该时间是启动磁臂的时间 s 与磁头移动 n 条磁道所花费的时间之和。其中 m 是一常数，与磁盘驱动器的速度有关，对一般磁盘 m = 0.2，对高速磁盘 m ≤ 0.1，磁臂的启动时间约为 2ms。对一般的磁盘，其寻道时间将随寻道距离的增大而增加。

寻道有许多阶段，首先是磁盘臂移动时的加速阶段，然后随着磁盘臂全速移动而惯性滑动，然后随着磁盘臂减速而减速，最后在磁头小心地放置在正确的磁道上时停下来。

旋转延迟时间

旋转延迟时间 Tr 是指定扇区移动到磁头下面所经历的时间，不同的磁盘类型中，旋转速度至少相差一个数量级，如软盘为 300 r/min，硬盘一般为 7200 r/min 到 15000 r/min 甚至更高。

对于磁盘旋转延迟时间而言，如硬盘旋转速度为 15000 r/min，每转需时 4ms，平均旋转延迟时间 Tr = 2ms。而对于软盘，其旋转速度为 300 r/min 或 600 r/min，这样平均 Tr = 50 ~ 100 ms。

传输时间

传输时间 Tt指把数据从磁盘读出或向磁盘写入数据所经历的时间，Tt 的大小与每次所读/写的字节数 b 和旋转速度有关。下面公式中，r 为磁盘每秒钟的转数，N 为一条磁道上的字节数。

当一次读/写的字节数相当于半条磁道上的字节数时，Tt 与 Tr 相同，因此可将访问时间 Ta 表示为如下公式。

由上式可以看出，在访问时间中，寻道时间和旋转延迟时间基本上都与所读/写数据的多少无关，而且它通常占据了访问时间中的大部分。例如假定寻道时间和旋转延迟时间平均为 20 ms，而磁盘的传输速率为 10 MB/s，如果要传输 10 KB，此时总的访问时间为 21 ms。当传输 100 KB 数据时，其访问时间也只是 30ms。可见适当地集中数据(不要太零散)传输，将有利于提高传输效率。

磁盘的时延

磁头读取一个扇区的内容后，需要一小段时间处理，而盘片又在不停地旋转。因此如果要读取的扇区相邻着排列，则读完一个扇区后无法连续不断地读入相邻的扇区，必须等盘片继续旋转使相邻扇区再次划过磁头，才能完扇区读入。可见：如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”。

磁盘调度

为了减少对文件的访问时间，应采用一种最佳的磁盘调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中主要是寻道时间，因此磁盘调度的目标是使磁盘的平均寻道时间最少。

调度样例

某磁盘组共有 200 个柱面，由外至内依次编号为 0，1，…，199。输入输出请求以 10、100、191、31、20、150、32 的次序到达，假定引臂当前位于柱面 98 处，移动方向为由外向内。对先到先服务、最短查找时间优先扫描、扫描算法、循环扫描算法分别给出寻道示意图，并计算总移动量。对扫描算法，假定引臂当前移动方向为由外向内，对循环扫描算法假定回扫方向由内向外。

先来先服务

先来先服务(FCFS)是最简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度。

总移动量
=（98-10）+（100-10）+（191-100）+（191-31）+（31-20）+（150-20）+ (150-32)
= 88 + 90 + 91 + 160 + 9 + 130 + 118
= 686。
此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长，故 FCFS 算法仅适用于请求磁盘 I/O 的进程数目较少的场合。

最短寻道时间优先

最短寻道时间优先(SSTF)算法是基于贪心算法来设计的，要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短。

总移动量
=（100-98）+（150-100）+（191-150）+（191-32）+（32-31）+（31-20）+ (20-10)
= 2 + 50 + 41 + 159 + 1 + 9 + 10
= 272
SSTF 算法平均每次磁头移动的距离明显低于 FCFS 算法的距离，较之 FCFS 有更好的寻道性能。

扫描算法

SSTF 算法会产生饥饿的原因在于，磁头有可能在一个小区域内来回来去地移动。扫描算法(SCAN)可以防止这个问题，可以规定只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。由于磁头移动的方式很像电梯，因此也叫电梯算法。

总移动量
=（100-98）+（150-100）+（191-150）+（199-191）+（199-32）+（32-31）+ (31-20) + (20-10)
=2 + 50 + 41 + 8 + 167 + 1 + 9 + 10
=288
扫描算法的优点是性能较好，平均寻道时间较短，不会产生饥饿现象。缺点是只有到达最边上的磁道时才能改变磁头移动方向，事实上有时并不需要到达最边上的磁道。同时当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时该进程必须等待磁头继续从里向外，然后再从外向里扫描完处于外面的所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。

循环扫描算法

SCAN 算法对于各个位置磁道的响应频率不平均，循环扫描(C-SCAN)算法可以解决这个问题。它规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

总移动量
=（100-98）+（150-100）+（191-150）+（199-191）+（10-0）+（20-10）+ (31-20) + (32-31)
= 2 + 50 + 41 + 8 + 10 + 10 + 9 + 1
= 131
C-SCAN 算法的优点是比起 SCAN，对于各个位置磁道的响应频率很平均。缺点是只有到达最边上的磁道时才能改变磁头移动方向，比起 SCAN 算法来平均寻道时间更长。

NStepSCAN算法

在 SSTF、SCAN 及 CSCAN 几种调度算法中，都可能出现磁臂停留在某处不动的情况。例如有一个或几个进程反复请求对某一磁道的 I/O 操作，从而垄断了整个磁盘设备，这一现象称为磁臂粘着”(Armstickiness)。
NStepSCAN 算法是将磁盘请求队列分成若干个长度为 N 的子队列，磁盘调度将按 FCFS 算法依次处理这些子队列。而每处理一个队列时又是按 SCAN 算法，对一个队列处理完后再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘 I/O 请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当 N 值取得很大时，会使 N 步扫描法的性能接近于 SCAN 算法的性能，当 N = 1时 N 步 SCAN算法便蜕化为 FCFS 算法。

FSCAN 算法

FSCAN 算法是 N 步 SCAN 算法的简化，即 FSCAN 只将磁盘请求队列分成两个子队列，一个是由当前所有请求磁盘 I/O 的进程形成的队列，由磁盘调度按 SCAN 算法进行处理。另一个是在扫描期间，将新出现的所有请求磁盘 I/O 的进程放入等待处理的请求队列，这样所有的新请求都将被推迟到下一次扫描时处理。

提高磁盘 I/O 速度

文件系统的性能可表现在多个方面，其中至关重要的一个方面是对文件的访问速度。提高对文件的访问速度可从三方面着手：

1. 改进文件的目录结构以及检索目录的方法来减少对目录的查找时间；
2. 选取好的文件存储结构，以提高对文件的访问速度；
3. 提高磁盘的 I/O 速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。

目前磁盘的 I/O 速度远低于对内存的访问速度，通常要低上 4~6 个数量级，因此磁盘的 I/O 已成为计算机系统的瓶颈。

磁盘高速缓存

提高磁盘 I/O 的速度其中最主要的技术便是采用磁盘高速缓存(Disk Cache)，是指在内存中为磁盘盘块设置的一个缓冲区，在缓冲区中保存了某些盘块的副本。当出现一个访问磁盘的请求时，由核心先去查看磁盘高速缓冲器，如果请求的盘块内容已在磁盘高速缓存中，便可从磁盘高速缓存中去获取。如果不在，才需要启动磁盘将所需要的盘块内容读入，并把所需盘块内容送给磁盘高速缓存。
在设计磁盘高速缓存时需要考虑的问题有：

1. 如何将磁盘高速缓存中的数据传送给请求进程；
2. 采用什么样的置换策略；
3. 已修改的盘块数据在何时被写回磁盘。

   数据交付方式

   数据交付就是指将磁盘高速缓存中的数据传送给请求者进程，系统可以采取两种方式将数据交付给请求进程。

指针交付方式由于所传送的数据量少，因而节省了数据从磁盘高速缓存存储空间到进程的内存工作区的时间。

置换算法

如同请求调页(段）一样，在将磁盘中的盘块数据读入高速缓存时，同样会出现因高速缓存中已装满盘块数据，而需要将其中某些盘块的数据先换出的问题。较常用的算法仍然是最近最久未使用算法 LRU、最近未使用算法 NRU 、最少使用算法 LFU 等。设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：

周期性写回

在有的系统中便将磁盘高速缓存中的所有盘块数据拉成一条 LRU 链，对于那些会严重影响到数据一致性的盘块数据放在 LRU 链的头部，使它们能被优先写回磁盘。对于那些可能在不久之后便要再次使用的盘块数据，应挂在 LRU 链的尾部，以便在以后需要时便可直接从 LRU 链中找到它们。
根据 LRU 算法，那些经常要被访问的盘块数据可能会一直保留在高速缓存中，长期不会被写回磁盘。因为链中任一元素在被访问之后，又被挂到链尾而不被写回磁盘，只有一直未被访问的元素才有可能移到链首，而被写回磁盘。为了解决这一问题，在 UNIX 系统中专门增设了一个修改(update)程序。该程序周期性地调用一个系统调用 SYNC，其主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。
故障所造成的工作损失不会超过30s的工作量。

提高磁盘 I/O 速度的其它方法

提前读

如果是采用顺序访问方式对文件进行访问，便可以预知下一次要读的盘块。此时可采取预先读方式，即在读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入
缓冲区。

延迟写

延迟写是指缓冲区 A 中的数据本应立即写回磁盘，但该缓冲区中的数据可能会在不久之后再被本进程或其它进程访问，因而并不立即将该缓冲区 A 中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾。随着空闲缓冲区的使用，缓冲区也缓缓往前移动，直至移到空闲缓冲队列之首。

优化物理块的分布

在采用链接组织和索引组织方式时，可以将一个文件分散在磁盘的任意位置，但如果安排得过于分散，会增加磁头的移动距离。对文件盘块位置的优化，应在为文件分配盘块时进行。系统中的空白存储空间是采用位示图方式表示时，只要从位示图中找到一片相邻接的多个空闲盘块即可。当系统采用线性表(链）法来组织空闲存储空间时，要可以将在同一条磁道上的若干个盘块组成一簇，在分配存储空间时，以簇为单位进行分配。

虚拟盘

由于访问内存的速度远高于访问磁盘的速度，于是有人试图利用内存空间去仿真磁盘形成所谓虚拟盘。该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行不是在磁盘上而是在内存中。这对用户都是透明的。虚拟盘的主要问题是它是易失性存储器，故一旦系统或电源发生故障或系统再启动时，原来保存在虚拟盘中的数据将会丢失，因此虚拟盘通常用于存放临时文件。

廉价磁盘冗余阵列(RAID)

如果使用一个组件对性能的改进受到了很大的限制，那么可通过使用多个相同的组件来获得性能的大幅度提高。可以由多个小磁盘组成一个大容量的廉价磁盘冗余阵列(Redundant Array of Inexpensive Disk，RAID)，系统利用一台磁盘阵列控制器来统一管理和控制一组(几台到几十台）磁盘驱动器，组成一个大型磁盘系统。RAID 不仅是大幅度地增加了磁盘的容量，而且也极大地提高了磁盘的 I/O 速度和整个磁盘系统的可靠性。