操作系统课件.ppt

1、第六章 文 件 管 理,6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性控制,6.1 文件和文件系统,6.1.1 文件、记录和数据项,1. 数据项,(1) 基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位。,(2) 组合数据项。它是由若干个基本数据项组成的，简称组项。根据属性的不同，需要用不同的数据类型来描述。,2. 记录 记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而

2、一个对象，由于他所处的环境不同可把他作为不同的对象。 例如，一个学生，当把他作为班上的一名学生时， 对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、 成绩等数据项。 但若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、 姓名、 性别、 出生年月、 身高、 体重、 血压及病史等项。,3. 文件,文件是指由创建者所定义的、 具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。 在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例如，可以将一个班的学生记录作

3、为一个文件。一个文件必须要有一个文件名， 它通常是由一串ASCII码或(和)汉字构成，名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中又规定可用14个字符。,属性可以包括： 文件类型。 (2) 文件长度。 (3) 文件的物理位置。 (4) 文件的建立时间。,图 6-1 文件、 记录和数据项之间的层次关系,6.1.2 文件类型和文件系统模型,1. 文件类型,按用途分类 系统文件。 (2) 用户文件。 (3) 库文件。 ,2) 按文件中数据的形式分类,源文件。 (2) 目标文件。 (3) 可执行文件。,3) 按存取控制属性分类,只执行文件。 (2) 只读文件。 (3)

4、读写文件。,2. 文件系统模型,图 6-2 文件系统模型,1) 对象及其属性 文件管理系统管理的对象有： 文件。 它作为文件管理的直接对象。 目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。 磁盘(磁带)存储空间。 文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。,2) 对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括：对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、对文件读和写的管

5、理，以及对文件的共享与保护等功能。,3) 文件系统的接口 为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口： (1) 命令接口。这是指作为用户与文件系统交互的接口。 用户可通过键盘终端键入命令，取得文件系统的服务。 (2) 程序接口。这是指作为用户程序与文件系统的接口。 用户程序可通过系统调用来取得文件系统的服务。,6.1.3 文件操作,创建文件。 (2) 删除文件。 (3) 读文件。 (4) 写文件。 (5) 截断文件。 (6) 设置文件的读/写位置。,2. 文件的“打开”和“关闭”操作,所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文

6、件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后， 当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉。,3. 其它文件操作 为了方便用户使用文件，通常，OS都提供了数条有关文件操作的系统调用，可将这些调用分成若干类：最常用的一类是有关对文件属性进行操作的，即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有

7、者(文件主)、改变对文件的访问权，以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另一类是有关目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。,6.2 文件的逻辑结构,对于任何一个文件，都存在着以下两种形式的结构： （1）文件的逻辑结构(File Logical Structure):从用户观点出发看到的文件的组织形式。 分为有结构的（记录式）和无结构的（流式）文件。,（2）文件的物理结构：指文件的存储结构，指文件在外存上的存储组织形式。,6.2.1 文件逻辑结构的类型,有结构文件

8、定长记录。 (2) 变长记录。 顺序文件。 (2) 索引文件。 (3) 索引顺序文件。,2. 无结构文件 如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大量的源程序、 可执行文件、 库函数等， 所采用的就是无结构的文件形式，即流式文件。 其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。在UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。,6.2.2 顺序文件,1. 逻辑记录的排序,第一种是串结构， 各记录之间的顺序与关键字无关。 通常的办法是由时间来

9、决定，即按存入时间的先后排列， 最先存入的记录作为第一个记录，其次存入的为第二个记录， 依此类推。 第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。,2. 对顺序文件(Sequential File)的读/写操作,图 6-3 定长和变长记录文件,3. 顺序文件的优缺点,顺序文件的最佳应用场合，是在对诸记录进行批量存取时， 即每次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上， 并能有效地工作。 在交互应用的场合，如果用户(程序)要求查找或修改单个记

10、录，为此系统便要去逐个地查找诸记录。 这时， 顺序文件所表现出来的性能就可能很差， 尤其是当文件较大时， 情况更为严重。 例如，有一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5103个记录； 如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。,顺序文件的另一个缺点是， 如果想增加或删除一个记录， 都比较困难。 为了解决这一问题， 可以为顺序文件配置一个运行记录文件(Log File)或称为事务文件(Transaction File)， 把试图增加、 删除或修改的信息记录于其中， 规定每隔一定时间， 例如4小

