第六章    文件管理

第六章 文件管理 6.1 文件和文件系统 6.2文件逻辑结构 6.3 存储介质 6.4 文件的物理结构 6.5 目录管理 第六章    文件管理 6.1 文件和文件系统 6.2文件逻辑结构 6.3 存储介质 6.4 文件的物理结构 6.5 目录管理 6.6 文件存储空间的管理 6.7 文件共享和保护 6.8 数据一致性控制

第六章    文件管理 6.1 文件和文件系统

6.1.1 概 述 所有的计算机应用程序都要存储信息和检索信息 三个基本要求： 能够存储大量的信息 长期保存信息 可以共享信息 解决方法：把信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。 文件是通过操作系统来管理的，包括：文件的结构，命名，存取，使用，保护和实现方法。

1.文件管理任务 文件管理是软件（程序与数据集合）资源管理，是涉及用户作业和内部硬件管理 任务：把存储、检索、共享和保护文件的手段，提供给本身和用户，以方便用户及资源利用 功能： 分配与管理外存 提供合适的存储方法 文件共享，保护解决冲突

2. 文件管理功能 分配与管理外部存储器，用户以文件形式存放信息，“按名存取”，文件的机内码与磁盘、光盘等外存的地址建立起相对应的表格联系 提供合适的存储方法，例如，鍵盘命令以及程序中使用系统调用控制。包括文件的创建(Create)、打开(Open)、关闭(Close)、读写(Read/Write)、刪除(Delete, Erase)和重命名或改名(Rename)等 文件的共享与保护，解决文件命名中的冲突和存取权限的控制

3. 文件的概念 文件是软件机构，软件资源的管理方式 具有符号名的一组相关元素的有序序列，是一段程序或数据的集合 一组赋名的相关联字符流的集合，或者是相关联记录。而记录是有意义的信息集合 信息项：构成文件内容的基本单位 文件的特性：包括文件说明、文件体。 文件是一个抽象机制，它提供了一种把信息保存在存储介质上，而且便于以后存取的方法，用户不必关心实现细节.

各信息项之间具有顺序关系 编号：0 1 …… i …… n-1 信息项 信息项 ……... 信息项 ……... 信息项 读写指针

文件命名规则 长度，数字和字符，大小写区分，支持文件扩展名（一个或多个） 例子：.bak .gif .doc .ppt .hlp .html .mpg .jpg .ps .tex .txt .zip

4. 文件系统的概念 是操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。 文件系统包含文件管理程序（文件与目录的集合）和所管理的全部文件 是用户与外存的接口 系统软件为用户提供统一方法（以数据记录的逻辑单位），访问存储在物理介质上的信息 文件系统=文件管理程序（文件和目录的集合）+它所管理的全部文件

1) 文件系统功能 用户角度：实现“按名存取” 系统角度：是对文件存储器的存储空间进行组织、分配、负责文件的存储并对存入的文件实施保护、检索的一组软件的集合。

2)文件系统具体功能 (1)统一管理文件的存储空间，实施存储空间的分配与回收 (2)实现文件的按名存取 名字空间 映射 存储空间 名字空间 映射 存储空间 (3)实现文件信息的共享，并提供文件的保护和保密措施 (4)向用户提供一个方便使用的接口（提供对文件系统操作命令，以及提供对文件的操作命令：信息存取、加工等） (5)系统维护及向用户提供有关信息 (6)文件系统的执行效率 文件系统在操作系统接口中占的比例最大,用户使用操作系统的感觉在很大程度上取决于对文件系统的使用效果. (7)提供与I/O的统一接口

3) 文件系统的优点 使用方便，灵活，用户按名存取 安全可靠， 保护系统和用户 提供保密与共享 UNIX文件系统特点 分层“倒树”型文件系统 每一用户可以是树的一个分支，分支独立，可以与别的“叶”重名 “树根”是所有用户有用的工具性程序

4)文件系统必须解决的问题 如何有效地分配文件存储器的存储空间 提供合适的存取方法 命名的冲突和文件的共享

