第06章 文件管理

1、1第第6章文件管理章文件管理6.1 6.1 文件系统的概念文件系统的概念 6.2 6.2 文件的逻辑结构文件的逻辑结构 6.3 6.3 文件的物理结构文件的物理结构 6.4 6.4 文件的存取方法文件的存取方法 6.5 6.5 文件目录文件目录 6.6 6.6 文件存储空间管理文件存储空间管理 6.7 6.7 文件共享和保护文件共享和保护 26.16.1文件系统的概念文件系统的概念 6.1.1 文件和文件系统 6.1.2 文件分类 6.1.3 文件操作36.1.1 6.1.1 文件和文件系统文件和文件系统 1.文件文件 ：具有文件名的一组相关信息的集合。通常，文件由若干个记录组成。记录是一些相

2、关数据项的集合，而数据项（信息项）是数据组织中可以命名的最小逻辑单位。 信息项信息项 信息项信息项 . 信息项信息项 . 信息项信息项编号：编号：0 1 i n-1读写指针读写指针46.1.1 6.1.1 文件和文件系统文件和文件系统 2.文件系统的主要功能文件系统的主要功能：n(1)实现按文件名存取文件信息 名字空间名字空间 映射映射 存储空间n(2)为用户提供统一的和友好的接口 n(3)实施对文件和文件目录的管理n(4)文件存储器空间的分配和回收n(5)提供有关文件的共享和保护56.1.1 6.1.1 文件和文件系统文件和文件系统 3.文件系统模型文件系统模型 用户（程序） 文件系统的接口

3、文件系统的接口对对象操纵和管理的软件对对象操纵和管理的软件集合集合对象及其属性对象及其属性图6.1文件系统的模型66.1.1 6.1.1 文件和文件系统文件和文件系统 3.文件系统模型文件系统模型n(1)(1)对象及其属性对象及其属性: :文件系统管理的对象包括： 文件 目录 磁盘(磁带)存储空间n(2)(2)操纵和管理的软件集合操纵和管理的软件集合：文件系统的核心，包括：文件存储空间的管理、文件目录的管理、将文件的逻辑地址转换为物理地址的机制、对文件读和写的管理，及对文件的共享与保护等。 76.1.1 6.1.1 文件和文件系统文件和文件系统 3.文件系统模型文件系统模型n(3)(3) 接口

4、：接口：两种类型的接口两种类型的接口1)命令接口：用户通过键盘键盘终端键入命令命令 2)程序接口：通过系统调用系统调用来使用文件系统文件系统= =文件管理程序文件管理程序+ +它所管理的它所管理的全部文件全部文件86.1.2 6.1.2 文件分类文件分类 目的：目的：为了更好地管理和使用文件。科学地分门别类，对不同的文件进行不同的管理，不仅提高了文件的存取速度，对文件的共享和保护也有利。 一般通过文件扩展名文件扩展名的方式来体现体现文件类型，文件名和扩展名之间用“.”分隔96.1.2 6.1.2 文件分类文件分类 1.按性质和用途分类按性质和用途分类n(1)系统文件：系统文件：系统软件的文件，

5、用户通过系统调用或系统提供的专用命今来执行，不允许对其进行读写和修改主要有操作系统核心和各种系统应用程序或实用工具程序和数据组成例如：,106.1.2 6.1.2 文件分类文件分类 1.按性质和用途分类按性质和用途分类n(2)库文件：库文件：允许用户进行读取和执行，不允许对其进行修改，主要由各种标准子程序库组成例如：C语言、FORTRAN子程序库存放在子目录下 *.LIB,/lib/,/usr/lib/n(3)用户文件：用户文件： 通过操作系统保存的用户文件主要由用户的源程序等组成，例如：*.c,*.for,*.f,*DBF,*.OBJ116.1.2 6.1.2 文件分类文件分类 2.按操作保

