文件管理

文件和文件系统

文件系统的管理功能，是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。而文件则是指具有文件名的若干相关元素的集合。元素通常是记录，而记录又是一组有意义的数据项的集合。基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。

文件、记录和数据项

数据项

数据项是在文件系统中最低级的数据组织形式，可分为:

• 基本数据项：用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。基本数据项除了数据名外，还应有数据类型。根据属性的不同，需要用不同的数据类型来描述。由数据项的名字和类型两者共同定义了一个数据项的“型”。而表征一个实体在数据项上的数据则称为“值”，例如，学号/30211、姓名/王有年、性别/男等。

• 组合数据项：是由若干个基本数据项组成的，简称组项。工资是个组项，它可由基本工资、工龄工资和奖励工资等基本项所组成。

记录

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。

例如，一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，但若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项。

在诸多记录中，为了能惟一地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字(key)，关键字是惟一能标识一个记录的数据项。有时可把几个数据项定为能惟一地标识出某个记录的关键字。

文件

文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例如，可以将一个班的学生记录作为一个文件。一个文件必须要有一个文件名，长度因系统不同而异。如在有的系统中把名字规定为 8 个字符，而在有的系统中又规定可用 14 个字符。用户利用文件名来访问文件。此外，文件应具有自己的属性，属性可以包括：

• 文件类型。可以从不同的角度来规定，如源文件、目标文件及可执行文件等。
• 文件长度。单位可以是字节、字或块，也可能是最大允许的长度。
• 文件的物理位置：用于指示文件在哪一个设备上及设备的哪个位置的指针。
• 文件的建立时间、最后修改时间等。

文件名和文件类型

文件名和扩展名

文件名

• 在一些老的系统中，名字的长度受到限制。例如 MS-DOS 最多允许8个字符老版的Unix系统支持14个字符；一些特殊字符也规定不能用于文件名如空格，因其常被作为分隔命令、参数和其他数据项的分符。

  近年的推出的不少 OS 已放宽了这种限制，如windows NT 以及其后的windows 2000/xp。Vista/7/8等所采用的NTFS文件系统便可以很好地支持长文件名。

• 早期OS如MS-DOS和windows95是不区分大小写字母的。但在Unix和Linux系统中是区分大小写的

扩展名

扩展名又称为后缀名，用于指示文件的类型，它可以方便系统和用户了解文件的类型，在大多数系统中用圆点将文件名和扩展名分开，扩展名的长度一般是1~4个字符。

文件类型

文件系统

文件系统模型可分为三个层次：

• 最底层是对象及其属性，文件管理系统管理的对象有：
  • 文件：文件管理的直接对象。
  • 目录。为了方便对文件的存取和检索，文件系统中须配置目录，每个目录项中，必须含有文件名及该文件所在的物理地址(或指针)。对目录的组织和管理是方便用户和提高对文件存取速度的关键。
  • 磁盘(磁带)存储空间。对存储空间的有效管理，能提高外存的利用率和对文件的存取速度。
• 中间层是对对象进行操纵和管理的软件集合：文件管理系统的核心部分，包括: 对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、对文件读和写的管理，以及对文件的共享与保护等功能。
• 最高层是文件系统提供给用户的接口：
  • 命令接口：作为用户与文件系统交互的接口。 用户可通过键盘终端键入命令，取得文件系统的服务。
  • 程序接口：作为用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。

文件操作

用户通过文件系统所提供的系统调用实施对文件的操作。

最基本的文件操作

1. 创建文件：系统先为新文件分配外存空间，并在文件系统的目录中，建立目录项。目录项中记录新文件的文件名及其在外存的地址等属性。
2. 删除文件：系统应先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
3. 读文件：相应系统调用中需给出文件名和应读入的内存目标地址。此时，系统要查找目录，找到指定的目录项，从中得到被读文件在外存中的位置。在目录项中，还有一个指针用于对文件的读/写。
4. 写文件。相应系统调用中需给出该文件名及该文件在内存中的(源)地址。先查找目录，找到指定文件的目录项，再利用目录中的写指针进行写操作。
5. 截断文件。如果一个文件的内容已经陈旧而需要全部更新时，可以选择将此文件删除，再重新创建。但如果文件名及其属性均无改变时，则可采取截断文件的方法，将原有文件的长度设置为 0。
6. 设置文件的读/写位置。对文件顺序存取的手段是从文件的始端读或写。设置文件读/写位置的操作，用于改顺序存取为随机存取。

文件的“打开”和“关闭”操作

当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录开始。为了避免多次重复地检索目录， OS 引入了“打开”(open)这一文件系统调用，这样节省了大量的检索开销，也显著地提高了对文件的操作速度：

1. 当用户第一次请求对某文件进行操作时，先利用 open 系统调用将该文件打开：将指名文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。
2. 以后再对该文件进行相应的操作时，便可利用索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找。
3. 如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS 将会把该文件从打开文件表中的表目上删除掉。

其它文件操作