5) 理想文件系统的特征 有效地分配文件存储器的存储空间 文件结构和存取的灵活性和多样性 具有对用户来说尽可能是透明的机制 尽可能达到文件存储装置的独立性 存储在文件中的信息的安全 能方便的共享公用的文件 有效地实现各种文件操作的命令

6.1.2 文件分类 1.文件分类原因 文件的分类是为了更好地管理和使用，要科学地分门别类，对不同的文件进行不同的管理。这样，不仅提高了文件的存取速度，对文件的共享和保护也有利 一般系统级与用户级要进行不同的管理，例如，一个系统文件工作时要读入内存，放在内存的某一固定区，有较高的保护级别，一般用户不允许进入。而一般用户的用户文件是在另外管辖的可用区有空闲时才能被调入指定的内存用户区

2. 文件分类 按文件性质与用途分类 按操作保护分类 按使用情况分类 按用户观点分类(UNIX或Linux操作系统) 按存取的物理结构分类 按文件中的数据形式分类

1) 按性质和用途分类 用户文件 系统文件 库文件 由系统软件构成的文件，只允许用户通过系统调用或系统提供的专用命今来执行它们，不允许对其进行读写和修改 主要有操作系统核心和各种系统应用程序或实用工具程序和数据组成 例如：ibmbio.com,ibmdos.com,\comand.com,/unix 库文件 文件允许用户对其进行读取和执行，但不允许对其进行修改 主要由各种标准子程序库组成 例如：C语言、FORTRAN子程序库存放在子目录下 *.LIB,/lib/,/usr/lib/ 用户文件 是用户通过操作系统保存的用户文件，由文件的所有者或所有者授权的用户才能使用 主要由用户的源程序源代码、可执行目标程序的文件和用户数据库数据等组成 例如：*.c,*.for,*.f,*DBF,*.OBJ

2) 按操作保护分类 只读文件：只允许文件主及被核准的用户去读文件，而不允许写文件。标记为：-r----- 可读可写文件：允许文件主及被核准的用户去读和写文件。标记为： -rw---- 可执行文件：允许文件主及被核准的用户去调用执行该文件而不允许读和写文件，标记为： ---x--- 各个操作系统的保护方法和级别有所不同 DOS操作系统三种保护：系统、隐藏、可写 UNIX或Linux操作系统有九个级别的保护

3) 按使用情况分类 临时文件：用于系统在工作过程中产生的中间文件，一般有暂存的目录，正常工作情况下，工作完毕会自动删除，一旦有异常情况往往会残留不少临时文件 永久文件: 指一般受系统管理的各种系统和用户文件，经过安装或编辑、编译生成的文件，存放在软盘、硬盘或光盘等外存上 档案文件: 系统或一些实用工具软件包在工作过程中记录在案的文挡资料文件，以便查阅历史挡案

4) 按用户观点分类 普通文件(常规文件) 是指系统中最一般组织格式的文件，一般是字符流组成的无结构文件 目录文件 是由文件的目录信息构成的特殊文件，操作系统将目录也做成文件，便于统一管理 特殊文件（设备驱动程序） 在UNIX或Linux操作系统中，所有的输入输出外部设备都被看作特殊文件便于统一管理 操作系统会把对特殊文件的操作转接指向相应的设备操作，真正的设备驱动程序不包含在这特殊文件中，而是指向与链接到操作系统核心中存放在内存高端部分

5) 按存取的物理结构分类 顺序（连续）文件 链接文件 索引文件 文件中的纪录，顺序地存储到连续的物理盘块中，顺序文件中所记录的次序，与它们存储在物理介质上存放的次序是一致的 链接文件 文件中的纪录可存储在并不相邻接的各个物理块中，通过物理块中的链接指针组成一个链表管理，形成一个完整的文件,又称指针串连文件或直接存取文件 索引文件 文件中的纪录可存储在并不相邻接的各个物理块中，纪录和物理块之间通过索引表项按关键字存取文件，通过物理块中的索引表管理，形成一个完整的文件

