第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用户文件用户文件- -用户的源代码、目标文件、可执行文件用户的源代码、目标文件、可执行文件或数据或数据n库文件库文件- -由标准子例程和常用的例

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

5、OI/O设备设备n按文件的逻辑结构分类按文件的逻辑结构分类有结构文件（记录式文件）有结构文件（记录式文件）无结构文件（流式文件）无结构文件（流式文件）n按文件的物理结构分类按文件的物理结构分类顺序文件顺序文件链接文件链接文件索引文件索引文件三、文件系统模型（三、文件系统模型（1）文件系统接口（文件系统接口（命令接口、系统调用接口命令接口、系统调用接口）对对象操纵对对象操纵和管理的软和管理的软件集合件集合对象对象( (文件、目录及磁盘存储空间文件、目录及磁盘存储空间) )及其属性说明及其属性说明用户（程序）用户（程序）对文件存储空间的管理对文件存储空间的管理对文件目录的管理对文件目录的管理将文件

6、的逻辑地址转换为物理地址的机制将文件的逻辑地址转换为物理地址的机制对文件的读和写管理对文件的读和写管理对文件的共享和保护对文件的共享和保护三、文件系统模型（三、文件系统模型（2）1) 1) 对象及其属性对象及其属性 文件管理系统管理的对象有：文件管理系统管理的对象有： 文件：它作为文件管理的直接对象。文件：它作为文件管理的直接对象。 目录：为了方便用户对文件的存取和检索，目录：为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。是方便用户和提高对文件存取速度的关键。 磁盘磁盘( (磁带磁带

7、) )存储空间：文件和目录必定占用存储空间：文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。外存的利用率，而且能提高对文件的存取速度。 三、文件系统模型（三、文件系统模型（3）2)2) 对对象操纵和管理的软件集合对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括：能大多是在这一层实现的，其中包括：n对文件存储空间的管理对文件存储空间的管理n对文件目录的管理对文件目录的管理n用于将文件的逻辑地址转换为物理地址

8、的机制用于将文件的逻辑地址转换为物理地址的机制n对文件读和写的管理对文件读和写的管理n对文件的共享与保护等功能对文件的共享与保护等功能三、文件系统模型（三、文件系统模型（4）3)3) 文件系统的接口文件系统的接口 为方便用户使用文件系统，文件系统通常向用为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口：户提供两种类型的接口： 命令接口。这是指作为用户与文件系统交互命令接口。这是指作为用户与文件系统交互的接口。的接口。 用户可通过键盘终端键入命令，取得文用户可通过键盘终端键入命令，取得文件系统的服务。件系统的服务。 程序接口（系统调用接口）。这是指作为用程序接口（系统调用接口）。这是

9、指作为用户程序与文件系统的接口。户程序与文件系统的接口。 用户程序可通过系统用户程序可通过系统调用来取得文件系统的服务。调用来取得文件系统的服务。四、文件操作四、文件操作 用户通过文件系统所提供的系统调用实施对用户通过文件系统所提供的系统调用实施对文件的操作。最基本的操作有：文件的操作。最基本的操作有：q对文件的操作对文件的操作最基本的：创建、最基本的：创建、打开打开、关闭关闭、删除、读、删除、读、写写其它的：文件属性类操作、目录类操作其它的：文件属性类操作、目录类操作7.2 7.2 文件逻辑结构文件逻辑结构 文件系统设计的关键要素：文件系统设计的关键要素： 对任一文件存在着两种形式的结构：对

10、任一文件存在着两种形式的结构：P文件的逻辑结构文件的逻辑结构（文件的组织）（文件的组织） 从用户观点出发，所观察到的从用户观点出发，所观察到的文件组织形式文件组织形式，是用户，是用户可以直接处理的数据及结构，它独立于物理特性。可以直接处理的数据及结构，它独立于物理特性。P文件的物理结构文件的物理结构（文件的存储结构）（文件的存储结构） 是指文件在外存上的是指文件在外存上的存储组织形式存储组织形式，与存储介质的存，与存储介质的存储性能有关，还和所采用的外存分配方式有关。（分为顺储性能有关，还和所采用的外存分配方式有关。（分为顺序、链接及索引结构）序、链接及索引结构）注：文件的逻辑结构和物理结构都

