计算机操作系统原理 ch7 文件系统.ppt

《计算机操作系统原理 ch7 文件系统.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统原理 ch7 文件系统.ppt（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章 文件系统n文件和文件系统 n文件结构及其存取方式 n文件存储空间管理n文件目录管理 n文件存取控制n文件的使用n文件系统的层次模型n小结 文件和文件系统n引言 n文件及其分类 n文件系统及其功能引言n在在早早期期计计算算机机系系统统中中，人人们们直直接接用用物物理理地地址址存存放放信信息息。存存放放信信息息时时，要要求求用用户户指指出出并并记记住住信信息息存存放放在在哪哪个个设设备备的的哪哪些些磁道、哪些扇区上。磁道、哪些扇区上。n在在多多用用户户的的环环境境中中这这几几乎乎是是不不可可能能的的，更是不能忍受的。更是不能忍受的。n实实际际上上对对用用户户来来说说，关关心心的的不不是是信

2、信息息的的具具体体存存放放位位置置，而而是是存存取取方方法法的的方方便便、可可靠靠。不不是是信信息息的的物物理理结结构构而而是是信信息息的的逻辑结构。逻辑结构。n因因此此，引引入入文文件件和和文文件件系系统统的的概概念念，它它是操作系统的重要组成部分。是操作系统的重要组成部分。文件及其分类n1、文件的定义n文文件件是是具具有有符符号号名名而而且且在在逻逻辑辑上上具具有有完完整整意意义义的的信信息息项项的的有有序序列。序序列。信息项信息项 信息项信息项.信息项信息项.信息项信息项编号：编号：0 1 i n-1读写指针读写指针n在在现现代代计计算算机机操操作作系系统统中中，为为方方便便用用户户，把

3、把设设备备也也作作为为文文件件来来统统一一管管理理，从从某某种种意义上说已拓宽了文件的含义。意义上说已拓宽了文件的含义。n一般情况下，一个文件是一组逻辑上具一般情况下，一个文件是一组逻辑上具有完整意义的信息集合，并赋以一个文有完整意义的信息集合，并赋以一个文件名。文件名是一个字符串。件名。文件名是一个字符串。2、文件的分类（1）以文件的用途分类n系统文件:指用操作系统的执行程序和数据组成的文件，这种文件不对用户开放，仅供系统使用。n库文件：是指系统为用户提供的各种标准函数，标准过程和实用程序等。用户只能使用这些文件，而无权对其进行修改。n用户文件:由用户的信息组成的文件，如源程序文件，数据文件

4、等。这种文件的使用和修改权均属于用户。（2）从按文件的属性分类n只读文件:只允许进行读操作。n可读/写文件:允许进行读写操作。n非保护文件:不作任何操作限制。n可执行文件：用户可执行该程序，但不能修改。（3）按文件的性质分类n普通文件:指一般的用户文件和系统文件。n目录文件:指由文件目录项组成的文件。n特别文件:有的系统把设备作为文件统一管理和使用，并为区别起见，把设备称为特别文件。UNIX操作系统把文件分成普通文件、目录文件和特别文件。3、文件属性n用一组信息指定文件的类型、操作特性和存取保护等，把这组信息称为文件的属性。文件的属性一般存放在文件的目录项中。n例如MS-DOS系统中，文件属性

5、占目录项的一个字节，在这个字节中，01表示文件仅读，02表示隐含文件等。文件系统及其功能n操作系统中负责管理文件的机构称为文件系统。也有的文献上叫信息系统。n文件系统负责文件的创立、撤消、读写、修改、复制和存取控制等，并管理存放文件的各种资源。文件系统主要功能(1)按名存取(2)文件存储空间的分配和回收(3)对文件及文件目录的管理(4)提供操作系统与用户的接口(5)提供有关文件自身的服务 文件的安全性、文件的共享机制等。文件的结构及其存取方式n概述 n文件的逻辑结构及其存取方式 n文件的物理结构及其存储设备 概述研究文件结构有两种观点：n用用户户的的观观点点（文文件件的的逻逻辑辑结结构构）：主

6、要研究用户思维中的抽象文件，为用户提供一种逻辑结构清晰、使用简便的逻辑文件。用户将按这种形式去存取、检索和加工文件。例如用户可将文件看作字节的集合。或者用户将文件看作记录的集合。n实现的观点（文件的物理结构）实现的观点（文件的物理结构）：主要研究驻留在存储介质上的文件的结构。文件的物理结构：文件的各个字节在存储介质上是如何摆放的。文件的逻辑结构及其存取方式1、文件的逻辑结构文件的逻辑结构是用户可见结构。文件的逻辑结构可分为两大类：字符流式的无结构文件和记录式的有结构文件。在文件系统设计时，选择何种逻辑结构才能更有利于用户对文件信息的操作呢？一般情况下，选取文件的逻辑结构应遵循下述原则：(1)当