11、时，将运行记录文件与原来的主文件加以合并， 产生一个按关键字排序的新文件。,6.2.3 索引文件,对于定长记录文件，如果要查找第i个记录， 可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址： Ai=iL 然而，对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则,图 6-4 索引文件的组织,6.2.4 索引顺序文件,图 6-5 索引顺序文件,6.2.5 直接文件和哈希文件,1. 直接文件,对于直接文件，则可根据给定的记录键

12、值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直接文件的关键， 在于用什么方法进行从记录值到物理地址的转换。,2. 哈希(Hash)文件,图 6-6 Hash文件的逻辑结构,6.3 外存分配方式,外存分配方式,连续分配：,链接分配：,索引分配：,顺序文件,链接文件,索引文件,文件的物理结构,连续分配为每一个文件分配一组相邻接的盘块。采用这种分配方式时，可把逻辑文件中的记录顺序的存储到邻接的物理盘块中，从而保证了逻辑文件中的记录顺序与存储器中占用盘块的

13、顺序一致性。,图 6-7 磁盘空间的连续分配,6.3.1 连续分配,同内存的动态分区一样， 在连续分配方法中，随着文件的建立和删除，磁盘空间被分割成很多小的碎片。 回忆内存动态分区分配中的碎片怎样解决？,“拼接”或“紧凑”算法，外存也可以通过此算法把空间集中到一块。,内存 不需用户干预系统自动完成 时间短,外存 需用户手动完成 时间比较长,2. 连续分配的主要优缺点,连续分配的主要优点如下： 顺序访问容易，且支持直接存取。 (2) 由于占用的是一条磁道或相邻的磁道，所以顺序访问速度快。,连续分配的主要缺点如下： 要求有连续的存储空间，降低了外存的利用率。 (2) 必须事先知道文件的长度。,6.

14、3.2 链接分配： 通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，这样形成的物理文件成为链接文件。,链接文件的优点（1）消除了外部碎片，提高了外存的利用率。（2）无需事先知道文件的大小，满足了动态增长的需要。,链接方式可分为隐式链接和显示链接。,1. 隐式链接:在文件的每个目录项中，都含有指向文件的起始盘块和最后一个盘块的指针。,图 6-8 磁盘空间的链接式分配,隐式链接方式存在的问题：,（1）只适合顺序访问，对随机访问的效率极低效。,（2）可靠性差：可用双向链表解决。,（3）检索速度慢，指针需占据一定的存储空间：可把几个盘块合成一个簇作为分配空间的基本单位。,2.

15、 显式链接：把用于链接文件各物理块的指针，显式的存放在内存的一张链接表中，该表在磁盘中仅有一张，由于分配给文件的所有盘块号都放在此表中，所以此表被称为文件分配表。,图 6-9 显式链接结构,该文件的第一个盘块,和隐式链接相比，由于FAT被加到内存中，查找的过程是在内存进行的，因此显著的提高了检索的速度，大大减少了访问磁盘的次数。 思考：显式链接存在什么问题？,6.3.3 FAT和NTFS技术,我们常用的文件系统FAT和NTFS所采用的文件分配方式基本上都是类似于前面介绍的显示链接方法。,卷：每个逻辑磁盘就是一个卷，每个卷都是一个能够被单独格式化和使用的逻辑单元，供文件系统分配空间时使用。每个卷

16、中都专门划出一个单独的区域存放自己的目录和FAT表，以及自己的逻辑驱动器字母。通常对于仅有一个硬盘的计算机，最多可将硬盘分为四个卷 。,1. FAT12 1)以盘块为单位进行分配： 在FAT12中,每个FAT表项为12位,在FAT表中最多允许有4096个表项,如果以磁盘块为单位(即扇区,一般为512字节),每个分区的容量为2MB,一个物理磁盘支持四个分区,支持的磁盘容量可达到8MB。,2）以簇为单位进行分配： 为了满足容量不断增大的需要，盘块分配时，以簇为基本单位，簇是一组连续的扇区，在FAT12中簇的大小可以为1、2、4、8个扇区，所管理的磁盘容量最大为64MB。,（3）FAT12的缺点：支

