第十二章 文件管理 （Chapter 5 File Management)

12.1 OVERVIEW 域 (Field) 记录 (Record) 文件 (File) 数据库 (Database) 文件管理系统 (File Management System) 数据库管理系统 (Database Management System)

域 域（又叫字段）是数据的基本组成单元；一个域只有一个唯一的值。 长度是字段的基本属性；一个字段的长度可以是固定的，也可以是可变的；域名和数据类型也是字段的基本属性；应用程序和数据库管理系统可以根据域名访问指定的字段，可以根据数据类型校验字段值的正确性。表示一个字段的元数据至少包含三个字段：域名、长度和数据类型。

记录 记录是一组相关字段组成的集合；应用程序和数据库管理系统可以把记录作为数据处理的基本单元。 记录也具有长度这一基本属性；一个记录的长度可以是固定的也可以是可变的；可变长度的记录或者含有数目不定的字段或者含有长度可变的字段。 经常地，记录中的某些字段被视作记录的关键字段，这些字段的值被视作关键字值（简称关键字）。

文件 文件是一组相关记录组成的集合；用户和应用程序可以把文件作为单个实体加以处理。 文件同样具有长度这一基本属性；一个文件的长度可以是固定的，也可以是可变的；可变长度的文件或者含有数目不定的记录或者含有长度可变的记录； 文件名是文件的另一个基本属性；用户和应用程序总是根据文件名访问指定的文件。 表示一个文件的元数据至少包含两个字段：文件名和长度；通常还包括文件类型、文件访问属性等。

数据库 数据库是一组相关数据组成的集合； 数据库中的每组数据均由一组相关记录构成。 数据库中的数据可以被组织成若干独立的文件； 因此，数据库也可被视作一组相关文件组成的集合。

文件管理系统 文件管理系统是一组管理文件的系统程序组成的集合；它为用户和应用程序使用文件提供了一组相关的系统服务。 文件管理系统可以作为一个独立的系统软件加以实现；不过，通常情况下，文件管理系统被视作 是OS的一个重要组成部分。 对于大多数OS中的文件管理系统而言，文件仅仅被视作是一个命名了的字节流。

文件管理系统的设计目标 满足数据管理的需要以及用户的需求； 尽可能保证文件中的数据是有效的； 优化系统吞吐量和用户请求响应时间； 支持各种类型的辅助存储设备； 减少或避免数据丢失或损坏的可能性； 提供一组标准的I/O服务例程； 支持多用户环境下多个用户的I/O操作

一个交互式通用系统的用户需求 每个用户都可以创建、删除以及更新文件； 每个用户都可以在被授权时访问其他用户的文件； 每个用户都可以控制其文件的访问属性； 每个用户都能够以适合问题的方式重构其文件； 每个用户都能够在文件之间移动数据； 每个用户都能够在危险情况下备份和恢复其文件； 每个用户都能够使用文件名访问其文件。

文件管理系统的组成结构

文件管理系统的基本功能

基本的文件管理功能 识别和定位用户请求访问的文件； 使用文件目录描述文件的位置和属性； 在支持文件共享的系统中描述和校验用户对文件的访问权限； 把用户对记录的访问请求转换成对数据块的访问请求； 为存储文件分配空闲的物理块； 管理辅存中的空闲物理块。

12.3 FILE ORGANIZATION AND ACCESS 文件的逻辑组织也叫做文件的逻辑结构，是指从用户和应用程序使用文件的角度所看到的记录在文件中的放置方式。

评价文件逻辑组织的标准 Rapid Access Ease of Update Economy of Storage Simple Maintenance Reliability

说 明 前述评价文件逻辑组织的指标哪一个重要 哪一个 不重要取决于使用文件的应用程序； 说 明 前述评价文件逻辑组织的指标哪一个重要 哪一个 不重要取决于使用文件的应用程序； 事实上， 这些指标也表示使用文件的应用程序对文件逻辑组织提出的一组基本要求。 如果一个应用程序按照批处理方式使用文件， 那么Rapid Access这一指标便是不重要的； 如果一个文件存储在CD-ROM上， 那么应用程序不可能要求更新它，所以Ease of Update这一指标也就无关紧要。

常见的文件逻辑组织 堆文件 (The Pile File) 顺序文件 (The Sequential File) 索引顺序文件 (The Indexed Sequential File) 索引文件 (The Indexed File) 直接或Hash文件 (The Direct, or Hashed, File)