11、将影响文件的检索速度。注：文件的逻辑结构和物理结构都将影响文件的检索速度。数据构成文件的方法数据构成文件的方法将文件存储到外存的方法将文件存储到外存的方法7.2 7.2 文件逻辑结构文件逻辑结构 对文件的逻辑结构提出的基本要求：对文件的逻辑结构提出的基本要求： 提高检索速度；提高检索速度； 便于修改；便于修改； 降低文件存储费用。降低文件存储费用。P文件逻辑结构的类型文件逻辑结构的类型P文件存取方法文件存取方法一、文件逻辑结构的类型（一、文件逻辑结构的类型（1）P有结构的记录式文件有结构的记录式文件文件构成：由一个以上的记录构成。文件构成：由一个以上的记录构成。记录长度：分为定长和变长。记录长

12、度：分为定长和变长。分类：分类：连续结构连续结构多重结构多重结构转置结构转置结构顺序结构顺序结构一、文件逻辑结构的类型（一、文件逻辑结构的类型（2）P无结构的流式文件无结构的流式文件文件构成：由字符流构成。大量的源程序、文件构成：由字符流构成。大量的源程序、 可执行可执行文件、文件、 库函数等，库函数等， 所采用的就是无结构的文件形式，所采用的就是无结构的文件形式，即流式文件。即流式文件。 长度：以字节为单位（通用计算机寻址的最小单位）长度：以字节为单位（通用计算机寻址的最小单位）访问：对流式文件的访问，则是采用读写指针来指出访问：对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。下

13、一个要访问的字符。 好处：更加方便、OS代码更加可靠、灵活，用户编程也更加方便连续结构连续结构n连续结构是一种把记录按生成的先后顺序连续排连续结构是一种把记录按生成的先后顺序连续排列的逻辑结构。列的逻辑结构。n优点：是适用性强，可用于所有文件优点：是适用性强，可用于所有文件（字符流式的（字符流式的无结构文件实质上记录长度为一个字符的连续结构文件）无结构文件实质上记录长度为一个字符的连续结构文件）, ,且记录的排列顺序与记录的内容无关。这有利于且记录的排列顺序与记录的内容无关。这有利于记录的追加与变更。记录的追加与变更。n缺点：连续结构文件的搜索性能较差，例如要找缺点：连续结构文件的搜索性能较差

14、，例如要找出某个指定键的记录时，系统必须对文件全体进出某个指定键的记录时，系统必须对文件全体进行搜索。行搜索。 如果把记录按键和记录名排列成行列式结构，则如果把记录按键和记录名排列成行列式结构，则一个包含一个包含n n个记录名、个记录名、m m个个(mn)(mn)个键的文件构成个键的文件构成 m mn n维行列式。维行列式。R1 R2 RN 0 10 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中。中。特点：特点：用行