6、护分类按操作保护分类n只读文件：只读文件：只允许读文件，而不允许写文件。标记为：-r r-n可读可写文件：可读可写文件：允许读和写文件。标记为： -rwrw-n可执行文件：可执行文件：允许执行该文件而不允许读和写，标记为： -x x-各个操作系统的各个操作系统的保护方法和级别保护方法和级别有所不同有所不同DOS操作系统三种保护：系统、隐藏、可写UNIX或Linux操作系统有九个级别的保护126.1.2 6.1.2 文件分类文件分类 3.按使用情况分类按使用情况分类n临时文件临时文件：用于系统在工作过程中产生的中间文件，一般有暂存的目录，正常工作情况下，工作完毕会自动删除，一旦有异常情况往往会残

7、留不少临时文件n永久文件永久文件: : 指一般受系统管理的各种系统和用户文件，经过安装或编辑、编译生成的文件，存放在软盘、硬盘或光盘等外存上n档案文件档案文件: : 系统或一些实用工具软件包在工作过程中记录在案的文挡资料文件，以便查阅历史挡案136.1.2 6.1.2 文件分类文件分类 4.按用户观点分类（按用户观点分类（UNIX/Linux系统）系统）n普通文件普通文件( (常规文件常规文件) ) 一般是字符流组成的无结构文件n目录文件目录文件是由文件的目录信息构成的特殊文件，便于操作系统统一管理n特殊文件特殊文件（设备驱动程序）（设备驱动程序）输入输出外部设备被看作特殊文件便于统一管理操作

8、系统把对特殊文件的操作转接指向相应的设备操作，真正的设备驱动程序不包含在这特殊文件中，而是指向与链接到操作系统核心中存放在内存高端部分146.1.2 6.1.2 文件分类文件分类 5.按数据形式分类按数据形式分类n源文件源文件由源程序和数据构成的文件n目标文件目标文件由源程序经过编译，但尚未经过链接程序链接的目标代码后缀名为“.OBJ”（DOS系统）或“.o”（UNIX或Linux操作系统）n可执行文件可执行文件 目标代码经链接程序链接后形成的可以运行的文件编译默认可运行文件：a.out（UNIX或Linux操作系统）或.exe（windows） 156.1.3 6.1.3 文件操作文件操作1

9、.最基本文件操作最基本文件操作n建立文件（建立文件（Create）：）：系统为新文件分配必要的外存空间，并为之建立一个目录项。目录项中记录文件名及其在外存的地址等属性。 n删除文件（删除文件（Delete）：）：系统从目录中找到要删除文件的目录项，使之成为空闲目录项，然后回收文件占用的存储空间。 n打开文件（打开文件（Open）：）：将待访问文件的目录信息读入内存活动文件表中，文件被打开就可以多次使用，直到文件被关闭为止。 166.1.3 6.1.3 文件操作文件操作1.最基本文件操作最基本文件操作n关闭文件（关闭文件（Close）:撤消主存中该文件的目录信息，若文件打开期间，该文件作过修改，

10、则应将其写回辅存。n读文件（读文件（Read）:系统查找目录，找到指定文件的目录项，从中得到被读文件在外存的地址，然后从外存将数据读入内存。 n写文件（写文件（Write）:系统查找目录，找到指定文件的目录项，再利用目录中的文件指针将信息写入文件。 176.1.3 6.1.3 文件操作文件操作2.其它文件操作其它文件操作一类是有关对文件属性进行操作的n改变文件的文件名n改变文件的拥有者n改变对文件的访问权n查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)186.1.3 6.1.3 文件操作文件操作2.其它文件操作其它文件操作另一类是有关目录的n创建一个目录n删除一个目录n改变当

11、前目录和工作目录n实现文件共享的系统调用和对文件系统进行操作的系统调用等。196.2 6.2 文件的逻辑结构文件的逻辑结构 6.2.1 文件逻辑结构的类型6.2.2 顺序文件 6.2.3 索引文件 6.2.4 索引顺序文件6.2.5 直接文件和散列文件 206.2 6.2 文件的逻辑结构文件的逻辑结构文件组织的两种观点：文件组织的两种观点：n用户观点用户观点（逻辑结构）：（逻辑结构）：研究的是用户思维中的抽象文件，也叫逻辑文件。其目的是为用户提供一种结构清晰、使用简便的逻辑组织。用户按此去存储、检索和加工处理有关文件信息。n实现观点实现观点（物理结构）：（物理结构）：研究的是存储在物理设备介质