6) 按文件的逻辑存储结构分类 有结构文件 无结构文件 由若干个记录所构成的文件，故又称为记录式文件 这是直接由字符序列所构成的文件，故又祢为流式文件

7) 按文件中的数据形式分类 源文件 目标文件 由源程序和数据构成的文件 一般是由美国信息交换标准码（ASCII）、EBCD码或汉字编码组成 由源程序经过相应的计算机语言编译程序编译，但尚未经过链接程序链接的目标代码所形成的文件 后缀名为“.OBJ”（DOS系统）或“.o”（UNIX或Linux操作系统）

3. UNIX系统的文件分类 UNIX将文件分为普通文件；目录文件；特殊文件（设备文件）三类 普通文件:包含的是用户的信息，一般为ASCII或二进制文件 目录文件:管理文件系统的系统文件 特殊文件: 字符设备文件：和输入输出有关，用于模仿串行I/O设备，例如终端，打印机，网络等 块设备文件：模仿磁盘 分类的目的：对不同文件进行管理,提高系统效率；提高用户界面友好性

第六章    文件管理 6．2文件逻辑结构

文件组织的两种观点 用户观点（逻辑结构）：研究的是用户思维中的抽象文件，也叫逻辑文件。其目的是为用户提供一种结构清晰、使用简便的逻辑组织。用户按此去存储、检索和加工处理有关文件信息。 实现观点（物理结构）：研究的是存储在物理设备介质上的实际文件，即物理文件。其目的是选择一些性能良好、设备利用率高的物理结构。系统按此和外部设备打交道，控制信息的传输。

6.2.1 文件逻辑结构的类型 有结构文件 定长记录 (2) 变长记录 顺序文件 (2) 索引文件 (3) 索引顺序文件

2. 无结构（流式）文件 流式文件是相关信息的有序集合，或者说是有一定意义的字符流。 对大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。 在UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。 好处：提供很大的灵活性

3. 记录式文件 记录式文件是由若干个记录组成，每个记录有一个键，可按键进行查找。记录式文件是有结构的文件。 文件：一个固定长度记录的序列，每条记录有其内部结构 组成记录按次序编号为record0,record1,...recordn。这种记录为逻辑记录，记录可以是定长或变长。

4. 定长记录与变长记录 定长记录： 所有记录长度相等 变长记录:记录长度不固定。 (a)固定长度记录 (b)可变长度记录

6.2.2 文件的存取方法 1.顺序存取方法： 定长记录： 读指针rptr——指向下一次读出的记录地址； 变长记录： 写指针wptr——指向下一次写入的记录地址。 读完指针做相应修改:rptr+m=>rptr 写完指针做相应修改:wptr+m=>wptr 变长记录： 每个记录长度存于记录前的单元中。 读完rptr+mi+1=>rptr

2. 对顺序文件的读/写操作 定长和变长记录文件

3. 顺序文件的优缺点 顺序文件的最佳应用是对记录进行批量存取时， 即每次要读或写一大批记录时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。 在交互应用的场合，如果用户要求查找或修改单个记录，系统要逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。 增加或删除一个记录较困难。

6.2.3 索引文件 对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址： Ai=i×L 对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则

索引文件的组织

6.2.4 索引顺序文件 索引顺序文件

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

2. 哈希(Hash)文件 Hash文件的逻辑结构

第六章    文件管理 6．3 存储介质

物理块与存储介质 物理块(块) 在文件系统中，文件的存储设备常常划分为若干大小相等的物理块。同时也将文件信息划分成相同大小的逻辑块（块），所有块统一编号。以块为单位进行信息的存储、传输，分配 存储介质:磁盘，磁带，光盘

1. 磁 带 永久保存大容量数据 顺序存取设备： 前面的物理块被存取访问之后, 才能存取后续的物理块的内容, 1. 磁 带 永久保存大容量数据 顺序存取设备： 前面的物理块被存取访问之后, 才能存取后续的物理块的内容, 存取速度较慢，主要用于后备存储， 或存储不经常用的信息，或用于 传递数据的介质