15、列式方法浪费存储空间用行列式方法浪费存储空间( (稀稀疏矩阵疏矩阵) )。多重结构多重结构 多重结构：如果把记录按键组成记录队列多重结构：如果把记录按键组成记录队列( (如下如下图）则一个包含图）则一个包含n n个记录名、个记录名、m m个个(mn)(mn)个键的个键的文件构成文件构成m m个队列，无个队列，无0 0项，这项，这m m个队列构成文件个队列构成文件的多重结构。的多重结构。 特点：多重结构比连续结构在由给定键的记录特点：多重结构比连续结构在由给定键的记录搜索速度方面要快。比用行列式节约存储空间搜索速度方面要快。比用行列式节约存储空间。多重结构多重结构转置结构转置结构n转置结构：把含

16、有相同键的记录指针全部指向该转置结构：把含有相同键的记录指针全部指向该键键( (不再队列排序不再队列排序) )，也就是说，把所有与同一键，也就是说，把所有与同一键对应的记录的指针对应的记录的指针连续地置于目录中该键的位置连续地置于目录中该键的位置下下n特点：转置结构最适合于由给定键的记录搜索。特点：转置结构最适合于由给定键的记录搜索。顺序结构顺序结构n顺序结构：把文件中的键按规定的顺序排列起来。顺序结构：把文件中的键按规定的顺序排列起来。n特点：如果系统要求按某种优先顺序来搜索或追特点：如果系统要求按某种优先顺序来搜索或追加、删除记录，则最好采用顺序结构。加、删除记录，则最好采用顺序结构。二、

17、文件的存取方法二、文件的存取方法n用户通过对文件的存取来完成对文件的修改、追用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。常用的存取方法有三种：加和搜索等操作。常用的存取方法有三种：n顺序存取法顺序存取法n随机存取法（直接存取法）随机存取法（直接存取法）n按键存取法按键存取法顺序存取法顺序存取法n是按照文件的是按照文件的逻辑地址逻辑地址顺序存取。顺序存取。n记录式文件：当前记录记录式文件：当前记录RiRi，则下一次读写自动，则下一次读写自动定位为定位为Ri+1Ri+1。n字符流文件：当前读写指针读取完一段信息后，字符流文件：当前读写指针读取完一段信息后，自动加减该信息段长度，指出下

18、次存取位置。自动加减该信息段长度，指出下次存取位置。随机存取法随机存取法n允许用户根据允许用户根据记录编号记录编号来存取文件的任一记录，来存取文件的任一记录，或者是根据存取命令把或者是根据存取命令把读写指针读写指针移到欲读写处来移到欲读写处来读写。读写。按键存取法按键存取法n文件的存取是根据文件的存取是根据给定的键给定的键或或记录名记录名进行的。多进行的。多用于数据库文件。用于数据库文件。7.37.3 外存分配方式外存分配方式n文件的物理结构即文件的外存分配方式，是从系文件的物理结构即文件的外存分配方式，是从系统的角度来看文件，从文件在物理介质上的存放统的角度来看文件，从文件在物理介质上的存放

19、方式来研究文件。方式来研究文件。n要考虑的主要问题：要考虑的主要问题：n目前常用的外存分配方法：目前常用的外存分配方法：（1 1）连续分配（顺序分配）连续分配（顺序分配） 顺序文件结构顺序文件结构（2 2）链接分配）链接分配 链接文件结构链接文件结构（3 3）索引分配）索引分配 索引文件结构索引文件结构如何有效地利用外存空间如何有效地利用外存空间如何提高对文件的访问速度如何提高对文件的访问速度外存分配单位外存分配单位n存储介质（如磁盘）与内存交换数据的单位是存储介质（如磁盘）与内存交换数据的单位是物物理块（理块（512512或或10241024字节）字节），外存划分成大小相等的外存划分成大小相

20、等的若干物理块，文件信息也被划分成与物理块大小若干物理块，文件信息也被划分成与物理块大小相等的相等的逻辑块逻辑块，外存以，外存以块为单位分配块为单位分配。文件的一。文件的一逻辑块中信息装入外存一物理块中。逻辑块中信息装入外存一物理块中。n连续文件连续文件: :它是一种最简单的物理文件结构它是一种最简单的物理文件结构, ,它把它把一个在逻辑上连续的文件信息依次存放到地址连一个在逻辑上连续的文件信息依次存放到地址连续的物理块中。续的物理块中。n优点优点: :算法简单，顺序访问速度快，查找速度快算法简单，顺序访问速度快，查找速度快（逻辑块号和物理块号的转变简单，可随机访（逻辑块号和物理块号的转变简单

21、，可随机访问）。问）。n缺点缺点: :预先说明长度，文件动态增长困难，易造成预先说明长度，文件动态增长困难，易造成外存碎片（删除导致零头）问题。外存碎片（删除导致零头）问题。（1 1）外存分配方式）外存分配方式- -连续连续/ /顺序分配顺序分配图：连续分配图：连续分配 （2 2）外存分配方式）外存分配方式- -链接分配链接分配n用用非连续的物理块非连续的物理块来存放文件信息。这些非连续来存放文件信息。这些非连续的物理块之间没有顺序关系，其中每一个物理块的物理块之间没有顺序关系，其中每一个物理块设有一个设有一个指针指针，指向其后续连接的另一物理块，指向其后续连接的另一物理块，从而使得存放同一文

22、件的物理块连接成一个串联从而使得存放同一文件的物理块连接成一个串联队列。队列。n特点特点: :外存可采用离散分配，解决了碎片问题，但外存可采用离散分配，解决了碎片问题，但搜索效率低，只适合于顺序存取方式，不适合随搜索效率低，只适合于顺序存取方式，不适合随机存取（通过位置编号直接存取）机存取（通过位置编号直接存取）图：链接分配图：链接分配 （3 3）外存分配方式外存分配方式- -索引分配索引分配n索引结构要求系统为每个文件建立一张索引结构要求系统为每个文件建立一张索引表索引表，表中每一栏目指出文件信息所在的逻辑块号和与表中每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。索引表的物理地址则

23、由文件之对应的物理块号。索引表的物理地址则由文件说明信息项给出。说明信息项给出。n优点：索引结构既适用于顺序存取，也适用于随优点：索引结构既适用于顺序存取，也适用于随机存取。机存取。也易于进行文件的增删。也易于进行文件的增删。n缺点：是由于使用了索引表而增加了存储空间的缺点：是由于使用了索引表而增加了存储空间的开销。开销。另外索引表的查找策略对文件系统的效率另外索引表的查找策略对文件系统的效率影响很大。影响很大。多重索引多重索引n当文件很大时，文件的索引表也会很大。如果索当文件很大时，文件的索引表也会很大。如果索引表的大小超过了一个物理块时，可以将索引表引表的大小超过了一个物理块时，可以将索引

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

25、型目录结构文件控制块和索引结点文件控制块和索引结点 从文件管理角度看，文件由从文件管理角度看，文件由FCBFCB和文件体（文和文件体（文件本身）两部分组成。件本身）两部分组成。 n文件控制块（文件控制块（FCB-File Control BlockFCB-File Control Block）n文件控制块是操作系统为管理文件而设置的数文件控制块是操作系统为管理文件而设置的数据结构，存放了文件的据结构，存放了文件的有关说明信息有关说明信息，记录了，记录了系统对文件进行管理所需要的全部信息。系统对文件进行管理所需要的全部信息。nFCBFCB是文件存在的标志。是文件存在的标志。nFCBFCB保存在文

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

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

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

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

30、结点）结点（即索引结点）的指针构成。的指针构成。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次）的次）的1/41

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

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

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

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

35、140405 540-4440-442 260603 360-6260-623 380806 680-8580-85一、空闲文件目录法（一、空闲文件目录法（1）n存储空间的分配与回收存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是采用首空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。次适应算法、循环首次适应算法等。 例如，在系统为某新创建的文件分配空闲盘块时：例如，在系统为某新创建的文件分配空闲盘块时： 先顺序地检索空闲表的各表项，直至找到第一个其大小先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区；能满足要求的空闲区； 再将该

36、盘区分配给用户再将该盘区分配给用户( (进程进程) )，同时修改空闲表。，同时修改空闲表。 系统在对用户所释放的存储空间进行回收时：也采取类系统在对用户所释放的存储空间进行回收时：也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。点的前区和后区相邻接，对相邻接者应予以合并。 一、空闲文件目录法（一、空闲文件目录法（2）二、空闲块链法二、空闲块链法n把文件存储设备上的所有空闲块链接在一起。把文件存储设备上的所有空闲块链接在一起。n有以下三种拉链方法：有以下三种拉链方法：1、空闲块链、空闲块链

37、：空闲块链中每一个节点是一个空：空闲块链中每一个节点是一个空闲物理块。闲物理块。3531051510free2、空闲区链、空闲区链：以空闲区为单位拉链，一个空闲：以空闲区为单位拉链，一个空闲区是若干个连续的物理块。区是若干个连续的物理块。365431312112120free成组链接法成组链接法3.3.成组链接法成组链接法 n空闲盘块的组织空闲盘块的组织n将将空闲块的块号分组空闲块的块号分组，每组包含，每组包含n n个块号如个块号如:n=50, :n=50, n=100n=100，并利用一组空闲块中的，并利用一组空闲块中的第一块第一块存放链中下一存放链中下一组中的块号和块数，由此拉成一条链。组

38、中的块号和块数，由此拉成一条链。n链尾组链尾组: :下一组块号指针为下一组块号指针为0(0(链尾标志链尾标志) )， 实际块号实际块号数只有数只有n-1n-1个。个。n链首组链首组: :可能不足可能不足n n个块号，链首组存放在个块号，链首组存放在文件资源表文件资源表（盘上专用区）中（盘上专用区）中, ,系统运行时系统运行时, ,存放在存放在内存空闲块号内存空闲块号栈栈中。中。成组链接法成组链接法41350187Super Blockcount50040400351.049count50450401.049count460.045count#350#400Last One.3104950成组链

39、接法（分配和回收）成组链接法（分配和回收）n空闲盘块的分配与回收空闲盘块的分配与回收n空闲块号成组链的链首组存放在空闲块号成组链的链首组存放在文件资源表文件资源表中中( (盘上专盘上专用区用区) )，系统运行时链首组被装入，系统运行时链首组被装入内存空闲盘块栈内存空闲盘块栈中。中。分配时将栈顶空闲块号弹出堆栈分配给文件使用。回收分配时将栈顶空闲块号弹出堆栈分配给文件使用。回收空闲块时，将空闲块号压入栈顶。分配回收过程中空闲块时，将空闲块号压入栈顶。分配回收过程中大部大部分时间在内存栈分时间在内存栈中进行，不需访问外存。只有在中进行，不需访问外存。只有在分配时分配时遇栈空或回收时遇栈满才需启动磁

40、盘遇栈空或回收时遇栈满才需启动磁盘，以装入下一组块，以装入下一组块号或将栈中一组块号写到磁盘。分配回收速度较快。号或将栈中一组块号写到磁盘。分配回收速度较快。成组链接法示例（成组链接法示例（1 1）n例：已知磁盘上有例：已知磁盘上有1717个空闲块，块号依次为：个空闲块，块号依次为：1 1、3 3、5 5、7 7、1414、1515、1717、1818、1919、2323、2424、2525、2828、2929、3030、3232、3434，请按请按5 5个块号为一组，成组拉链。个块号为一组，成组拉链。n解：解：因因 17 5 = 3 2可知共应分为可知共应分为4组组，链尾组链尾组4个块号，个

41、块号，链首组链首组3个块号个块号 第四组第四组 第三组第三组 第二组第二组 第一组第一组13537141517185192324252852930323405012345# 18# 28# 链首组链首组 链尾组链尾组 第第5块处的指块处的指针指向的块针指向的块成组链接法示例（成组链接法示例（2 2）n为文件为文件A A分配两块之后，分配两块之后，1 1、3 3号空闲块依次出栈分配给文件号空闲块依次出栈分配给文件A A，成组链变为成组链变为7141517185511923242526529303234050123S-free内存栈中内存栈中5# 第四组第四组 第三组第三组 第二组第二组 第一组第

42、一组内存空闲块栈成为第四组的映像内存空闲块栈成为第四组的映像成组链接法示例（成组链接法示例（3 3）n接着接着A A又需又需2 2块，当前堆栈中只有一块号块，当前堆栈中只有一块号(5(5号号) )，需装入下一，需装入下一组块号到内存堆栈组块号到内存堆栈( (简称堆栈装入简称堆栈装入) )。执行过程如下：。执行过程如下：n将将5#5#存放的一组块号装入堆栈存放的一组块号装入堆栈n将将5#5#块分给文件块分给文件A An将将7#7#块分给文件块分给文件A A01234S-free内存栈中内存栈中141517184192324252652930323405分配之分配之后成组后成组链的状链的状态态内存

43、空闲块栈成为第三组的映像内存空闲块栈成为第三组的映像成组链接法示例（成组链接法示例（4 4）n按着按着A A释放块号释放块号5 5，系统回收该块号，成组链变为：，系统回收该块号，成组链变为：5141517185192324252652930323405012345S-free内存栈中内存栈中18#第三组第三组 第二组第二组 第一组第一组26#成组链接法示例（成组链接法示例（5 5）n按着按着A A释放块号释放块号1 1、3 3。由于内存栈已满一组块号，不能再压。由于内存栈已满一组块号，不能再压入回收块号，需将栈中的一组块号写入回收的块号对应的物入回收块号，需将栈中的一组块号写入回收的块号对应的

44、物理块中理块中( (简称栈满腾空简称栈满腾空) )。n回收块号回收块号1 1、3 3之后之后. .成组链的状态成组链的状态51415171851321923242526529303234050123S-free内存栈中内存栈中1# 18# 26# 第四组第四组 第三组第三组 第二组第二组 第一组第一组内存空闲块栈成为第四组的映像内存空闲块栈成为第四组的映像成组链接法特点成组链接法特点n不需额外的空间存储空闲块信息（自带指针）。不需额外的空间存储空闲块信息（自带指针）。n分配和回收大部分时间在内存，速度快。分配和回收大部分时间在内存，速度快。n启动一次磁盘可以读入或写出一组块号，减少启动一次磁盘

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

46、对应的盘块号。假定找到的值为“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) 将回收盘块的盘块号转换成位示图中的将回收盘块的盘块号转换成位示图中的行号和列号。行号和列号。 转换公式为：转换公式为： i=(

47、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早期实现文件共享的方法早期实现文件共享的方法绕弯路法（低效）绕弯路法（低效） 允许每个用户获得一允许每个用户获得一“当前目录当前目录”，用户所，用户所访问的所有文件均相对于当前目录，若不在，则访问的所有文件均相对于当前目录，若不在，则“向上走向上走”绕弯路

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

49、d=7id=11id=11id=12id=12id=14id=14id=13id=13h hf f目录目录d did=8id=8id=6id=6id=5id=5连访法连访法CBADEFAGKMJDBACAKNJFHAa 用户可在自己的文件目录中对要共享的文件建立相用户可在自己的文件目录中对要共享的文件建立相应的目录项，直接指向被共享文件所在的目录项。应的目录项，直接指向被共享文件所在的目录项。利用基本文件目录实现文件共享利用基本文件目录实现文件共享 在早期，实现文件共享的一种有效方法，在早期，实现文件共享的一种有效方法，将将文件目录分成两个部分来存放文件目录分成两个部分来存放。 1)符号文件目

50、录符号文件目录SFD：仅包含文件名及文件：仅包含文件名及文件ID2)基本文件目录基本文件目录BFD：包含除文件名外的其它所有信息包含除文件名外的其它所有信息 (如：物理块号、如：物理块号、 结构、存取控制结构、存取控制 )。BFD中的表目序中的表目序号即为文件号即为文件ID利用基本文件目录实现文件共享利用基本文件目录实现文件共享基于索引结点的共享方式（基于索引结点的共享方式（1）注注：任何用户对文件进行附加操作或修改，：任何用户对文件进行附加操作或修改，所引起的相应索引结点内容的改变，对其所引起的相应索引结点内容的改变，对其它共享用户均是可见，从而可提供其他用它共享用户均是可见，从而可提供其他