• 有关对文件属性进行操作的，即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权，以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；
• 有关目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；
• 用于实现文件共享的系统调用
• 用于对文件系统进行操作的系统调用等。

有许多文件操作都可以利用上述基本操作加以组合来实现。例如，创建一个文件拷贝的操作，其第一步是利用创建文件的系统调用来创建一个新文件；第二步是将原有文件中的内容写入新文件中。

文件的逻辑结构

文件系统设计的关键要素，是指将记录构成一个文件的方法，以及将一个文件存储到外存上的方法。对应着文件的逻辑结构和物理结构，它们两者都会影响对文件的检索速度。

• 文件的逻辑结构：从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。
• 文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。

对文件逻辑结构所提出的基本要求，首先是能提高检索速度，即在将大批记录组成文件时，应有利于提高检索记录的速度和效率；其次是便于修改，即便于在文件中增加、删除和修改一个或多个记录；第三是降低文件的存储费用，即减少文件占用的存储空间，不要求大片的连续存储空间。

无结构文件

无结构文件又称为流式文件，指由字符流构成的文件，大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读/写指针来指出下一个要访问的字符。可以把流式文件 看做是记录式文件的一个特例：一个记录仅有一个字节。

在 UNIX 系统中，所有的文件都被看做是流式文件，即使是有结构文件，也被视为流式文件，系统不对文件进行格式处理。

有结构文件

有结构文件又称为记录式文件，是指由一个以上的记录构成的文件，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。大量的数据结构和数据库是采用有结构的文件形式。

记录的长度可分两类：

• 定长记录：文件中所有记录的长度都是相同的，各数据项都处在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录的处理方便、开销小，这种记录格式被广泛用于数据处理中。
• 变长记录：文件中各记录的长度不相同（可能是由于一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等，或数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。）

不论是哪一种，在处理前，每个记录的长度是可知的。根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件：

• 顺序文件：由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。
• 索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。
• 索引顺序文件：为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。

顺序文件

逻辑记录的排序

文件中的记录可以按照各种不同的顺序进行排列。一般地，可归纳为两种：

• 串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列。
• 顺序结构，指文件中的所有记录按关键字排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。

对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必须从头开始，逐个记录地查找，直至找到指定的记录。而对顺序结构文件，则可利用某种有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法来提高检索效率。

读/写操作

• 对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。在读一个文件时，可设置一个读指针 Rptr，令它指向下一个记录的首地址，每当读完一个记录时，便执行 Rptr:=Rptr + L 操作，使之指向下一个记录的首地址，其中的 L 为记录长度。写文件时类似。
• 对于变长记录的顺序文件，在顺序读或写时的情况相似，但在每次读或写完一个记录后，须将读或写指针加上刚读或刚写完的记录的长度 L_i。

优缺点

• 👍 在对诸记录进行批量存取时，存取效率最高的；
• 👍只有顺序文件才能存储在磁带上有效地工作。

• 👎交互应用中，查找或修改单个记录时，需要逐个查找诸记录。性能就可能很差，对于可变长文件查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。
• 👎增删记录比较困难。为了解决这一问题， 可以为顺序文件配置一个运行记录文件(Log File)，或称为事务文件，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。

索引文件

顺序文件中，变长记录文件查找一个记录，必须从第一个记录查起，一直顺序查找到目标记录为止，无法实现直接存取。 由于索引文件可有较快的检索速度，故它主要用于对信息处理的及时性要求较高的场合。

索引文件为变长记录文件建立一张索引表，分别为主文件中的每个记录在索引表中设一个表项，用于记录该记录的长度 及指向该记录的指针。索引表是关键字排序的，因此本身是一个定长记录的顺序文件，这样就把对变长记录顺序文件的顺序检索转变为对定长记录索引文件的随机检索，加快检索速度，实现直接存取。

检索时，可根据用户提供的关键字，并利用折半查找法去检索索引表，从中找到相应的表项；再利用该表项中的指向记录的指针值，去访问所需的记录。而每当要向索引文件中增加一个新记录时，便须对索引表进行修改。

具有多个索引表的索引文件

可以为顺序文件建立多个索引表，为每一种可能成为检查条件的域，都配置一张索引表，每个索引表中按照相应的属性或者关键词进行排序，比如图书文件中第一个索引表所用的关键字是图书编号，第二个是书名，第三个是作者姓名。第四个是出版时间等，这样用户可以根据自己的需要用不同的关键字来进行检索。

优缺点

• 👍 将需要顺序查找的文件改造成可随机查找的文件。提高了文件的查找速度。
• 👍 插入和删除记录也非常方便。
• 👎 每个记录都在索引表中有一个索引项，提高了存储开销。

索引顺序文件

最常见的一种逻辑文件形式，有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。

