文件与文件系统
文件的逻辑结构
文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构是从实现观点出发，又称为文件的存储结构，是指文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关，但文件的物理结构与存储介质的特性有很大关系。
按逻辑结构，文件有无结构文件和有结构文件两种类型：无结构文件和有结构文件。
无结构文件（流式文件)
无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累保存，它是有序相关信息项的集合，以字节(Byte)为单位。由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，故这种文件形式对大多数应用不适用。但字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于釆用字符流的无结构方式，如源程序文件、目标代码文件等。
有结构文件（记录式文件）
有结构文件按记录的组织形式可以分为：
1) 顺序文件。
文件中的记录一个接一个地顺序排列，记录可以是定长的或变长的，可以顺序存储或以链表形式存储，在访问时需要顺序搜索文件。顺序文件有以下两种结构：
第一种是串结构，记录之间的顺序与关键字无关。通常的办法是由时间决定，即按存入时间的先后排列，最先存入的记录作为第1个记录，其次存入的为第2个记录，依此类推。
第二种是顺序结构，指文件中的所有记录按关键字顺序排列。
在对记录进行批量操作时，即每次要读或写一大批记录，对顺序文件的效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作，但顺序文件对查找、修改、增加或删除单个记录的操作比较困难。
2) 索引文件。
3) 索引顺序文件。
索引顺序文件是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。
4) 直接文件或散列文件(Hash File)
给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。
文件目录结构
与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的信息，包括属性、 位置和所有权等，这些信息主要是由操作系统进行管理。首先我们来看目录管理的基本要求: 从用户的角度看，目录在用户（应用程序）所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”；目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度；在共享系统中，目录还需要提供用于控制访问文件的信息。此外，文件允许重名也是用户的合理和必然要求，目录管理通过树形结构来解决和实现。
文件控制块和索引结点
同进程管理一样，为实现目录管理，操作系统中引入了文件控制块的数据结构。
1) 文件控制块。
文件控制块(FCB)是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项。
FCB主要包含以下信息：
- 基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
- 存取控制信息，如文件存取权限等。
- 使用信息，如文件建立时间、修改时间等。
2) 索引结点。
在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需调入内存。因此，有的系统（如UNIX，见表4-1）釆用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称为 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。
目录结构
在理解一个文件系统的需求前，我们首先来考虑在目录这个层次上所需要执行的操作，这有助于后面文件系统的整体理解。
- 搜索：当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
- 创建文件：当创建一个新文件时，需要在目录中增加一个目录项。
- 删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
- 显示目录：用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。
- 修改目录：某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。
操作时，考虑以下几种目录结构：
1) 单级目录结构。
在整个文件系统中只建立一张目录表，每个文件占一个目录项.
当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项中。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。
单级目录结构实现了 “按名存取”，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。
2) 两级目录结构
单级目录很容易造成文件名称的混淆，可以考虑釆用两级方案，将文件目录分成主文件目录(Master File Directory, MFD)和用户文件目录（User File Directory, UFD)两级，如图4-4所示。
主文件目录项记录用户名及相应用户文件目录所在的存储位置。用户文件目录项记录该用户文件的FCB信息。当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD，这既解决了不同用户文件的“重名”问题，也在一定程度上保证了文件的安全。
两级目录结构可以解决多用户之间的文件重名问题，文件系统可以在目录上实现访问限制。但是两级目录结构缺乏灵活性，不能对文件分类。
3) 多级目录结构（树形目录结构)
将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构，如图4-5所示。
用户要访问某个文件时用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件的通路上的所有目录名与数据文件名用分隔符链接起来而成。从根目录出发的路径称绝对路径。当层次较多时，每次从根目录查询浪费时间，于是加入了当前目录，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
4) 无环图目录结构。
树形目录结构可便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享，如图4-6所示。
当某用户要求删除一个共享结点时，若系统只是简单地将它删除，当另一共享用户需要访问时，却无法找到这个文件而发生错误。为此可以为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加 1;每当某用户提出删除该结点时，计数器减1。仅当共享计数器为0时，才真正删除该结点，否则仅删除请求用户的共享链。
共享文件：硬链接和软链接
文件共享使多个用户（进程）共享同一份文件，系统中只需保留该文件的一份副本。如果系统不能提供共享功能，那么每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。随着计算机技术的发展，文件共享的范围已由单机系统发展到多机系统，进而通过网络扩展到全球。这些文件的分享是通过分布式文件系统、远程文件系统、分布式信息系统实现的。这些系统允许多个客户通过C/S模型共享网络中的服务器文件。
现代常用的两种文件共享方法有：
基于索引结点的共享方式（硬链接）
在树形结构的目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地找到该文件，如图4-7所示。
在这种共享方式中引用索引结点，即诸如文件的物理地址及其他的文件属性等信息，不再是放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还应有一个链接计数count,用于表示链接到本索引结点（亦即文件） 上的用户目录项的数目。当count=2时，表示有两个用户目录项链接到本文件上，或者说是有两个用户共享此文件。
利用符号链实现文件共享（软链接）
为使用户B能共享用户A的一个文件F,可以由系统创建一个LINK类型的新文件，也取名为F，并将文件F写入用户B的目录中，以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接
上述两种链接方式都存在一个共同的问题，即每个共享文件都有几个文件名。换言之，每增加一条链接，就增加一个文件名。这实质上就是每个用户都使用自己的路径名去访问共享文件。当我们试图去遍历整个文件系统时，将会多次遍历到该共享文件。
硬链接和软链接都是文件系统中的静态共享方法，在文件系统中还存在着另外的共享需求，即两个进程同时对同一个文件进行操作，这样的共享可以称为动态共享。
文件保护：文件访问类型和访问控制
为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。
文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。
访问控制
解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是为每个文件和目录增加一个访问控制列表(Access-Control List, ACL)，以规定每个用户名及其所允许的访问类型。
这种方法的优点是可以使用复杂的访同方法。其缺点是长度无法预期并且可能导致复杂的空间管理，使用精简的访问列表可以解决这个问题。
精简的访问列表釆用拥有者、组和其他三种用户类型。
拥有者：创建文件的用户。
组：一组需要共享文件且具有类似访问的用户。
其他：系统内的所有其他用户。
注意两个问题：
- 现代操作系统常用的文件保护方法，是将访问控制列表与用户、组和其他成员访问控制方案一起组合使用。
- 对于多级目录结构而言，不仅需要保护单个文件，而且还需要保护子目录内的文件, 即需要提供目录保护机制。目录操作与文件操作并不相同，因此需要不同的保护机制。
文件系统层次结构
现代操作系统有多种文件系统类型（如FAT32、NTFS、 ext2、ext3、ext4等），因此文件系统的层次结构也不尽相同。图4-11是一种合理的层次结构。
1) 用户调用接口
文件系统为用户提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件，建立、删除目录等。此层由若干程序模块组成，每一模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块。
2) 文件目录系统
文件目录系统的主要功能是管理文件目录，其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织在存储设备上的文件目录结构、调用下一级存取控制模块。
3) 存取控制验证
实现文件保护主要由该级软件完成，它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访问的合法性。
4) 逻辑文件系统与文件信息缓冲区
逻辑文件系统与文件信息缓冲区的主要功能是根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。
5) 物理文件系统
物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址。
6) 分配模块
分配模块的主要功能是管理辅存空间，即负责分配辅存空闲空间和回收辅存空间。
7) 设备管理程序模块
设备管理程序模块的主要功能是分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。
磁盘的结构
磁盘(Disk)是由表面涂有磁性物质的金属或塑料构成的圆形盘片，通过一个称为磁头 的导体线圈从磁盘中存取数据。在读/写操作期间，磁头固定，磁盘在下面高速旋转。如图 4-23所示，磁盘的盘面上的数据存储在一组同心圆中，称为磁道。每个磁道与磁头一样宽, 一个盘面有上千个磁道。磁道又划分为几百个扇区，每个扇区固定存储大小（通常为512B), 一个扇区称为一个盘块。相邻磁道及相邻扇区间通过一定的间隙分隔开，以避免精度错误。
注意，由于扇区按固定圆心角度划分，所以密度从最外道向里道增加，磁盘的存储能力受限于最内道的最大记录密度。
磁盘安装在一个磁盘驱动器中，它由磁头臂、用于旋转磁盘的主轴和用于数据输入/输 出的电子设备组成。如图4-24所示，多个盘片垂直堆叠，组成磁盘组，每个盘面对应一个 磁头，所有磁头固定在一起，与磁盘中心的距离相同且一起移动。所有盘片上相对位置相同 的磁道组成柱面。按照这种物理结构组织，扇区就是磁盘可寻址的最小存储单位，磁盘地址 用“柱面号 • 盘面号 • 扇区号（或块号）”表示。
磁盘调度算法
一次磁盘读写操作的时间由寻找（寻道）时间、延迟时间和传输时间决定：
目前常用的磁盘调度算法有以下几种：
1) 先来先服务(First Come First Served, FCFS)算法
FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法，如图4-25所示。该算法的优点是具有公平性。如果只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则有望达到较好的性能；但如果有大量进程竞争使用磁盘，那么这种算法在性能上往往接近于随机调度。所以，实际磁盘调度中考虑一些更为复杂的调度算法。
2) 最短寻找时间优先(Shortest Seek Time First, SSTF)算法
SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比 FCFS算法更好的性能。这种算法会产生“饥饿”现象。如图4-26所示，若某时刻磁头正在 18号磁道，而在18号磁道附近频繁地增加新的请求，那么SSTF算法使得磁头长时间在18 号磁道附近工作，将使184号磁道的访问被无限期地延迟，即被“饿死”。
3) 扫描(SCAN)算法（又称电梯算法）
SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，如图4-27所示。由于磁头移动规律与电梯运行相似，故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如FCFS算法和 SSTF算法好。
4) 循环扫描(Circulair SCAN, C-SCAN)算法
在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型的C-SCAN算法来避免这个问题。
磁盘的管理
磁盘初始化
一个新的磁盘只是一个含有磁性记录材料的空白盘。在磁盘能存储数据之前，它必须分成扇区以便磁盘控制器能进行读和写操作，这个过程称为低级格式化（物理分区）。低级格式化为磁盘的每个扇区釆用特别的数据结构。每个扇区的数据结构通常由头、数据区域（通常为512B大小）和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息。
为了使用磁盘存储文件，操作系统还需要将自己的数据结构记录在磁盘上：第一步将磁盘分为由一个或多个柱面组成的分区（即我们熟悉的C盘、D盘等形式的分区）；第二步对物理分区进行逻辑格式化（创建文件系统)，操作系统将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间以及一个初始为空的目录。
引导块
计算机启动时需要运行一个初始化程序（自举程序），它初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。为此，该自举程序应找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的运行。
自举程序通常保存在ROM中，为了避免改变自举代码需要改变ROM硬件的问题，故只在ROM中保留很小的自举装入程序，将完整功能的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位。拥有启动分区的磁盘称为启动磁盘或者系统磁盘。
坏块
由于磁盘有移动部件且容错能力弱，所以容易导致一个或多个扇区损坏。部分磁盘甚至从出厂时就有坏扇区。根据所使用的磁盘和控制器，对这些块有多种处理方式。
对于简单磁盘，如电子集成驱动器（IDE)。坏扇区可手工处理，如MS-DOS的Format 命令执行逻辑格式化时便会扫描磁盘以检查坏扇区。坏扇区在FAT表上会标明，因此程序不会使用。
文件系统知识点总结
磁盘结构
引导控制块(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。
一旦文件被创建，它就能用于I/O，不过首先要打开文件。调用open将文件名传给文件 系统，文件系统根据给定文件名搜索目录结构。部分目录结构通常缓存在内存中以加快目录 操作。找到文件后，其FCB复制到系统范围的打开文件表。该表不但存储FCB，也有打开 该文件的进程数量的条目。
然后，单个进程的打开文件表中会增加一个条目，并通过指针将系统范围的打开文件表 的条目同其他域（文件当前位置的指针和文件打开模式等）相连。调用open返回的是一个 指向单个进程的打开文件表中合适条目的指针。所以文件操作都是通过该指针进行。
文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不 再使用文件名了。对于访问打开文件表的索引，UNIX称之为文件描述符(File Descriptor)；而Windows 2000称之为文件句柄(File Handle)。因此，只要文件没有被关闭，所有文件操 作通过打开文件表来进行。
当一个进程关闭文件，就删除一个相应的单个进程打开文件表的条目即目录项，系统范 围内打开文件表的打开数也会递减。当打开文件的所有用户都关闭了一个文件时，更新的文 件信息会复制到磁盘的目录结构中，系统范围的打开文件表的条目也将删除。
在实际中，系统调用open会首先搜索系统范围的打开文件表以确定某文件是否已被其 他进程所使用。如果是，就在单个进程的打开文件表中创建一项，并指向现有系统范围的打 开文件表的相应条目。该算法在文件已打开时，能节省大量开销。
文件的分配
文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方 法有三种：连续分配、链接分配和索引分配。
- 顺序分配：顺序 分配方法要求每个文件在磁盘上占有一组连续的块。
- 隐式链接分配： 每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何地方，除最后一个盘块外，每一个盘块都有指向下一个盘块的指针，这些指针对用户是透明的。
- 显式链接分配：是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。 该表在整个磁盘仅设置一张，每个表项中存放链接指针，即下一个盘块号。 在该表中，凡是 属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件 地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行 的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的 所有盘块号都放在该表中，故称该表为文件分配表（File Allocation Table, FAT)。MS-DOS 采用的就是这种方式。