在现代计算机系统中，要用到大量的程序和数据，因内存容量有限，且不能长期保存， 故而平时总是把它们以文件的形式存放在外存中，需要时再随时将它们调入内存。如果由用户直接管理外存上的文件，不仅要求用户熟悉外存特性，了解各种文件的属性，以及它 们在外存上的位置，而且在多用户环境下，还必须能保持数据的安全性和一致性。显然， 这是用户所不能胜任、也不愿意承担的工作。于是，取而代之的便是在操作系统中又增加 了文件管理功能，即构成一个文件系统，负责管理在外存上的文件，并把对文件的存取、 共享和保护等手段提供给用户。这不仅方便了用户，保证了文件的安全性，还可有效地提 高系统资源的利用率。
6.1 文件和文件系统
在现代 OS 中，几乎毫无例外地是通过文件系统来组织和管理在计算机中所存储的大量程序和数据的；或者说，文件系统的管理功能，是通过把它所管理的程序和数据组织成一 系列文件的方法来实现的。而文件则是指具有文件名的若干相关元素的集合。元素通常是记录，而记录又是一组有意义的数据项的集合。可见，基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。
6.1.1 文件、记录和数据项
- 数据项
(1) 基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名 的最小逻辑数据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。 例如，用于描述一个学生的基本数据项有学号、姓名、年龄、所在班级等。
(2) 组合数据项。它是由若干个基本数据项组成的，简称组项。例如，经理便是个组项， 它由正经理和副经理两个基本项组成。又如，工资也是个组项，它可由基本工资、工龄工 资和奖励工资等基本项所组成。
基本数据项除了数据名外，还应有数据类型。因为基本项仅是描述某个对象的属性， 根据属性的不同，需要用不同的数据类型来描述。例如，在描述学生的学号时，应使用整 数；描述学生的姓名则应使用字符串(含汉字)；描述性别时，可用逻辑变量或汉字。可见， 由数据项的名字和类型两者共同定义了一个数据项的“型”。而表征一个实体在数据项上的 数据则称为“值”。例如，学号/30211、姓名/王有年、性别/男等。
记录
记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含 哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把 他作为不同的对象。例如，一个学生，当把他作为班上的一名学生时，对他的描述应使用 学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。但 若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出 生年月、身高、体重、血压及病史等项。
在诸多记录中，为了能惟一地标识一个记录，必须在一个记录的各个数据项中，确定 出一个或几个数据项，把它们的集合称为关键字(key)。或者说，关键字是惟一能标识一个 记录的数据项。通常，只需用一个数据项作为关键字。例如，前面的病历号或学号便可用 来从诸多记录中标识出惟一的一个记录。然而有时找不到这样的数据项，只好把几个数据 项定为能在诸多记录中惟一地标识出某个记录的关键字。
文件
文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件 和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被 看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例 如，可以将一个班的学生记录作为一个文件。一个文件必须要有一个文件名，它通常是由 一串 ASCII 码或(和)汉字构成的，名字的长度因系统不同而异。如在有的系统中把名字规定 为 8 个字符，而在有的系统中又规定可用 14 个字符。用户利用文件名来访问文件。
此外，文件应具有自己的属性，属性可以包括：
(1) 文件类型。可以从不同的角 度来规定文件的类型，如源文件、目标文件及可执行文 件等。
(2) 文件长度。文件长度指文件的当前长度，长度的单位可以是字节、字或块，也可能 是最大允许的长度。
(3) 文件的物理位置。该项属性通常是用于指示文件在哪一个设备上及在该设备的哪个 位置的指针。
(4) 文件的建立时间。这是指文件最后一次的修改时间等。 图 6-1 示出了文件、记录和数据项之间的层次关系。
6.1.2 文件类型和文件系统模型
- 文件类型
1)按用途分类
(1) 系统文件。这是指由系统软件构成的文件。大多数的系统文件只允许用户调用，但 不允许用户去读，更不允许修改；有的系统文件不直接对用户开放。
(2) 用户文件。指由用户的源代码、目标文件、可执行文件或数据等所构成的文件。用 户将这些文件委托给系统保管。
(3) 库文件。这是由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用， 但不允许修改。
2)按文件中数据的形式分类
(1) 源文件。这是指由源程序和数据构成的文件。通常由终端或输入设备输入的源程序 和数据所形成的文件都属于源文件。它通常是由 ASCII 码或汉字所组成的。
(2) 目标文件。这是指把源程序经过相应语言的编译程序编译过，但尚未经过链接程序 链接的目标代码所构成的文件。它属于二进制文件。 通常，目标文件所使用的后缀名是 “.obj”。
(3) 可执行文件。这是指把编译后所产生的目标代码再经过链接程序链接后所形成的 文件。
3)按存取控制属性分类
(1) 只执行文件。该类文件只允许被核准的用户调用执行，既不允许读，更不允许写。
(2) 只读文件。该类文件只允许文件主及被核准的用户去读，但不允许写。
(3) 读写文件。这是指允许文件主和被核准的用户去读或写的文件。
4) 按组织形式和处理方式分类
根据文件的组织形式和系统对其的处理方式，可将文件分为三类：
(1) 普通文件：由 ASCII 码或二进制码组成的字符文件。一般用户建立的源程序文件、 数据文件、目标代码文件及操作系统自身代码文件、库文件、实用程序文件等都是普通文 件，它们通常存储在外存储设备上。
(2) 目录文件：由文件目录组成的，用来管理和实现文件系统功能的系统文件，通过目 录文件可以对其它文件的信息进行检索。由于目录文件也是由字符序列构成，因此对其可 进行与普通文件一样的种种文件操作。
(3) 特殊文件：特指系统中的各类 I/O 设备。 为了便于统一管理， 系统将所有的输入/输出设备都视为文件，按文件方式提供给用户使用，如目录的检索、权限的验证等都 与普通文件相似，只是对这些文件的操作是和设备驱动程序紧密相连的，系统将这些操作 转为对具体设备的操作。根据设备数据交换单位的不同，又可将特殊文件分为块设备文件 和字符设备文件。前者用于磁盘、光盘或磁带等块设备的 I/O 操作，而后者用于终端、打 印机等字符设备的 I/O 操作。
文件系统模型
图 6-2 示出了文件系统的模型。可将该模型分为三个层次，其最底层是对象及其属性； 中间层是对对象进行操纵和管理的软件集合；最高层是文件系统提供给用户的接口。
1) 对象及其属性
文件管理系统管理的对象有：
① 文件。它作为文件管理的直接对象。
② 目录。为了 方便用户对文件的存取和检索，在文件系统中必须配置目录，每个目录项中，必须含有文 件名及该文件所在的物理地址(或指针)。对目录的组织和管理是方便用户和提高对文件存取 速度的关键。
③ 磁盘(磁带)存储空间。文件和目录必定占用存储空间，对这部分空间的有 效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。
2) 对对象操纵和管理的软件集合
这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括: 对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、 对文件读和写的管理，以及对文件的共享与保护等功能。
3) 文件系统的接口
为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口:
(1) 命令接口。 这是指作为用户与文件系统交互的接口。 用户可通过键盘终端键入命 令，取得文件系统的服务。
(2) 程序接口。这是指作为用户程序与文件系统的接口。用户程序可通过系统调用来取 得文件系统的服务。
6.1.3 文件操作
- 最基本的文件操作
(1) 创建文件。在创建一个新文件时，系统首先要为新文件分配必要的外存空间，并在 文件系统的目录中，为之建立一个目录项。目录项中应记录新文件的文件名及其在外存的 地址等属性。
(2) 删除文件。当已不再需要某文件时，可将它从文件系统中删除。在删除时，系统应 先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
(3) 读文件。在读一个文件时，须在相应系统调用中给出文件名和应读入的内存目标地 址。此时，系统同样要查找目录，找到指定的目录项，从中得到被读文件在外存中的位置。 在目录项中，还有一个指针用于对文件的读/写。
(4) 写文件。在写一个文件时，须在相应系统调用中给出该文件名及该文件在内存中的 (源)地址。为此，也同样须先查找目录，找到指定文件的目录项，再利用目录中的写指针进 行写操作。
(5) 截断文件。如果一个文件的内容已经陈旧而需要全部更新时，一种方法是将此文件 删除，再重新创建一个新文件。但如果文件名及其属性均无改变时，则可采取另一种所谓的截 断文件的方法，此即将原有文件的长度设置为 0，或者说是放弃原有的文件内容。
(6) 设置文件的读/写位置。前述的文件读/写操作都只提供了对文件顺序存取的手段， 即每次都是从文件的始端读或写。设置文件读/写位置的操作，用于设置文件读/写指针的位 置，以便每次读/写文件时，不是从其始端而是从所设置的位置开始操作。也正因如此，才 能改顺序存取为随机存取。
文件的“打开”和“关闭”操作
当前 OS 所提供的大多数对文件的操作，其过程大致都是这样两步: 第一步是通过检索文 件目录来找到指定文件的属性及其在外存上的位置；第二步是对文件实施相应的操作，如读 文件或写文件等。当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录 开始。为了避免多次重复地检索目录，在大多数 OS 中都引入了“打开”(open)这一文件系统 调用，当用户第一次请求对某文件进行操作时，先利用 open 系统调用将该文件打开。
所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷 贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当 用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请 求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次 检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已 不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS 将会把该文件从打开文件表中的表目上删除掉。
其他文件操作
为了方便用户使用文件，通常，OS 都提供了数条有关文件操作的系统调用，可将这些 调用分成若干类: 最常用的一类是有关对文件属性进行操作的，即允许用户直接设置和获得 文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权， 以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另一类是有关 目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。
值得说明的是，有许多文件操作都可以利用上述基本操作加以组合来实现。例如，创 建一个文件拷贝的操作，可利用两条基本操作来实现。其第一步是利用创建文件的系统调 用来创建一个新文件；第二步是将原有文件中的内容写入新文件中。
6.2 文件的逻辑结构
通常，文件是由一系列的记录组成的。文件系统设计的关键要素，是指将这些记录构 成一个文件的方法，以及将一个文件存储到外存上的方法。事实上，对于任何一个文件， 都存在着以下两种形式的结构:
(1) 文件的逻辑结构(File Logical Structure)。这是从用户观点出发所观察到的文件组织 形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织(File Organization)。
(2) 文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。 无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。本节只介绍 文件的逻辑结构。 对文件逻辑结构所提出的基本要求，首先是能提高检索速度，即在将大批记录组成文 件时，应有利于提高检索记录的速度和效率；其次是便于修改，即便于在文件中增加、删 除和修改一个或多个记录；第三是降低文件的存储费用，即减少文件占用的存储空间，不要求大片的连续存储空间。
6.2.1 文件逻辑结构的类型
- 有结构文件
(1) 定长记录。这是指文件中所有记录的长度都是相同的，所有记录中的各数据项都处 在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录 的处理方便、开销小，所以这是目前较常用的一种记录格式，被广泛用于数据处理中。
(2) 变长记录。这是指文件中各记录的长度不相同。产生变长记录的原因，可能是由于 一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等；也可能是 数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。不 论是哪一种，在处理前，每个记录的长度是可知的。 根据用户和系统管理上的需要， 可采用多种方式来组织这些记录，形成下述的几种 文件：
(1) 顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定 长记录，因而能用较快的速度查找文件中的记录。
(2) 索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一 个表项，以加快对记录检索的速度。
(3) 索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为 每一组记录中的第一个记录设置一个表项。
无结构文件
如果说大量的数据结构和数据库是采用有结构的文件形式的话，则大量的源程序、可 执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单 位。对流式文件的访问，则是采用读/写指针来指出下一个要访问的字符。可以把流式文件 看做是记录式文件的一个特例。在 UNIX 系统中，所有的文件都被看做是流式文件，即使 是有结构文件，也被视为流式文件，系统不对文件进行格式处理。
6.2.2 顺序文件
- 逻辑记录的排列
文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的 顺序进行排列。一般地，可归纳为以下两种情况：
第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即 按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录……， 依此类推。
第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短 从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。
对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必须从头开 始，逐个记录地查找，直至找到指定的记录，或查完所有的记录为止。而对顺序结构文件， 则可利用某种有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法来提高检 索效率。
对顺序文件的 读/写操作
顺序文件中的记录可以是定长的，也可以是变长的。 对于定长记录的顺序文件，如 果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。 在读一个文件时， 可设置一个读指针 Rptr， 令它指向下一个记录的首地址， 每当读完一个记录时， 便 执行
Rptr:=Rptr + L 操作，使之指向下一个记录的首地址，其中的 L 为记录长度。类似地，在写一个文件时， 也应设置一个写指针 Wptr，使之指向要写的记录的首地址。同样，在每写完一个记录时， 又须执行以下操作:
Wptr:=Wptr + L
对于变长记录的顺序文件，在顺序读或写时的情况相似，但应分别为它们设置读或写指针，在每次读或写完一个记录后，须将读或写指针加上 Li 。L i 是刚读或刚写完的记录的 长度。图 6-3 所示为定长和变长记录文件。
顺序文件的优缺点
顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录 时。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能 存储在磁带上，并能有效地工作。
在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地 查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况 更为严重。例如，有一个含有 10 4 个记录的顺序文件，如果对它采用顺序查找法去查找一个 指定的记录，则平均需要查找 5×10 3 个记录；如果是可变长记录的顺序文件，则为查找一 个记录所需付出的开销将更大，这就限制了顺序文件的长度。
顺序文件的另一个缺点是，如果想增加或删除一个记录都比较困难。为了解决这一问 题， 可以为顺序文件配置一个运行记录文件(Log File)，或称为事务文件(Transaction File)， 把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如 4 小时，将运行记 录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。
6.2.3 索引文件
对于定长记录文件，如果要查找第 i 个记录，可直接根据下式计算来获得第 i 个记录相 对于第一个记录首址的地址：
A i = i × L
然而，对于可变长度记录的文件，要查找其第 i 个记录时，须首先计算出该记录的首地 址。为此，须顺序地查找每个记录，从中获得相应记录的长度 Li ，然后才能按下式计算出 第 i 个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则
可见，对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。 然而，对于变长记录就较难实现直接存取了，因为用直接存取方法来访问变长记录文件中 的一个记录是十分低效的，其检索时间也很难令人接受。为了解决这一问题，可为变长记 录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于 记录该记录的长度 L 及指向该记录的指针(指向该记录在逻辑地址空间的首址)。由于索引表 是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地 实现直接存取。图 6-4 示出了索引文件(Index File)的组织形式。
在对索引文件进行检索时，首先是根据用户(程序)提供的关键字，并利用折半查找法去 检索索引表，从中找到相应的表项；再利用该表项中给出的指向记录的指针值，去访问所 需的记录。而每当要向索引文件中增加一个新记录时，便须对索引表进行修改。由于索引 文件可有较快的检索速度，故它主要用于对信息处理的及时性要求较高的场合，使用索引文件的主要问题是，它除了有主文件外，还须配置一张索引表，而 且每个记录都要有一个索引项，因此提高了存储费用。
6.2.4 索引顺序文件
索引顺序文件可能是最常见的一种逻辑文件形式。它有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。前已述及，它是顺序文件和索引文件相结合的产物。它将顺序文件中的所有记录分为若干个组(例如，50 个 记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个 索引项，其中含有该记录的键值和指向该记录的指针。索引顺序文件如图 6-5 所示。
在对索引顺序文件进行检索时，首先也是利用用户(程序)所提供的关键字以及某种查 找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第 一个记录在主文件中的位置；然后，再利用顺序查找法去查找主文件，从中找到所要求的 记录。
如果在一个顺序文件中所含有的记录数为 N，则为检索到具有指定关键字的记录，平均 须查找 N/2 个记录；但对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只 要查找 N 个记录数，因而其检索效率 S 比顺序文件约提高 N /2 倍。例如，有一个顺序 文件含有 10 000 个记录，平均须查找的记录数为 5000 个。但对于索引顺序文件，则平均只 须查找 100 个记录。可见，它的检索效率是顺序文件的 50 倍。
但对于一个非常大的文件，为找到一个记录而须查找的记录数目仍然很多，例如，对 于一个含有 10 6 个记录的顺序文件，当把它作为索引顺序文件时，为找到一个记录，平均须 查找 1000 个记录。为了进一步提高检索效率，可以为顺序文件建立多级索引，即为索引文 件再建立一张索引表，从而形成两级索引表。例如，对于一个含有 10 6 个记录的顺序文件， 可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表应含有 10 4 个表项， 而每个表项中存放顺序文件中每个组第一个记录的记录键值和指向该记录的指针，然后再 为低级索引表建立一张高级索引表。这时，也同样是每 100 个索引表项为一组，故具有 102 个表项。这里的每个表项中存放的是低级索引表每组第一个表项中的关键字和指向该表项 的指针。此时，为找到一个具有指定关键字的记录，所须查找的记录数平均为 50+50+50=150， 或者可表示为(3/2) 3 N 。其中，N 是顺序文件中记录的个数。注意，在未建立索引文件时所 需查找的记录数平均为 50 万个；对于建立了一级索引的顺序索引文件，平均需查找 1000 次；建立两级索引的顺序索引文件，平均只需查找 150 次。
======第六章文件管理======（2）：https://developer.aliyun.com/article/1415865?spm=a2c6h.13148508.setting.24.16254f0exsfwiz