索引顺序文件(Index Sequential File) 将顺序文件中的所有记录分为若干个组；在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。检索时，首先也是利用关键字以及某种查找算法去检索索引表，找到该记录所在组中第一个记录的表项，从中得到其在主文件中的位置；然后，再利用顺序查找法去查找主文件，从中找到所要求的记录。如果在顺序文件中为检索到具有指定关键字的记录，平均须查找 N/2 个记录；则对于索引顺序文件，平均只要查找 $\sqrt{N}$ 个记录数。

例如，有一个顺序文件含有 10 000 个记录，平均须查找的记录数为 5000 个。但对于索引顺序文件，则平均只 须查找 100 个记录。可见，它的检索效率是顺序文件的 50 倍。

但对于大文件，为找到一个记录而须查找的记录数目仍然很多，例如，对于一个含有 10⁶个记录的顺序文件，当把它作为索引顺序文件时，为找到一个记录，平均须查找 1000 个记录。为了进一步提高检索效率，可以为顺序文件建立多级索引，即为索引文件再建立一张索引表，例如：

• 低级索引表，每 100 个记录为一组，含有 10⁴个表项。每个表项中存放顺序文件中每个组第一个记录的记录键值和指向该记录的指针
• 高级索引表。每 100 个索引表项为一组，故具有 10²个表项。每个表项中存放的是低级索引表每组第一个表项中的关键字和指向该表项的指针。 此时，为找到一个具有指定关键字的记录，所须查找的记录数平均为 50+50+50=150，或者可表示为(3/2) $\sqrt[3]{N}$ 。

注意，在未建立索引文件时所需查找的记录数平均为 50 万个；对于建立了一级索引的顺序索引文件，平均需查找 1000次；建立两级索引的顺序索引文件，平均只需查找 150 次。

文件的物理结构

物理结构直接与外存分配方式有关。在采用不同的分配方式时，将形成不同的文件物理结构。通常在一个系统中，仅采用一种方法来为文件分配外存空间。

磁盘具有可直接访问的特性，利用其来存放文件时，具有很大的灵活性。在为文件分配外存空间时所要考虑的主要问题是：怎样有效地利用外存空间和如何提高对文件的访问速度。

连续分配

连续分配方式(Continuous Allocation)：把逻辑文件中的记录顺序地存储到邻接的各物理盘块中。为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址（通常都位于一条磁道上，在进行读/写时不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道）。目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。

如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，磁盘空间将被分割成许多小块，形成外存的碎片。可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。

例如，可以运行一个再装配例程(repack routine)，由它将磁盘 A 上的大量文件拷贝到一张软盘 B 或几张软盘(C，D，…)上，并释放原来的 A 盘，使之成为一个空闲盘。然后再将软盘 B(C，D，…)上的文件拷回 A 盘上。但将空闲空间进行一次紧凑的时间远比将内存紧凑时间多得多。

优缺点

• 👍 顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到文件所在的第一个盘块号，从此开始逐个盘块地往下读/写。也支持直接存取。
• 👍访问速度快。文件占用的盘块可能是位于一条或几条相邻的磁道上，磁头的移动距离最少，因此这种方式对文件访问的速度最高。

• 👎要求有连续的存储空间，导致产生外部碎片，降低了外存空间的利用率。若定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。
• 👎必须事先知道文件的长度。事先在存储空间中找出一块大小足够的存储区将文件装入。文件大小有时只能靠估算，用户往往将文件长度估得比实际的大（否则写文件容易因存储空间不足而中止），这会严重地浪费外存空间。对于动态增长的文件，即使事先知道文件的最终大小，预分配存储空间，也将使大量存储空间长期空闲。

链接分配 (Chained Allocation)

通过在每个盘块上的链接指针，将一个文件的多个离散的盘块链接成一个链表。链接分配采取离散分配方式，消除了外部碎片，显著提高了外存空间的利用率；当文件动态增长时，可动态地再为它分配盘块，故而无需事先知道文件的大小。此外，对文件的增、删、改也十分方便。

链接方式又可分为隐式链接和显式链接两种形式。

隐式链接

每个目录项中含有指向链接文件第一个盘块和最后一个盘块的指针。每个盘块中都含有一个指向下一个盘块的指针。如果指针占用 4 个字节，对于盘块大小为 512 字节的磁盘，则每个盘块中只有 508 个字节可供用户使用。

• 👎只适合于顺序访问，对随机访问是极其低效的。如果要访问文件所在的第 i 个盘块，则必须先读出文件的第一个再顺序地查找直至第 i 块。须多次启动磁盘去实现读盘块的操作，
• 👎只通过链接指针将离散的盘块链接起来，可靠性较差，任何一个指针出现问题都会导致整个链的断开。

为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。比如，一个簇可包含 4 个盘块，在进行盘块分配时，是以簇为单位进行的。但这样会增大内部碎片，而且这种改进非常有限。

显式链接

把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中，即文件分配表 FAT(File Allocation Table)。该表在整个磁盘仅设置一张。表的序号是物理盘块号，从 0 开始。在每个表项中存放链接指针，即下一个盘块号。每个文件的第一个盘块号均作为文件地址被填入相应 FCB 的“物理地址”字段中。