51、用户共享。户共享。 将文件的物理地址和文件属性等信息将文件的物理地址和文件属性等信息放在索引结点中，在文件目录中，有文件放在索引结点中，在文件目录中，有文件名及指向索引结点的指针，另外在索引结名及指向索引结点的指针，另外在索引结点中增加链接计数点中增加链接计数count,count,表示共享的用户表示共享的用户数，删除时必须数，删除时必须count=0count=0才可以。才可以。r rTestTestwang的文件目录Lee的文件目录r rTest Test count=2count=2文件物理地址test索引结点索引结点基于索引结点的共享方式（基于索引结点的共享方式（2）C的目录Owner

52、=cCount=1链接前B的目录C的目录Owner=cCount=2建立链接后B的目录Owner=cCount=1若拥有者C删除文件，会引起指针悬空，故C不能删除利用符号链实现文件共享（利用符号链实现文件共享（1） 共享某文件共享某文件testtest时，创建一新文件时，创建一新文件fdfd，并加到用户目，并加到用户目录中，该文件仅包含被链接文件录中，该文件仅包含被链接文件testtest的路径名，称该链接的路径名，称该链接方法为符号链接。该方式中，只有文件主才拥有指向其索方法为符号链接。该方式中，只有文件主才拥有指向其索引结点的指针，其它共享的用户只有该文件的路径名。引结点的指针，其它共享的

