第7章 文件管理

1、课程主要内容课程主要内容 操作系统引论（第操作系统引论（第1 1章）章） 处理机管理（第处理机管理（第2-42-4章）章） 存储器管理（第存储器管理（第5 5章）章） 设备管理（第设备管理（第6 6章）章） 文件管理文件管理（第（第7 7章）章） 第第7章章 文件管理文件管理 q文件系统的功能文件系统的功能/ /需解决的问题需解决的问题 v从系统角度看：从系统角度看： 负责为用户建立、删除、读、写、修负责为用户建立、删除、读、写、修 改和复制文件。改和复制文件。 v从用户的角度看：从用户的角度看： 实现了按名存取实现了按名存取 文件系统的功能：提供高效、快速、方便的文件系统的功能：提供高效、快

2、速、方便的 信息存储和访问功能。信息存储和访问功能。 n文件和文件系统文件和文件系统 n文件逻辑结构文件逻辑结构 n外存分配方式外存分配方式 n目录管理目录管理 n文件存储空间的管理文件存储空间的管理 n文件共享与文件保护文件共享与文件保护 n数据一致性控制数据一致性控制 n本章习题本章习题 第第7章章 文件管理文件管理 P文件文件 P文件类型和文件系统模型文件类型和文件系统模型 P文件操作文件操作 7.1 文件和文件系统文件和文件系统 一、文件一、文件 n文件文件 n是指记录在外存上的具有文件名的一组相关信是指记录在外存上的具有文件名的一组相关信 息的集合。可分为息的集合。可分为有结构文件有

3、结构文件和和无结构文件无结构文件两两 种。有结构文件由若干个相关记录组成，而无种。有结构文件由若干个相关记录组成，而无 结构文件则被看成一个字符流。结构文件则被看成一个字符流。 n文件属性文件属性 n文件名、文件类型、文件长度、文件的物理位文件名、文件类型、文件长度、文件的物理位 置、文件的建立日期以及用户对该文件的存取置、文件的建立日期以及用户对该文件的存取 权限等权限等 二、文件类型（二、文件类型（1） -文件名文件名.扩展名扩展名 n按用途分类按用途分类 n系统文件系统文件- -由系统软件构成的文件由系统软件构成的文件 n用户文件用户文件- -用户的源代码、目标文件、可执行文件用户的源代

4、码、目标文件、可执行文件 或数据或数据 n库文件库文件- -由标准子例程和常用的例程构成由标准子例程和常用的例程构成 n按数据形式分类按数据形式分类 n源文件源文件 n目标文件目标文件 n可执行文件可执行文件 n按存取控制属性按存取控制属性 n只读文件只读文件 n读写文件读写文件 n只执行文件只执行文件 二、文件类型（二、文件类型（2） -文件名文件名.扩展名扩展名 n按组织形式和处理方式分类按组织形式和处理方式分类 普通文件普通文件- -由由ASCIIASCII码或二进制码组成的字符文件码或二进制码组成的字符文件 目录文件目录文件- -由文件目录组成，用来管理和实现文由文件目录组成，用来管理

5、和实现文 件系统功能的系统文件件系统功能的系统文件 特殊文件特殊文件- -特指系统中的各类特指系统中的各类I/OI/O设备设备 n按文件的逻辑结构分类按文件的逻辑结构分类 有结构文件（记录式文件）有结构文件（记录式文件） 无结构文件（流式文件）无结构文件（流式文件） n按文件的物理结构分类按文件的物理结构分类 顺序文件顺序文件 链接文件链接文件 索引文件索引文件 三、文件系统模型（三、文件系统模型（1） 文件系统接口（文件系统接口（命令接口、系统调用接口命令接口、系统调用接口） 对对象操纵对对象操纵 和管理的软和管理的软 件集合件集合 对象对象( (文件、目录及磁盘存储空间文件、目录及磁盘存储

6、空间) )及其属性说明及其属性说明 用户（程序）用户（程序） 对文件存储空间的管理对文件存储空间的管理 对文件目录的管理对文件目录的管理 将文件的逻辑地址转换为物理地址的机制将文件的逻辑地址转换为物理地址的机制 对文件的读和写管理对文件的读和写管理 对文件的共享和保护对文件的共享和保护 三、文件系统模型（三、文件系统模型（2） 1) 1) 对象及其属性对象及其属性 文件管理系统管理的对象有：文件管理系统管理的对象有： 文件：它作为文件管理的直接对象。文件：它作为文件管理的直接对象。 目录：为了方便用户对文件的存取和检索，目录：为了方便用户对文件的存取和检索， 在文件系统中必须配置目录。对目录的

7、组织和管理在文件系统中必须配置目录。对目录的组织和管理 是方便用户和提高对文件存取速度的关键。是方便用户和提高对文件存取速度的关键。 磁盘磁盘( (磁带磁带) )存储空间：文件和目录必定占用存储空间：文件和目录必定占用 存储空间，对这部分空间的有效管理，不仅能提高存储空间，对这部分空间的有效管理，不仅能提高 外存的利用率，而且能提高对文件的存取速度。外存的利用率，而且能提高对文件的存取速度。 三、文件系统模型（三、文件系统模型（3） 2)2) 对对象操纵和管理的软件集合对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功这是文件管理系统的核心部分。文件系统的功 能大多是在这一层

