操作系统OSppt06

1、第六章第六章 文件管理文件管理教学目的和要求：教学目的和要求： 使学生掌握文件系统的基本概念和实现过程。要求使学生掌握文件系统的基本概念和实现过程。要求理解文件系统的概念。了解文件的使用、文件系统的理解文件系统的概念。了解文件的使用、文件系统的层次模型。掌握文件的逻辑结构、物理组织及对不同层次模型。掌握文件的逻辑结构、物理组织及对不同类型文件的存取方法、文件目录。熟练掌握外存空间类型文件的存取方法、文件目录。熟练掌握外存空间管理及文件共享方式。管理及文件共享方式。 重点难点：重点难点： 文件的逻辑结构、物理组织、文件目录，外存空间文件的逻辑结构、物理组织、文件目录，外存空间管理及文件共享方式。

2、管理及文件共享方式。 第一节第一节 文件和文件系统文件和文件系统第二节第二节 文件的逻辑结构文件的逻辑结构第三节第三节 外存分配方式外存分配方式第四节第四节 目录管理目录管理第五节第五节 文件存储空间的管理文件存储空间的管理第六节第六节 文件共享与文件保护文件共享与文件保护第七节第七节 数据一致性控制（自学）数据一致性控制（自学）作业与复习题作业与复习题目录第一节 文件和文件系统 OS通过文件系统来组织和管理计算机中通过文件系统来组织和管理计算机中存储的大量数据和程序。存储的大量数据和程序。文件的定义与分类文件的定义与分类文件系统模型文件系统模型文件操作文件操作1、文件的定义与分类、文件的定义

3、与分类文件的定义文件的定义l文件是指由创建者所定义的、具有文件名的一组相文件是指由创建者所定义的、具有文件名的一组相关数据元素的集合；关数据元素的集合；l文件的属性文件的属性：文件类型、文件长度、文件的物理位：文件类型、文件长度、文件的物理位置、文件的建立时间等。置、文件的建立时间等。基于文件系统的概念，可以把数据组成分为数据项、基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级记录和文件三级文件文件记录记录1记录记录2记录记录n数据项数据项1数据项数据项2数据项数据项n数据项数据项l基本数据项：描述一个对象的某种属性的字符集基本数据项：描述一个对象的某种属性的字符集l组合数据项：由

4、若干个基本数据项组成组合数据项：由若干个基本数据项组成记录记录l记录是一组相关记录是一组相关数据项数据项的集合，用于描述一个对的集合，用于描述一个对象的某些属性。象的某些属性。l关键字：能够唯一标识一个记录的数据项关键字：能够唯一标识一个记录的数据项文件的两种类型文件的两种类型l有结构文件（记录式文件）有结构文件（记录式文件）l无结构文件（流式文件）无结构文件（流式文件）文件的类型文件的类型 1）按文件的性质和用途分：）按文件的性质和用途分：l系统文件：由系统软件构成的文件，只允许调用执系统文件：由系统软件构成的文件，只允许调用执行，不允许用户读和修改。行，不允许用户读和修改。l用户文件：只允

5、许文件的授权者使用。用户文件：只允许文件的授权者使用。l库文件：允许用户调用不允许修改。库文件：允许用户调用不允许修改。 2）按文件中数据的形式分：）按文件中数据的形式分：l源文件、目标文件、可执行文件源文件、目标文件、可执行文件 3）按存取控制属性分：）按存取控制属性分：l只执行文件、只读文件、读写文件只执行文件、只读文件、读写文件2、文件系统模型、文件系统模型三个层次：三个层次：l对象及其属性对象及其属性l文件：文件管理的直接对象文件：文件管理的直接对象l目录：方便用户对文件的存取和检索目录：方便用户对文件的存取和检索l磁盘（磁带）存储空间磁盘（磁带）存储空间l对对象操纵和管理的软件集合对

6、对象操纵和管理的软件集合（文件系统的核心）（文件系统的核心）l功能：对文件存储空间的管理、对文件目录的管理、用功能：对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、对文件读于将文件的逻辑地址转换为物理地址的机制、对文件读和写的管理、对文件的共享与保护功能。和写的管理、对文件的共享与保护功能。对象及其属性对象及其属性对对象操纵和管理对对象操纵和管理的软件集合的软件集合文件系统接口文件系统接口l文件系统的接口文件系统的接口l命令接口：用户与文件系统的接口命令接口：用户与文件系统的接口l程序接口：用户程序与文件系统的接口程序接口：用户程序与文件系统的接口3、文件操作