53、用户只有该文件的路径名。test test r rWangWang的文件目录的文件目录LeeLee的文件目录的文件目录fdfd文件物理地址文件物理地址testtestfdfdfdfd文件内容：文件内容：WangtestWangtest文件物理地址文件物理地址符号链符号链索引结点索引结点索引结点索引结点利用符号链实现文件共享（利用符号链实现文件共享（2）n优点优点n当文件主删除一共享文件时，其它共享文件的当文件主删除一共享文件时，其它共享文件的用户不会留下一个悬空指针。用户不会留下一个悬空指针。n可链接世界上任何地方的机器中的文件。可链接世界上任何地方的机器中的文件。n缺点缺点n根据给定的文件路

54、径名去查找目录，将使访问根据给定的文件路径名去查找目录，将使访问文件的开销大，启动磁盘频率较高。文件的开销大，启动磁盘频率较高。n符号链文件虽然简单，但仍要为它配置一个索符号链文件虽然简单，但仍要为它配置一个索引结点，耗费一定的磁盘空间引结点，耗费一定的磁盘空间7.7 7.7 文件保护文件保护P影响文件安全性的主要因素影响文件安全性的主要因素P人为因素人为因素P系统因素系统因素P自然因素自然因素P确保文件系统安全性的措施确保文件系统安全性的措施P存取控制机制存取控制机制-人为因素人为因素P系统容错技术系统容错技术-系统因素系统因素P后备系统后备系统-自然因素自然因素7.7 7.7 文件保护文件