17、持的磁盘容量较小，而且只支持8+3格式的文件名。,图 6-10 MS-DOS的文件物理结构,2. FAT16 为了满足容量不断增大的需要，我们把FAT表的宽度增至16位,我们把16位的FAT表称为FAT16。在FAT16中簇的大小可以为4、8、16、32、64个扇区，因此可管理的最大空间为216 *64*512B=2048MB。,FAT16的缺点：对FAT12 的改善有限，当磁盘容量较大时，如果仍然使用FAT16，采用的簇较大，从而使簇内碎片也增加；FAT12和FAT16都只支持8+3格式的文件名。,3. FAT32 FAT表的项达到了32位，为了减小碎片，FAT32中采用较小的簇，当分区容量

18、不超过8GB时，每个簇大小都固定为4KB。,FAT32的缺点 : (1)文件分配表的扩大，使其运行速度变慢。 (2)FAT32不支持容量小于512MB的分区。 (3)文件的最大长度不能大于4GB。 (4)FAT32不能保持向下兼容。,4. NTFS NTFS是专门为NT开发的文件系统。它有新的特点：首先，它采用64位的磁盘地址；其次，能够支持长文件名；第三，具有系统容错功能；第四，提供了数据一致性；此外，还提供了文件加密、压缩等功能。 NTFS中也是以簇为单位进行分配的，簇也称作“卷因子”，簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定。对于小磁盘，默认磁盘的大小为512字节，对

19、于1G的磁盘，默认磁盘的大小为1KB;事实上，为了在传输效率和簇内碎片之间进行折中，簇的大小通常为4KB。,在NTFS中，以卷为单位，将一个卷中所有的文件信息、目录信息以及未分配空间信息，以文件记录的形式记录在一张主控文件表（MFT）中。卷中的每个文件作为一条记录，在此表中占有一行，每行的大小为1KB,每行称为该行对应文件的元数据，也称为主控文件字。在MFT表中，每个元数据对应文件的所有信息，当文件较小时，全部记录在这1KB的空间内；当文件较大时，可以记录到卷中其它簇中，元数据中记录指向这些簇的指针。,NTFS的缺点：只能被Windows NT识别,缺乏兼容性。,6.3.3 索引分配,1. 单

20、级索引分配 链接分配方式虽然解决了连续分配方式所存在的问题， 但又出现了另外两个问题， 即：,(1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。 (2)需把整个FAT表调入内存，但实际读一个文件时，只用到该文件的盘块号。 ,图 6-11 索引分配方式,1,2,3,0,5,6,7,4,9,10,11,8,13,14,15,12,17,18,19,16,21,22,23,20,25,26,27,24,29,30,31,28,count,file,块序号,jeep,19,目录,索引分配：为每个文件分配一个索引块，把分配给该文件的盘块号都记录在该索引

21、块中。,索引分配的优点： （1）支持直接存取。 （2）不会产生外部碎片。 （3）读取一个文件时，只需把该文件的索引块读入即可。,缺点：每个文件都应有一个对应的索引块，会花费比较多的空间。对于小型文件来说，索引块的利用率极低。,思考：如果一个块的大小为512B,一个索引项占两个字节，单级索引支持的文件大小是多大？,当一个文件太大时，如果分配出去的盘块号已经装满了一个盘块，便为这个文件再分配另一个索引块，再通过指针将各索引块链接起来，当索引块太多时，显然是低效的。为此引进了多级索引机制。,2. 多级索引分配,图 6-12 两级索引分配,思考：如果一个块的大小为512B,一个索引项占两个字节，二级索

22、引支持的文件大小是多大？,图 6-13 混合索引方式,3. 混合索引分配方式,在索引结点中可设置10个直接地址项， 即用iaddr(0)iaddr(9)来存放直接地址。,对于大、 中型文件， 可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。,当文件更大时，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。,思考：在上图中，如果每个磁盘块的大小为4KB,每个索引项占4B，能够管理文件的大小为多大？,直接地址管理文件的大小为：40KB 当文件大于40KB时，与一次间接地址相配合使用，能够管理文件的大小为：40KB+4MB 当文件大于40KB+4MB时，

23、直接地址与一次间接地址、二次间接地址相配合使用，能够管理文件的大小为：40KB+4MB+4GB ,6.4 目 录 管 理,对目录管理的要求： 实现“按名存取”。 (2) 提高对目录的检索速度。 (3) 文件共享。 (4) 允许文件重名。,这是目录管理最基本的功能，也是文件系统提供的最基本的服务。,6.4.1 文件控制块和索引结点,文件控制块（FCB）：用于描述和控制文件的数据结构。文件与文件控制块一一对应。,文件目录：文件控制块的有序集合。一个文件控制块就是一个文件目录项。,目录文件：一个文件目录也被看作一个文件，称为目录文件。它用来管理和实现文件系统功能的文件,通过目录文件可以对其他文件的信

24、息进行检索。,文件控制块 基本信息类 文件名 ； 文件物理位置 ； 文件逻辑结构 ； 文件的物理结构 (2) 存取控制信息类 (3) 使用信息类,图 6-15 MS-DOS的文件控制块,1) 索引结点的引入：文件目录存放在磁盘上，当文件很多时，文件目录可能要占用很多盘块，查找目录的过程中，先将存放目录文件的第一个盘块的目录调入内存，与给定的文件名比较，若未找到，则将下一个盘块的目录项调入内存。如此需要多次启动磁盘。,2. 索引结点,由于检索目录的过程中只用到文件名 ，所以在很多系统中，采用把文件名和文件的描述信息分开的方法，使文件的描述信息形成一个称为索引结点的数据结构，也称为I结点。,2)