堆文件 堆文件中的各个记录可以有不同的域或者有相同的域但各个域在记录中的逻辑位置可以不同； 正是因为堆文件中的各个记录具有上述特征，所以堆文件中的各个记录其包含的域应当是自描述(Self-describing)的； 各个记录在堆文件中的逻辑位置与它们加入到堆文件中的次序（即到达次序）是一致的； 为了响应应用程序对堆文件中的记录进行存取的请求，文件管理系统必须对堆文件进行耗尽搜索(Exhaustive Search)。

顺序文件 顺序文件中的各个记录具有相同的格式；这意味着，顺序文件中的各个记录具有相同的域、各个域在记录中的逻辑位置是相同的并且各个域具有固定的长度； 正是因为顺序文件中的各个记录具有上述特征，所以顺序文件中记录所包含的各个域其域名、长度、类型等用于表示域的各种元数据可以作为文件逻辑结构的属性加以描述；

各个记录在顺序文件中的逻辑位置由各个记录的关键字确定； 通常应用程序欲访问顺序文件中的某个记录时必须向文件管理系统提交该记录的关键字值以便文件管理系统据此定位应用程序请求访问的记录。（此种存取方法即所谓的按键存取）

索引顺序文件 索引顺序文件由三部分组成：主文件(Main File)、索引文件(Index File)以及溢出文件(Overflow File)； 主文件是一个顺序文件；它与普通顺序文件的区别在于：主文件中的每个记录均含指向溢出文件中相关记录的指针；依据关键字值所确定的次序，指针所在的主文件中的记录位于指针所指的溢出文件中的相关记录之前。显然，通过指针，溢出文件中的记录在逻辑上被集成在主文件中。

索引文件也是一个顺序文件，其记录的排列顺序与主文件记录的排列顺序是一致的；它与普通顺序文件的区别在于：索引文件中的每个记录只含两 个域；其中一个域为关键字域，该域与主文件中记录的关键字域完全相同；另一个域为指针域，该域包含一个指向主文件相关记录的指针。 溢出文件与前面所说的日志文件类似，它也是一个堆文件，其记录时常被合并到主文件中；不过，与日志文件不同，溢出文件中的每个记录均含指向位于溢出文件中的逻辑上是其直接后继的相关记录的指针。

索引文件 前面所介绍的索引顺序文件只是索引文件的一个特例。在索引文件中，主文件不必是顺序文件，主文件中的记录也 不必拥有相同的格式和统一的长度；当然，溢出文件也可能没有存在的必要。 在索引文件中，有两种常见的索引： 完全索引(Exhaustive Index) 此类索引为主文件中的每个记录建立一个入口； 部分索引(partial Index) 此类索引只为主文件中包含某个特定字段的记录建立入口。 对于索引文件而言，当一个新的记录加入到主文件中时，所有相关索引都必须被更新。

Hash文件 当应用程序请求存取Hash文件中的某个记录时，文件管理系统通常要求应用程序提交记录的关键字值。 与前面所介绍的各种文件逻辑组织形式不同，在使用Hash文件的情况下，文件管理系统并不根据应用程序提交的记录的关键字值查询Hash文件，而是根据应用程序提交的记录的关键字值计算出应用程序请求访问的记录在Hash文件中的位置。 文件的此种逻辑组织形式常用于快速存取一个固定长度记录的场合。

12.3 文件目录 文件管理系统使用一种称为文件目录(File Directory)的数据结构管理一组文件。利用文件目录，文件管理系统可以定位应用程序请求访问的文件、可以控制应用程序对文件的各种存取权限、可以在多个应用程序之间实现文件共享。从用户和应用程序的角度看，文件目录在文件名与文件之间建立了一种映射关系；正是利用这种映射关系，文件管理系统为用户和应用程序提供了按名存取文件的功能。

文件目录的特点 内容： 包含表示文件的各种元数据，比如：文件名、文件属主、文件长度、文件在辅存空间中的位置等（参见：pp. 513 Table 12.2）。 逻辑组织： 大多数文件管理系统把文件目录本身视作文件(称为目录文件)；目录文件通常采用顺序文件这种逻辑组织形式，有时也采用Hash文件这种逻辑组织形式。 存取操作： 只有文件管理系统才能直接存取文件目录中的数据；用户和应用程序只能通过文件管理系统所提供的系统服务间接地访问文件目录中的某些内容。