7、、文件操作用户通过文件系统提供的用户通过文件系统提供的系统调用系统调用实施对文件的操作实施对文件的操作最基本的文件操作最基本的文件操作l创建文件：分配外存空间创建文件：分配外存空间建立目录项建立目录项l删除文件：删除目录项删除文件：删除目录项回收外存空间回收外存空间l读文件：文件名、内存目标地址、目录项、读指针读文件：文件名、内存目标地址、目录项、读指针l写文件：文件名、内存中源地址、目录项、写指针写文件：文件名、内存中源地址、目录项、写指针l截断文件：将原有文件长度置截断文件：将原有文件长度置0l读写指针定位读写指针定位文件的打开与关闭文件的打开与关闭l打开：系统将指名文件的属性（包括文件在

8、外存打开：系统将指名文件的属性（包括文件在外存的物理位置）从外存拷贝到内存的物理位置）从外存拷贝到内存打开文件表打开文件表的一的一个表目中，将表目编号返回用户个表目中，将表目编号返回用户l关闭：将文件从打开文件表的表目上删除，释放关闭：将文件从打开文件表的表目上删除，释放表目空间表目空间其它操作其它操作l对文件属性的操作对文件属性的操作l对文件目录的操作对文件目录的操作第二节第二节 文件的逻辑结构文件的逻辑结构 文件逻辑结构是从用户角度观察到的文件组织形式文件逻辑结构是从用户角度观察到的文件组织形式 文件物理结构是文件在外存上的存储组织形式文件物理结构是文件在外存上的存储组织形式 提高检索速度

9、提高检索速度 便于修改便于修改 减少文件占用的存储空间减少文件占用的存储空间对文件逻辑结构提出的基本要求：对文件逻辑结构提出的基本要求： 文件逻辑结构的类型文件逻辑结构的类型 顺序文件顺序文件 索引文件索引文件 索引顺序文件索引顺序文件内容包括：内容包括：1、文件逻辑结构的类型、文件逻辑结构的类型有结构文件（记录式文件）有结构文件（记录式文件）l定义定义：由一个以上的记录构成的文件：由一个以上的记录构成的文件l基本分类基本分类：定长记录、变长记录：定长记录、变长记录l文件的组织文件的组织：l顺序文件：一系列记录按某种顺序排列形成顺序文件：一系列记录按某种顺序排列形成l索引文件：记录为变长，索引

10、文件：记录为变长，每个每个记录一个索引表项记录一个索引表项l索引顺序文件：索引顺序文件：每组每组记录的第一个记录设一表项记录的第一个记录设一表项无结构文件（无结构文件（流式文件）流式文件）l定义定义：由字符流构成的文件：由字符流构成的文件l大量的源程序、可执行文件、库函数等大量的源程序、可执行文件、库函数等l文件长度以文件长度以字节字节为单位为单位l对流式文件的访问采用读写指针指出下一个要访对流式文件的访问采用读写指针指出下一个要访问的字符问的字符lUNIX系统中所有文件都被看作是流式文件系统中所有文件都被看作是流式文件2、顺序文件、顺序文件逻辑记录的排序逻辑记录的排序l串结构串结构(以时间排

11、序以时间排序)、顺序结构（按关键字排序）、顺序结构（按关键字排序）对顺序文件的读对顺序文件的读/写操作写操作l定长记录：定长记录：Rptr:= Rptr + Ll变长记录：变长记录：Rptr:= Rptr + LiR0R1R2Ri- 0- L- 2L- 3L- iLLRptrL0R0LiRi- 0- L0+1-(L0+1)+(Li-1+1)- (L0+1)+(Li+1)L0Rptr- 1顺序文件的优缺点顺序文件的优缺点l适于批量存取、能用于磁带存储适于批量存取、能用于磁带存储l批量存取时，批量存取时，对顺序文件的存取效率是所有逻辑文对顺序文件的存取效率是所有逻辑文件中最高的件中最高的l查找或修