第i块 间隙 第i+1块

2. 磁 盘 直接（随机）存取设备： 存取磁盘上任一物理块的时间不依赖于该物理块所处的位置

扇区 磁道

扇区 磁臂 柱面 磁头

1) 磁道与柱面 信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头 所有盘面中处于同一磁道号上的所有磁道组成一个柱面 物理地址形式： 磁头号（盘面号） 磁道号（柱面号） 扇区号

2) 磁盘系统与磁盘分类 磁盘系统由磁盘本身和驱动控制设备组成，实际存取读写的动作过程是由磁盘驱动控制设备按照主机要求完成的 硬盘又分为两种： 固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高 移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低

3) 访盘请求完成过程 磁盘地址（设备号，柱面号，磁头号，扇区号），内存地址（源/目） 一次访盘请求（读/写）完成过程由三个动作组成： 寻道（时间）：磁头移动定位到指定磁道 旋转延迟（时间）：等待指定扇区从磁头下旋转经过 数据传输（时间）：数据在磁盘与内存之间的实际传输

3. 光 盘 光盘容量大，速度快，价格便宜，但一般不可写 可读写光盘驱动器价格贵，写过程很麻烦 光盘的空间结构与磁盘类似

4. 外存的特点 容量大，断电后仍可保存信息，速度较慢，成本较低 两部分组成：驱动部分+存储介质 种类很多 外存空间组织与地址与存取方式非常复杂 I/O过程方式非常复杂

5. 用户对外存的要求 用户对外存的使用：读写外存数据 用户对外存的要求：方便、效率、安全 (1) 在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作 (2) 存取速度尽可能快，容量大且空间利用率高 (3) 外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权 (4) 可以方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况 (5) 以尽可能小的代价完成上述要求

第六章    文件管理 6．4 文件的物理结构

文件的物理结构 文件的物理结构也即文件的外存分配方式。是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件

6.4.1 连续分配 一个文件的信息存放在若干连续的物理块中 由一组相邻的物理块组成，是对记录式文件取连续区分配而构成的文件。 优点: 简单 支持顺序存取和随机存取 顺序存取速度快 所需的磁盘寻道次数和寻道 时间最少

1. 连续文件结构

2. 连续文件 由一组相邻的物理块组成，是对记录式文件取连续区分配而构成的文件。 当文件逻辑记录和物理块大小相等时；假设，第i 个逻辑记录对应m块，则第i+n个记录对应==>m+n　 当记录与块不等时。则记录所在的块号＝[i*l/块长]取整+ 余数 例：逻辑记录　l=256 块　n=512存取i=3的记录　块号＝[256*3/512]=1 余0.5

3. 连续文件例 磁盘空间的连续分配

4. 连续分配的主要优缺点 连续分配的主要优点如下： 顺序访问容易 (2) 顺序访问速度快 连续分配的主要缺点如下： 要求有连续的存储空间 (2) 必须事先知道文件的长度

6.4.2 链接分配 一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块 优点：提高了磁盘空间利用率 不存在外部碎片问题 有利于文件插入和删除 有利于文件动态扩充 缺点：存取速度慢，不适于随机存取 可靠性问题，如指针出错 更多的寻道次数和寻道时间 链接指针占用一定的空间 链接结构的一个变形: 文件分配表FAT

1. 隐式链接 文件目录 文件名 始址 末址 jeep 9 25 磁盘空间的链接式分配 1 10 2 3 4 5 6 7 8 9 16 10 文件名 始址 末址 jeep 9 25 1 10 2 3 4 5 6 7 8 9 16 10 25 11 12 13 14 15 16 1 17 18 19 20 21 22 23 24 25 -1 26 27 28 29 30 31 磁盘空间的链接式分配

2. 显式链接 显式链接结构

6.4.3 索引分配 一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在一个索引表中 索引表：一个文件所有记录的关键字和其它地址的对照表。 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块