由于查找记录的过程是在内存中进行的，因而显著提高了检索速度，并减少了访问磁盘的次数。

FAT 和 NTFS 技术

在微软公司的早期 MS-DOS 中，所使用的是 12 位的 FAT12 文件系统，后来为 16 位的 FAT16文件系统；在Windows 95和Windows 98操作系统中则升级为32位的FAT32；Windows NT、Windows 2000 和 Windows XP 操作系统又进一步发展为新技术文件系统 NTFS(New Technology File System)。这几种文件系统所采用的文件分配方式基本上都是类似于显式链接方法。

在早期 MS-DOS 的 FAT 文件系统中，引入了“卷”的概念，可以支持将一个物理磁盘分成四个逻辑磁盘，因此，通常对于仅有一个硬盘的计算机，最多可将其硬盘分为“C：”、“D：”和“E：”“F：”四个卷(逻辑磁盘)。每个逻辑磁盘就是一个卷(也称为分区)，能够被单独格式化和使用，供文件系统分配空间时使用。

• 一个卷中包含了文件系统信息、一组文件以及空闲空间。
• 每个卷都专门划出一个单独区域来存放自己的目录和 FAT表，以及自己的逻辑驱动器字母。
• 在现代 OS 中，一个物理磁盘可以划分为多个卷，一个卷也可以由多个物理磁盘组成，如 RAID 磁盘阵列。

FAT12

FAT12 文件系统每个分区中都配有两张文件分配表 FAT1 和 FAT2，在 FAT 的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，一个文件的第一个盘块号放在自己的 FCB 中。整个系统有一张文件分配表 FAT。

对于 1.2 MB 的软盘，每个盘块的大小为 512 B，在每个 FAT中共含有 2.4 K 个表项，由于每个 FAT 表项占 12 位，故 FAT 表占用 3.6 KB 的存储空间。

以盘块为分配单位时，所允许的最大磁盘容量： 4096 个表项 （每个 FAT 表项为12 位）× 512 B（每个盘块扇区的大小一般是 512 字节）= 2 MB 。一个物理磁盘支持 4 个逻辑磁盘分区，所以相应的磁盘最大容量仅为 8 MB。这对最早时期的硬盘还可应付，但很快磁盘的容量就超过了 8 MB，为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇是一组连续的扇区，在 FAT 中它是作为一个虚拟扇区，簇的大小一般是 2ⁿ个盘块，一个簇应包含扇区的数量与磁盘容量的大小直接有关。

当一个簇包含两个扇区时，磁盘的最大容量可以达到 16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到 64 MB。 使用簇作为基本的分配单位虽可减少 FAT 表中的项数，这一方面会使 FAT 表占用更少的存储空间，并减少访问 FAT 表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(与存储器管理中的页内零头相似)。

FAT12 已老化，不能满足操作系统发展的需要，其对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只能支持 8+3 格式的文件名。

FAT16

具有 16 位表宽的 FAT 表称为 FAT16。FAT12 表最多只允许 4096 个表项，随着磁盘容量的增加，簇的大小和簇内碎片也将增加。将 FAT 表的宽度增至 16 位，最大表项数将增至 65536 个，此时便能将一个分区分为65536 个簇。在 FAT16 的每个簇中可以有的盘块数为 4、8、16、32 直到 64，可得出 FAT16 可以管理的最大分区空间为 2¹⁶ × 64 × 512 = 2048 MB。FAT16 对 FAT12 的局限性有所改善，但很有限。当磁盘容量迅速增加时，如果再继续使用 FAT16，所形成的簇内碎片所造成的浪费也越大。为了解决这一问题，微软推出了 FAT32。

例如，当要求磁盘分区的大小为 8 GB 时，则每个簇的大小达到 128 KB，这意味着内部零头最大可达到 128 KB。一般而言，对于 1～4 GB 的硬盘来说，大约会浪费 10％～20％的空间。

另外，由于 FAT12 和 FAT16 都不支持长文件名，文件名受到了 8 个字符文件名和 3 个 字符文件扩展名的长度限制，为了满足用户通过文件名更好地描述文件内容的需求，在Windows 95 以后的系统中，对 FAT16 进行了扩展，通过一个长文件名占用多个目录项的方法，使得文件名的长度可以长达 255 个字符，这种扩展的 FAT16 也称为 VFAT。

FAT32

FAT32 中每一簇在FAT表中的表项占据4字节(2³²)，FAT 表可以表示 4 294 967 296 项，这样就允许在FAT32 中采用较小的簇，每个簇都固定为 4 KB，即每簇用 8 个盘块代替 FAT16 的 64 个盘块，每个盘块仍为 512 字节，FAT32 分区格式可以管理的单个最大磁盘空间大到 4 KB×2³²= 2 TB。