12、改单个记录效率低，系统开销大查找或修改单个记录效率低，系统开销大l增增/删一个记录比较困难删一个记录比较困难。（增加事物文件）。（增加事物文件）3、索引文件、索引文件索引表本身是一个定长记录的顺序文件索引表本身是一个定长记录的顺序文件l索引号（记录键或关键字）索引号（记录键或关键字）l长度长度l指针指针索引号索引号 长度长度 指针指针0 m0 xx1 m1 xx2 m2 xx i mi xx 索引表索引表R0R1R2Ri逻辑文件逻辑文件 利用定长记录的顺序文件访问变长记录的文件利用定长记录的顺序文件访问变长记录的文件，对索引进行折半查找，速度更快对索引进行折半查找，速度更快检索时，利用用户程序

13、检索时，利用用户程序提供的关键字和查找算提供的关键字和查找算法法 ，检索索引表，检索索引表，访问访问主文件的记录。主文件的记录。向索引文件中增加新向索引文件中增加新记录时，需修改索引记录时，需修改索引表。表。折半查找举例1,4,7,9,10,30，查找10lowhighmidlowmid high4、索引顺序文件、索引顺序文件索引顺序文件是顺序文件和索引文件的结合，是索引顺序文件是顺序文件和索引文件的结合，是最常见的一种逻辑文件形式。最常见的一种逻辑文件形式。顺序文件中的所有记录分为若干个组；顺序文件中的所有记录分为若干个组；为顺序文件建立一张索引表，在索引表中为每组为顺序文件建立一张索引表，

14、在索引表中为每组中的第一个记录建立一个索引项；中的第一个记录建立一个索引项；索引键索引键 逻辑地址逻辑地址AAA BAAA CAA 索引表索引表AAA AABD AAC BAAA CAA 逻辑文件逻辑文件主键主键 其它属性其它属性检索时，利用用户程序提供的关键字和查找算法检索时，利用用户程序提供的关键字和查找算法 ，检索索引表检索索引表，.，利用顺序查找法查找，利用顺序查找法查找主文件。主文件。索引顺序文件速度：例1:10000个记录，顺序文件：5000次查找查到。索引顺序文件。设100个记录一组。索引表的找法设为顺序法的情况下，则查找次数为50+50=100.例2:1000000个记录：低级

15、索引（100个记录一组）：10000 高级索引：100 速度：50+50+50=150.第三节第三节 外存分配方式外存分配方式连续分配连续分配顺序式文件结构顺序式文件结构链接分配链接分配链接式文件结构链接式文件结构索引分配索引分配索引式文件结构索引式文件结构 外存分配方式即文件的物理组织形式。文件的物理外存分配方式即文件的物理组织形式。文件的物理结构与外存分配方式有关，采用不同的分配方式时，结构与外存分配方式有关，采用不同的分配方式时，将形成不同的文件物理结构。将形成不同的文件物理结构。分配方式分配方式 文件物理结构文件物理结构1、连续分配、连续分配连续分配方式连续分配方式l为每一个文件分配一

16、组相邻接的盘块；为每一个文件分配一组相邻接的盘块；l把逻辑文件中的记录顺序的存储到邻接的各物理把逻辑文件中的记录顺序的存储到邻接的各物理盘块中，此时的文件结构称为盘块中，此时的文件结构称为顺序文件结构顺序文件结构。物。物理文件称为理文件称为顺序文件顺序文件。l保证了逻辑文件中的记录顺序和存储器中文件占保证了逻辑文件中的记录顺序和存储器中文件占用盘块的顺序的一致性。用盘块的顺序的一致性。目录目录26f418list314tr20coulengthstarfile04812159131620172126101418223711151923coutrflist连续分配的优缺点连续分配的优缺点l顺序访

17、问容易，并可实现直接存取；顺序访问容易，并可实现直接存取；l顺序访问速度快；（磁头的移动距离最少）顺序访问速度快；（磁头的移动距离最少）l缺点：要求有连续的存储空间（定期做紧凑处缺点：要求有连续的存储空间（定期做紧凑处理）、必须事先知道文件的长度。理）、必须事先知道文件的长度。外部碎片外部碎片l随着空间的分配和回收，磁盘空间会出现一些随着空间的分配和回收，磁盘空间会出现一些小的、难以再利用的连续区，称为外存的碎片。小的、难以再利用的连续区，称为外存的碎片。l“碎片碎片”的解决方法的解决方法“紧凑紧凑”2、链接分配、链接分配将文件装到多个离散的盘块中，是离散的分配方式。将文件装到多个离散的盘块中