1. 单级索引分配  链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即： (1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。 (2) FAT需占用较大的内存空间。

文件目录 文件名 索引表地址 Jeep 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 9 16 1 10 25 -1 19

2. 索引表组织 链接模式:一个盘块一个索引表,多个索引表链接起来 多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中

3 索引结构优缺点 优点： 保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间 缺点： 较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间

4. 多级索引 以多级索引为例　记录数为K，物理块长度为N，满足N<K<=N2，可采用二级目录。设K=N2，需N+1索引块，每个索引中有N个表目 设：N=10 ， K=86 要存取i=74的记录，可通过： 1.确定第一级索引的表目 [i/N]取整=[74/10]取整=7； 2.确定在i=7的表目中的位置: mod  N==>74 mod  10=4

5. 多级索引分配 两级索引分配

混合索引方式 (综合模式)

6. 综合模式 UNIX文件系统采用的是多级索引结构(综合模式)。每个文件的索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址） 如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址 UNIX中采用了三级索引结构后，文件最大可达16兆个物理块

文件类型与文件存取器、存取方法的关系 存取设备 磁盘、磁鼓 磁带 文件类型 连续文件 串联文件 索引文件 Hssh文件 文件长度 固定 固定、可变 存取方法 直接、顺序 顺序

第六章    文件管理 6．5 目录管理

6.5 目录管理 对目录管理的要求如下： 实现“按名存取” (2) 提高对目录的检索速度 (3) 文件共享 (4) 允许文件重名

文件目录 文件目录：是文件系统中主要数据结构之一,文件存储后用户通过用户文件逻辑结构的索引链接找到对应的物理结构 按文件符号名把文件信息的逻辑结构映象设备介质的物理结构，由文件目录实现 把文件操作命令转换相应I/O指令。需要文件目录

6.5.1 文件控制块 文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。 文件控制块是文件存在的标志

1. 文件控制块的内容 (1)基本信息类 ① 文件名 ； ② 文件物理位置 ； ③ 文件逻辑结构 ； ④ 文件的物理结构 ① 文件名 ； ② 文件物理位置 ； ③ 文件逻辑结构 ； ④ 文件的物理结构 (2) 存取控制信息类 (3) 使用信息类 MS-DOS的文件控制块

2. 文件控制块包括的内容 文件名 文件设备 指向下一个PCB的指针 文件标识符 物理位置 当前共享的状态 文件结构 存取控制 共享访问时等待状态 文件类型 口令 进程访问文件所用的逻辑单元号 记录长度 文件建立时间 当前的逻辑位置 当前文件大小 上次存取时间 访问元素的当前物理位置 缓冲区大小 缓冲区地址 文件创建者 当前存取方式 文件拥有者 临时\永久文件 最大文件尺寸 上次修改时间 下一个元素的物理位置

3. FCB的创建过程 用户进程请求打开文件； 文件系统读出有关目录信息； 如有误，返回状态信息； 生成新的FCB； 更新目录信息； 将FCB挂到调用进程的PCB上； 向用户进程返回状态信息。

文件控制块的创建过程

6.5.2 索引结点 1) 索引结点的引入 文件名 索引结点编号 文件名1 文件名2 … … UNIX的文件目录

2) 磁盘索引结点 文件主标识符 (2) 文件类型 (3) 文件存取权限 (4) 文件物理地址 (5) 文件长度 (6) 文件连接计数 (7) 文件存取时间

3) 内存索引结点 (1) 索引结点编号。 用于标识内存索引结点。(2) 状态。 指示i结点是否上锁或被修改。 (4) 文件所属文件系统的逻辑设备号。 (5) 链接指针。 设置有分别指向空闲链表和散列队列的指针。

6.5.3 文件目录 把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合 目录项：构成文件目录的项目（目录项就是FCB） 目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件

1. 单级目录结构 为所有文件建立一个目录文件。单级目录的优点是简单且能实现目录管理的基本功能——按名存取。 缺点：(1) 查找速度慢 ; (2) 不允许重名 (3) 不便于实现文件共享 文件名 物理地址 文件说明 状态位 文件名1 文件名2 …