12、上的实际文件，即物理文件。其目的是选择一些性能良好、设备利用率高的物理结构。系统按此和外部设备打交道，控制信息的传输。216.2.1 6.2.1 文件逻辑结构的类型文件逻辑结构的类型1.有结构文件有结构文件-记录式文件记录式文件 (1) 定长记录 (2) 变长记录 根据记录的组织方式分类： (1) 顺序文件 (2) 索引文件 (3) 索引顺序文件 226.2.1 6.2.1 文件逻辑结构的类型文件逻辑结构的类型2. 无结构文件无结构文件即流式文件流式文件，其长度以字节为单位。大量的源程序、可执行文件、库函数等。采用读写指针来指出下一个要访问的字符，可以把流式文件看作是记录式文件的一个特例。在U

13、NIX系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。 236.2.2 6.2.2 顺序文件顺序文件定长记录： 所有记录长度相等变长记录: 记录长度不固定。(a)固定长度记录 (b)可变长度记录246.2.2 6.2.2 顺序文件顺序文件顺序文件的优缺点：顺序文件的优缺点：n优点：优点：要读或写一大批记录时，对顺序文件的存取效率是所有逻辑文件中最高的；只有顺序文件才能存储在磁带上，并能有效地工作。n缺点：缺点：如果用户要求查找或修改单个记录，系统要逐个地查找诸记录, 效率很差，尤其是当文件较大时，情况更为严重。n增加或删除一个记录较困难。25