18、，是离散的分配方式。可通过在每个盘块上的链接指针，将同属于一个文件可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，形成的多个离散的盘块链接成一个链表，形成链接式文件链接式文件结构结构。物理文件称为。物理文件称为链接文件链接文件。消除了消除了“碎片碎片”，有利于文件的动态改变。，有利于文件的动态改变。类型：类型：l隐式链接隐式链接l显式链接显式链接隐式链接隐式链接l 在文件的每个在文件的每个目录项目录项中，都含有指向链接文件中，都含有指向链接文件第一盘块和最后一个盘块的指针。第一盘块和最后一个盘块的指针。l每个每个盘块中盘块中都有指向下一个盘块的指针。都有指向下一个

19、盘块的指针。l 只适合于顺序访问，随机访问效率极低。只适合于顺序访问，随机访问效率极低。显式链接显式链接l 把用于链接文件各物理块的指针，显式地存放在把用于链接文件各物理块的指针，显式地存放在内存内存的一张的一张“链接表链接表”中。该表在整个磁盘只设置中。该表在整个磁盘只设置一张。即文件分配表（一张。即文件分配表（FAT）。序号为盘块号）。序号为盘块号0.n-1l FCB （文件控制块）：每个文件的首盘块号作为（文件控制块）：每个文件的首盘块号作为文件地址记录在文件地址记录在FCB中。中。隐式链接隐式链接0 1 2 2 EOF 3 4 7 5 6 7 8 物理块号物理块号 FAT 8 1 FC

20、B物理地址物理地址:4显式链接显式链接目录目录起始块号起始块号:4结束块号结束块号:2文件名文件名:xx01236789451011 0 EOF 1 2 2 EOF 3 4 7 5 6 0 7 8 物理块号物理块号 FAT 8 1 FCB A物理地址物理地址:4MS-DOS的文件物理结构的文件物理结构FCB B物理地址物理地址:6文件文件A占用盘块号：占用盘块号：4、7、8、1、2文件文件B占用盘块号：占用盘块号：6、03、索引分配、索引分配链接分配方式的缺点：链接分配方式的缺点：l不能支持高效的直接存取不能支持高效的直接存取lFAT需要占用较大的内存空间需要占用较大的内存空间单级索引分配单级

21、索引分配l基本思想：将每个文件对应的盘块号集中存放基本思想：将每个文件对应的盘块号集中存放l方法：为每个文件分配一个索引块（表），该方法：为每个文件分配一个索引块（表），该文件的所有盘块号记录在内。文件的所有盘块号记录在内。索引分配方式的索引分配方式的优缺点优缺点：l是一种离散分配方式，不会产生外部碎片是一种离散分配方式，不会产生外部碎片l支持直接访问支持直接访问l缺点：缺点：花费较多的外存空间花费较多的外存空间04812159131620172126101418223711151923countFile 块序号块序号Jeep 19目录目录 9 16 1 10 22 -119索引表索引表多级索

22、引分配多级索引分配l基本思想：基本思想： 为大文件分配磁盘空间时，可形成多个索引块，为大文件分配磁盘空间时，可形成多个索引块，需建立索引块的索引，放到一个索引块中，形需建立索引块的索引，放到一个索引块中，形成两级索引分配方式。成两级索引分配方式。l如果文件非常大，还可用三级、四级索引分配如果文件非常大，还可用三级、四级索引分配方式。方式。第二级索引第二级索引012105106254356357985105106254356357985磁盘空间磁盘空间36074011253607401125第一级索引第一级索引两级索引分配两级索引分配混合索引分配混合索引分配l多种索引分配方式相结合而形成的一种分