55、保护P访问矩阵访问矩阵P访问矩阵的实现访问矩阵的实现（访问控制表、访问权限表）（访问控制表、访问权限表）P分级安全管理分级安全管理系统级安全管理系统级安全管理用户级安全管理用户级安全管理目录级安全管理目录级安全管理文件级安全管理文件级安全管理P磁盘容错技术磁盘容错技术访问矩阵访问矩阵F用以描述系统存取控制的矩阵：访问矩阵中的行代表域，列用以描述系统存取控制的矩阵：访问矩阵中的行代表域，列代表对象，矩阵中每一项由一组访问权组成。代表对象，矩阵中每一项由一组访问权组成。nR-R-读；读；W-W-写；写；E-E-执行执行n访问权访问权 access(i,j)access(i,j)定义了在域定义了在域

56、DiDi中执行的进程能对对象施中执行的进程能对对象施加的操作集。加的操作集。n访问权通常由资源的拥有者或管理者所决定。访问权通常由资源的拥有者或管理者所决定。 文件文件A A 文件文件B B 文件文件C C打印机打印机 域域D1D1R,WR,WR RW W域域D2D2W,RW,RE EW W域域D3D3R R，W WW W访问矩阵访问矩阵保护实现保护实现：当进程向文件系统提出存取请求时，系统：当进程向文件系统提出存取请求时，系统就根据存取控制矩阵将本次请求和该进程对文件的就根据存取控制矩阵将本次请求和该进程对文件的存取权限进行比较，若不匹配就拒绝执行。存取权限进行比较，若不匹配就拒绝执行。特点