14、6.2.3 6.2.3 索引文件索引文件索引文件的组织 变长记录的文件，如果组织为顺序文件，要实现直接存取，效率将非常低。可将其组织为索引文件。 266.2.4 6.2.4 索引顺序文件索引顺序文件将顺序文件中的所有记录分为若干个组记录分为若干个组(例如，50个记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组引表中为每组中的第一个记录建立一个索引项第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。 276.2.4 6.2.4 索引顺序文件索引顺序文件图6.3 索引顺序文件 286.2.5 6.2.5 直接文件和散列文件直接文件和散列文件1. 直接文件直接文件 根据给定

15、的记录键值，直接获得指定记录的物理地址。 2. 散列文件散列文件/哈希哈希(Hash)文件文件 应用最为广泛的一种直接文件。利用Hash函数(或称散列函数)，可将记录键值转换为相应记录的地址。 296.2.5 6.2.5 直接文件和散列文件直接文件和散列文件图6.4 散列文件的逻辑结构306.3 6.3 文件的物理结构文件的物理结构 物理结构物理结构指一个文件在外存上的存储组织形式，是从系统的角度来看文件。采用不同的外存分配方式时，将形成不同的文件物理结构。例如，在采用连续分配方式时的文件物理结构，将是顺序式的文件结构；链接分配方式将形成链接式文件结构；而索引分配方式则将形成索引式文件结构。

16、316.3 6.3 文件的物理结构文件的物理结构 6.3.1 顺序结构 6.3.2 链接结构 6.3.3 索引结构 326.3.1 6.3.1 顺序结构顺序结构又称连续结构连续结构，是一种最简单的物理文件结构，它将一个文件的信息存放在若干连续的物理块中由一组相邻的物理块组成，是对记录式文件取连续区分配而构成的文件。特点特点 ：顺序存取速度快 所需的磁盘寻道次数和寻道 时间最少336.3.1 6.3.1 顺序结构顺序结构346.3.1 6.3.1 顺序结构顺序结构图6.5 顺序文件的连续空间分配 356.3.1 6.3.1 顺序结构顺序结构连续分配的主要优点如下： (1) 顺序访问容易 (2)

17、顺序访问速度快连续分配的主要缺点如下： (1) 要求有连续的存储空间 (2) 必须事先知道文件的长度 思考：程序文件、数据库文件是否适合连续分配？程序文件、数据库文件是否适合连续分配？366.3.2 6.3.2 链接结构链接结构又称串联结构串联结构，将一个逻辑上连续的文件信息存放在外存的不连续(或连续)物理块中。在采用链接分配(Chained Allocation)方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表 376.3.2 6.3.2 链接结构链接结构优点：优点：提高了磁盘空间利用率 不存在外部碎片问题 有利于文件插入和删除 有利于文件动态扩充缺点：缺

18、点：存取速度慢，不适于随机存取 可靠性问题，如指针出错 更多的寻道次数和寻道时间 链接指针占用一定的空间链接结构的一个变形: 文件分配表文件分配表FATFAT显式链接38文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录01234567891011121314151617181920212223242526272829303111016-1251.1.隐式链接隐式链接 磁盘空间的链接式分配392.2.显式链接显式链接 文件分配表文件分配表(FAT) 显式链接结构 40文件分配表文件分配表(FAT)(FAT)将盘块中的链接字按盘块号的顺序集中起来，构成盘文件映射表/文件分配表 。

19、利用FAT可方便地进行随机存取。41图示图示42文件分配表文件分配表(FAT)(FAT)缺点：缺点：FAT也要占用一定的存储空间，若盘的容量较大，也可能占用较多的存储空间。在进行文件访问时，可能在内存中装不下整个FAT，这样就会造成若要读某块文件信息时，还要读盘块映射表的操作，影响使用效率。43FATFAT的实例的实例在在MS-DOSMS-DOS和和WindowsWindows系统中，文件的物理系统中，文件的物理结构使用的是结构使用的是FATFAT结构。结构。将磁盘空间划分为块，每块大小为扇区将磁盘空间划分为块，每块大小为扇区的整数倍。在的整数倍。在FATFAT文件系统中块称为文件系统中块称为

20、簇簇一个磁盘分区能分为多少簇则一个磁盘分区能分为多少簇则FATFAT就有多就有多少表项少表项44思考思考什么叫什么叫FAT16FAT16、FAT32FAT32？在在FAT16FAT16中一簇最大中一簇最大6464个扇区，为什么个扇区，为什么FAT16FAT16能管理的磁盘分区为能管理的磁盘分区为2G2G？FAT32FAT32同同FAT16FAT16相比有什么优点？相比有什么优点？45思考思考对于对于FAT16FAT16文件系统，若一个磁盘分区的文件系统，若一个磁盘分区的大小为大小为512M512M，问一个簇最少要为多少个，问一个簇最少要为多少个扇区？扇区？簇是大点好，还是小点好？簇是大点好，还

21、是小点好？466.3.3 6.3.3 索引结构索引结构文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中索引表索引表：存放文件信息所在的逻辑块号和与之对应的物理块号 476.3.3 6.3.3 索引结构索引结构486.3.3 6.3.3 索引结构索引结构每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号，都记录在该索引块中，该索引块就是一个含有许多盘块号的数组。 单级索引分配单级索引分配49012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索

22、引表地址文件目录文件目录Jeep 19 916 11025 -1 -1 -119图6.9单级索引分配506.3.3 6.3.3 索引结构索引结构为大文件分配磁盘空间时，如果所分配盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块。再通过链指针将各索引块链接起来，此时效率较低，可采用多级索引。多级索引多级索引: :将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中2. 多级索引分配多级索引分配512.2.多级索引分配多级索引分配01210510625435635798510510625474035635711259853607401125主索引360第二级索引

23、磁盘空间图6.10两级索引分配526.3.3 6.3.3 索引结构索引结构指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。 3.混合索引分配混合索引分配533.3.混合索引分配混合索引分配图 6.11混合索引分配543.3.混合索引分配混合索引分配- -例例例：假如每个盘块的大小为4KB，iaddr(0)iaddr(9) 这10个直接地址项支持的文件最大为：4KB4KB10=10=40KB一次间接地址：iaddr(10)地址项可存放1K个盘块号，因而允许文件长达： 1K 1K 4KB 4KB

24、40KB40KB4MB4MB 二次间接地址：iaddr(11) 地址项可存放：1K 1K=1M个盘块号，允许的文件长度为：1M1M 4kB 4kB 4MB 4MB 4 4B B三次间接地址：同理地址项iaddr(12) 允许的文件最大长度可达4TB4TB。553.3.混合索引分配混合索引分配unixUNIX文件系统采用的是混合索引结构(综合模式)。每个文件的索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址） 。 如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项

25、作为二次和三次间接寻址UNIX中采用了三级索引结构后，文件最大可达16兆个物理块566.3.3 6.3.3 索引结构索引结构优点：优点： 保持了链接结构的优点,又解决了其缺点：既能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间缺点：缺点： 较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间576.4 6.4 文件的存取方法文件的存取方法 文件的存取方法是指读写文件存储器上的一个物理块的方法，通常有以下三类存取方法：6.4.1 顺序存取6.4.2 直接存取6.4.3 按键存取586.4.1 6.4.1 顺序存取顺序存取顺序存取是按照文件

26、的逻辑顺序依次存取。R0R1R2R3RiLLLLLL2L3L4LL(i 1)LRptr(a) 定长记录文件L0R0L1R1RiWptr(b) 变 长记录文件Li00L0L0 1L1L0 L1 2Li(Lk 1)i1k0(Lk 1)ik0596.4.1 6.4.1 顺序存取的方法顺序存取的方法定长记录：定长记录：读指针rptr指向下一次读出的记录地址； 写指针wptr指向下一次写入的记录地址。 读完指针做相应修改:rptr+L=rptrrptr+L=rptr 写完指针做相应修改:wptr+L=wptrwptr+L=wptr变长记录：变长记录： 每次将读写指针加上Li，Li是刚读或刚写完的记录的长

27、度：rptr+Lrptr+Li=rptr=rptrwptr+Lwptr+Li=wptr=wptr606.4.2 6.4.2 直接存取直接存取直接存取(又称随机存取随机存取)法允许按任意顺序存取文件中的任何一个物理记录，可以根据记录的编号来直接存取文件中的任意一个记录，或者是根据存取命令把读写指针移到欲读写信息处。UNIX系统以及MS-DOS等操作系统都采用顺序存取和随机存取等两种方法。616.4.2 6.4.2 直接存取直接存取定长记录的顺序文件，第i个记录的首地址为：Rptraddr i L其中addr是该文件的首地址，L为记录长度。变长记录的文件，通常采用索引文件的方式组织，由于索引表本身

28、是定长的，也可以采用同样的方法，先用直接存取法在索引表中找，再找到具体对应的地址。 626.4.3 6.4.3 按键存取按键存取按键存取法实质上是直接存取法直接存取法，它不是根据记录编号或地址来存取，而是根据文件记录中的关键字(通常称为键)经过某种方法计算处理，转换成相应的物理地址后进行存取，它被广泛用于现代操作系统和数据库管理系统中的数据查找。 636.4.3 6.4.3 按键存取的搜索方法按键存取的搜索方法对文件进行搜索的目的：查找出特定记录所对应的逻辑地址，以便将其转换为相应的物理地址 搜索包括：键的搜索和记录的搜索。在用户给定所要搜索的键名和记录之后，确定该键名在文件中的位置；然后在搜

29、索到所要查找的键之后，在含有该键的所有记录中查找出所需要的记录。 646.4.3 6.4.3 按键存取的搜索方法按键存取的搜索方法由Ri所对应键名查找记录队列找到吗？在记录队列查找Ri返回Ri的逻辑地址返回空返回空找到吗？否否是是图6.13记录 Ri的搜索过程656.4.3 6.4.3 按键存取按键存取对键或记录的搜索属于表格搜索，搜索算法大致分为三种类型，即：n(1)线性搜索法线性搜索法(linear search)略略n(2)散列法散列法(hash coding)简要介绍简要介绍n(3)二分搜索法二分搜索法(binary search algorithm) 略略666.4.3 6.4.3

30、按键存取按键存取n(2)散列法散列法(hash coding)：定义一个散列函数h(k)，对于给定的键k，h(k)将其变换为 k所对应的逻辑地址。676.4.3 6.4.3 按键存取按键存取散列冲突：散列冲突：两个不同的输入值变换到同一地址的问题。即对于k1!=k2，有h(k1)=h(k2)=A。 解决散列冲突的方法：n多次散列搜索法多次散列搜索法 n随机数法随机数法n平方散列函数法平方散列函数法 686.5 6.5 文件目录文件目录 6.5.1 文件控制块与索引结点 6.5.2 文件目录与目录文件 6.5.3 目录结构6.5.4 目录查询技术 696.5.16.5.1文件控制块与索引结点文件

31、控制块与索引结点文件控制块（文件控制块（FCB）：操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。一个文件控制块就是一个文件目录项文件目录项。 文件控制块是文件存在的标志FCB就是目录表中的一个目录项706.5.16.5.1文件控制块与索引结点文件控制块与索引结点1 1文件控制块的内容文件控制块的内容(1)基本信息类 文件名 ； 文件物理位置 ； 文件逻辑结构 ； 文件的物理结构 (2) 存取控制信息类 (3) 使用信息类 71DOS/WindowsDOS/Windows中的文件控制块中的文件控制块字节位置FAT16FAT320-7字节文件名文件名8-10字节文件的扩展

32、名文件的扩展名11字节文件的属性文件的属性12-13字节保留未用仅长文件名目录项用，存储其对应的短文件名字节校验和等14-15字节文件建立时间16-17字节文件建立日期18-19字节文件最新访问日期20-21字节文件首簇号的高16位22-23字节文件的创建时间文件最新修改时间24-25字节文件的创建日期文件最新修改日期26-27字节文件的首簇号文件首簇号的低16位28-31字节文件的大小文件的大小（字节）726.5.16.5.1文件控制块与索引结点文件控制块与索引结点2 2索引结点索引结点问题：当文件多时，文件目录占用磁盘上大量的盘块 。设文件目录所占用的盘块数为N，按顺序法查找一个目录项平均

33、需调入盘块(N+1)2次。 分析：分析：在检索目录文件的过程中，只用到了文件名。为此，有的系统(UNIX)，把文件名与文件描述信息分开存放73. .索引结点索引结点文件名索引结点编号文件名1文件名2UNIX的文件目录 将文件除文件名外的描述信息单独形成一个称为索引结点索引结点的数据结构，简称为i结点结点。 文件目录项目录项，由文件名和指向对应的i结点的指针构成 74. .索引结点索引结点磁盘索引结点：磁盘索引结点：存放在磁盘上的索引结点，每个文件有惟一的一个，内容为：n(1) 文件主标识符n(2) 文件类型 n(3) 文件存取权限 n(4) 文件物理地址 n(5) 文件长度 n(6) 文件连接

34、计数 n(7) 文件存取时间 75. .索引结点索引结点内存索引结点内存索引结点 ：存放在内存中 ，文件被打开时，磁盘索引结点拷贝到内存的索引结点中，并增加了以下内容： n(1) 索引结点编号。 n(2) 状态。n(3) 访问计数。 n(4) 文件所属文件系统的逻辑设备号。 n(5) 链接指针。766.5.2 6.5.2 文件目录与目录文件文件目录与目录文件 文件目录文件目录 ：文件控制块(FCB)的有序集合，用于文件描述和文件控制，实现按名存取和文件信息共享与保护。 目录项：目录项：构成文件目录的项目（目录项就是FCB）目录文件：目录文件：文件系统将若干个文件目录组成的一个独立的文件 776

35、.5.2 6.5.2 文件目录与目录文件文件目录与目录文件 对目录管理的要求： n(1) 实现“按名存取” n(2) 提高对目录的检索速度 n(3) 文件共享 n(4) 允许文件重名 786.5.3 6.5.3 目录结构目录结构1单级目录结构单级目录结构为所有文件建立一个目录表。优点：简单且能实现目录管理的基本功能按名存取。 缺点：(1) 查找速度慢 (2) 不允许重名 (3) 不便于实现文件共享 文件名文件名物理地址物理地址文件说明文件说明状态位状态位文件名文件名1 1文件名文件名2 2796.5.3 6.5.3 目录结构目录结构2二级目录结构二级目录结构n将目录分为2级：主文件目录主文件目

36、录（MFDMFD） 和用户文件目录用户文件目录（UFDUFD） nMFD 由用户名，用户子目录所在的物理位置组成； UFD登记该用户所有文件的FCBn产生于多用户分时系统，文件主目录的表目按用户分，每个用户有一个用户文件目录80.二级目录结构81.二级目录结构优点：优点：解决了文件的重名问题和文件共享问题，提高搜索速度，查找时间降低缺点：缺点：不太适合大量用户和大量文件的大系统，增加了系统开销 为此人们提出了多级目录结构，其中为此人们提出了多级目录结构，其中MULTICSMULTICS及及UNIXUNIX系统均采用了多级目录结系统均采用了多级目录结构，它们是当前文件系统的典型而完美的构，它们是

37、当前文件系统的典型而完美的代表。代表。823. 多级目录结构多级目录结构也称树型目录树型目录产生于UNIX操作系统，巳被现代操作系统广泛采用。目录与文件在一起，目录也做成文件优点：优点：层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制 缺点：缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度833. 多级目录结构图6.15多级目录结构 根目录：根目录：根结点各级目录文件：各级目录文件： 用方框表示。数据文件：数据文件：叶结点，用圆圈表示。843. 多级目录结构路径名路径名:从树的根(即主目录)开始，把全部目录文件名与数

38、据文件名，依次地用“/” 连接起来，即构成数据文件的路径名路径名（绝对路径（绝对路径 ）。例如，在图6.15中文件15的路径名为BFJ 853. 多级目录结构当前目录：当前目录：为了提高文件检索速度，文件系统向用户提供了一个当前正在使用的目录，称为当前目录（也称工作目录工作目录或值班目录值班目录）。查找一个文件可从当前目录开始，使用部分路径名(相对路径相对路径)例如，在图6.15中，假定当前目录是目录文件12，那么文件15的相对路径名为J，文件8的相对路径名为././C/G。 863. 多级目录结构增加和删除目录增加和删除目录 ：两种方法处理n(1) 不删除非空目录。不删除非空目录。如果目录中

39、还包含有子目录，还必须采取递归调用方式来将其删除，在MS-DOS中就是采用这种删除方式。n(2) 可删除非空目录。可删除非空目录。876.5.4 6.5.4 目录查询技术目录查询技术1线性检索法线性检索法查找/usr/ast/mbox的步骤 886.5.4 6.5.4 目录查询技术目录查询技术2. Hash方法方法 :一种查找的有效规则是：n(1) 查找目录时，如果相应的目录项是空的，则表示系统中并无指定文件。n (2) 如果目录项中的文件名与指定文件名相匹配， 则表示该目录项正是所要寻找的文件所对应的目录项。n(3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突

40、”，此时须利用解决散列冲突的方法再次查找。896.6 6.6 文件存储空间管理文件存储空间管理为新创建的文件分配外存空间，可采取连续分配方式或离散分配方式。 为实现存储空间的分配，系统应为分配存储空间而设置相应的数据结构；还应提供对存储空间进行分配和回收的手段。 906.6 6.6 文件存储空间管理文件存储空间管理 6.6.1 空闲表和空闲链表6.6.2 位示图 6.6.3 UNIX 成组链接 916.6.1 6.6.1 空闲表和空闲链表空闲表和空闲链表1空闲表法空闲表法系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘

41、块数等信息。 921 1空闲表法空闲表法序序号号第一空白块号第一空白块号 空白块空白块个数个数空闲物理块号空闲物理块号1 12 24 4（2 2，3 3，4 4，5 5）2 29 93 3（9 9，1010，1111）3 315155 5（1515，1616，1717，1818，19)19)4 4仅当有少量的空白区时才有较好的效果如果存取空间中有着大量的小的空白区，则空闲表变得很大，效率大为降低。这种分配技术适用于建立连续文件。 931 1空闲表法空闲表法存储空间的分配与回收：存储空间的分配与回收：n为新文件分配空闲盘块时，系统先检索空闲表的各表项，找到一个大小能满足要求的空闲区。n系统在对用