8、实现的，其中包括：能大多是在这一层实现的，其中包括： n对文件存储空间的管理对文件存储空间的管理 n对文件目录的管理对文件目录的管理 n用于将文件的逻辑地址转换为物理地址的机制用于将文件的逻辑地址转换为物理地址的机制 n对文件读和写的管理对文件读和写的管理 n对文件的共享与保护等功能对文件的共享与保护等功能 三、文件系统模型（三、文件系统模型（4） 3)3) 文件系统的接口文件系统的接口 为方便用户使用文件系统，文件系统通常向用为方便用户使用文件系统，文件系统通常向用 户提供两种类型的接口：户提供两种类型的接口： 命令接口。这是指作为用户与文件系统交互命令接口。这是指作为用户与文件系统交互 的

9、接口。的接口。 用户可通过键盘终端键入命令，取得文用户可通过键盘终端键入命令，取得文 件系统的服务。件系统的服务。 程序接口（系统调用接口）。这是指作为用程序接口（系统调用接口）。这是指作为用 户程序与文件系统的接口。户程序与文件系统的接口。 用户程序可通过系统用户程序可通过系统 调用来取得文件系统的服务。调用来取得文件系统的服务。 四、文件操作四、文件操作 用户通过文件系统所提供的系统调用实施对用户通过文件系统所提供的系统调用实施对 文件的操作。最基本的操作有：文件的操作。最基本的操作有： q对文件的操作对文件的操作 最基本的：创建、最基本的：创建、打开打开、关闭关闭、删除、读、删除、读、

10、写写 其它的：文件属性类操作、目录类操作其它的：文件属性类操作、目录类操作 7.2 7.2 文件逻辑结构文件逻辑结构 文件系统设计的关键要素：文件系统设计的关键要素： 对任一文件存在着两种形式的结构：对任一文件存在着两种形式的结构： P文件的逻辑结构文件的逻辑结构（文件的组织）（文件的组织） 从用户观点出发，所观察到的从用户观点出发，所观察到的文件组织形式文件组织形式，是用户，是用户 可以直接处理的数据及结构，它独立于物理特性。可以直接处理的数据及结构，它独立于物理特性。 P文件的物理结构文件的物理结构（文件的存储结构）（文件的存储结构） 是指文件在外存上的是指文件在外存上的存储组织形式存储组

11、织形式，与存储介质的存，与存储介质的存 储性能有关，还和所采用的外存分配方式有关。（分为顺储性能有关，还和所采用的外存分配方式有关。（分为顺 序、链接及索引结构）序、链接及索引结构） 注：文件的逻辑结构和物理结构都将影响文件的检索速度。注：文件的逻辑结构和物理结构都将影响文件的检索速度。 数据构成文件的方法数据构成文件的方法 将文件存储到外存的方法将文件存储到外存的方法 7.2 7.2 文件逻辑结构文件逻辑结构 对文件的逻辑结构提出的基本要求：对文件的逻辑结构提出的基本要求： 提高检索速度；提高检索速度； 便于修改；便于修改； 降低文件存储费用。降低文件存储费用。 P文件逻辑结构的类型文件逻辑

12、结构的类型 P文件存取方法文件存取方法 一、文件逻辑结构的类型（一、文件逻辑结构的类型（1） P有结构的记录式文件有结构的记录式文件 文件构成：由一个以上的记录构成。文件构成：由一个以上的记录构成。 记录长度：分为定长和变长。记录长度：分为定长和变长。 分类：分类： 连续结构连续结构 多重结构多重结构 转置结构转置结构 顺序结构顺序结构 一、文件逻辑结构的类型（一、文件逻辑结构的类型（2） P无结构的流式文件无结构的流式文件 文件构成：由字符流构成。大量的源程序、文件构成：由字符流构成。大量的源程序、 可执行可执行 文件、文件、 库函数等，库函数等， 所采用的就是无结构的文件形式，所采用的就是

13、无结构的文件形式， 即流式文件。即流式文件。 长度：以字节为单位（通用计算机寻址的最小单位）长度：以字节为单位（通用计算机寻址的最小单位） 访问：对流式文件的访问，则是采用读写指针来指出访问：对流式文件的访问，则是采用读写指针来指出 下一个要访问的字符。下一个要访问的字符。 好处：更加方便、OS代码更加可靠、灵 活，用户编程也更加方便 连续结构连续结构 n连续结构是一种把记录按生成的先后顺序连续排连续结构是一种把记录按生成的先后顺序连续排 列的逻辑结构。列的逻辑结构。 n优点：是适用性强，可用于所有文件优点：是适用性强，可用于所有文件（字符流式的（字符流式的 无结构文件实质上记录长度为一个字符

14、的连续结构文件）无结构文件实质上记录长度为一个字符的连续结构文件）, , 且记录的排列顺序与记录的内容无关。这有利于且记录的排列顺序与记录的内容无关。这有利于 记录的追加与变更。记录的追加与变更。 n缺点：连续结构文件的搜索性能较差，例如要找缺点：连续结构文件的搜索性能较差，例如要找 出某个指定键的记录时，系统必须对文件全体进出某个指定键的记录时，系统必须对文件全体进 行搜索。行搜索。 如果把记录按键和记录名排列成行列式结构，则如果把记录按键和记录名排列成行列式结构，则 一个包含一个包含n n个记录名、个记录名、m m个个(mn)(mn)个键的文件构成个键的文件构成 m mn n维行列式。维行