2. 二级目录结构 为改变一级目录文件目录命名冲突，并提高对目录文件检索速度而将目录分为两级：一级称为主文件目录，给出用户名，用户子目录所在的物理位置；二级称为用户文件目录，给出该用户所有文件的FCB 产生于多用户分时系统，DOS2.0版本以上采用，文件主目录（MFD）的表目按用户分，每个用户有一个用户文件目录（UFD） 优点：解决了文件的重名问题和文件共享问题，提高搜索速度，查找时间降低 缺点：缺点是不太适合大量用户和大量文件的大系统，增加了系统开销，

两级目录结构

3. 多级目录结构 多级目录结构也称树型目录 产生于UNIX操作系统，巳被现代操作系统广泛采用。目录与文件在一起，目录也做成文件 优点： 层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制 缺点： 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度

1) 多级目录结构 多级目录结构

2) 路径名 在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上从树的根(即主目录)开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名。系统中的每一个文件都有惟一的路径名。例如，在上图中用户B为访问文件J，应使用其路径名/B/F/J来访问。

3) 当前目录 为了提高文件检索速度，文件系统向用户提供了一个当前正在使用的目录，称为当前目录（也称工作目录或值班目录）。查找一个文件可从当前目录开始，使用部分路径名 当前目录可根据需要任意改变。 当前目录一般存放在内存

4. 增加和删除目录 (2) 可删除非空目录。当要删除一目录时，如果在该目录中还包含有文件，则目录中的所有文件和子目录也同时被删除。 (1) 不删除非空目录。当目录(文件)不空时， 不能将其删除，而为了删除一个非空目录，必须先删除目录中的所有文件，使之先成为空目录，后再予以删除。如果目录中还包含有子目录，还必须采取递归调用方式来将其删除，在MS-DOS中就是采用这种删除方式。 (2) 可删除非空目录。当要删除一目录时，如果在该目录中还包含有文件，则目录中的所有文件和子目录也同时被删除。

6.5.4 目录查询技术 1. 线性检索法 查找/usr/ast/mbox的步骤

2. Hash方法 一种处理“冲突”的有效规则是：

6.5.5 文件目录的管理 目录做成文件，文件系统便于内部统一管理,目录文件在使用时调入内存 打开文件：把当前用户要使用的某个文件的有关目录表目复制到内存。 OPEN "文件名" 关闭文件：文件不用时，系统将其在主存中相应的目录表目删去，切断用户和文件的联系。 CLOSE "文件名"

1.文件目录检索 访问文件包括： 目录检索：用户给出文件名，按名寻找目录项 根据路径名检索： 全路径名：从根开始 相对路径：从当前目录开始 文件寻址：根据FCB中文件物理地址等信息，求出文件的任意记录或字符在存取介质上的地址，称为文件寻址

2. 文件目录改进 为加快目录检索可采用目录项分解法：把FCB分成两部分： 符号目录顶（次部） 文件名，文件号 基本目录项（主部） 除文件名外的所有项目 UNIX：I节点（索引节点）

3. 符号目录与基本目录

第六章    文件管理 6．6 文件存储空间的管理

6.6.1 外存空间管理 1. 空闲块表（空白文件目录） 将所有空闲块记录在一个表中，即空闲块表 2. 空闲块链表 把所有空闲块链成一个链 3. 位图法 用一串二进制位反映磁盘空间中分配使用情况, 每个物理块对应一位, 分配物理块为1，否则为0

1. 空白的文件目录 一个连续的未分配区域称为“空白文件” ，系统为所有这些“空白文件”单独建立一个目录。每个空白文件，在目录中建立一个表目。表目的内容包括：第一空白物理块的地址（块号）、空白块的数目。 当请求分配存储空间时，系统依次扫描空白文件目录的表目，直到找到一个合适的空白文件为止 当用户撤消一个文件时，系统回收该文件所占用的空间。扫描目录，寻找一个空表目，并将释放空间的第一物理号及它所占的物理块数填到这个表目中。