42、户所释放的存储空间进行回收时，也要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。 946.6.1 6.6.1 空闲表和空闲链表空闲表和空闲链表2空闲链表法空闲链表法将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链空闲盘块链和空闲盘区链空闲盘区链。 952.2.空闲链表空闲链表(1)空闲盘块链：空闲盘块链：以盘块为单位拉成一条链以盘块为单位拉成一条链 ，创建文件需要一个或几个物理块时，就从链头依次取下一块或几块。回收时将盘块依次插入链的末尾 。(2)空闲盘区链：空闲盘区链：以盘区以盘区(1个盘区可包含若干盘块个盘区可包含若干盘

43、块)拉成一条链。拉成一条链。每个盘区上除有指示下一个盘区的指针外，还应指明本盘区大小。分配盘区通常采用首次适应算法。回收盘区时，也要将回收区与相邻接的空闲盘区相合并。 966.6.2 6.6.2 位示图位示图系统建立一张位示图，以反映整个存储空间的分配情况用二进制位反映磁盘空间的分配, 每个物理块对应一位, 1 1表示对应的物理块已分配，0 0表示其对应的块未分配申请物理块时，可以在位示图中查找为0的位，返回对应物理块号回收时，将对应位置0976.6.2 6.6.2 位示图位示图图6.17 位示图 986.6.3 UNIX 6.6.3 UNIX 成组链接成组链接空闲表法和空闲链表法空闲表法和空