15、列式。 R1 R2 RN 0 1 0 11 1 0 j i K1 K2 Km 元素元素a aijij为为0 0表示键表示键KiKi不包含在记录不包含在记录R Rj j中。中。 元素元素a aijij为为1 1表示键表示键K Ki i包含在记录包含在记录R Rj j中。中。 特点：特点：用行列式方法浪费存储空间用行列式方法浪费存储空间( (稀稀 疏矩阵疏矩阵) )。 多重结构多重结构 多重结构：如果把记录按键组成记录队列多重结构：如果把记录按键组成记录队列( (如下如下 图）则一个包含图）则一个包含n n个记录名、个记录名、m m个个(mn)(mn)个键的个键的 文件构成文件构成m m个队列，无

16、个队列，无0 0项，这项，这m m个队列构成文件个队列构成文件 的多重结构。的多重结构。 特点：多重结构比连续结构在由给定键的记录特点：多重结构比连续结构在由给定键的记录 搜索速度方面要快。比用行列式节约存储空间搜索速度方面要快。比用行列式节约存储空间 。 多重结构多重结构 转置结构转置结构 n转置结构：把含有相同键的记录指针全部指向该转置结构：把含有相同键的记录指针全部指向该 键键( (不再队列排序不再队列排序) )，也就是说，把所有与同一键，也就是说，把所有与同一键 对应的记录的指针对应的记录的指针连续地置于目录中该键的位置连续地置于目录中该键的位置 下下 n特点：转置结构最适合于由给定键

17、的记录搜索。特点：转置结构最适合于由给定键的记录搜索。 顺序结构顺序结构 n顺序结构：把文件中的键按规定的顺序排列起来。顺序结构：把文件中的键按规定的顺序排列起来。 n特点：如果系统要求按某种优先顺序来搜索或追特点：如果系统要求按某种优先顺序来搜索或追 加、删除记录，则最好采用顺序结构。加、删除记录，则最好采用顺序结构。 二、文件的存取方法二、文件的存取方法 n用户通过对文件的存取来完成对文件的修改、追用户通过对文件的存取来完成对文件的修改、追 加和搜索等操作。常用的存取方法有三种：加和搜索等操作。常用的存取方法有三种： n顺序存取法顺序存取法 n随机存取法（直接存取法）随机存取法（直接存取法

18、） n按键存取法按键存取法 顺序存取法顺序存取法 n是按照文件的是按照文件的逻辑地址逻辑地址顺序存取。顺序存取。 n记录式文件：当前记录记录式文件：当前记录RiRi，则下一次读写自动，则下一次读写自动 定位为定位为Ri+1Ri+1。 n字符流文件：当前读写指针读取完一段信息后，字符流文件：当前读写指针读取完一段信息后， 自动加减该信息段长度，指出下次存取位置。自动加减该信息段长度，指出下次存取位置。 随机存取法随机存取法 n允许用户根据允许用户根据记录编号记录编号来存取文件的任一记录，来存取文件的任一记录， 或者是根据存取命令把或者是根据存取命令把读写指针读写指针移到欲读写处来移到欲读写处来

19、读写。读写。 按键存取法按键存取法 n文件的存取是根据文件的存取是根据给定的键给定的键或或记录名记录名进行的。多进行的。多 用于数据库文件。用于数据库文件。 7.37.3 外存分配方式外存分配方式 n文件的物理结构即文件的外存分配方式，是从系文件的物理结构即文件的外存分配方式，是从系 统的角度来看文件，从文件在物理介质上的存放统的角度来看文件，从文件在物理介质上的存放 方式来研究文件。方式来研究文件。 n要考虑的主要问题：要考虑的主要问题： n目前常用的外存分配方法：目前常用的外存分配方法： （1 1）连续分配（顺序分配）连续分配（顺序分配） 顺序文件结构顺序文件结构 （2 2）链接分配）链接

20、分配 链接文件结构链接文件结构 （3 3）索引分配）索引分配 索引文件结构索引文件结构 如何有效地利用外存空间如何有效地利用外存空间 如何提高对文件的访问速度如何提高对文件的访问速度 外存分配单位外存分配单位 n存储介质（如磁盘）与内存交换数据的单位是存储介质（如磁盘）与内存交换数据的单位是物物 理块（理块（512512或或10241024字节）字节），外存划分成大小相等的外存划分成大小相等的 若干物理块，文件信息也被划分成与物理块大小若干物理块，文件信息也被划分成与物理块大小 相等的相等的逻辑块逻辑块，外存以，外存以块为单位分配块为单位分配。文件的一。文件的一 逻辑块中信息装入外存一物理块中

21、。逻辑块中信息装入外存一物理块中。 n连续文件连续文件: :它是一种最简单的物理文件结构它是一种最简单的物理文件结构, ,它把它把 一个在逻辑上连续的文件信息依次存放到地址连一个在逻辑上连续的文件信息依次存放到地址连 续的物理块中。续的物理块中。 n优点优点: :算法简单，顺序访问速度快，查找速度快算法简单，顺序访问速度快，查找速度快 （逻辑块号和物理块号的转变简单，可随机访（逻辑块号和物理块号的转变简单，可随机访 问）。问）。 n缺点缺点: :预先说明长度，文件动态增长困难，易造成预先说明长度，文件动态增长困难，易造成 外存碎片（删除导致零头）问题。外存碎片（删除导致零头）问题。 （1 1）

22、外存分配方式）外存分配方式- -连续连续/ /顺序分配顺序分配 图：连续分配图：连续分配 （2 2）外存分配方式）外存分配方式- -链接分配链接分配 n用用非连续的物理块非连续的物理块来存放文件信息。这些非连续来存放文件信息。这些非连续 的物理块之间没有顺序关系，其中每一个物理块的物理块之间没有顺序关系，其中每一个物理块 设有一个设有一个指针指针，指向其后续连接的另一物理块，指向其后续连接的另一物理块， 从而使得存放同一文件的物理块连接成一个串联从而使得存放同一文件的物理块连接成一个串联 队列。队列。 n特点特点: :外存可采用离散分配，解决了碎片问题，但外存可采用离散分配，解决了碎片问题，但

23、 搜索效率低，只适合于顺序存取方式，不适合随搜索效率低，只适合于顺序存取方式，不适合随 机存取（通过位置编号直接存取）机存取（通过位置编号直接存取） 图：链接分配图：链接分配 （3 3）外存分配方式外存分配方式- -索引分配索引分配 n索引结构要求系统为每个文件建立一张索引结构要求系统为每个文件建立一张索引表索引表， 表中每一栏目指出文件信息所在的逻辑块号和与表中每一栏目指出文件信息所在的逻辑块号和与 之对应的物理块号。索引表的物理地址则由文件之对应的物理块号。索引表的物理地址则由文件 说明信息项给出。说明信息项给出。 n优点：索引结构既适用于顺序存取，也适用于随优点：索引结构既适用于顺序存取

24、，也适用于随 机存取。机存取。也易于进行文件的增删。也易于进行文件的增删。 n缺点：是由于使用了索引表而增加了存储空间的缺点：是由于使用了索引表而增加了存储空间的 开销。开销。另外索引表的查找策略对文件系统的效率另外索引表的查找策略对文件系统的效率 影响很大。影响很大。 多重索引多重索引 n当文件很大时，文件的索引表也会很大。如果索当文件很大时，文件的索引表也会很大。如果索 引表的大小超过了一个物理块时，可以将索引表引表的大小超过了一个物理块时，可以将索引表 作为一个文件，再为其建立一个作为一个文件，再为其建立一个“索引表索引表”，这，这 个个“索引表索引表”作为文件索引的索引，从而构成了作为

25、文件索引的索引，从而构成了 二级索引。以此类推可再逐级建立索引，进而构二级索引。以此类推可再逐级建立索引，进而构 成多级索引。成多级索引。 7.4 7.4 目录管理目录管理 对文件目录的管理要求对文件目录的管理要求 P实现实现“按名存取按名存取” P提高对目录的检索速度提高对目录的检索速度 P文件共享文件共享 P允许文件重名允许文件重名 7.4 7.4 目录管理目录管理 P文件控制块和索引结点文件控制块和索引结点 P单级目录结构单级目录结构 P两级目录结构两级目录结构 P树型目录结构树型目录结构 文件控制块和索引结点文件控制块和索引结点 从文件管理角度看，文件由从文件管理角度看，文件由FCBF

26、CB和文件体（文和文件体（文 件本身）两部分组成。件本身）两部分组成。 n文件控制块（文件控制块（FCB-File Control BlockFCB-File Control Block） n文件控制块是操作系统为管理文件而设置的数文件控制块是操作系统为管理文件而设置的数 据结构，存放了文件的据结构，存放了文件的有关说明信息有关说明信息，记录了，记录了 系统对文件进行管理所需要的全部信息。系统对文件进行管理所需要的全部信息。 nFCBFCB是文件存在的标志。是文件存在的标志。 nFCBFCB保存在文件目录中，一个保存在文件目录中，一个FCBFCB就是一个目录就是一个目录 项。项。 文件控制块和

27、索引结点文件控制块和索引结点 n文件控制块（文件控制块（FCBFCB）（续）（续） nFCBFCB中的信息中的信息 基本信息类：文件名、文件长度、类型、属基本信息类：文件名、文件长度、类型、属 性、文件物理位置性、文件物理位置 存取控制信息类：文件存取权限、用户名、存取控制信息类：文件存取权限、用户名、 口令、共享计数口令、共享计数 使用信息类：文件的建立日期、最后修改日使用信息类：文件的建立日期、最后修改日 期、保存期限、最后访问日期期、保存期限、最后访问日期 文件控制块（文件控制块（FCBFCB） n文件目录文件目录 把所有的把所有的FCBFCB组织在一起，就构成了文件目录，组织在一起，就

28、构成了文件目录， 即文件控制块的有序集合。即文件控制块的有序集合。 n目录项目录项 构成文件目录的项目（目录项就是构成文件目录的项目（目录项就是FCBFCB） n目录文件目录文件 为了实现对文件目录的管理，通常将文件目录为了实现对文件目录的管理，通常将文件目录 以文件的形式保存在外存，这个文件就叫目录文件。以文件的形式保存在外存，这个文件就叫目录文件。 索引结点索引结点 n索引结点索引结点 n索引结点引入索引结点引入 设目录文件所占的盘块数是设目录文件所占的盘块数是 N N，则查找一个目录项平均，则查找一个目录项平均 需要调入盘块（需要调入盘块（N+1N+1）/2/2次。假设一个次。假设一个F

29、CBFCB为为64B,64B, 盘块大小为盘块大小为1KB1KB，则每个盘块中只能存放，则每个盘块中只能存放 1KB/64B=161KB/64B=16个个FCB;FCB;若一个文件目录共有若一个文件目录共有640640个个FCBFCB， 需占用需占用640/16=40640/16=40个盘块，平均查找一个文件需个盘块，平均查找一个文件需 启动磁盘启动磁盘2020次。次。 文件名文件名索引结点编号索引结点编号 文件名文件名1 1 文件名文件名2 2 索引结点索引结点 n索引结点索引结点 n索引结点引入索引结点引入 在目录检索的过程中，只用到了文件名，仅当找到在目录检索的过程中，只用到了文件名，仅

30、当找到 一个目录项时，才需从该目录项中读出文件的物一个目录项时，才需从该目录项中读出文件的物 理地址。理地址。 UNIXUNIX系统中，采用了把文件名和文件描述信息分开系统中，采用了把文件名和文件描述信息分开 的方法，把文件描述信息单独形成一个数据结构，的方法，把文件描述信息单独形成一个数据结构， 叫叫索引结点索引结点。 文件名文件名索引结点编号索引结点编号 文件名文件名1 1 文件名文件名2 2 索引结点索引结点 n索引结点索引结点 n索引结点引入索引结点引入 在文件目录中的每个目录项在文件目录中的每个目录项 仅由文件名和指向该文件所对应的仅由文件名和指向该文件所对应的i i结点（即索引结点

31、）结点（即索引结点） 的指针构成。的指针构成。 UNIXUNIX系统中，一个目录项只占系统中，一个目录项只占1616个字节（个字节（1414字节为文件名，字节为文件名， 2 2个字节为指向个字节为指向i i结点的指针）。在结点的指针）。在1KB1KB的盘块中可存放的盘块中可存放 1KB/16B=641KB/16B=64个目录项，如果一个文件目录中共有个目录项，如果一个文件目录中共有640640个目个目 录项，只占用录项，只占用640/64=10640/64=10个盘块，平均启动磁盘个盘块，平均启动磁盘10/2=510/2=5次，次， 减少到原来（平均启动减少到原来（平均启动2020次）的次）的

32、1/41/4，大大节省了开销。，大大节省了开销。 文件名 i 结点编号 单级目录结构单级目录结构 n在整个系统中只建立在整个系统中只建立一张目录表一张目录表 优点优点: : 简单，易实现按名存取简单，易实现按名存取 缺点缺点: : 限制了用户对文件的命名（即易重名）限制了用户对文件的命名（即易重名） 文件平均检索时间长文件平均检索时间长( (查找速度慢查找速度慢) ) 不便于实现文件共享，只适用于单用户环境不便于实现文件共享，只适用于单用户环境 文件名文件名状态位状态位物理地址物理地址文件其它属性文件其它属性 Alpha Report Text 两级目录结构两级目录结构 n在整个系统中建立两级

33、目录在整个系统中建立两级目录 n为每个用户建立一个单独的为每个用户建立一个单独的用户文件目录（用户文件目录（UFDUFD） n系统中为所有用户建立一个系统中为所有用户建立一个主文件目录（主文件目录（MFDMFD） 两级目录结构两级目录结构 优点优点: : n提高了检索目录的速度；提高了检索目录的速度； n不同用户目录中可重名；不同用户目录中可重名； n不同用户可用不同文件名来访问系统中一个不同用户可用不同文件名来访问系统中一个 共享文件共享文件 缺点缺点: : n增加了系统开销，缺乏灵活性，无法反映真增加了系统开销，缺乏灵活性，无法反映真 实世界复杂的文件结构形式。实世界复杂的文件结构形式。

34、树型目录结构（树型目录结构（1） n在两级目录中若允许用户建立自己的子目录，则在两级目录中若允许用户建立自己的子目录，则 形成形成3 3级或多级目录结构（即树型目录结构）级或多级目录结构（即树型目录结构） 树型目录结构（树型目录结构（2） 优点优点 n层次结构清晰层次结构清晰, ,实现分组实现分组, ,便于管理和保护；便于管理和保护； n解决重名问题；解决重名问题； n查找速度加快查找速度加快 缺点缺点 n查找一个文件按路径名逐层检查查找一个文件按路径名逐层检查, ,由于每个文件由于每个文件 都放在外存都放在外存, ,多次访盘影响速度多次访盘影响速度 7.57.5 文件存储空间的管理文件存储空

35、间的管理 n文件存储空间的管理实质上是一个文件存储空间的管理实质上是一个空闲块空闲块的组织的组织 和管理问题，它包括空闲块的组织，空闲块的分和管理问题，它包括空闲块的组织，空闲块的分 配与空闲块的回收等几个问题。配与空闲块的回收等几个问题。 n三种空闲块管理方法：三种空闲块管理方法： n空闲文件目录法（空闲块表法）空闲文件目录法（空闲块表法） n空闲块链法空闲块链法 n位示图法位示图法 n把文件存储设备中的空闲块的块号统一放在一把文件存储设备中的空闲块的块号统一放在一 个称为空闲文件目录的物理块中。其中空闲文个称为空闲文件目录的物理块中。其中空闲文 件目录的每个表项对应一个由多个空闲块构成件目

36、录的每个表项对应一个由多个空闲块构成 的空闲区。的空闲区。 区号区号首块号首块号块数块数块号块号 1 140405 540-4440-44 2 260603 360-6260-62 3 380806 680-8580-85 一、空闲文件目录法（一、空闲文件目录法（1） n存储空间的分配与回收存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是采用首空闲盘区的分配与内存的动态分配类似，同样是采用首 次适应算法、循环首次适应算法等。次适应算法、循环首次适应算法等。 例如，在系统为某新创建的文件分配空闲盘块时：例如，在系统为某新创建的文件分配空闲盘块时： 先顺序地检索空闲表的各表项，直至

37、找到第一个其大小先顺序地检索空闲表的各表项，直至找到第一个其大小 能满足要求的空闲区；能满足要求的空闲区； 再将该盘区分配给用户再将该盘区分配给用户( (进程进程) )，同时修改空闲表。，同时修改空闲表。 系统在对用户所释放的存储空间进行回收时：也采取类系统在对用户所释放的存储空间进行回收时：也采取类 似于内存回收的方法，即要考虑回收区是否与空闲表中插入似于内存回收的方法，即要考虑回收区是否与空闲表中插入 点的前区和后区相邻接，对相邻接者应予以合并。点的前区和后区相邻接，对相邻接者应予以合并。 一、空闲文件目录法（一、空闲文件目录法（2） 二、空闲块链法二、空闲块链法 n把文件存储设备上的所有

38、空闲块链接在一起。把文件存储设备上的所有空闲块链接在一起。 n有以下三种拉链方法：有以下三种拉链方法： 1、空闲块链、空闲块链：空闲块链中每一个节点是一个空：空闲块链中每一个节点是一个空 闲物理块。闲物理块。 3 5 3 10 5 15 10 free 2、空闲区链、空闲区链：以空闲区为单位拉链，一个空闲：以空闲区为单位拉链，一个空闲 区是若干个连续的物理块。区是若干个连续的物理块。 365431312112120 free 成组链接法成组链接法 3.3.成组链接法成组链接法 n空闲盘块的组织空闲盘块的组织 n将将空闲块的块号分组空闲块的块号分组，每组包含，每组包含n n个块号如个块号如:n=

39、50, :n=50, n=100n=100，并利用一组空闲块中的，并利用一组空闲块中的第一块第一块存放链中下一存放链中下一 组中的块号和块数，由此拉成一条链。组中的块号和块数，由此拉成一条链。 n链尾组链尾组: :下一组块号指针为下一组块号指针为0(0(链尾标志链尾标志) )， 实际块号实际块号 数只有数只有n-1n-1个。个。 n链首组链首组: :可能不足可能不足n n个块号，链首组存放在个块号，链首组存放在文件资源表文件资源表 （盘上专用区）中（盘上专用区）中, ,系统运行时系统运行时, ,存放在存放在内存空闲块号内存空闲块号 栈栈中。中。 成组链接法成组链接法 41 350 187 Su

40、per Block count 50 0 40 400 351 . 0 49 count 50 450 401 . 0 49 count 46 0 . . 0 45 count #350#400Last One . 310 49 50 成组链接法（分配和回收）成组链接法（分配和回收） n空闲盘块的分配与回收空闲盘块的分配与回收 n空闲块号成组链的链首组存放在空闲块号成组链的链首组存放在文件资源表文件资源表中中( (盘上专盘上专 用区用区) )，系统运行时链首组被装入，系统运行时链首组被装入内存空闲盘块栈内存空闲盘块栈中。中。 分配时将栈顶空闲块号弹出堆栈分配给文件使用。回收分配时将栈顶空闲块号

41、弹出堆栈分配给文件使用。回收 空闲块时，将空闲块号压入栈顶。分配回收过程中空闲块时，将空闲块号压入栈顶。分配回收过程中大部大部 分时间在内存栈分时间在内存栈中进行，不需访问外存。只有在中进行，不需访问外存。只有在分配时分配时 遇栈空或回收时遇栈满才需启动磁盘遇栈空或回收时遇栈满才需启动磁盘，以装入下一组块，以装入下一组块 号或将栈中一组块号写到磁盘。分配回收速度较快。号或将栈中一组块号写到磁盘。分配回收速度较快。 成组链接法示例（成组链接法示例（1 1） n例：已知磁盘上有例：已知磁盘上有1717个空闲块，块号依次为：个空闲块，块号依次为：1 1、3 3、5 5、7 7、 1414、1515、

42、1717、1818、1919、2323、2424、2525、2828、2929、3030、3232、3434， 请按请按5 5个块号为一组，成组拉链。个块号为一组，成组拉链。 n解：解：因因 17 5 = 3 2可知共应分为可知共应分为4组组，链尾组链尾组4个块号，个块号，链首组链首组3个块号个块号 第四组第四组 第三组第三组 第二组第二组 第一组第一组 1 3 5 3 7 14 15 17 18 5 19 23 24 25 28 5 29 30 32 34 0 5 0 1 2 3 4 5# 18# 28# 链首组链首组 链尾组链尾组 第第5块处的指块处的指 针指向的块针指向的块 成组链接法示

43、例（成组链接法示例（2 2） n为文件为文件A A分配两块之后，分配两块之后，1 1、3 3号空闲块依次出栈分配给文件号空闲块依次出栈分配给文件A A， 成组链变为成组链变为 7 14 15 17 18 5 5 1 19 23 24 25 26 5 29 30 32 34 0 5 0 1 2 3 S-free 内存栈中内存栈中 5# 第四组第四组 第三组第三组 第二组第二组 第一组第一组 内存空闲块栈成为第四组的映像内存空闲块栈成为第四组的映像 成组链接法示例（成组链接法示例（3 3） n接着接着A A又需又需2 2块，当前堆栈中只有一块号块，当前堆栈中只有一块号(5(5号号) )，需装入下一

44、，需装入下一 组块号到内存堆栈组块号到内存堆栈( (简称堆栈装入简称堆栈装入) )。执行过程如下：。执行过程如下： n将将5#5#存放的一组块号装入堆栈存放的一组块号装入堆栈 n将将5#5#块分给文件块分给文件A A n将将7#7#块分给文件块分给文件A A 0 1 2 3 4 S-free 内存栈中内存栈中 14 15 17 18 4 19 23 24 25 26 5 29 30 32 34 0 5 分配之分配之 后成组后成组 链的状链的状 态态 内存空闲块栈成为第三组的映像内存空闲块栈成为第三组的映像 成组链接法示例（成组链接法示例（4 4） n按着按着A A释放块号释放块号5 5，系统回

45、收该块号，成组链变为：，系统回收该块号，成组链变为： 5 14 15 17 18 5 19 23 24 25 26 5 29 30 32 34 0 5 0 1 2 3 4 5 S-free 内存栈中内存栈中18# 第三组第三组 第二组第二组 第一组第一组 26# 成组链接法示例（成组链接法示例（5 5） n按着按着A A释放块号释放块号1 1、3 3。由于内存栈已满一组块号，不能再压。由于内存栈已满一组块号，不能再压 入回收块号，需将栈中的一组块号写入回收的块号对应的物入回收块号，需将栈中的一组块号写入回收的块号对应的物 理块中理块中( (简称栈满腾空简称栈满腾空) )。 n回收块号回收块号1

46、 1、3 3之后之后. .成组链的状态成组链的状态 5 14 15 17 18 5 1 3 2 19 23 24 25 26 5 29 30 32 34 0 5 0 1 2 3 S-free 内存栈中内存栈中 1# 18# 26# 第四组第四组 第三组第三组 第二组第二组 第一组第一组 内存空闲块栈成为第四组的映像内存空闲块栈成为第四组的映像 成组链接法特点成组链接法特点 n不需额外的空间存储空闲块信息（自带指针）。不需额外的空间存储空闲块信息（自带指针）。 n分配和回收大部分时间在内存，速度快。分配和回收大部分时间在内存，速度快。 n启动一次磁盘可以读入或写出一组块号，减少启动一次磁盘可以读

47、入或写出一组块号，减少I/OI/O 次数。次数。 n只适合非连续分配（链接文件、索引文件）。只适合非连续分配（链接文件、索引文件）。 三、位示图法（三、位示图法（1 1） n用二进制一位来表示磁盘中一个盘块的使用情况。用二进制一位来表示磁盘中一个盘块的使用情况。mxnmxn数组数组 n盘块的分配盘块的分配 (1) (1) 顺序扫描位示图，从中找出一个或一组其顺序扫描位示图，从中找出一个或一组其 值为值为“0”0”的二进制位的二进制位(“0”(“0”表示空闲表示空闲) )。 (2) (2) 将所找到的一个或一组二进制位，转换成将所找到的一个或一组二进制位，转换成 与之相对应的盘块号。假定找到的值

48、为与之相对应的盘块号。假定找到的值为“0”0”的二的二 进制位，位于位示图的第进制位，位于位示图的第i i行、第行、第j j列，则其相应的列，则其相应的 盘块号（假设块号从盘块号（假设块号从1 1开始）应按下式计算：开始）应按下式计算： b=n(i-1)+jb=n(i-1)+j 式中，式中， n n代表每行的位数。代表每行的位数。 (3) (3) 修改位示图，令修改位示图，令mapmapi,ji,j=1=1。 三、位示图法（三、位示图法（2） n盘块的回收盘块的回收 (1) (1) 将回收盘块的盘块号转换成位示图中的将回收盘块的盘块号转换成位示图中的 行号和列号。行号和列号。 转换公式为：转换

49、公式为： i=(b-1)DIV n +1i=(b-1)DIV n +1 j=(b-1)MOD n +1 j=(b-1)MOD n +1 (2) (2) 修改位示图。修改位示图。 令令mapmapi,ji,j=0=0。 三、位示图法（三、位示图法（3） 7.67.6 文件共享文件共享 P文件共享：不同用户之间共同使用某些文件文件共享：不同用户之间共同使用某些文件 P早期实现文件共享的方法早期实现文件共享的方法 绕弯路法（低效）绕弯路法（低效） 允许每个用户获得一允许每个用户获得一“当前目录当前目录”，用户所，用户所 访问的所有文件均相对于当前目录，若不在，则访问的所有文件均相对于当前目录，若不在

50、，则 “向上走向上走”绕弯路去访问其上级目录，如图所示：绕弯路去访问其上级目录，如图所示： 连访法连访法 利用基本文件目录实现文件共享利用基本文件目录实现文件共享 P基于索引结点的共享方式基于索引结点的共享方式 P利用符号链实现文件共享利用符号链实现文件共享 假定当前目录假定当前目录7 7，需共享文件，需共享文件9 9。( (用表示父结点用表示父结点) ) 其路径名：其路径名： : : c a ac cb b 主目录主目录 a ab b 用户用户A A id=2id=2 x xt t 用户用户C C id=4id=4 id=9id=9id=10id=10 id=1id=1 c cd d 用户用

51、户B B id=3id=3 a ac c 目录目录c c id=7id=7 id=11id=11 id=12id=12id=14id=14 id=13id=13 h hf f 目录目录d d id=8id=8 id=6id=6id=5id=5 连访法连访法 CBA DEFAG KMJ DBA CA KNJFHA a 用户可在自己的文件目录中对要共享的文件建立相用户可在自己的文件目录中对要共享的文件建立相 应的目录项，直接指向被共享文件所在的目录项。应的目录项，直接指向被共享文件所在的目录项。 利用基本文件目录实现文件共享利用基本文件目录实现文件共享 在早期，实现文件共享的一种有效方法，在早期，

52、实现文件共享的一种有效方法，将将 文件目录分成两个部分来存放文件目录分成两个部分来存放。 1)符号文件目录符号文件目录SFD：仅包含文件名及文件：仅包含文件名及文件ID 2)基本文件目录基本文件目录BFD：包含除文件名外的其它所有信息包含除文件名外的其它所有信息 (如：物理块号、如：物理块号、 结构、存取控制结构、存取控制 )。BFD中的表目序中的表目序 号即为文件号即为文件ID 利用基本文件目录实现文件共享利用基本文件目录实现文件共享 基于索引结点的共享方式（基于索引结点的共享方式（1） 注注：任何用户对文件进行附加操作或修改，：任何用户对文件进行附加操作或修改， 所引起的相应索引结点内容的