23、配方式。多种索引分配方式相结合而形成的一种分配方式。既采用了直接地址，又采用了一级、两级或多级索既采用了直接地址，又采用了一级、两级或多级索引分配方式。引分配方式。l已在已在UNIX系统系统中采用。索引结点中共设中采用。索引结点中共设13个地址个地址项。其中项。其中i.addr(0)i.addr(9)存放直接地址，其它存放直接地址，其它地址项提供间接地址。地址项提供间接地址。datedatedatedatedatedatedatedatei.addr(0)i.addr(1)Single indirectDouble indirect混合索引方式混合索引方式 索引结点索引结点第四节第四节 目录管

24、理目录管理目录管理的要求目录管理的要求文件控制块和索引结点文件控制块和索引结点目录结构目录结构目录管理的要求目录管理的要求目录目录：用于标识系统中文件及其物理地址的一种数：用于标识系统中文件及其物理地址的一种数据结构，供检索使用。据结构，供检索使用。目录管理的要求：目录管理的要求：l实现实现“按名存取按名存取”最基本的功能最基本的功能l提高对目录的检索速度提高对目录的检索速度l文件共享文件共享l允许文件重名允许文件重名1、文件控制块和索引结点、文件控制块和索引结点文件控制块（文件控制块（FCB）l定义定义：描述和控制文件的数据结构：描述和控制文件的数据结构lFCB的有序集合称为的有序集合称为文

25、件目录文件目录（或目录文件）（或目录文件）lFCB包含的信息项包含的信息项l基本信息：基本信息：文件名文件名/物理位置物理位置/逻辑结构逻辑结构/物理结构物理结构l存取控制信息：存取控制信息：不同用户存取权限不同不同用户存取权限不同l使用信息：使用信息：建立建立/修改的日期、时间等修改的日期、时间等盘盘块块数数第第一一块块号号日日期期时时间间备备用用属属性性扩扩展展名名文文件件名名MS-DOS的的FCB索引结点索引结点l索引结点的引入索引结点的引入：l文件很多时，目录文件占用大量盘块。查找目录时文件很多时，目录文件占用大量盘块。查找目录时要多次启动磁盘，顺序读取存放目录文件的盘块。要多次启动磁

26、盘，顺序读取存放目录文件的盘块。l实际上实际上，检索目录文件时，只需要利用文件名进行，检索目录文件时，只需要利用文件名进行查找，所以可以给文件目录瘦身。查找，所以可以给文件目录瘦身。lUNIX系统中，把文件名和文件描述信息分开，由系统中，把文件名和文件描述信息分开，由文件描述信息单独构成文件描述信息单独构成索引结点（简称索引结点（简称i结点）结点）lFCB改变为改变为：文件名指向：文件名指向i结点的指针结点的指针设目录文件所占用的盘块数为N，按顺序查找的方法，找到一个目录项平均需要调入盘块（N+1）/2次。假如一个FCB为64B，盘块大小为1KB，则每个盘块中只能存放16个FCB；若一个文件目

27、录中共有640个FCB，需占用40个盘块，故平均查找一个文件需启动磁盘20次。0 13 14 15UNIX的文件目录的文件目录l磁盘索引结点磁盘索引结点：（每个文件唯一）：（每个文件唯一）文件主标识符文件主标识符：标识文件拥有者：标识文件拥有者文件类型文件类型文件存取权限文件存取权限文件物理地址文件物理地址：每个索引结点有：每个索引结点有13个地址项，直个地址项，直接或间接给出盘块号接或间接给出盘块号文件长度文件长度文件连接计数文件连接计数： 所有指向该文件的文件名的指针计数所有指向该文件的文件名的指针计数文件存取时间文件存取时间：文件最近被存取修改的时间和索：文件最近被存取修改的时间和索引结

28、点被修改的时间。引结点被修改的时间。l内存索引结点内存索引结点：存放在内存中的索引结点。存放在内存中的索引结点。当文件被打开时，要将磁盘的索引结点拷贝到内当文件被打开时，要将磁盘的索引结点拷贝到内存的索引结点中。存的索引结点中。增加了以下内容：增加了以下内容：索引结点编号、状态、访问计数、文件所属文件索引结点编号、状态、访问计数、文件所属文件系统的逻辑设备号、链接指针系统的逻辑设备号、链接指针2、目录结构、目录结构单级目录结构单级目录结构l在整个文件系统中建立一张目录表，每个文件占一在整个文件系统中建立一张目录表，每个文件占一个目录项。个目录项。l目录项包括目录项包括：文件名、扩展名、长度、类