25、磁盘索引结点,文件主标识符 (2) 文件类型 (3) 文件存取权限 (4) 文件物理地址 (5) 文件长度 (6) 文件连接计数 (7) 文件存取时间,3) 内存索引结点 (1) 索引结点编号。 用于标识内存索引结点。 (2) 状态。 指示i结点是否上锁或被修改。 (3) 访问计数。 每当有一进程要访问此i结点时， 将该访问计数加1， 访问完再减1。 (4) 文件所属文件系统的逻辑设备号。 (5) 链接指针。 设置有分别指向空闲链表和散列队列的指针。,例1. 文件系统的主要目的是（ ）。 A.实现对文件的“按名存取” B.实现虚拟存取 C.提高外存的读写速度 D.用于存储系统文件 2. 在文件

26、系统中，要求物理块必须连续的物理文件是（ ）。 A.顺序文件B.链接文件C.索引文件D.多重索引文件 3.下列描述中不是文件系统的功能的是（ ）。 A.建立文件目录 B.提供一组文件操作 C.实现对磁盘的驱动调度D.实现从逻辑文件到物理文件的转换 4. 在文件系统中，对文件随机存取时必须按指针进行，效率比较低，采用这种物理结构的是（ ）。 A.顺序文件B.链接文件C.索引文件D.多重索引文件,6.4.2 目录结构,1. 单级目录结构,图 6-16 单级目录,文件系统只有一张目录表,单级目录的优点是简单且能实现目录管理的基本功能按名存取，但却存在下述一些缺点： (1) 查找速度慢 (2) 不允许

27、重名 (3) 不便于实现文件共享,结论：只适用于单用户环境。,2. 两级目录,图 6-17 两级目录结构,主文件目录,用户文件目录,具有以下优点： 提高了检索目录的速度。 (2) 在不同的用户目录中， 可以使用相同的文件名。 (3) 不同用户还可使用不同的文件名来访问系统中的同一个共享文件。,3. 多级目录结构,(1) 目录结构,图 6-19 多级目录结构,(2) 路径名。 在树形目录结构中， 从根目录到任何数据文件， 都只有一条惟一的通路。 在该路径上从树的根(即主目录)开始， 把全部目录文件名与数据文件名，依次地用“/”连接起来， 即构成该数据文件的路径名(path name)。 系统中的

28、每一个文件都有惟一的路径名。 例如，在图 6-19 中用户B为访问文件J， 应使用其路径名/B/F/J来访问。,(3) 当前目录(Current Directory)。 为了方便文件访问，可为每个进程设置一个“当前目录”，又称为“工作目录”。此时各文件所使用的路径名， 只需从当前目录开始， 逐级经过中间的目录文件，最后到达要访问的数据文件。把这一路径上的全部目录文件名与数据文件名用“/”连接形成路径名，如用户B的当前目录是F，则此时文件J的相对路径名仅是J本身。 这样， 把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)；而把从树根开始的路径