53、改变，对其所引起的相应索引结点内容的改变，对其 它共享用户均是可见，从而可提供其他用它共享用户均是可见，从而可提供其他用 户共享。户共享。 将文件的物理地址和文件属性等信息将文件的物理地址和文件属性等信息 放在索引结点中，在文件目录中，有文件放在索引结点中，在文件目录中，有文件 名及指向索引结点的指针，另外在索引结名及指向索引结点的指针，另外在索引结 点中增加链接计数点中增加链接计数count,count,表示共享的用户表示共享的用户 数，删除时必须数，删除时必须count=0count=0才可以。才可以。 r r TestTest wang的文件目录 Lee的文件目录 r r Test Te

54、st count=2count=2 文件物理地址 test 索引结点索引结点 基于索引结点的共享方式（基于索引结点的共享方式（2） C的目录 Owner=c Count=1 链接前 B的目录C的目录 Owner=c Count=2 建立链接后 B的目录 Owner=c Count=1 若拥有者C删除文件， 会引起指针悬空， 故C不能删除 利用符号链实现文件共享（利用符号链实现文件共享（1） 共享某文件共享某文件testtest时，创建一新文件时，创建一新文件fdfd，并加到用户目，并加到用户目 录中，该文件仅包含被链接文件录中，该文件仅包含被链接文件testtest的路径名，称该链接的路径名，