29、型、物理：文件名、扩展名、长度、类型、物理地址及其它文件属性。地址及其它文件属性。xxxxxxxxxxxx文件名文件名2xxxxxxxxxxxx文件名文件名1状态位状态位文件说明文件说明物理地址物理地址文件名文件名表明目录项表明目录项是否空闲是否空闲单级目录结构单级目录结构l新建文件新建文件时，要检索所有目录项，保证新文件名唯时，要检索所有目录项，保证新文件名唯一。建立新表项，置状态位为一。建立新表项，置状态位为1。l删除文件删除文件时，找到目录项，回收空间，清除目录项时，找到目录项，回收空间，清除目录项l优点优点：简单、能实现按名存取：简单、能实现按名存取l缺点缺点： 查找速度慢；查找速度慢

30、； 不允许重名；不允许重名； 不便于文件共享，只能适用于单用户环境。不便于文件共享，只能适用于单用户环境。xxxxxxxxxxxx文件名文件名2xxxxxxxxxxxx文件名文件名1状态位状态位文件说明文件说明物理地址物理地址文件名文件名表明目录项表明目录项是否空闲是否空闲两级目录结构两级目录结构l为每个用户建立一个单独的用户文件目录，由用户为每个用户建立一个单独的用户文件目录，由用户的所有的所有FCB组成。组成。l系统中再建立一个主文件目录。每个用户的目录文系统中再建立一个主文件目录。每个用户的目录文件占一个目录项。件占一个目录项。xxxxSunxxxxWangxxxxZhang指向子目录指

31、针指向子目录指针用户名用户名TestAlphaTestReportmisxDeviceBetaAlphaTestReportTestDeviceBetaMisxMFDUFD两级目录结构两级目录结构l用户可请求系统为自己用户可请求系统为自己建立建立UFD，也可请求系统，也可请求系统将其将其撤消撤消。l新建新建用户文件时，用户文件时，OS检查用户检查用户UFD文件名，文件名，建立新表项。建立新表项。l删除删除用户文件时，用户文件时，OS查找用户查找用户UFD 文件目录文件目录项，回收存储空间，删除目录项。项，回收存储空间，删除目录项。l优点：优点： 提高检索目录的速度提高检索目录的速度 不同的用户

32、目录中文件可以同名不同的用户目录中文件可以同名多级目录结构多级目录结构（树型目录结构）（树型目录结构）l1、目录结构：、目录结构：大型文件系统采用三级或三级以上的目录结构。大型文件系统采用三级或三级以上的目录结构。CBADBADEFAGCAKNJKMJFHA1234567891011121314151617 18 19 20 21ab多级目录结构多级目录结构l2、路径名：、路径名： 从根目录到任何数据文件，都有一条从根目录到任何数据文件，都有一条唯一唯一的通路，的通路，把全部目录文件名和数据文件名，依次用把全部目录文件名和数据文件名，依次用“/”链接链接起来，构成该数据文件的路径名（绝对路径）

33、。起来，构成该数据文件的路径名（绝对路径）。如：如：B/E/J3、当前目录：、当前目录： 进程在一定时间内所访的文件仅限于某个文件目进程在一定时间内所访的文件仅限于某个文件目录之下，该文件目录可设置为当前目录。录之下，该文件目录可设置为当前目录。 把从当前目录开始直到数据文件为止构成的路径把从当前目录开始直到数据文件为止构成的路径名叫做名叫做相对路径相对路径。例如：用户。例如：用户B的当前目录是的当前目录是E，则，则可使用相对路径名可使用相对路径名“J”来访问自己的来访问自己的J文件。文件。增加和删除目录增加和删除目录l增加目录：增加目录： 用户可为自己建立用户可为自己建立UFD，并可再创建子

34、目录。创建，并可再创建子目录。创建文件时，先查看自己的文件时，先查看自己的UFD及其子目录，无重名文及其子目录，无重名文件则在件则在UFD或某子目录中增加一个新目录项。或某子目录中增加一个新目录项。l删除目录：删除目录： 若为空目录，可直接删除目录项。若为空目录，可直接删除目录项。 若非空目录，则：若非空目录，则： a、不删除非空目录。采用的递规用方式删除。、不删除非空目录。采用的递规用方式删除。 b、可删除非空目录。所有文件、可删除非空目录。所有文件/子目录同时删除。子目录同时删除。MS-DOS目录查询技术目录查询技术l线性检索法（顺序检索）：线性检索法（顺序检索）： a.单级目录中单级目录