29、名称为绝对路径名(absolute path name)。,多级目录的优点：查询速度快，层次结构清晰，能够有效地进行文件的管理和保护。,缺点：在多级目录中查找一个文件，需按路径名逐渐访问各中间节点，增加了磁盘访问的次数，影响查询速度。,4. 增加和删除目录,(1) 不删除非空目录。当目录(文件)不空时， 不能将其删除，而为了删除一个非空目录，必须先删除目录中的所有文件，使之先成为空目录， 后再予以删除。如果目录中还包含有子目录，还必须采取递归调用方式来将其删除， 在MS-DOS中就是采用这种删除方式。 (2) 可删除非空目录。当要删除一目录时，如果在该目录中还包含有文件，则目录中的所有文件和子

30、目录也同时被删除。,例1.文件系统采用二级目录可以（ ）。 A.缩短访问存储器的时间 B.解决同一用户间的命名冲突 C.节省内存空间 D.解决不同用户间的命名冲突 2. 对文件进行检索时，检索的起点必须是根目录。（ ） 3.设置打开文件的目的是把该文件相关信息复制到主存指定区域，以建立和该文件的联系，减少启动磁盘的次数。（ ） 4.操作系统中提供文件系统服务后，用户可以按名存取文件，故用户使用的文件必须有不同的名字。（ ）,6.4.3 目录查询技术,1. 线性检索法：查找/usr/ast/mbox文件的过程如下,图 6-20 查找/usr/ast/mbox的步骤,Usr目录文件存放在132号盘

31、块中,Usr/ast目录文件存放在496号盘块中,2. Hash方法,一种处理此“冲突”的有效规则是： (1) 在利用Hash法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。 (2) 如果目录项中的文件名与指定文件名相匹配， 则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。 (3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值， 再返回到第一步重新开始查找。,例：有一文件系统如图所示，图中的框表示目录，圈表示普通文件。

32、根目录常驻内存，目录文件组织成链接文件，普通文件组织成索引文件。目录表目指示下一级文件名和磁盘地址（共占四个字节）。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后四个字节供链接使用。下级文件在上级目录文件中的次序在图中为从左到右。每个盘块有512字节。普通文件的文件控制块采用混合索引方式，其中每个磁盘块地址占两个字节，前10个地址为直接地址，第11个地址为一级索引表地址，第12个地址为二级索引表地址，第13个地址为三级索引表地址。（如图所示）,（1）一个普通文件最多可以有多少个块？ （2）若要读出文件J中的一页，最多启动磁

33、盘多少次？（3）若要读出文件W中的一页，最少启动磁盘多少次？ （4）就（3）而言，为最大限度减少启动磁盘的次数，可采用什么方法？此时，最多启动磁盘多少次？,6.5 文件存储空间的管理,6.5.1 空闲表法和空闲链表法,1. 空闲表法,图 6-20 空闲盘块表,(2) 存储空间的分配与回收。 空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项， 直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，

34、 即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。,2. 空闲链表法,空闲盘块链。 优点:分配和回收一个盘块非常简单. 缺点:为一个文件分配盘块时,可能要重复操作多次. (2) 空闲盘区链。,6.5.2 位示图法,1. 位示图：利用二进制的一位表示磁盘中的一个盘块使用情况。,图 6-22 位示图,2. 盘块的分配,(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。 (2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-

35、1)+j 式中， n代表每行的位数。 (3) 修改位示图， 令mapi,j=1。,3. 盘块的回收,(1) 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修改位示图。 令map i,j=0。,6.5.3 成组链接法,1. 空闲盘块的组织,图 6-23 空闲盘块的成组链接法,2. 空闲盘块的分配与回收 当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底， 即S.

36、free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。 然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。,在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时， 表示栈已满，便将现有栈中的100个盘块号， 记入新回收的盘块中，再将其盘块号作为新栈底。,6.6 文件

37、共享与文件保护,图 6-24 包含有共享文件的文件系统,由树变成了有向非循环图,图 6-25 基于索引结点的共享方式,图 6-25 进程B链接前后的情况,6.6.2 利用符号链实现文件共享,在利用符号链方式实现文件共享时， 只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。这样， 也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。 当文件的拥有者把一个共享文件删除后， 其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。,缺点（1）当其他用户读文

38、件时，系统根据给定的文件路径名，去查找目录，直至找到该文件的索引结点。每次访问共享文件时，都可能要多次读盘。（2）符号链文件要耗费一定的磁盘空间。（3）两种共享方式都有一个共同的问题遍历文件系统时，会多次遍历到该共享文件。,例：位示图方法可用于( )。A.磁盘空间的管理B.磁盘的驱动调度C.文件目录的查找D.页式虚拟存贮管理中的页面调度,6.6.3 磁盘容错技术,(1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。 (2) 通过磁盘容错技术， 来防止由磁盘部分的故障所造成的文件不安全性。 (3) 通过“后备系统”来防止由自然因素所造成的不安全性。,1.访问控制技术,9.4.1 访问矩

39、阵(Access Matrix),1) 访问权 为了对系统中的对象加以保护，应由系统来控制进程对对象的访问。我们把一个进程能对某对象执行操作的权力称为访问权(Access right)。每个访问权可以用一个有序对(对象名， 权集)来表示，,2) 保护域 为了对系统中的资源进行保护而引入了保护域的概念，保护域简称为“域”。“域”是进程对一组对象访问权的集合， 进程只能在指定域内执行操作，这样，“域”也就规定了进程所能访问的对象和能执行的操作。在图 9 - 9中示出了三个保护域。在域1中有两个对象，即文件F1和F2，只允许进程对F1读，而允许对F2读和写；而对象Printer1同时出现在域2和域3

40、中，这表示在这两个域中运行的进程都能使用打印机。,图 9 9 三个保护域,3) 进程和域间的静态联系方式 在进程和域之间，可以一一对应，即一个进程只联系着一个域。这意味着，在进程的整个生命期中，其可用资源是固定的，我们把这种域称为“静态域”。在这种情况下，进程运行的全过程都是受限于同一个域，这将会使赋予进程的访问权超过了实际需要。 例如，某进程在运行开始时需要磁带机输入数据；而在进程快结束时，又需要用打印机打印数据。在一个进程只联系着一个域的情况下，则需要在该域中同时设置磁带机和打印机这两个对象，这将超过进程运行的实际需要。,4) 进程和域间的动态联系方式 在进程和域之间，也可以是一对多的关系