7、用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。(2)当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统在尽可能短的时间内查找到需要查找的记录或基本信息单位。(3)应使文件信息占据最小的存储空间。(4)应是便于用户进行操作的。显然，对于字符流的无结构文件来说，查找文件中的基本信息单位，例如某个单词，是比较困难的。但反过来，字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，例如，源程序文件、目标代码文件等。除了字符流的无结构方式外，记录式的有结构文件可把文件中的记录按各种不同的方

8、式排列，构成不同的逻辑结构，以便用户对文件中的记录进行修改、追加、查找和管理等操作。记录是一个具有特定意义的信息单位，它由该记录在文件中的逻辑地址(相对位置)与记录名所对应的一组键、属性及其属性值所组成。下图是一个记录的组成例。图中，1296是名为R 的记录在文件中的逻辑地址，姓名:A 是该记录的键，而 性别，出生年月，工资 等是该记录的属性，紧跟在这些后面的是属性值。一个记录可以有多个键名，每个键名可对应于多项属性。再者，根据各系统设计的要求不一样，记录既可以是定长的，也可以是变长的。记录的长度可以短到一个字符，也可以长到一个文件，这要由系统设计人员确定。常用的记录式结构文件有以下几种:(1

9、)连续结构(2)多重结构(3)转置结构(4)顺序结构(1)连续结构连续结构是一种把记录按生成的先后顺序连续排列的逻辑结构。优点：优点：适用性强，可用于所有文件，且记录的排列顺序与记录的内容无关。这有利于记录的追加与变更。缺点：缺点：搜索性能较差，例如要找出某个指定键的记录时，系统必须对文件全体进行搜索。(2)多重结构 如果把记录按键和记录名排列成行列式结构，则一个包含n个记录名、m个(mn)个键的文件构成一m*n维行列式。其中，如果第i(1im)行和第j(1jn)列所对应的位置上为1，则表示键Ki在记录 R中;反之,则表示键Ki不在记录 Rj 中。另外，同一个键也可以同时属于不同记录。文件的记

10、录名和键构成的行列式n显然，如果只按行列式结构来排列记录，将会浪费较多的存储空间。从而，我们把行列式中那些为零的项去掉，并以键Ki为队首，以包含键Ki的记录为队列元素来构成一个记录队列。对于一个有m个键的队列来说，这样的队列有m个。这m个队列构成了该文件的多重结构(multi_list)。如图a所示。(3)转置结构 在图a的多重结构中，每个队列中和键直接相连的只有一个记录。这种结构虽然在检索时要优于连续结构，但在检索某一特定记录时，必须在找到该记录所对应的键之后，再在该键所对应的队列中顺序查找。转置结构转置结构把含有相同键的记录指针全部指向该键，也就是说，把所有与同一键对应的记录的指针连续地置

11、于目录中该键的位置下(图b)。转置结构最适合于给定键后的记录搜索。图a 文件的多重结构 图b 文件的转置结构(4)顺序结构如果系统要求按某种优先顺序来搜索或追加、删除记录，则最好采用顺序结构。如果给定了顺序规定(例如按字母顺序)，则把文件中的键按规定的顺序排列起来就形成了顺序结构文件。例如，把人民日报上登载的新闻按年月日为键做成记录放入文件中，并以时间先后顺序组成文件。这样，如果要处理某段时间内所发生的大事等问题，就会变得非常简单。例如用户想了解两伊战争的情况，则只要把1990年8 月19日开始的两个月内的有关记录搜索到就行了。存取方法用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。

12、常用的存取方法有三种：(1)顺序存取法(2)随机存取法(直接存取法)(3)按键存取法 顺序存取是按照文件的逻辑地址顺序存取。在记录式文件中，这反映为按记录的排列顺序来存取，例如，若当前读取的记录为Ri，则下一次读取的记录被自动地确定为Ri的下一个相邻的记录Ri+1。在无结构的字符流文件中，顺序存取反映当前读写指针的变化。在存取完一段信息之后，读写指针自动加或减去该段信息长度，以便指出下次存取时的位置。随机存取法允许用户根据记录的编号来存取文件的任一记录，或者是根据存取命令把读写指针移到欲读写处来读写。UNIX系统以及MS-DOS等操作系统都采用顺序存取和随机存取等两种方法。按键存取是一种用在复

13、杂文件系统，特别是数据库管理系统中的存取方法。文件的存取是根据给定的键或记录名进行的。按键存取法首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地址后进行存取。下面，介绍按键存取的搜索方法。对文件进行搜索的目的是要查找出特定记录所对应的逻辑地址，以便将其转换为相应的物理地址，实现对文件的操作。对文件的搜索包括两种：键的搜索和记录的搜索。对键的搜索是在用户给定所要搜索的键名和记录之后，确定该键名在文件中的位置；而记录的搜索则是在搜索到所要查找的键之后，在含有该键的所有记录中查找出所需要的记录。显然，对于不同的逻辑结构的文件，其搜索方法和搜索效率都是不一样的。对指定记录Ri的搜索过程如