35、中，利用用户提供的文件名，利用顺序，利用用户提供的文件名，利用顺序查找法，从文件目录中找到指名文件的目录项。查找法，从文件目录中找到指名文件的目录项。 b.在树型目录中在树型目录中，用户提供的文件名是，用户提供的文件名是由由多个文件多个文件分量名组成的路径名，此时须对多级目录进行查找分量名组成的路径名，此时须对多级目录进行查找根目录文件根目录文件 假定用户给定的文件路径名是假定用户给定的文件路径名是/usr/ast/mbox，则查，则查找过程如下：找过程如下：/usr的目录文件的目录文件/usr/ast的目录文件的目录文件第五节第五节 文件存储空间的管理文件存储空间的管理空闲表法和空闲链表法空

36、闲表法和空闲链表法位示图法位示图法成组链接法成组链接法 分配方式：连续分配、离散分配分配方式：连续分配、离散分配 存储空间的基本分配单位是以磁盘块（扇区）存储空间的基本分配单位是以磁盘块（扇区）为单位，而非字节。为单位，而非字节。1、空闲表法和空闲链表法、空闲表法和空闲链表法空闲表法空闲表法连续分配方式连续分配方式l为外存上的所有空闲区建立一张空闲表为外存上的所有空闲区建立一张空闲表l存储空间的分配与回收存储空间的分配与回收l分配：首次适应算法、循环首次适应算法分配：首次适应算法、循环首次适应算法l回收：考虑邻接的前后空闲区拼接合并回收：考虑邻接的前后空闲区拼接合并空闲链表法空闲链表法离散分配

37、方式离散分配方式l空闲盘块链空闲盘块链 将磁盘上的所有空闲空间，以盘块为单位拉成将磁盘上的所有空闲空间，以盘块为单位拉成一条链。一条链。 分配盘块时从链首开始；回收盘块时插入链尾分配盘块时从链首开始；回收盘块时插入链尾l空闲盘区链空闲盘区链 将磁盘上所有空闲盘区（每个盘区可包含若干将磁盘上所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。个盘块）拉成一条链。 每个盘区含有：指示下一个盘区的指针；每个盘区含有：指示下一个盘区的指针； 本盘区大小的信息本盘区大小的信息 分配盘区常采用首次适应算法；回收时要和相分配盘区常采用首次适应算法；回收时要和相邻空闲盘区合并邻空闲盘区合并2 2、位示图法、位

38、示图法位示图位示图l利用二进制的一位来表示磁盘中一个盘块的使用利用二进制的一位来表示磁盘中一个盘块的使用情况。由所有盘块所对应的位构成一个集合，称情况。由所有盘块所对应的位构成一个集合，称为为位示图位示图。用。用mxn个位数构成个位数构成位示图位示图。盘块的分配（分三步进行）盘块的分配（分三步进行）l顺序扫描位示图，找到一个或一组值为顺序扫描位示图，找到一个或一组值为“0”的位；的位；l将找到的位转换成与之相对应的盘块号：将找到的位转换成与之相对应的盘块号： b=n(i-1)+jl修改位示图，令修改位示图，令mapi,j=111000111001001100001111110000111111

39、00011111100001234.161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16位示图位示图盘块的回收（分两步进行）盘块的回收（分两步进行）l将回收的盘块号转换成位示图中的行号和列号：将回收的盘块号转换成位示图中的行号和列号： i=(b-1) DIV n +1 j=(b-1) MOD n +1i=(b-1) DIV n +1 j=(b-1) MOD n +1l修改位示图，修改位示图，令令mapi,j=0优点优点l从位示图中很容易找到一个或一组相邻接的空闲从位示图中很容易找到一个或一组相邻接的空闲盘块；盘块；l位示图占用空间小，可常驻内存；位示图占用空间小，可