假设两个磁盘容量都为 2 GB，一个磁盘采用了 FAT16 ，另一个采用了 FAT32 文件，采用 FAT16 磁盘的簇大小为 32 KB，而 FAT32 磁盘簇只有 4 KB 的大小，这样，磁盘碎片减少，比 FAT16 的存储器利用率要高很多，通常情况下可以提高 15%。

FAT32 主要应用于 Windows 98 及后续 Windows系统，它可以有效地节省硬盘空间，同时也支持长文件名；

NTFS

为了解决 FAT32 的以下不足之处，微软公司又引入了NTFS

• 👎由于文件分配表的扩大，运行速度比 FAT16格式要慢；
• 👎有最小管理空间的限制，FAT32 卷必须至少有 65 537 个簇，因此不支持容量小于 512 MB 的分区，小分区仍然需使用 FAT16 或 FAT12；
• 👎单个文件的长度不能大于 4 GB；
• 👎兼容性方面不能保持向下兼容。

索引分配

链接分配方式的问题：

1. 👎不能支持高效的直接存取。对大文件进行直接存取，须首先在 FAT 中顺序地查找许多盘块号。
2. 👎FAT 需占用较大的内存空间。由于文件盘块号是随机分布在FAT 中，只有将整个 FAT 调入内存，才能保证在 FAT 中找到一个文件的所有盘块号。当磁盘容量较大时，FAT 可能要占用数兆字节以上的内存空间。

在打开文件时，理应只需把该文件占用的盘块的编号调入内存即可，而非整个 FAT。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法为每个文件分配一个索引块(表)，记录分配给该文件的所有盘块号。建立文件时，在为之建立的目录项中填上指向该索引块的指针。

优缺点

• 👍 支持直接访问。当要读文件的第 i 个盘块时，可以方便地直接从索引块中找到第 i 个盘块的盘块号。
• 👍 不会产生外部碎片。当文件较大时，索引分配方式要优于链接分配方式。

• 👎可能要花费较多的外存空间。建立文件时须为之分配索引块，但小文件甚至只需 1～2 个盘块，采用链接分配方式时只需设置 1～2 个指针。而索引分配方式通常需要专门的盘块作为索引块，其中可存放成百个、甚至上千个盘块号。索引块的利用率将是极低的。

多级索引分配

当 OS 为大文件分配的盘块的盘块号已经装满一个索引块时，便分配另一个索引块，通过链指针将各索引块按序链接起来。当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，将第一块、第二块……等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。

如果每个盘块的大小为 1 KB，每个盘块号占 4 个字节，则在一个索引块中可存放 256 个盘块号。这样，在两级索引时， 最多可包含的存放文件的盘块的盘块号总数 N = 256 × 256 = 64 K 个盘块号。由此所允许的文件最大长度为 64 MB。倘若盘块的大小为 4 KB，在采用单级索引时所允许的最大文件长度为 4 MB；而在采用两级索引时所允许的最大文件长度可达 4 GB。

混合索引分配方式

将多种索引分配方式相结合，就形成混合索引分配方式方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式等（已在 UNIX 系统中采用）。在 UNIX System Ⅴ的索引结点中，共设置了13个地址项，即iaddr(0)～iaddr(12)，所有的地址项分成直接地址和间接地址：

1. 直接地址：为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即用 iaddr(0)～iaddr(9)来存放直接地址，即该文件数据所在盘块的盘块号。假如每个盘块的大小为 4 KB，当文件不大于 40 KB 时，便可直接从索引结点中读出该文件的全部盘块号。
2. 一次间接地址：对于大、中型文件，可再利用索引结点中的地址项 iaddr(10)来提供一次间接地址，即一级索引分配方式。一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放 1 K 个盘块号，因而允许文件长达 4 MB。
3. 多次间接地址：
   • 当文件长度大于 4 MB + 40 KB → 一次间址与 10 个直接地址项时，用地址项 iaddr(11) 提供二次间接地址，在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达 4 GB。
   • 地址项 iaddr(12)作为三次间接地址，其所允许的文件最大长度可达 4 TB。

文件目录

为了能对大量的文件实施有效的管理，需要通过文件目录实现对文件的妥善组织，文件目录也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下：

1. 实现“按名存取”，即用户只须向系统提供所需访问文件的名字，便能快速准确地找到指定文件在外存上的存储位置。这是目录管理中最基本的功能。
2. 提高对目录的检索速度。合理地组织目录结构，可加快对目录的检索速度，从而提高对文件的存取速度。
3. 文件共享。在多用户系统中，应允许多个用户共享一个文件，在外存中只保留一份该文件的副本，供不同用户使用，以节省存储空间，提高文件利用率。
4. 允许文件重名。系统应允许不同用户对不同文件采用相同的名字，以便于用户按照自己的习惯给文件命名和使用文件。

文件控制块和索引结点

文件控制块

文件控制块（FCB）是为文件设置的用于描述和控制文件的数据结构。文件管理程序可借助于文件控制块中的信息，对文件施以各种操作。文件与文件控制块一一对应，文件控制块的有序集合称为文件目录，一个文件控制块就是一个文件目录项。通常，一个文件目录也被看做是一个文件，称为目录文件。

