4.9 磁盘的结构
磁盘(Disk)是由表面涂有磁性物质的金属或塑料构成的圆形盘片，通过一个称为磁头的导体线圈从磁盘中存取数据。在读/写操作期间，磁头固定，磁盘在下面高速旋转。如图 4-23所示，磁盘的盘面上的数据存储在一组同心圆中，称为磁道。每个磁道与磁头一样宽, 一个盘面有上千个磁道。磁道又划分为几百个扇区，每个扇区固定存储大小（通常为512B), 一个扇区称为一个盘块。相邻磁道及相邻扇区间通过一定的间隙分隔开，以避免精度错误。注意，由于扇区按固定圆心角度划分，所以密度从最外道向里道增加，磁盘的存储能力受限于最内道的最大记录密度。
磁盘安装在一个磁盘驱动器中，它由磁头臂、用于旋转磁盘的主轴和用于数据输入/输 出的电子设备组成。如图4-24所示，多个盘片垂直堆叠，组成磁盘组，每个盘面对应一个 磁头，所有磁头固定在一起，与磁盘中心的距离相同且一起移动。所有盘片上相对位置相同 的磁道组成柱面。按照这种物理结构组织，扇区就是磁盘可寻址的最小存储单位，磁盘地址 用“柱面号 • 盘面号 • 扇区号（或块号）”表示。
磁盘按不同方式可以分为若干类型：磁头相对于盘片的径向方向固定的称为固定头磁盘，每个磁道一个磁头；磁头可移动的称为活动头磁盘，磁头臂可以来回伸缩定位磁道。磁 盘永久固定在磁盘驱动器内的称为固定盘磁盘；可移动和替换的称为可换盘磁盘。
4.10 磁盘调度算法
一次磁盘读写操作的时间由寻找（寻道）时间、延迟时间和传输时间决定：1) 寻找时间Ts：活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。这个时间除跨越n条磁道的时间外，还包括启动磁臂的时间s，即：
式中，m是与磁盘驱动器速度有关的常数，约为0.2ms，磁臂的启动时间约为2ms。2)延迟时间Tr：磁头定位到某一磁道的扇区（块号）所需要的时间，设磁盘的旋转速度为r，则：
对于硬盘，典型的旋转速度为5400r/m，相当于一周11.1ms，则Tr为5.55ms;对于软盘，其旋转速度在300~600r/m之间，则Tr为50~100ms。3) 传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间，这个时间取决于每次所读/写的字节数b和磁盘的旋转速度：
式中，r为磁盘每秒钟的转数；N为一个磁道上的字节数。在磁盘存取时间的计算中，寻道时间与磁盘调度算法相关，下面将会介绍分析几种算法，而延迟时间和传输时间都与磁盘旋转速度相关，且为线性相关，所以在硬件上，转速是磁盘性能的一个非常重要的参数。
总平均存取时间Ta可以表示为：
虽然这里给出了总平均存取时间的公式，但是这个平均值是没有太大实际意义的，因为在实际的磁盘I/O操作中，存取时间与磁盘调度算法密切相关。调度算法直接决定寻找时间，从而决定了总的存取时间。
目前常用的磁盘调度算法有以下几种：
1) 先来先服务(First Come First Served, FCFS)算法
FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法，如图4-25所示。该算法的优点是具有公平性。如果只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则有望达到较好的性能；但如果有大量进程竞争使用磁盘，那么这种算法在性能上往往接近于随机调度。所以，实际磁盘调度中考虑一些更为复杂的调度算法。
图4-25 FCFS磁盘调度算法
例如，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100磁道，釆用FCFS算法磁头的运动过程如图4-25所示。磁头共移动了 (45+3+19+21+72+70+10+112+146)=498 个磁道，平均寻找长度=498/9=55.3。
2) 最短寻找时间优先(Shortest Seek Time First, SSTF)算法
SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比 FCFS算法更好的性能。这种算法会产生“饥饿”现象。如图4-26所示，若某时刻磁头正在 18号磁道，而在18号磁道附近频繁地增加新的请求，那么SSTF算法使得磁头长时间在18 号磁道附近工作，将使184号磁道的访问被无限期地延迟，即被“饿死”。
图4-26 SSTF磁盘调度算法
例如，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100磁道，釆用SSTF算法磁头的运动过程如图4-26所示。磁头共移动了 (10+32+3+16+1+20+132+10+24)=248 个磁道，平均寻找长度=248/9=27.5。
3) 扫描(SCAN)算法（又称电梯算法）
SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，如图4-27所示。由于磁头移动规律与电梯运行相似，故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如FCFS算法和 SSTF算法好。
图4-27 SCAN磁盘调度算法
例如，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100 磁道。釆用SCAN算法时，不但要知道磁头的当前位置，还要知道磁头的移动方向，假设磁头沿磁道号增大的顺序移动，则磁头的运动过程如图4-27所示。磁头共移动了(50+10+24+94+32+3+16+1+20)=250 个磁道，平均寻找长度=250/9=27.8。
4) 循环扫描(Circulair SCAN, C-SCAN)算法
在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型的C-SCAN算法来避免这个问题。釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK和C-LOOK调度。这是因为它们在朝一个给定方向移动前会查看是否有请求。注意，若无特别说明，也可以默认SCAN 算法和C-SCAN算法为LOOK和C-LOOK调度。
图4-28 C-SCAN磁盘调度算法
例如，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100磁道。釆用C-SCAN算法时，假设磁头沿磁道号增大的顺序移动，则磁头的运动过程如图4-28所示。磁头共移动了(50+10+24+166+20+1+16+3+32)=322个磁道，平均寻道长度=322/9=35.8。
对比以上几种磁盘调度算法，FCFS算法太过简单，性能较差，仅在请求队列长度接近于1时才较为理想；SSTF算法较为通用和自然；SCAN算法和C-SCAN算法在磁盘负载较大时比较占优势。它们之间的比较见表4-4。
| 优 点 | 缺 点 | |
|---|---|---|
| FCFS算法 | 公平、简单 | 平均寻道距离大，仅应用在磁盘I/O较少的场合 |
| SSTF算法 | 性能比“先来先服务”好 | 不能保证平均寻道时间最短，可能出现“饥饿”现象 |
| SCAN算法 | 寻道性能较好，可避免“饥饿”现象 | 不利于远离磁头一端的访问请求 |
| C-SCAN算法 | 消除了对两端磁道请求的不公平 | -- |
除减少寻找时间外，减少延迟时间也是提高磁盘传输效率的重要因素。可以对盘面扇区进行交替编号，对磁盘片组中的不同盘面错位命名。假设每个盘面有8个扇区，磁盘片组共 8个盘面，则可以釆用如图4-29所示的编号。
图4-29磁盘片组扇区编号
磁盘是连续自转设备，磁头读/写一个物理块后，需要经过短暂的处理时间才能开始读/ 写下一块。假设逻辑记录数据连续存放在磁盘空间中，若在盘面上按扇区交替编号连续存放，则连续读/写多个记录时能减少磁头的延迟时间；同柱面不同盘面的扇区若能错位编号，连续读/写相邻两个盘面的逻辑记录时也能减少磁头延迟时间。
由于传输时间由磁盘转速决定，所以无法通过其他方法减少传输时间。以图4-29为例，在随机扇区访问情况下，定位磁道中的一个扇区平均需要转过4个扇区，这时，延迟时间是传输时间的4倍，这是一种非常低效的存取方式。理想化的情况是不需要定位而直接连续读取扇区，没有延迟时间，这样磁盘数据存取效率可以成倍提高。但是由于读取扇区的顺序是不可预测的，所以延迟时间不可避免。图4-29中的编号方式是读取连续编号扇区时的一种方法。
4.11 磁盘的管理：磁盘初始化、引导块、坏块
磁盘初始化
一个新的磁盘只是一个含有磁性记录材料的空白盘。在磁盘能存储数据之前，它必须分成扇区以便磁盘控制器能进行读和写操作，这个过程称为低级格式化（物理分区）。低级格式化为磁盘的每个扇区釆用特别的数据结构。每个扇区的数据结构通常由头、数据区域（通常为512B大小）和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息。为了使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上：第一步将磁盘分为由一个或多个柱面组成的分区（即我们熟悉的C盘、D盘等形式的分区）；第二步对物理分区进行逻辑格式化（创建文件系统)，操作系统将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间以及一个初始为空的目录。
引导块
计算机启动时需要运行一个初始化程序（自举程序），它初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。为此，该自举程序应找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的运行。自举程序通常保存在ROM中，为了避免改变自举代码需要改变ROM硬件的问题，故只在ROM中保留很小的自举装入程序，将完整功能的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位。拥有启动分区的磁盘称为启动磁盘或者系统磁盘。
坏块
由于磁盘有移动部件且容错能力弱，所以容易导致一个或多个扇区损坏。部分磁盘甚至从出厂时就有坏扇区。根据所使用的磁盘和控制器，对这些块有多种处理方式。对于简单磁盘，如电子集成驱动器（IDE)。坏扇区可手工处理，如MS-DOS的Format 命令执行逻辑格式化时便会扫描磁盘以检查坏扇区。坏扇区在FAT表上会标明，因此程序不会使用。
对于复杂的磁盘，如小型计算机系统接口（SCSI)，其控制器维护一个磁盘坏块链表。该链表在出厂前进行低级格式化时就初始化了，并在磁盘的整个使用过程中不断更新。低级格式化将一些块保留作为备用，对操作系统透明。控制器可以用备用块来逻辑地替代坏块，这种方案称为扇区备用。
4.12 文件系统知识点总结
磁盘结构
引导控制块(Boot Control Block)包括系统从该分区引导操作系统所需要的信息。如果磁盘没有操作系统，那么这块的内容为空。它通常为分区的第一块。UFS称之为引导块(Boot Block)； NTFS 称之为分区引导扇区(Partition Boot Sector)。分区控制块(Partition Control Block)包括分区详细信息，如分区的块数、块的大小、 空闲块的数量和指计、空闲FCB的数量和指针等。UPS称之为超级块(Superblock)；而NTFS 称之为主控文件表(Master File Table)。
内存结构
内存分区表包含所有安装分区的信息。内存目录结构用来保存近来访问过的目录信息。对安装分区的目录，可以包括一个指向分区表的指针。
系统范围的打开文件表，包括每个打开文件的FCB复制和其他信息。
单个进程的打开文件表，包括一个指向系统范围内已打开文件表中合适条目和其他信息的指针。
文件系统实现概述
为了创建一个文件，应用程序调用逻辑文件系统。逻辑文件系统知道目录结构形式，它将分配一个新的FCB 给文件，把相应目录读入内存，用新的文件名更新该目录和FCB,并将结果写回到磁盘。图4-32显示了一个典型 的 FCB。
图4-32 典型的FCB
一旦文件被创建，它就能用于I/O，不过首先要打开文件。调用open将文件名传给文件系统，文件系统根据给定文件名搜索目录结构。部分目录结构通常缓存在内存中以加快目录操作。找到文件后，其FCB复制到系统范围的打开文件表。该表不但存储FCB，也有打开该文件的进程数量的条目。
然后，单个进程的打开文件表中会增加一个条目，并通过指针将系统范围的打开文件表的条目同其他域（文件当前位置的指针和文件打开模式等）相连。调用open返回的是一个 指向单个进程的打开文件表中合适条目的指针。所以文件操作都是通过该指针进行。
文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不 再使用文件名了。对于访问打开文件表的索引，UNIX称之为文件描述符(File Descriptor)；而Windows 2000称之为文件句柄(File Handle)。因此，只要文件没有被关闭，所有文件操 作通过打开文件表来进行。
当一个进程关闭文件，就删除一个相应的单个进程打开文件表的条目即目录项，系统范 围内打开文件表的打开数也会递减。当打开文件的所有用户都关闭了一个文件时，更新的文 件信息会复制到磁盘的目录结构中，系统范围的打开文件表的条目也将删除。
在实际中，系统调用open会首先搜索系统范围的打开文件表以确定某文件是否已被其 他进程所使用。如果是，就在单个进程的打开文件表中创建一项，并指向现有系统范围的打 开文件表的相应条目。该算法在文件已打开时，能节省大量开销。
混合索引分配的实现
混合索引分配已在UNIX系统中釆用。在UNK SystemV的索引结点中，共设置了 13 个地址项，即iaddr(O)~iaddr(12)，如图4-33所示。在BSD UNIX的索引结点中，共设置了 13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。
图4-33 UNIX系统的inode结构示意图