55、称该链接 方法为符号链接。该方式中，只有文件主才拥有指向其索方法为符号链接。该方式中，只有文件主才拥有指向其索 引结点的指针，其它共享的用户只有该文件的路径名。引结点的指针，其它共享的用户只有该文件的路径名。 test test r r WangWang的文件目录的文件目录 LeeLee的文件目录的文件目录 fdfd 文件物理地址文件物理地址 testtest fdfd fdfd文件内容：文件内容： WangtestWangtest 文件物理地址文件物理地址符号链符号链 索引结点索引结点 索引结点索引结点 利用符号链实现文件共享（利用符号链实现文件共享（2） n优点优点 n当文件主删除一共享文

56、件时，其它共享文件的当文件主删除一共享文件时，其它共享文件的 用户不会留下一个悬空指针。用户不会留下一个悬空指针。 n可链接世界上任何地方的机器中的文件。可链接世界上任何地方的机器中的文件。 n缺点缺点 n根据给定的文件路径名去查找目录，将使访问根据给定的文件路径名去查找目录，将使访问 文件的开销大，启动磁盘频率较高。文件的开销大，启动磁盘频率较高。 n符号链文件虽然简单，但仍要为它配置一个索符号链文件虽然简单，但仍要为它配置一个索 引结点，耗费一定的磁盘空间引结点，耗费一定的磁盘空间 7.7 7.7 文件保护文件保护 P影响文件安全性的主要因素影响文件安全性的主要因素 P人为因素人为因素 P