作用于文件目录的典型操作 检索目录 (Search Directory)当用户或应用程序请求访问某个文件时，文件管理系统将根据用户或应用程序提交的文件名检索文件目录； 创建目录项 (Create Directory Entry)当用户或应用程序请求创建一个新文件时，文件管理系统将会在文件目录中为该文件创建一个目录项； 删除目录项 (Delete Directory Entry) 当用户或应用程序请求删除一个老文件时，文件管理系统将会从文件目录中删除该文件所对应的目录项； 列目录清单 (List Directory) 用户常常请求文件管理系统列出文件目录中的某些内容，比如文件名、文件属主、文件长度、文件类型等。

单级目录 (Single-Level Directory) 两级目录 (Two-Level Directory) 多级目录 (Multi-Level Directory) 也叫做树型目录 (Tree-Structured Directory)

工作目录 (Working Directory) 所谓工作目录，简单地说，就是用户当前正在使用的目录。 在使用树型目录的系统中引入工作目录后，用户每次请求访问文件时仅需提交文件的相对路径名就行了。在树型目录结构中从工作目录开始直至某文件所在的位置其间所经过的各个目录的名字以及该文件的本名构成了该文件的相对路径名。

12.4 文件共享 允许多个用户同时存取同一文件(即文件共享)是人们对多用户操作系统提出的一个基本需求。 为了实现文件共享， 文件管理系统的设计者必须解决以下两 个基本问题： 规定用户对文件的存取权限； 控制多个用户进程对文件的同时存取。

常见的文件存取权限 探知 (Knowledge) 禁止访问 (None)拥有此种存取权限的用户无法知道相关文件的存在。 为了实现此种存取权限，文件管理系统将禁止拥有此种存取权限的用户访问相关文件所在的目录。 探知 (Knowledge) 拥有此种存取权限的用户可以探知相关文件的存在并了解相关文件的属主是谁。 拥有此种存取权限的用户常常进一步向相关文件的属主请求更多的存取权限。

读 (Read) 执行 (Execution)拥有此种存取权限的用户可以从相关文件中取出程序并执行它，但不能复制它。 拥有此种存取权限的用户可以读取相关文件的内容用于任何目的（包括复制和执行）。 某些系统规定了文件的浏览（View）权；拥有浏览权的用户仅能读取相关文件的内容用于显示； 这些系统通常还规定了文件的复制（Copy）权；拥有复制权的用户可以读取相关文件的内容用于复制。

更改权限 (Changing Protection) 追加 (Appending) 拥有此种存取权限的用户可以追加记录到相关文件的尾部，但不能修改或删除相关文件的内容。 更新 (Updating) 拥有此种存取权限的用户既可以增加内容到相关文件中也可以修改或删除相关文件的内容。 更改权限 (Changing Protection) 此种存取权限通常为文件的属主所拥有；拥有此种存取权限的文件属主可以改变授予其它用户的对相关文件的存取权限。(待续)

(接续) 某些系统允许非属主用户拥有此种存取权限； 拥有此种存取权限的非属主用户可以把自己所拥有的对相关文件的存取权限转授予其他用户。 删除 (Deletion) 拥有此种存取权限的用户可以从系统中删除相关文件。 注：前面所讨论的文件存取权限依讨论次序形成了一个嵌套结构(即层次结构)；这意味着，若某用户被授予某种权限(比如：更新权)，那么该用户也将同时拥有该权限之前的所有权限(即：探知、执行、读以及追加权)。

多个用户进程同时存取文件的控制方法 大多数文件管理系统使用文件锁(File Lock)来协调多个用户进程同时存取同一文件的请求； 文件锁可以作用于： 整个文件（即锁定整个文件）； 文件中的单个记录（即锁定某个记录）。

文件的物理组织 文件的物理组织也叫做文件的物理结构，是指从文件管理系统在辅存空间中存储文件的角度所看到的文件中的各个数据块在辅存空间中的存储布局。

12.5 记录组块 虽然从用户和应用程序的角度看文件是由一组记录组成的集合，但从文件管理系统的角度看文件是由一组数据块组成的集合。之所以如此是因为，在现代计算机系统中，文件将以数据块为单位在内外存之间进行传输并最终以数据块的形式存储在辅存空间中。 显然，文件管理系统在传输和存储文件之前必须把文件中的记录组织成数据块。我们把文件管理系统所做的此项工作称为“记录组块(Record Blocking)”。

记录组块的方法 固定组块法 (Fixed Blocking) 可变长跨块组块法 (Variable-length Spanned Blocking) 可变长非跨块组块法 (Variable-length Unspanned Blocking)

固定组块法