41、，即一个进程可以联系着多个域。在此情况下，可将进程的运行分为若干个阶段，其每个阶段联系着一个域，这样便可根据运行的实际需要，来规定在进程运行的每个阶段中所能访问的对象。我们把一对多的联系方式称为动态联系方式，在采用这种方式的系统中，应增设保护域切换功能，以使进程能在不同的运行阶段， 从一个保护域切换到另一个保护域。,2. 访问矩阵 我们可以利用一个矩阵来描述系统的访问控制，并把该矩阵称为访问矩阵(Access Matrix)。 访问矩阵中的行代表域， 列代表对象，矩阵中的每一项是由一组访问权组成的,每一项访问权access(i,j)定义了在域Di中执行的进程能对对象Qj所施加的操作集。,图 9

42、 10 一个访问矩阵,3. 具有域切换权的访问矩阵 为了实现在进程和域之间的动态联系，应能够将进程从一个保护域切换到另一个保护域。为了能对进程进行控制，同样应将切换作为一种权力，仅当进程有切换权时，才能进行这种切换。 为此，在访问矩阵中又增加了几个对象，分别把它们作为访问矩阵中的几个域；当且仅当switchaccess(i,j)时，才允许进程从域i切换到域j。,图 9 11 具有切换权的访问控制矩阵,9.4.2 访问矩阵的修改,1. 拷贝权(Copy Right),图 9 12 具有拷贝权的访问控制矩阵,2. 所有权(Owner Right) 人们不仅要求能将已有的访问权进行有控制的扩散，而且

43、同样需要能增加某种访问权，或者能删除某种访问权。此时， 可利用所有权(O)来实现这些操作。如果在access(i,j)中包含所有访问权，则在域Di上运行的进程，可以增加或删除其在j列上任何项中的访问权。换言之，进程可以增加或删除在任何其它域中运行的进程对对象j的访问权。,图 9 13 带所有权的访问矩阵,3. 控制权(Control Right) 拷贝权和所有权都是用于改变矩阵内同一列中的各项访问权的，或者说，是用于改变在不同域中运行的进程对同一对象的访问权。控制权则可用于改变矩阵内同一行中(域中)的各项访问权，亦即，用于改变在某个域中运行进程对不同对象的访问权。如果在access(i,j)中