14、图所示。对于给定的Ri,首先,系统确定Ri所对应键名的记录队列。如果在所查找的文件中不存在这样的队列，则搜索算法结束返回，从而无法搜索到Ri。如果找到Ri，则返回其所对应的逻辑地址。如果找不到Ri，则返回无法找到Ri的有关信息。对键或记录的搜索与其他数据搜索问题一样，都属于表格搜索问题。有许多搜索算法用来解决表格搜索问题。这些算法可以大致分为三种类型。即，(1)线性搜索法(linear search)，(2)散列法(hash coding)，(3)二分搜索法(binary search algorithm)。下面分别简单地介绍这几种搜索算法。(1)线性搜索法它从第一个键或记录开始，依次和所要搜

15、索的键或记录相比较，直到找到所需要的记录为止。线性搜索法所需要的搜索时间与所搜索的表格大小的 1/2成正比。这是因为找到一个所需要的记录平均要和表中登记的总项数的1/2项比较后才能得到。线性搜索法的搜索效率较低，在文件中记录个数较多时不宜采用。(2)散列法散列搜索法被被广泛用于现代操作系统的数据查找。散列法的核心思想是定义一个散列函数h(k)，使得对于给定的键k，散列函数h(k)将其变换为 k所对应的逻辑地址。在使用散列函数进行搜索时，有时会出现两个不同的输入值变换到同一地址的问题。即对于k1!=k2，有h(k1)=h(k2)=A。显然，k1和k2 中，至少有一个与 A中的内容不一致。也就是说

16、，由散列变换得到的结果并不是所要搜索的键。这种问题称为散列冲突。解决散列冲突的方法是采用多次散列探索。例如，设第i 次散列变换的结果为hi(k)，i=2,3，则可令hi(k)=(h1(k)+di)(mod t)这里，t 为被搜索表格长度，di为第i 次搜索所得地址与第1次搜索所得地址之间的距离。di的取值方法很多，最简单的方法是设di为i的线性函数，即di=a*i(a为一大于零的常数)。这种方法称线性散列法。但是，使用线性散列法并不能完全解决散列冲突问题。例如，对于i!=j，k=1,2，如果 hi(k1)=hj(k2)，则存在 hi+k(k1)=hj+k(k2)。解决散列冲突的另一个方法是生成