空白的文件目录（续） 仅当有少量的空白区时才有较好的效果 如果存取空间中有着大量的小的空白区，则其目录变得很大，因而效率大为降低。 序号 第一空白块号 空白块个数 物理块号 1 2 4 （2，3，4，5） 9 3 （9，10，11） 15 5 （15，16，17，18，19） — 仅当有少量的空白区时才有较好的效果 如果存取空间中有着大量的小的空白区，则其目录变得很大，因而效率大为降低。 这种分配技术适用于建立连续文件。

2. 空闲块链 创建文件需要一个或几个物理块时，就从链头依次取下一块或几块。 回收文件时回收块链到空白链上。 把其中所有的“空白块” 链在一起。 创建文件需要一个或几个物理块时，就从链头依次取下一块或几块。 回收文件时回收块链到空白链上。

3 位示图法 常用的管理存储空间的办法是建立一张位示图，以反映整个存取空间的分配请况 用一串二进制位反映磁盘空间中分配使用情况, 每个物理块对应一位, "1"表示对应的物理块已分配，"0"表示其对应的块未分配 申请物理块时，可以在位示图中查找为0的位，返回对应物理块号 归还时；将对应位转置0 描述能力强，适合各种物理结构

1) 位示图 位示图

2) 盘块的分配 (1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。 (2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j 式中，n代表每行的位数。 (3) 修改位示图， 令map［i,j］=1。

3) 盘块的回收 (1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修改位示图。 令map ［i,j］=1。

6.6.2 成组链接法 1. 空闲盘块的组织 空闲盘块的成组链接法

2. 空闲盘块的分配与回收 当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。 然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。

在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。

第六章    文件管理 6.7 文件共享和保护

6.7.1. 文件共享 文件共享形式与目的 1）定义 : 一个文件被多个用户或程序使用 2）共享形式： 被多个用户使用，由存取权限控制 被多个程序使用，但各用自己的读写指针 被多个程序使用，但共享读写指针 多个用户用相同或不同的名字来访问同一文件。 3）目的:节省时间和存储空间，减少了用户工作量；进程间通过文件交换信息

2.文件共享的实现 1)建立值班目录 由系统目录实现对文件的共享 用户通过全路径名共享地访问这些文件 2)采用链访技术对要共享的文件进行连接: 通过“连接（Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，即建立两个文件的等价关系

3) 基于索引结点的共享方式 将文件的物理地址和文件属性等信息放在索引结点中，在文件目录中，设文件名及指向索引结点的指针，另外在索引结点中增加链接计数count,表示共享的用户数删除时必须count=0，方可。

基于索引结点的共享方式

进程B链接前后的情况

3. 利用符号链实现文件共享 共享某文件时，创建一新文件，并加到用户目录中，该文件仅包含被链接文件F的路径名，称该链接方法为符号链接。该方式中，只有文件才拥有指向其索引结点的指针，其它共享的用户只有该文件的路径名。

4.符号链实现文件共享优缺点 优点：方便地链接任一文件（用路径名） 缺点：访问共享文件时开销大（多次读盘，消费盘空间），每一共享文件都要增加一文件名（因路径名各不相同）

5. UNIX实例 Link(A/F,B/C) 在B目录中建立一个新表目，并在文件F所对应的目录表目中的“连接数”项加1 文件名 内部标识号

6.7.2 文件的保护机制 文件保护用于提供安全性的特定的操作系统机制。 对拥有权限的用户，应该让其进行相应操作，否则，应禁止 防止其他用户冒充对文件进行操作 实现： * 用户验证 * 存取控制