44、包含了控制权，则在域Di中运行的进程可以删除在域Dj中运行进程对各对象的任何访问权。,图 9 14 具有控制权的访问矩阵,9.4.3 访问控制矩阵的实现,1. 访问控制表(Access Control List) 这是指对访问矩阵按列(对象)划分，为每一列建立一张访问控制表ACL。在该表中，已把矩阵中属于该列的所有空项删除，此时的访问控制表是由一有序对(域， 权集)所组成。 由于在大多数情况下，矩阵中的空项远多于非空项，因而使用访问控制表可以显著地减少所占用的存储空间，并能提高查找速度。在不少系统中，当对象是文件时，便把访问控制表存放在该文件的文件控制表中，或放在文件的索引结点中， 作为该文件

45、的存取控制信息。,域是一个抽象的概念，可用各种方式实现。 最常见的一种情况是每一个用户是一个域，而对象则是文件。此时，用户能够访问的文件集和访问权限，取决于用户的身份。 通常，在一个用户退出而另一个用户进入时，即用户发生改变时，要进行域的切换；另一种情况是， 每个进程是一个域，此时，能够访问的对象集中的各访问权，取决于进程的身份。 访问控制表也可用于定义缺省的访问权集， 即在该表中列出了各个域对某对象的缺省访问权集。在系统中配置了这种表后，当某用户(进程)要访问某资源时，通常是首先由系统到缺省的访问控制表中，去查找该用户(进程)是否具有对指定资源进行访问的权力。如果找不到，再到相应对象的访问控

46、制表中去查找。,2. 访问权限(Capabilities)表 如果把访问矩阵按行(即域)划分，便可由每一行构成一张访问权限表。换言之，这是由一个域对每一个对象可以执行的一组操作所构成的表。表中的每一项即为该域对某对象的访问权限。 当域为用户(进程)、对象为文件时，访问权限表便可用来描述一个用户(进程)对每一个文件所能执行的一组操作。 图 9 - 15 示出了对应于图 9 - 11 中域D2的访问权限表。在表中共有三个字段。 其中类型字段用于说明对象的类型；权力字段是指域D2对该对象所拥有的访问权限；对象字段是一个指向相应对象的指针，对UNIX系统来说，它就是索引结点的编号。由该表可以看出，域D

47、2可以访问的对象有4个，即文件3、4、 5和打印机，对文件3的访问权限是只读；对文件4的访问权限是读、写和执行等。,图 9 15 访问权限表,访问权限表不能允许直接被用户(进程)所访问。 通常， 将访问权限表存储到系统区内的一个专用区中，只允许专用于进行访问合法性检查的程序对该表进行访问，以实现对访问控制表的保护。 目前，大多数系统都同时采用访问控制表和访问权限表， 在系统中为每个对象配置一张访问控制表。当一个进程第一次试图去访问一个对象时，必须先检查访问控制表，检查进程是否具有对该对象的访问权。如果无权访问，便由系统来拒绝进程的访问，并构成一例外(异常)事件；否则(有权访问)，便允许进程对该

48、对象进行访问，并为该进程建立一访问权限，将之连接到进程。以后，该进程便可直接利用这一返回的权限去访问该对象，这样，便可快速地验证其访问的合法性。 当进程不再需要对该对象进行访问时，便可撤消该访问权限。,1. 第一级容错技术SFT-,1) 双份目录和双份文件分配表 在磁盘上存放的文件目录和文件分配表FAT， 是文件管理所用的重要数据结构。如果这些表格被破坏， 将导致磁盘上的部分或全部文件成为不可访问的，因而也就等效于文件的丢失。为了防止这类情况发生，可在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和FAT。 其中，一份被称为主目录及主FAT； 把另一份称为备份目录及备份FAT。,2) 热修复重定向和写后读校验,热修复重定向(Hot-Redirection)。 (2) 写后读校验(Read after write Verification)方式。,2. 第二级容错技术SFT-,(1) 磁盘镜像(Disk Mirroring)。,图 6-26 磁盘镜像示意,(2) 磁盘双工(Disk Duplexing)。,图 6-27 磁盘双工示意,3. 基于集群技术的容错功能 1）双机热备份模式 2）双机互为备份模式 3）公用磁盘模式,6.7 数据一致性控制,6.7.1 事务,1. 事务的定义 事务是用于访问和修改各种数据项的一个程序单位