17、一组随机数r1,r2，rn，且令di=ri。显然，除了 h1(k1)=h1(k2)可能存在之外，h1(k1)=h1+k(k2)的可能性很小，不过，使用随机数的方法需要占用一定的存储空间来生成和存放随机数组。还有一个解决散列冲突的方法是采用平方散列函数方法。即令：hi(k)=(h1(k)+c*(i*i)(mod t)这里，t是一个表示被搜索表格长度的素数，c 是一个大于零的常数。可以证明，对于j1(mod t)，即使有 h1(k1)=hj(k2)，那么，对于i=1,2，t-1，有 hi(k1)!=hj+i(k2)。(3)二分搜索法 对于顺序结构排列的键或记录来说，二分搜索法具有较高的搜索效率。二

18、分搜索法首先把所要搜的键与队列的首尾键相比较,如果和其中之一相等，则返回所搜索到的键的逻辑位置。否则，再与队列1/2处的键比较，如果所要搜索的键正好等于该键的话,则返回该键的逻辑地址；否则，如果所要搜索的键K 小于位于队列中央的键的话，则继续搜索左边的半个队列。如果所要搜索的键K大于位于队列中央的键的话,则继续搜索右边的半个队列。这样，每次用以中央键画分的部分组成新的队列反复进行上述搜索操作，直到找到为止。这一搜索过程如图所示。二分搜索法的搜索过程n二分搜索法的好处是搜索效率高。与线性搜索法相比，当 n(表长)=16时,它比线性搜索法约快二倍;当 n=1 024 时，其平均搜索速度要快50倍。

19、不过，二分搜索法需要事先把搜索对象按一定顺序排列。文件的物理结构与存储设备文件系统采用哪种存取方法和逻辑结构，实际上是和物理存储介质有关的。因此，本节介绍文件的物理结构，同时也介绍常用的文件存储设备。文件的物理结构文件的物理结构是指文件在物理存储介质上的结构。n连续文件n链接文件n索引文件(1)连续文件连续文件是一种最简单的物理文件结构，它把一个在逻辑上连续的文件信息依次存放到物理块中。在下图中，一个逻辑块号为 0,1,2,3的文件依次存放在物理块 10,11,12,13中。连续文件结构n优点：快速存取。一旦知道了文件在文件存储设备上的起址和文件长度，就能很快地进行存取。这是因为文件的逻辑块号

20、到物理块号的变换可以非常简单地完成。n缺点：在建立文件时必须在文件说明信息中确定文件信息长度，且以后不能动态增长；而且在文件进行某些部分的删除后，又会留下无法使用的零头空间。因此，连续文件结构不宜用来存放用户文件、数据库文件等经常被修改的文件。(2)串联文件串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系，其中每个物理块设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。下图给出了串联文件的物理结构。串联文件的物理结构优点：优点：1、无需确定文件长度。使用串联文件结构时，不必在文件说明信息中指明文件的长度，只需指明该文件的第

21、一个块号就行了；2、方便插入删除。文件长度可以动态地增长，只要调整连接指针就可在任何一个信息块之间插入或删除一个信息块。缺点：缺点：由于串联文件结构只能按队列中的串联指针顺序搜索，因此，串联文件结构的搜索效率串联文件结构的搜索效率较低。串连文件结构一般只适用于逻辑上连续较低。串连文件结构一般只适用于逻辑上连续的文件，且存取方法应该是顺序存取的。的文件，且存取方法应该是顺序存取的。否则，为了读取某个信息块而造成的磁头大幅度移动将花去较多的时间。因此，串联文件结构不适宜随机存取。(3)索引文件索引结构要求系统为每个文件建立一张索引表，表中每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。索引

22、表的物理地址则由文件说明信息项给出。索引结构如下图所示。索引文件示意图索引文件结构既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取。因为有关逻辑块号和物理块号的信息全部放在一个集中的索引表中，而不是像串联文件结构那样分散在各个物理块中。多重索引在很多情况下，有的文件很大，文件索引表也就较大。如果索引表的大小超过了一个物理块，那么我们必须象处理其他文件的存放那样决定索引表的物理存放方式，但这不利于索引表的动态增加；索引表也可按串联方式存放，但这却增加了存放索引表的时间开销。一种较好的解决办法是采用间接索引间接索引(多重索引多重索引)，也就是在索引表所指的物理块中存放的不是文件信息

23、，而是装有这些信息的物理块地址。这样，如果一个物理块可装下n个物理块地址的话，则经过一级间接索引，可寻址的文件长度将变为 n*n 块。如果文件长度还大于 n*n块的话，还可以进行类似的扩充，即二级间接索引。其原理如下图。多重索引结构直接寻址间接寻址不过，大多数文件不需要进行多重索引，也就是说，这些文件所占用的物理块数的块号可以放在一个物理块内。如果对这些文件也采用多重索引，则显然会降低文件的存取速度。因此，在实际系统中，总是把索引表的头几项设计成直接寻址方式，也就是这几项所指的物理块中存放的是文件信息；而索引表的后几项设计成多重索引，也就是间接寻址方式。在文件较短时，就可利用直接寻址方式找到物

24、理块号而节省存取时间。索引结构既适用于顺序存取，也适用于随机存取。索引结构的缺点：1、由于使用了索引表而增加了存储空间的开销；2、在存取文件时需要至少访问存储器二次以上。其中，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。由于文件在存储设备的访问速度较慢，因此，如果把索引表放在存储设备上，势必大大降低文件的存取速度。改进的方法：当对某个文件进行操作之前，系统预先把索引表放入内存。这样，文件的存取就可直接在内存通过索引表确定物理地址块号，而访问磁盘的动作只需要一次。文件存储设备n常用的存储设备有磁盘、光盘、磁带等。其中磁盘又可分为硬盘和软盘。由于存储设备的特性决定了文件的方法，

25、因此，这里介绍以磁带为代表的顺序存储设备和以磁盘为代表的直接存储设备的特性及有关存取方法。1.顺序存取设备磁带是一种最典型的顺序存取设备。顺序存取设备只有在前面的物理块被存取访问过之后，才能存取后续的物理块的内容。而且，为了在存取一个物理块时让磁带机提前加速和不停止在下一个物理块的位置上，磁带的两相邻的物理块之间设计有一个间隙将它们隔开。磁带的结构磁带设备的存取速度或数据传输率与下列因素有关：(1)信息密度(字符数/英寸)(2)磁带带速(英寸/秒)(3)块间间隙 如果带速高，信息密度大，且所需块间隙(磁头启动和停止时间)小的话，则磁带存取速度和数据传输率高，反之亦然。优点：容量大，顺序存取方式

26、时存取速度高。缺点：按随机方式或按键存取方式存取磁带上的文件信息的话，其效率不会很高。由磁带的读写方式可知，只有当第i块被存取之后，才能对第i+1块进行存取操作。因此，某个特定记录或物理块的存取访问与该物理块到磁头当前位置的距离有很大关系。如果相距甚远，则要花费很长的存取时间来移动磁头。2.直接存取设备 磁盘是最典型的直接存取设备。磁盘设备允许文件系统直接存取磁盘上的任意物理块。为了存取一个特定的物理块，磁头将直接移动到所要求的位置上，而不需要像顺序存取那样事先存取其他的物理块。磁盘机一般由一些磁盘片组成的磁盘组组成。其中每个磁盘片对应一个装有 读/写 磁头的磁头臂，磁头臂上的两个读/写磁头分

27、别对磁盘片的上下两面进行读写。系统在对磁盘进行初始化处理时，把每个磁盘片分割成一些大小相等的扇区。在磁盘转动时经过读/写 磁头所形成的圆形轨迹称为磁道。由于磁头臂可沿半径方向移动，因此，磁盘上有多条磁道。n另外，人们通常把所有磁盘片的相同磁道称为一个柱面，因此，磁盘上每个物理块的位置可用柱面号、磁头号和扇区号表示，这些地址和物理块号一一对应。磁盘的结构如图所示。文件存储空间管理存储空间管理是文件系统的重要任务之一。只有有效地进行存储空间管理，才能保证多个用户共享文件存储设备和得以实现文件的按名存取。由于文件存储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，文件存储空间的管理

28、实质上是一个空闲块的组织和管理问题，它包括空闲块的组织，空闲块的分配与空闲块的回收等几个问题。有3种不同的空闲块管理方法。(1)空闲文件目录(2)空闲块链(3)位示图(1)空闲文件目录最简单的空闲块管理方法就是把文件存储设备中的空闲块的块号统一放在一个称为空闲文件目录的物理块中。其中空闲文件目录的每个表项对应一个由多个空闲块构成的空闲区，它包括空闲块个数，空闲块号和第一个空闲块号等。在系统为某个文件分配空闲块时，首先扫描空闲文件目录项，如找到合适的空闲区项，则分配给申请者，并把该项从空白文件目录中去掉。如果一个空闲区项不能满足申请者要求，则把目录中另一项分配给申请者(连续文件结构除外)。如果一

29、个空闲区项所含块数超过申请者要求，则为申请者分配了所要的物理块之后，再修改该表项。当一个文件被删除，释放存储物理块时，系统则把被释放的块号、长度以及第一块块号置入空白目录文件的新表项中。显然，在内存管理时讨论过有关空闲连续区分配和释放算法。只要稍加修改就可用于空闲文件项的分配和回收。空闲文件项方法适用于连续文件结构的文件存储区的分配与回收。(2)空闲块链空闲块链是一种较常用的空闲块管理方法。空闲块链把文件存储设备上的所有空闲块链接在一起，当申请者需要空闲块时，分配程序从链头开始摘取所需要的空闲块，然后调整链首指针。反之，当回收空闲块时，把释放的空闲块逐个插入链尾上。空闲块链的链接方法因系统而异

30、，常用的链接方法有按空闲区大小顺序链接的方法；按释放先后顺序链接的方法；以及按成组链接法。其中成组链接法可被看作空闲块链的链接法的扩展。按空闲区大小顺序链接和按释放先后顺序链接的空闲块管理在增加或移动空闲块时需对空闲块链做较大的调整，因而需耗去一定的系统开销。成组链法在空闲块的分配和回收方面要优于上述两种链接法。成组链法首先把文件存储设备中的所有空闲块按50块画分为一组。组的画分为从后往前顺次画分。其中，每组的第一块用来存放前一组中各块的块号和总块数。由于第一组的前面已无其他组存在，因此，第一组的块数为49块。不过，由于存储设备的空间块不一定正好是50的整倍数，因而最后一组将不足50块，且由于

31、该组后面已无另外的空闲块组，所以，该组的物理块号与总块数只能放在管理文件存储设备用的文件资源表中。成组链法的组织n在成组链法对文件设备进行了上述分组之后，系统可根据申请者的要求进行空闲块的分配，并在释放文件时回收空闲块。下面我们介绍成组链法的分配和释放过程。首先，系统在初启时把文件资源表复制到内存，从而使文件资源表中放有最后一组空闲块块号与总块数的堆栈进入内存，并使得空闲块的分配与释放可在内存进行。减少了启动 I/O设备的压力。与空闲块块号及总块数相对应，用于空闲块分配与回收的堆栈有栈指针 Ptr，且 Ptr的初值等于该组空闲块的总块数。当申请者提出空闲块要求 n时，按照后进先出的原则，分配程

32、序在取走Ptr 所指的块号之后，再做PtrPtr-1 的操作。这个过程一直持续到所要求的n块都已分配完毕或堆栈中只剩下最后一个空闲块的块号。当堆栈中只剩下最后一个空闲块号时，系统启动设备管理程序，将该块中存放的下一组的块号与总块数读入内存之后将该块分配给申请者。然后，系统重新设置Ptr指针，并继续为申请者进程分配空闲块。文件存储设备的最后一个空闲块中设置有尾部标识，以指示空闲块分配完毕。如果用户进程不再使用有关文件并删除这些文件时，回收程序回收装有这些文件的物理块。成组链法的回收过程仍利用文件管理堆栈进行回收。在回收时，回收程序先做PtrPtr+1操作，然后把回收的物理块号放入当前指针Ptr所

33、指的位置。如果 Ptr等于50，则表示该组已经回收结束。此时，如果还有新的物理块需要回收的话，回收该块并启动I/O设备管理程序，把回收的50个块号与块数写入新回收的块中。然后，将Ptr重新置1另起一个新组。显然，对空闲块的分配和释放必须互斥进行，否则将会发生数据混乱。(3)位示图空闲文件目录和空闲块链法在分配和回收空闲块时，都需在文件存储设备上查找空闲文件目录项或链接块号，这必须经过设备管理程序启动外设才能完成。为提高空闲块的分配回收速度，用位示图进行管理。系统首先从内存中画出若干个字节，为每个文件存储设备建立一张位示图。这张位示图反映每个文件存储设备的使用情况。在位示图中，每个文件存储设备的

34、物理块都对应一个比特位。如果该位为“0”，则表示所对应的块是空闲块；反之，如果该位为“1”，则表示所对应的块已被分配出去。利用位示图来进行空闲块分配时，只需查找图中的“0”位，并将其置为“1”位。反之，利用位示图回收时只需把相应的比特位由“1”改为“0”即 可。文件目录管理为了实现对文件的按名存取，首先，每个文件必须有一个文件名与其对应。一般用户文件名由用户指定，系统文件和特殊文件在系统设计时指定。必须把文件名及其结构信息等按一定的组织结构排列，以方便文件的搜索。把文件名和对该文件实施控制管理的控制管理信息称为该文件的文件说明，并把一个文件说明按一定的逻辑结构存放到物理存储块的一个表目中。利用

35、文件说明信息，可以完成对文件的创建、检索以及维护作用。因此，把一个文件的文件说明信息称为该文件的目录。对文件目录的管理就是对文件说明信息的管理。文件目录的管理要解决存储空间的有效利用，还要解决快速搜索、文件命名冲突、以及文件共享问题。文件的组成从文件管理角度看，一个文件包括两部分：文件说明和文件体。文件体指文件本身的信息，它可能是前面各节讨论的记录式文件或字符流式文件。文件说明有时也叫文件控制块(FCB)，它至少包括文件名、与(物理结构是连续结构时)文件名相对应的文件内部标识以及文件信息在文件存储设备上第一个物理块的地址（物理结构是边连续结构时）。另外，根据系统要求不同，它还包括关于文件逻辑结

36、构、物理结构、存取控制和管理信息等。这里的管理信息主要指访问时间、以及记账信息等。文件说明组成目录文件。文件系统利用目录文件完成按名存取和对文件信息的共享与保护。文件目录文件目录可分为单级目录、二级目录和多级目录。单级目录是一种最简单、最原始的目录结构。如果文件系统为存储设备的所有文件建立一张目录表，每个文件在其中占有一项用来存放文件说明信息。该目录表存放在存储设备的某固定区域，在系统初启时或需要时，系统将其调入内存，(或部分调入内存)。文件系统通过对该表提供的信息对文件进行创建、搜索、删除等操作。利用单级目录，文件系统就可实现对文件系统空间的自动管理和按名存取。单级目录时的文件系统读写处理过

37、程如图。单级目录的读写处理过程 不过，由于在单级目录表中，各文件说明项都处于平等地位，只能按连续结构或顺序结构存放。如果两个不同的文件重名的话，则系统将把它们视为同一文件。另外，由于单级目录必须对单级目录表中所有文件信息项进行搜索，因而，搜索效率也较低。为了改变单级目录中文件命名冲突问题和提高对目录表的搜索速度，单级目录被扩充成二级目录。二级目录结构中，各个文件的说明信息被组织成目录文件，且以用户为单位把各自的文件说明画分为不同的组。然后，这些不同的组名有关存取控制信息存放在OK主目录(MFD)的目录项中。与主目录 MFD相对应，用户文件的文件说明所组成的目录文件被称为用户文件目录(UFD)。

38、这样，由MFD和UFD就形成二级目录。二级目录的结构如图。二级目录结构当用户要对一个文件进行存取操作或创建、删除一个文件时，首先从 MFD找到对应的目录名，并从用户名查找到该用户的 MFD。余下的操作与单级目录时相同。使用二级目录可以解决文件重名和文件共享问题，并可获得较高的搜索速度。由于二级目录时首先从主目录 MFD开始搜索，因此，从系统管理的角度来看，文件名已演变成为用户名/用户文件名。从而，即使两个不同的用户具有同名文件，系统也会把它们区别开来。再者，利用二级目录，也可以方便地解决不同用户间的文件共享问题，这只要在被共享的文件说明信息中增加相应的共享管理项和把共享文件的文件说明项指向被共

39、享文件的文件说明项即可。另外，与单级目录相比，如果单级目录表的长度为 n的话，则单级目录时的搜索时间与 n成正比;在二级目录时，由于的目录已被画分为个子集，则二级目录的搜索时间是与成正比的。这里的是用户个数，是每个用户的文件的个数。一般有，从而二级目录的搜索时间要快于单级目录。把二级目录的层次关系加以推广，就形成了多级目录。在多级目录结构中，除了最低一级的物理块中装有文件信息外，其他每一级目录中存放的都是下一级目录或文件的说明信息。由此形成层次关系，最高层为根目录，最低层为文件。多级目录构成树形结构，如图所示。文件系统的树形结构树形结构多级目录结构具有下列特点：(1)层次清楚。由于分支结构，不

40、同性质、不同用户的文件可以构成不同的子树，便于管理。不同层次、不同用户的文件可以被赋予不同的存取权限，有利于文件的保护。(2)解决了文件重名问题。文件在系统中的搜索路径是从根开始到文件名为止的各文件名组成，因此，只要在同一子目录下的文件名不发生重复，就不会由文件重名而引起混乱。(3)查找搜索速度快。对文件中键名的各种搜索方法,例如线性搜索法,散列法以及二分搜索法都可用来对各级目录进行查找。由于对多级目录的查找每次只查找目录的一个子集，因此，其搜索速度较单级、二级目录时更快。便于共享的文件目录文件系统的一个重要任务就是为用户提供共享文件信息的手段。这是因为对于某一个公用文件来说，如果每个用户都在

41、文件系统内保留一份该文件的副本，这将极大地浪费存储空间。如果系统提供了共享文件信息的手段，则在文件存储设备上只需存储一个文件副本，共享该文件的用户以自己的文件名去访问该文件的副本就可以了。从系统管理的观点看，有三种方法可以实现文件共享。即：(1)绕道法(2)链接法(3)基本文件目录表 BFD绕道法要求每个用户处在当前目录下工作，用户对所有文件的访问都是相对于当前目录进行的。用户文件的固有名(为了访问某个文件而必须访问的各个目录和文件的目录名与文件名的顺序连接称为固有名)是由当前目录到信息文件通路上所有各级目录的目录名加上该信息文件的符号名组成。使用绕道法进行文件共享时，用户从当前目录出发向上返

42、回到与所要共享文件所在路径的交叉点，再顺序下访到共享文件。绕道法需要用户指定所要共享文件的逻辑位置或到达被共享文件的路径。绕道法的原理如图所示。绕道法绕道法要绕弯路访问多级目录，搜索效率不高。为了提高共享其它目录中文件的速度，另一种共享的办法是在相应目录表之间进行链接。即将一个目录中的链指针直接指向被共享文件所在的目录。链接法仍然需要用户指定被共享的文件和被链接的目录。n实现文件共享的一种有效方法是采用基本文件目录表 BFD的方法。该方法把所有文件目录的内容分成两部分：一部分包括文件的结构信息、物理块号、存取控制和管理信息等，并由系统赋予唯一的内部标识符来标识；另一部分则由用户给出的符号名和系

43、统赋给文件说明信息的内部标识符组成。这两部分分别称为符号文件目录表(SFD)和基本文件目录表(BFD)。SFD中存放文件名和文件内部标识符，BFD中存放除了文件名之外的文件说明信息和文件的内部标识符。采用基本文件目录的多级目录结构在图中，为了简单起见，未在 BFD表项中列出结构信息、存取控制信息和管理控制信息等。另外，在文件系统中，系统通常预先规定赋予基本文件目录、空白文件目录、主目录 MFD的符号文件目录固定不变的唯一标识符，在图中它们分别为 0,1,2。采用基本文件目录方式可较方便地实现文件共享。如果用户要共享某个文件，则只需给出被共享的文件名，系统就会自动在SDF的有关文件处生成与被共享

44、文件相同的内部标识符id,例如在图中，用户Wang和Zhang共享标识符为6的文件，对于系统来说，标识符6指向同一个文件；而对Wang和Zhang两用户来说,则对应于不同的文件名b.c和f.c。目录管理存放文件说明信息或目录管理说明信息的目录项构成目录文件，这些文件同样存放在文件存储设备中。在存取一个文件时，必须访问多级目录。如果访问每级目录时都必须到文件存储设备上去搜索，浪费CPU处理时间、降低了处理速度，给输入输出设备增加了负担。一种解决办法是在系统初启时，把所有的目录文件读入内存，由文件系统在内存完成对各级目录的搜索。这种方法需要大量的内存支持。显然是不可取的。另一种折中的方法是：把当前

45、正在使用的那些文件的目录表目复制到内存中。为此，系统提供两种特殊的操作把有关的目录文件复制到内存的指定区；以及当用户不再访问有关信息文件时删去有关目录文件的内存副本。把文件存储设备上的目录文件复制到内存的操作称为打开文件(fopen)，而把删除文件的内存副本的操作称为关闭文件(fclose)。这两个操作一般以系统调用的方式提供。对于按BDF和SDF方式排列的多级文件目录来说，系统按以下方式打开一个文件。(1)把主目录 MFD中的相应表目，也就是与待打开文件相联系的有关表目复制到内存。例如，若准备打开图中的文件a.c，则将 MFD中的第一项(Wang)复制到内存。(2)根据(1)所复制得到的标识

46、符，再复制此标识符所指明的基本文件目录表BDF 的有关表目。例如图中的id=3的BDF中表目项。这个表目中包括有存取控制信息、结构信息以及下级目录的物理块号等。(3)根据(2)所得到的子目录说明信息搜索SFD，以找到与待打开文件相对应的目录表项。如果找到的表目仍然是子目录名，则系统将根据其对应的标识符id，继续上述复制过程，直到所找到的表目是待打开的文件名。例如在图中文件名a.c。(4)根据(3)所搜索到的文件名所对应的标识符id，把相应的BDF 的表目项复制到内存。这样，待打开文件的说明信息就已复制到了内存中。由复制的文件说明，系统显然可以方便地得到文件的有关物理块号。从而，系统可对文件进行

47、有关操作。n在完成了上述个步骤之后，就说文件是被打开的了。称这样的文件为打开的文件或活动文件。而且，把内存中存放活动文件的 SFD表目的表称为活动名字活动名字表表，这个表每个用户一张。另外，把内存中存放活动文件的 BFD表目的表称为活动文件表活动文件表，这个表整个系统一张。文件存取控制文件的存取控制是和文件的共享、保护和保密三个不同而又相互联系的问题紧密相关的。文件的共享是指不同的用户共同使用一个文件。文件保护则指文件本身需要防止文件的拥有者本人或其他用户破坏文件内容。文件保密指未经文件拥有者许可，任何用户不得访问该文件。这三个问题实际上是一个用户对文件的使用权限，即读、写、执行的许可权问题。

48、n文件系统的存取控制部分应做到：(1)对于拥有读、写或执行权限的用户，应让其对文件进行相应的操作。(2)对于没有读、写或执行权限的用户，应禁止他们对文件进行相应的操作。(3)应防止一个用户冒充其他用户对文件进行存取。(4)应防止拥有存取权限的用户误用文件。这些功能是由一组称为存取控制验证模块的程序提供的。它们分三步验证用户的存取操作。(1)审定用户的存取权限。(2)比较用户权限的本次存取要求是否一致。(3)将存取要求和被访问文件的保密性比较，看是否有冲突。可有下述个方式来验证用户的存取操作,它们是：(1)存取控制矩阵;(2)存取控制表;(3)口令;(4)密码术。系统设计人员根据需要选择其中一种

49、或几种并将相应的数据结构置于文件说明(BFD等)中，在用户访问存取文件时，对用户的存取权限、存取要求的一致性以及保密性等进行验证。(1)存取控制矩阵存取控制矩阵方式以一个二维矩阵来进行存取控制。二维矩阵的一维是所有的用户，另一维是所有的文件。对应的矩阵元素则是用户对文件的存取控制权，包括读，写，和执行。如图所示。存取控制矩阵当用户向文件系统提出存取要求时，由存取控制验证模块根据该矩阵内容对本次存取要求进行比较，如果不匹配的话，系统拒绝执行。当文件和用户较多时，存取控制矩阵将变得非常庞大，这无论是在占用内存空间的大小上，还是在为使用文件而对矩阵进行扫描的时间开销上都是不合适的。因此，在实现时往往

50、采取某些辅助措施以减少时间和空间的开销。(2)存取控制表存取控制表以文件为单位，把用户按某种关系画分为若干组，同时规定每组的存取权限。这样，所有用户组对文件权限的集合就形成了该文件的存取控制表，如图所示。存取控制表每个文件都有一张存取控制表。在实现时，该表存放在文件说明中，也就是BFD 的有关表目中。文件被打开时,由于存取控制表也相应地被复制到了内存活动文件中,因此,存取控制验证能高效进行。(3)口令方式口令方式有两种。一种是当用户进入系统，为建立终端进程时获得系统使用权的口令。另一种口令方式是，每个用户在创建文件时，为每一个创建的文件设置一个口令，且将其置于文件说明中。显然，口令只有设置者自