在文件控制块中，通常应含有三类信息，即基本信息、存取控制信息及使用信息

• 基本信息类

• 存取控制信息类：存取控制信息类包括：文件主的存取权限、核准用户的存取权限以及一般用户的存取 权限。
• 使用信息类包括: 文件的建立日期和时间、上次修改的日期和时间及当前使用信息(包括当前已打开该文件的进程数、是否被其它进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上)。

不同 OS 的文件系统，由于功能不同，可能只含有上述信息中的某些部分。

索引结点

当文件很多时，文件目录可能要占用大量的盘块。在查找目录的过程中，先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所给定的文件名与目录项中的文件名逐一比较。若未找到指定文件，便再将下一个盘块中的目录项调入内存。设目录文件所占用的盘块数为 N，按此方法查找，则查找一个目录项平均需要调入盘块(N+1)/2 次。

假如一个 FCB 为 64 B，盘块大小为 1 KB，则每个盘块中只能存放 16 个 FCB；若一个文件目录中共有 640 个 FCB，需占用 40 个盘块，故平均查找一个文件需启动磁盘 20 次。

在检索目录文件的过程中，只用到了文件名，仅当找到匹配的目录项时，才需从该目录项中读出该文件的物理地址。而其它一些对该文件进行描述的信息，在检索目录时一概不用，实际并不需调入内存。为此，在有的系统中，如 UNIX 系统，把文件名与文件描述信息分开，使文件描述信息单独形成一个称为索引结点的数据结构，简称为 i 结点。每个目录项仅由文件名和指向该文件所对应的 i 结点的指针所构成。

UNIX 系统中一个目录仅占 16 个字节，其中 14 个字节是文件名，2 个字节为 i 结点指针。这样，为找到一个文件，可使平均启动磁盘次数减少到原来的 1/4，大大节省了系统开销。

磁盘内存中的索引结点

每个文件有惟一的一个磁盘索引结点，当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，便于以后使用。在内存索引结点中又增加了一些内容：

目录结构

目录结构的组织，关系到文件系统的存取速度，也关系到文件的共享性和安全性。因此，组织好文件的目录，是设计好文件系统的重要环节。

单级目录结构

整个文件系统中只建立一张目录表，每个文件占一个目录项每当要建立一个新文件时，必须先检索所有的目录项，以保证新文件名在目录中惟一。然后再从目录表中找出一个空白目录项，填入新文件的文件名及其它说明信息，并置状态位为 1。删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。

缺点：

1. 查找速度慢。目录项较多时，为找到一个指定的目录项要花费较多的时间。对于一个具有 N 个目录项的单级目录，为检索出一个目录项，平均需查找 N/2 个目录项。
2. 不允许重名。在一个目录表中的所有文件，都不能与另一个文件有相同的名字。然而，重名问题在多道程序环境下却又是难以避免的；即使在单用户环境下，当文件数超过数百个时，也难于记忆。
3. 不便于实现文件共享。通常，每个用户都有自己的名字空间或命名习惯，而单级目录要求所有用户都用同一个名字来访问同一文件。

简言之，单级目录只能满足对目录管理的四点要求中的第一点， 因而，它只能适用于单用户环境。

两级目录

两级目录为每一个用户建立有相似的结构的单独的用户文件目录 UFD(User File Directory)，它由用户所有文件的文件控制块组成。此外，主文件目录 MFD(Master File Directory)中，每个用户目录文件都占有一个目录项，其包括用户名和指向该用户目录文件的指针。用户可以请求系统为自己建立一个用户文件目录，如果不再需要 UFD，也可以请求系统管理员将它撤消。在有了 UFD 后，用户可以根据自己的需要创建新文件。OS 只需检查该用户的 UFD 中是否已有同名的另一个文件。

两级目录结构有以下优点：

1. 提高了检索目录的速度。主目录和用户目录 n × m 个目录项中，为查找指定的目录项，最多只需检索 n + m 个目录项。单级目录结构则最多需检索 n × m 个目录项。假定 n = m，采用两级目录可使检索效率提高 n/2 倍。
2. 在不同的用户目录中，可以使用相同的文件名。只要在用户自己的 UFD 中，每一个文件名都是惟一的。
3. 不同用户还可使用不同的文件名来访问系统中的同一个共享文件。两级目录结构结构虽然能有效地将多个用户隔开，在各用户之间完全无关时，这种隔离是一个优点；但当多个用户之间要相互合作去完成一个大任务，且一用户又需去访问其他用户的文件时，这种隔离会使诸用户之间不便于共享文件。

树形结构目录

多级目录结构又称为树型目录结构，可以提高对目录的检索速度和文件系统的性能，为了提高文件系统的灵活性，应允许在一个目录文件中的目录项既是作为目录文件的 FCB，又是数据文件的 FCB，这一信息可用目录项中的一位来指示。