大多数系统使用固定长度的数据块；因为这样可以简化内外存之间的I/O传输、简化内存中的I/O缓冲区的分配、简化数据块在辅存中的组织与存储。

可变长跨块组块法

特征：数据块由变长记录组成且允许一条记录跨越两个数据块；对于跨块记录，常在该记录所在的第一个数据块中保存一个指向该记录所在的第二个数据块的指针。 评价： 数据块内不存在没有被使用的空间； 对于垮块记录，要求两次I/O操作； 不管使用何种逻辑组织，文件总是很难更新； 此种组块法很难实现。

可变长非跨块组块法

评价： 特征：数据块由变长记录组成但不允许一条记录跨越两个数据块。 每个数据块的尾部可能有一些没有被使用的空间；记录的长度受限于数据块的长度。

12.6 辅存空间管理 文件分配 (File Allocation):分配空间用于存储文件； 空闲空间管理 (Free Space Management) 跟踪可用辅存空间以便实施分配； 当创建一个新文件时，文件管理系统是否按照该文件的最大空间需求为其分配辅存空间？ 作为文件管理系统分配辅存空间时所使用的分配单位，Portion的尺寸应该为多大？ 作为文件管理系统跟踪文件存储布局时所使用的数据基，FAT使用何种数据结构？

预分配与动态分配 预分配 (Preallocation) 动态分配 (Dynamic Allocation) 文件管理系统在创建一个文件时就根据该文件的最大尺寸为其分配足够的辅存空间； 动态分配 (Dynamic Allocation) 文件管理系统随时根据一个文件的实际尺寸调整分配给该文件的辅存空间。

常用的文件分配方法 连续分配 (Contiguous Allocation) 链式分配 (Chained Allocation) 索引分配 (Indexed

连续分配

使用连续分配方法的文件管理系统通常也同时使用预分配策略。 在 FAT中为每个文件建立一个唯一的入口: 每个文件在辅存空间中所占用的第一个物理块的块号以及所占用的物理块的数目均将被保存在FAT中。 连续分配方法既适宜于组织顺序文件的存储；不过，连续分配方法将会导致辅存空间出现外零头。 解决外零头问题的一个有效方法就是使用“紧凑”技术。

链式分配

使用链式分配方法的文件管理系统通常也同时使用动态分配策略。 此类文件管理系统将在每个文件所占用的每个物理块中保存一个指向同一文件所占用的下一个物理块的指针。 在 FAT中为每个文件建立一个唯一的入口: 所占用的第一个物理块的块号以及所占用的物理块的数目均将被保存在FAT中。 链式分配方法适宜于组织顺序文件的存储但不适宜于应用程序对文件数据块进行随机访问。 虽然链式分配方法不会导致辅存空间出现外零头，但链式分配方法并未体现文件访问的局部性原理；为了弥补此点不足，许多使用链式分配方法的文件管理系统周期性地对文件进行整合(Consolidate)。

索引分配

使用索引分配方法的文件管理系统将为每个文件建立一 个索引；索引中的每一个入口保存一个指向相关文件所占用的一个块的指针; 为了压缩索引的尺寸，使用索引分配方法的文件管理系统经常对文件进行整合。 索引分配方法既适宜于应用程序对文件数据块进行顺序访问也适宜于应用程序对文件数据块进行随机存取，因而得到广泛应用。

与空闲空间管理 Bit Tables(位表或位示图) Chained Free Portions(空块链) Indexing(空闲区索引表)

Bit Tables(位表) 用一个 bit表示一个磁盘块的使用状况：bit=0，表示对应的磁盘块是空闲的； bit=1，表示对应的磁盘块已经被文件占用。 Bit Tables较小，可以保存在内存中，从而减少文件管理系统在实施空闲空间分配时读盘次数； 使用Bit Tables，文件管理系统可以相对容易地发现一组连续的空闲磁盘块。

Chained Free Portions(空闲块链) 用一个指针变量指向磁盘中的第一个空闲块并用一个长度变量记录第一个空闲所包含的空闲磁盘块数； 在磁盘中的每一个空闲块中保存指向磁盘中的下一个空闲块的指针以及下一个空闲块所包含的空闲磁盘块数。 空闲块链的空间开销可以忽略不计。

Indexing(空闲区索引表) 文件管理系统将把磁盘中所有空闲区视作一个文件并为该文件建立一个索引表目； 索引表中的每一个表目将保存一个指向一个空闲区的指针。

感谢大家对我的支持！ 祝 诸 位 考 个 好 成 绩 ！ 祝 诸 位 好 运 ！