57、系统因素系统因素 P自然因素自然因素 P确保文件系统安全性的措施确保文件系统安全性的措施 P存取控制机制存取控制机制-人为因素人为因素 P系统容错技术系统容错技术-系统因素系统因素 P后备系统后备系统-自然因素自然因素 7.7 7.7 文件保护文件保护 P访问矩阵访问矩阵 P访问矩阵的实现访问矩阵的实现（访问控制表、访问权限表）（访问控制表、访问权限表） P分级安全管理分级安全管理 系统级安全管理系统级安全管理 用户级安全管理用户级安全管理 目录级安全管理目录级安全管理 文件级安全管理文件级安全管理 P磁盘容错技术磁盘容错技术 访问矩阵访问矩阵 F用以描述系统存取控制的矩阵：访问矩阵中的行代表

58、域，列用以描述系统存取控制的矩阵：访问矩阵中的行代表域，列 代表对象，矩阵中每一项由一组访问权组成。代表对象，矩阵中每一项由一组访问权组成。 nR-R-读；读；W-W-写；写；E-E-执行执行 n访问权访问权 access(i,j)access(i,j)定义了在域定义了在域DiDi中执行的进程能对对象施中执行的进程能对对象施 加的操作集。加的操作集。 n访问权通常由资源的拥有者或管理者所决定。访问权通常由资源的拥有者或管理者所决定。 文件文件A A 文件文件B B 文件文件C C打印机打印机 域域D1D1R,WR,WR RW W 域域D2D2W,RW,RE EW W 域域D3D3R R，W W