多级目录较两级目录而言，查询速度更快，层次结构更加清晰，能够更加有效地进行文件的管理和保护。在多级目录中，不同性质、不同用户的文件可以构成不同的目录子树，不同层次、不同用户的文件分别呈现在系统目录树中的不同层次或不同子树中，可以容易地赋予不同的存取权限。但是在多级目录中查找一个文件，需要按路径名逐级访问中间节点，增加了磁盘访问次数，无疑将影响查询速度。目前，大多数操作系统如 UNIX、Linux 和 Windows 系列都采用了多级目录结构。

路径名和当前目录

• 路径名：从根目录到任何数据文件，都只有一条惟一的通路。在该路径上从根目录开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构成该数据文件的路径名(path name)。系统中的每一个文件都有惟一的路径名。
• 当前目录(Current Directory) ：每访问一个文件，都要使用从树根开始直到树叶数据文件为止的、包括各中间节点(目录)名的全路径名是相当麻烦的事，同时由于一个进程运行时所访问的文件大多仅局限于某个范围，因而非常不便。可为每个进程设置一个“当前目录”，又称为“工作目录”。进程对各文件的访问都相对于“当前目录” 进行。把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)；而把从树根开始的路径名称为绝对路径名(absolute path name)。

目录操作

• 创建：在用户要创建一个新文件时，只需查看在自己的 UFD 及其子目录中有无与新建文件相同的文件名。若无，便 可在 UFD 或其某个子目录中增加一个新目录项。 删除：如果所要删除的目录是空的，即在该目录中已不再有任何文件，就可简单地将该目录项删除，使它在其上一级目录中对应的目录项为空；如果要删除的目录不空，则可采用下述两种方法处理： (1) 不删除非空目录。当目录(文件)不空时，不能将其删除，而为了删除一个非空目录，必须先删除目录中的所有文件，使之先成为空目录，然后再予以删除。如果目录中还包含有子目录，还必须采取递归调用方式来将其删除，在 MS-DOS 中就是采用这种删除方式。 (2) 可删除非空目录。当要删除一个目录时，如果在该目录中还包含有文件，则目录中的所有文件和子目录也同时被删除。 上述两种方法实现起来都比较容易，第二种方法则更为方便，但比较危险。因为整个目录结构虽然用一条命令即能删除，但如果是一条错误命令，其后果则可能很严重。

目录查询技术

当用户要文件时，系统首先利用文件名对目录进行查询，找出该文件的文件控制块或对应索引结点。

线性检索法

线性检索法又称为顺序检索法。在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，假定用户给定的文件路径名是/usr/ast/mbox，则首先，系统应先读入第一个文件分量名 usr，用它与根目录中各目录项中的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号 6，再从 6 号索引结点中得知 usr 目录文件放在 132 号盘块中，将该盘块内容读入内存。接着，系统再用分量名 ast 与 132 号盘块中的各目录项的文件名顺序进行比较，又找到匹配项，从中得到 ast 的目录文件放在 26 号索引结点中，... ，最后得到/usr/ast/mbox 的索引结点号为 60，该索引结点中存放了指定文件的物理地址。

Hash 方法

直接文件和哈希文件

直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这 种由记录键值到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直接文件的关键，在于用什么方法进行从记录值到物理地址的转换。

哈希(Hash)文件

哈希文件是目前应用最为广泛的一种直接文件。它利用 Hash 函数(或称散列函数)，将记录键值转换为指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块，例如，若令 K 为记录键值，用 A 作为通过 Hash 函数 H 的转换所形成的该记录在目录表中对应表目的位置，则有关系 A=H(K)。通常，把 Hash函数作为标准函数存于系统中，供存取文件时调用。

建立了 Hash 索引文件目录，便可利用Hash 方法进行查询，即系统利用文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，这将显著地提高检索速度。

当使用模式匹配功能，即在文件名中使用了通配符“*”、“？”等时，系统无法利用 Hash 方法检索目录，因此，这时系统还是需要利用线性查找法查找目录。

在进行文件名的转换时，有可能把 n 个不同的文件名转换为相同的 Hash 值，即出现了所谓的“冲突”。一种处理此“冲突”的有效规则是: 如果相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其 Hash 值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值。

文件共享

现代计算机系统应允许多个用户(进程)共享同一份文件。这样，在系统中只需保留该共享文件的一份副本。否则凡是需要该文件的用户，都须各自备有此文件的副本，会造成对存储空间的极大浪费。随着计算机技术的发展，文件共享的范围也在不断扩大，从单机系统中的共享，扩展为多机系统的共享，进而又扩展为计算机网络范围的共享。

基于索引结点的共享方式

在树型结构的目录中，当有多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到多个用户的目录中，此时该文件系统的目录结构已不再是树型结构，而是个有向非循环图 DAG(Directed Acyclic Graph)。