40、常驻内存；3 3、成组链接法、成组链接法结合了空闲表法和空闲链表法而形成的一种空闲盘块结合了空闲表法和空闲链表法而形成的一种空闲盘块管理方法，克服了表太长的缺点。（管理方法，克服了表太长的缺点。（UNIXUNIX采用采用）空闲盘块的组织空闲盘块的组织l空闲盘块号栈超级块空闲盘块号栈超级块l每每100100个空闲盘块作为一组个空闲盘块作为一组l将第一组的盘块总数和所有的盘块号，记入空闲盘将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中块号栈中l每组含有的盘块数和所有盘块记入前一组的末盘块每组含有的盘块数和所有盘块记入前一组的末盘块l最后一组只有最后一组只有9999个盘块，以个盘块，以0作为结

41、束标志作为结束标志空闲盘块号栈总数019899201299300400399301500499401599501第一组第二组第三组最后一组空闲盘块的分配空闲盘块的分配用户申请一个盘块用户申请一个盘块超级块中空闲块总数超级块中空闲块总数1？从栈顶取出盘块号，从栈顶取出盘块号，将对应盘块分给用户将对应盘块分给用户将栈底盘块号对应的盘块内容读入栈中，将栈底盘块号对应的盘块内容读入栈中，把原栈底对应的盘块分配出去把原栈底对应的盘块分配出去NY 将回收盘块的盘块号记入空闲盘块号栈顶部，总数将回收盘块的盘块号记入空闲盘块号栈顶部，总数1 当栈中原空盘块总数当栈中原空盘块总数100时（栈满），将现有栈中的时

42、（栈满），将现有栈中的100个盘块号，记入新回收盘块中，再将其盘块号作为个盘块号，记入新回收盘块中，再将其盘块号作为新栈底。新栈底。空闲盘块的回收空闲盘块的回收1182455845680空闲块数空闲块数98118245584568思考：思考：Unix系统中超级块系统中超级块如下图示如下图示，问：，问：（1）当用户释放了）当用户释放了78，89，108，204物理块物理块后，超级块中的变化情况如何？后，超级块中的变化情况如何？（2）当用户又申请了五个物理）当用户又申请了五个物理块，超级块中的变化情况如何？块，超级块中的变化情况如何？第六节 文件共享与文件保护基于索引结点的共享方式基于索引结点的共

43、享方式利用符号链实现文件共享利用符号链实现文件共享磁盘容错技术磁盘容错技术1 1、基于索引结点的共享方式、基于索引结点的共享方式引入引入：l在树型结构目录中，多用户要共享一个文件，必须在树型结构目录中，多用户要共享一个文件，必须将共享文件链接到多个用户目录中。将共享文件链接到多个用户目录中。如何建立如何建立B目录与共享文件的链接呢？目录与共享文件的链接呢？l方法一：在目录文件中每个目录项是原始的方法一：在目录文件中每个目录项是原始的FCB，则在链接时，必须将文件的物理地址则在链接时，必须将文件的物理地址COPY到到B目目录中。录中。l缺点缺点：以后：以后B或或C继续向该文件添加的内容（盘块）继

44、续向该文件添加的内容（盘块）将不能被共享。将不能被共享。ABCBBBCCCCCCC?BA根目录盘块数盘块数盘块号盘块号filec盘块数盘块数盘块号盘块号文件名文件名2文件名文件名1物理地址物理地址盘块号盘块号盘块数盘块数C目录文件目录文件B目录文件目录文件盘块数盘块数盘块号盘块号filec盘块数盘块数盘块号盘块号文件名文件名2文件名文件名1盘块号盘块号盘块数盘块数基于索引结点的共享方式基于索引结点的共享方式l文件目录中只设置文件名及指向相应索引结点的指文件目录中只设置文件名及指向相应索引结点的指针；针；l文件的物理地址及其它的文件属性等信息只存放在文件的物理地址及其它的文件属性等信息只存放在索引结点中；索引结点中；C用户文件目录用户文件目录CmnFile1Owner=CCount=2物理地址物理地址索引结点索引结点CmnFile1B用户文件目录用户文件目录CmnFile1链接计链接计数数缺点：用户缺点：用户C不再需要此文件时不能执行删除不再需要此文件时不能执行删除2 2、利用符号链实现文件共享、利用符号链