6.7.3 磁盘容错技术 (2) 通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。 6.7.3 磁盘容错技术 (1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。 (2) 通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。 (3) 通过“后备系统”来防止由自然因素所造成的不安全性。

1.第一级容错技术SFT－I 采用双份目录，双份文件分配表及写后读校验等。FAT（文件分配表）：记录文件属性，物理地址等。系统每次启动时，对两份FAT检查是否一致。 修复重定向：在磁盘中划出一部分作为热修复重定向区，存放坏磁道的待写数据 写后读校验：内存—（写）盘时，从盘读出与内存校验看是否一致，不一致，重写入热修复重定向区，标记坏盘块。

2. 第二级容错技术SFT-II 1)磁盘镜像：增设一个完全相同的磁盘驱动器。 优点：磁盘驱动器发生故障时切换，仍能正常工作。 缺点：磁盘的利用率为50％。 磁盘镜像示意图

2) 磁盘双工(Disk Duplexing) 将两台磁盘驱动器分别接两个磁盘控制器。 特点：每个磁盘有自己独立的通道，可同时将数据写入，加块数据读取速度。 图 6-27 磁盘双工示意

3. 廉价磁盘冗余阵列 利用一磁盘阵列控制器，统一管理和控制一组磁盘驱动器 并行交叉存取，传输时间大大减少 RAID分级，可靠性高，磁盘I/O速度高，性能/价格比高 最简单的RAID组织方式：镜像 最复杂的RAID组织方式：块交错校验

磁盘0 磁盘1 数据1 的备份 数据0 的备份 数据0 数据1 CPU

1. 第一级容错技术SFT-Ⅰ 1) 双份目录和双份文件分配表 在磁盘上存放的文件目录和文件分配表FAT， 是文件管理所用的重要数据结构。如果这些表格被破坏，将导致磁盘上的部分或全部文件成为不可访问的，因而也就等效于文件的丢失。为了防止这类情况发生，可在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和FAT。其中，一份被称为主目录及主FAT；把另一份称为备份目录及备份FAT。

2) 热修复重定向和写后读校验 热修复重定向(Hot-Redirection)。 (2) 写后读校验(Read after write Verification)方式。

第六章    文件管理 6．8 数据一致性控制

6.8.1 事务 1. 事务的定义 事务是用于访问和修改各种数据项的一个程序单位。 事务也可以被看作是一系列相关读和写操作。

2. 事务记录(Transaction Record) ·事务名：用于标识该事务的惟一名字； ·数据项名：它是被修改数据项的惟一名字； ·旧值：修改前数据项的值； ·新值：修改后数据项将具有的值。

3. 恢复算法 恢复算法可利用以下两个过程： (1) undo〈Ti〉：该过程把所有被事务Ti修改过的数据，恢复为修改前的值。 (2) redo〈Ti〉：该过程能把所有被事务Ti修改过的数据，设置为新值。 如果系统发生故障，系统应对以前所发生的事务进行清理。

6.8.2 检查点 对事务记录表中事物记录的清理工作经常化。当出现检查点时，利用undo/redo过程实现恢复功能。 6.8.2 检查点 1. 检查点(Check Points)的作用 对事务记录表中事物记录的清理工作经常化。当出现检查点时，利用undo/redo过程实现恢复功能。

2. 新的恢复算法 恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。并利用redo和undo过程对它们进行处理。 如果把所有在事务Ti以后开始执行的事务表示为事务集T， 则新的恢复操作要求：对所有在T中的事务TK, 如果在事务记录表中出现了〈TK托付〉记录，则执行redo〈TK〉操作；反之，如果在事务记录表中并未出现〈TK托付〉记录，则执行undo〈TK〉操作。

6.8.3 并发控制 利用互斥锁实现“顺序性” 利用互斥锁和共享锁实现顺序性（共享锁允许多个事务对相应对象执行读操作，而不允许执行写操作。）

6.8.4 重复数据的数据一致性问题 1. 重复文件的一致性 UNIX类型的目录

2. 盘块号一致性的检查 检查盘块号一致性情况

检查盘块号一致性情况

3. 链接数一致性检查 为每个盘块建立一个表项，记录该索引结点号的计数值。检查时，从根目录开始查找，当在目录中遇到该索引结点号时，在该计数器表中相应文件的表项上加1。检查完后，将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较，如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。 当链接计数count值大于或小于计数器表中索引结点号计数值的情况时，解决的方法是将count值置为正确值。

The End