59、W W 访问矩阵访问矩阵 保护实现保护实现：当进程向文件系统提出存取请求时，系统：当进程向文件系统提出存取请求时，系统 就根据存取控制矩阵将本次请求和该进程对文件的就根据存取控制矩阵将本次请求和该进程对文件的 存取权限进行比较，若不匹配就拒绝执行。存取权限进行比较，若不匹配就拒绝执行。 特点特点：对整个系统中所有文件的访问权限进行集中控：对整个系统中所有文件的访问权限进行集中控 制。制。 缺点缺点：当用户和文件较多时，存取控制矩阵就较大，：当用户和文件较多时，存取控制矩阵就较大， 占据的存储空间就较多；查找花费时间较长。占据的存储空间就较多；查找花费时间较长。 访问矩阵的实现访问矩阵的实现-访

60、问控制表访问控制表 将将访问矩阵按列（对象）访问矩阵按列（对象） 划分，为每一列建立一张划分，为每一列建立一张 访问控制表访问控制表ACLACL。 在该表中无原矩阵中的空在该表中无原矩阵中的空 项。项。 对象为文件时，常将对象为文件时，常将ACLACL存存 放于该文件的放于该文件的FCB/FCB/索引结索引结 点中，作为存取控制信息。点中，作为存取控制信息。 可定义缺省的访问权集。可定义缺省的访问权集。 F将访问矩阵按行（域）划分，形成一行一张将访问矩阵按行（域）划分，形成一行一张 访问权限表。下图为某用户的访问权限表：访问权限表。下图为某用户的访问权限表： 类型类型权力权力对象对象 文件文件