57、特点：对整个系统中所有文件的访问权限进行集中控：对整个系统中所有文件的访问权限进行集中控制。制。 缺点缺点：当用户和文件较多时，存取控制矩阵就较大，：当用户和文件较多时，存取控制矩阵就较大，占据的存储空间就较多；查找花费时间较长。占据的存储空间就较多；查找花费时间较长。 访问矩阵的实现访问矩阵的实现-访问控制表访问控制表将将访问矩阵按列（对象）访问矩阵按列（对象）划分，为每一列建立一张划分，为每一列建立一张访问控制表访问控制表ACLACL。在该表中无原矩阵中的空在该表中无原矩阵中的空项。项。对象为文件时，常将对象为文件时，常将ACLACL存存放于该文件的放于该文件的FCB/FCB/索引结索引结

58、点中，作为存取控制信息。点中，作为存取控制信息。可定义缺省的访问权集。可定义缺省的访问权集。F将访问矩阵按行（域）划分，形成一行一张将访问矩阵按行（域）划分，形成一行一张访问权限表。下图为某用户的访问权限表：访问权限表。下图为某用户的访问权限表：类型类型权力权力对象对象文件文件R-R-指向文件指向文件3 3的指针的指针 文件文件RWE RWE 指向文件指向文件4 4的指针的指针 文件文件RW-RW-指向文件指向文件5 5的指针的指针 打印机打印机-W-W-指向打印机指向打印机1 1的指针的指针 访问矩阵的实现访问矩阵的实现-访问权限表访问权限表分级安全管理分级安全管理-系统级安全管理系统级安全