如果在文件目录中包含了文件的物理地址，则在链接时，必须将文件的物理地址拷贝到 B 目录中去。但如果以后 B 或 C 还要继续向该文件中添加新内容，新增加的盘块只会出现在执行了操作的目录中，不能被共享。为此，可以引用索引结点，即诸如文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。`在文件目录中只设置文件名及指向相应索引结点的指针。此时，由任何用户对文件进行 Append 操作或修改，所引起的相应结点内容的改变，能提供给其他用户共享。

在索引结点中还应有一个链接计数 count，用于表示链接到本索引结点上的用户目录项的数目。当用户 C 创建一个新文件时，他便是该文件的所有者，此时将 count 置 1。当有用户 B要共享此文件时，在用户 B 的目录中增加一目录项，并设置一指针指向该文件的索引结点，此时，文件主仍然是 C，count=2。如果用户 C 不再需要此文件，不能将此文件删除呢，因为删除了该文件的索引结点，会使 B 的指针悬空，而 B 则可能正在此文件上执行写操作，此时将因此半途而废。但如果 C 不删除此文件而等待 B 继续使用，这样，由于文件主是 C，如果系统要记账收费，则 C 必须为 B 使用此共享文件而付账，直至 B 不再需要。

利用符号链实现文件共享

为使 B 能共享 C 的一个文件 F，可以由系统创建一个 LINK 类型的新文件，也取名为 F，并写入 B 的目录中，以实现 B 的目录与文件 F 的链接。在新文件中只包含被链接文件 F 的路径名。这样的链接方法被称为符号链接(Symbolic Linking)。新文件中的路径名则只被看作是符号链(Symbolic Link)，当 B 要访问被链接的文件 F 且正要读 LINK 类新文件时，此要求将被 OS 截获，OS 根据新文件中的路径名去读该文件，于是就实现了用户 B 对文件 F的共享。

在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删除后，其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。

缺点: 当其他用户去读共享文件时，系统是根据给定的文件路径名，逐个分量(名)地去查找目录，直至找到该文件的索引结点。因此，在每次访问共享文件时，都可能要多次地读盘。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而由于该链实际上是一个文件，尽管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间。

优点：能够用于链接(通过计算机网络)世界上任何地方的计算机中的文件，此时只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。

上述两种链接方式都存在这样一个共同的问题，即每一个共享文件都有几个文件名。每增加一条链接，就增加一个文件名。这在实质上就是每个用户都使用自己的路径名去访问共享文件。当我们试图去遍历整个文件系统时，将会多次遍历到该共享文件。例如，当有一个程序员要将一个目录中的所有文件都转储到磁带上去时，就可能对一个共享文件产生多个拷贝。

文件保护

影响文件安全性的主要因素有三：

directory entry、inode和index block 辨析：

• 目录项和 inode 之间的关系是一对一的关系。目录项中的 inode 号码指向了对应文件的 inode，通过 inode 可以获取文件的属性和数据。
• inode和索引块之间的关系是一对多的关系。一个 inode 可以指向多个索引块，而每个索引块又可以指向多个数据块。
• 目录项是为了方便用户使用文件名进行查找和管理文件，而 inode 和索引块则是文件系统内部使用的数据结构，用于管理文件的元数据和数据块。
• 目录项和 inode 通常存储在文件系统的目录区域，而索引块则存储在文件系统的数据区域。

总结起来，目录项提供了文件名和 inode 之间的映射关系，inode 存储了文件的元数据和数据块的指针，索引块则用于管理文件的数据块。

1. Directory Entry（目录项）： 目录项是文件系统中的一种数据结构，每个目录项通常包含文件名和inode号码的映射关系。目录项充当了文件名和文件数据之间的桥梁，使得文件系统能够根据文件名查找到对应的inode，并进而获取文件的属性和数据。

2. Inode（索引节点）： Inode是文件系统中的另一个数据结构，用于存储文件的元数据，包括文件的权限、所有者、大小、时间戳等信息。每个文件在文件系统中都有一个唯一的inode，通过inode可以找到文件的数据块。Inode中还包含了指向文件数据块的指针或引用。

3. Index Block（索引块）： Index Block是文件系统中的一个数据结构，用于存储文件数据块的位置信息。当文件的大小超过一个数据块的大小时，文件系统会使用索引块来管理文件的数据块。索引块中存储了指向文件数据块的指针或引用。

• 目录项是文件系统中的一种数据结构，用于将文件名与文件的元数据关联起来。目录项通常包含文件名和指向对应文件的索引节点的指针。
• 索引节点用于存储文件的元数据，如文件的大小、权限、创建时间、修改时间等。索引节点还包含指向文件数据块的指针。索引节点中的指针指向索引块。
• 索引块用于存储文件数据块的地址。当文件大小超过一个数据块的大小时，文件系统使用索引块来存储指向数据块的指针。索引块可以是直接索引块、间接索引块或双重间接索引块，这取决于文件大小。

因此，目录项通过指向索引节点的指针来关联文件名和文件的元数据，而索引节点通过指向索引块的指针来管理文件的数据块。这些数据结构共同组成了文件系统的基本组成部分。