44、闲链表法，不适用于大型文件系统，因为这会使空闲表或空闲链表太长。UNIX系统采用的成组链接法，成组链接法，将上述两种方法相结合，兼备了优点而克服了两种方法的缺点。 996.6.3 UNIX 6.6.3 UNIX 成组链接成组链接100400399301300100300299-202201299-100400399-2013019907999790179007899-78017999-7901空闲盘块号栈S.free019899图6.18 空闲盘块的成组链接法 1.空闲盘块的组织空闲盘块的组织1006.6.3 UNIX 6.6.3 UNIX 成组链接成组链接2.空闲盘块的分配：空闲盘块的分配：

45、先从栈顶取出一空闲盘块号，将对应的盘块分配，然后栈顶指针下移一格。若该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号。该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。 然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。 1016.6.3 UNIX 6.6.3 UNIX 成组链接成组链接3.空闲盘块的回收：空闲盘块的回收：系统将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满

46、，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。 1026.7 6.7 文件共享和保护文件共享和保护文件共享：文件共享：指不同的用户可以使用同一个文件，可以节省大量的辅存空间和主存空间，减少输入输出操作，为用户间的合作提供便利条件。文件共享要解决两个问题解决两个问题，一是如何实现文件共享；二是对各类需共享文件的用户如何进行存取控制，以保护文件的使用安全。1036.7 6.7 文件共享和保护文件共享和保护 6.7.1 文件共享的模式 6.7.2 文件的保护 1046.7.1 6.7.1 文件共享的模式文件共享的模式1.早期的文件共享方法早期的文件共享方法：早期实现文件

47、共享的方法有三种，即绕道法、链接法和基本文件目录表。 n绕道法：绕道法：由系统目录实现对文件的共享，用户通过全路径名共享地访问这些文件1051.1.早期的文件共享方法早期的文件共享方法n链接法：链接法：在相应目录表之间进行链接。在相应目录表之间进行链接。采用链访技术对要共享的文件进行连接:在用户自己的目录项中将链接指针直接指向被共享文件所在的目录，如前所示图6.15多级目录结构中的虚线a和b。 1061.1.早期的文件共享方法早期的文件共享方法n基本文件目录表：基本文件目录表：把文件目录的内容分成2部分：一部分称基本文件目录表基本文件目录表(BFD)，包括文件的结构信息、物理块号、存取控制和管理信息等，并由系统赋予惟一的内部标识符来标识另一部分称为符号文件目录表符号文件目录表(SFD)，由用户给出的符号名和系统的内部标识符组成。1071.1.早期的文件共享方法早期的文件共享方法图6.19 基本文件目录表实现共享1086.7.1 6.7.1 文件共享的模式文件共享的模式2.基于索引节点的共享方式基于索引节点的共享方式：