59、管理P主要任务主要任务 不允许未经核准的用户进入系统不允许未经核准的用户进入系统P主要方法主要方法注册注册登录登录其它措施其它措施系统级安全管理系统级安全管理用户级安全管理用户级安全管理目录级安全管理目录级安全管理文件级安全管理文件级安全管理其它措施其它措施n规定用户定期修改口令规定用户定期修改口令n限定用户的终端限定用户的终端n限定用户的上机时间限定用户的上机时间 注册用户表注册用户表用户用户1 1用户用户2 2用户用户3 3用户用户2 2表表用户名用户名口令口令上机时间上机时间终端号终端号分级安全管理分级安全管理-用户级安全管理用户级安全管理P主要任务主要任务 根据用户性质、需求及文件属性

60、给用户分配根据用户性质、需求及文件属性给用户分配“文件访文件访问权问权” ” 。P主要方法主要方法用户分类用户分类 文件主文件主 其他用户（超级用户、系统操作员、用户、顾客）其他用户（超级用户、系统操作员、用户、顾客）文件访问权（建立、删除、读、写。）文件访问权（建立、删除、读、写。）系统级安全管理系统级安全管理用户级安全管理用户级安全管理目录级安全管理目录级安全管理文件级安全管理文件级安全管理分级安全管理分级安全管理-目录级安全管理目录级安全管理P主要任务主要任务 为保护系统中各种目录的安全，系统对目录操为保护系统中各种目录的安全，系统对目录操作指定了权限。作指定了权限。P实现方法实现方法