计算机操作系统(第八章)

1、计算机操作系统第八章 文件系统第2页文件系统 文件系统必须完成的工作（1）外存的分配与回收（2）按名存取（最基本目标）（3）文件的共享和保护2022年5月2日星期一Operating System 操作系统 第八章 文件系统第3页 信息是计算机系统中的重要资源。操作系统中的一个重要组成部分，文件系统，就负责信息的组织、存储和访问。 文件系统的功能就是提供高效、快速和方便的信息存储和访问功能。本章的主要内容就是信息的组织。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第4页8.1 文件系统的基本概念8.2 文件的逻辑结构与存取方法8.3 文件的物理结构与存储

2、设备8.4 文件存储空间管理8.5 文件目录结构8.6 文件的共享与保护8.7 文件操作8.8 文件系统的层次模型2022年5月2日星期一Operating System 操作系统 第八章 文件系统第5页8.1 文件系统的概念1.1.引言引言2022年5月2日星期一Operating System 操作系统 第八章 文件系统第6页图图7.1 操作系统的软硬件管理操作系统的软硬件管理(1)使用现有的软件资源来协助完成自己的任务(2)编制完成的或未完成的程序存放在什么地方,需要访问的数据存放在什么地方，从而使得人们可以再利用已有的软件资源。2022年5月2日星期一Operating System

3、操作系统 第八章 文件系统第7页2. 文件和文件系统文件的定义 文件文件是具有标识符（文件名）的一组相关信息的集合。标识符是用来标识文件的。不同的系统对标识符的规定有所不同。文件的确切定义有两种说法： （1）字符流的集合。 （2）文件相关记录的集合。 文件是数据在外存储器上的存储单位。第8页 不同的系统对标识符的规定有所不同。文件的确切定义有两种说法： （1）文件是具有文件名的具有相关属性的字符的有序集合。（文件是具有符号名的信息文件是具有符号名的信息(数据数据)项的集合）项的集合） （2）文件是具有文件名的具有相关属性的记录的有序集合。（文件是具有符号名的记录的集合）文件是具有符号名的记录的

4、集合） 构成文件的基本单位构成文件的基本单位 信息项信息项、域、域、记录记录2022年5月2日星期一Operating System 操作系统 第八章 文件系统第9页文件系统的定义文件系统的定义 文件系统：操作系统中与管理文件有关的软件和数文件系统：操作系统中与管理文件有关的软件和数据的集合据的集合 它负责为用户建立文件，撤消、读写、修改和复制文件，还负责完成对文件的按名存取和进行存取控制。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第10页文件系统的特点 友好的用户接口，用户只对文件进行操作，而不管文件结构和存放的物理位置。 对文件按名存取，对用户透

5、明。 能够实现文件的用户级和进程级（某些文件可以被多个用户或进程所共享。） 文件系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质，因此，可存储大量信息2022年5月2日星期一Operating System 操作系统 第八章 文件系统 3 文件分类 (1) (1) 按文件的性质和用途分类按文件的性质和用途分类系统文件系统文件程序库文件（库文件）程序库文件（库文件）用户文件用户文件 （2）组织形式分类）组织形式分类普通文件普通文件 目录文件目录文件 特殊文件（如输入输出设备）特殊文件（如输入输出设备）UNIX系统文件分类方法：系统文件分类方法：1、普通文件、普通文件普通文件是无结构的字符的

6、集合。普通文件是无结构的字符的集合。2、目录文件、目录文件目录文件是由文件的目录项组成的文件。目录文件是由文件的目录项组成的文件。3、特别文件、特别文件特别文件就是设备。特别文件就是设备。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第12页第13页4. 文件名文件名 根据文件的定义，每个文件必须有一个唯一的文件名，根据文件的定义，每个文件必须有一个唯一的文件名，不论是系统管理，还是用户使用文件都使用文件名。不论是系统管理，还是用户使用文件都使用文件名。 文件名是一个有限长度的字符串。文件名是一个有限长度的字符串。 (1) DOS(1) DOS、WINDO

7、WSWINDOWS系统中文件名系统中文件名 文件名文件名 .文件扩展名文件扩展名 文件名是一个不大于文件名是一个不大于8 8个字符的字符串，但个字符的字符串，但WINDOWSWINDOWS系统中允许超长文件名，最多可有系统中允许超长文件名，最多可有256256个字符，不区分英个字符，不区分英文字母的大小写。文字母的大小写。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第14页文件扩展名：文件扩展名：不大于不大于3个字符，一般用来表示文件的类型。个字符，一般用来表示文件的类型。例如：例如：C C语言源程序文件语言源程序文件COM 可执行文件（小模式）可执行文

8、件（小模式）EXE 可执行文件（大模式）可执行文件（大模式）BAT 批处理文件批处理文件OBJ 目标文件目标文件hust.txt ll.c ll.obj ll.exe 操作系统教学片操作系统教学片91.ppt2022年5月2日星期一Operating System 操作系统 第八章 文件系统第15页 (2) UNIX (2) UNIX系统中的文件名系统中的文件名 文件名是一个不大于文件名是一个不大于14个字符的字符串。并且区分英个字符的字符串。并且区分英文字母的大小写。文字母的大小写。 例如：例如：unix linux ll.c a .out aa AA 注意：在注意：在UNIX系统中文件名就

9、是一个字符串，系统中文件名就是一个字符串，没有文没有文件名和文件扩展名之分件名和文件扩展名之分，文件的类型由用户命名时确定。，文件的类型由用户命名时确定。 例如，例如，li.c，UNIX系统认为这个文件名的长度是系统认为这个文件名的长度是4个字符。个字符。 而在而在DOS、WINDOWS系统中则解释这个文件名，系统中则解释这个文件名，li是文是文件名，件名，c是文件扩展名，表示该文件是一个是文件扩展名，表示该文件是一个C语言的源程语言的源程序文件，而序文件，而.是文件名和文件扩展名的分隔符。是文件名和文件扩展名的分隔符。2022年5月2日星期一Operating System 操作系统 第八章

10、 文件系统第16页5.文件的属性文件的属性文件属性反映文件的类型、存取控制、等文件属性反映文件的类型、存取控制、等UNIX系统中文件属性：系统中文件属性： 普通文件普通文件 d 目录文件目录文件 p 管道文件管道文件 c 字符型设备文件字符型设备文件b 块设备文件块设备文件 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第17页文件管理的目的 方便的文件访问和控制：以符号名称作为文件标识，便于用户使用； 并发文件访问和控制：在多道程系统中支持对文件的并发访问和控制； 统一的用户接口：在不同设备上提供同样的接口，方便用户操作和编程； 多种文件访问权限：在多用

11、户系统中的不同用户对同一文件会有不同的访问权限； 优化性能：存储效率、检索性能、读写性能； 差错恢复：能够验证文件的正确性，并具有一定的差错恢复能力；2022年5月2日星期一Operating System 操作系统 第八章 文件系统第18页 文件系统的功能文件系统的功能 （1）用户可执行创建、修改、删除读写文件的命令。 （2）用户能以合适的方式构造他的文件。 （3）用户能在系统的控制下，共享其他用户的文件。 （4）允许用户用符号名访问文件。 （5）系统应有转存和恢复文件的能力，以防止意外事故的发生。 （6）系统应提供可靠保护及保密措施。2022年5月2日星期一Operating System

12、 操作系统 第八章 文件系统第19页文件系统必须完成的工作：(1) 为了合理的存放文件，必需对磁盘等辅助存储器空间 (或称文件空间) 进行统一管理。在用户创建新文件时为其分配空闲区，而在用户删除或修改某个文件时,回收和调整存储区。(2) 为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进行信息的存取和加工。这种逻辑结构是独立于物理存储设备的。(3) 为了便于存放和加工信息，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。(4) 完成对存放在存储设备上的文件信息的查找。(5) 完成文件的共享和提供保护功能。2022年5月2日星期一Oper

13、ating System 操作系统 第八章 文件系统第20页文件系统的结构和功能元素返回1. 文件系统的结构应用程序多种文件类型（划分记录，顺序或索引等）基本 I/O 管理（I/O 缓存和调度，性能优化）物理 I/O（基本文件系统）外部存储器文件系统2022年5月2日星期一Operating System 操作系统 第八章 文件系统第21页2. 文件管理的服务功能元素 文件访问：文件的创建、打开和关闭，文件的读写； 目录管理：用于文件访问和控制的信息，不包括文件内容 文件结构管理：划分记录，顺序，索引 访问控制：并发访问和用户权限 限额(quota)：限制每个用户能够建立的文件数目、占用外存空

14、间大小等 审计(auditing)：记录对指定文件的使用信息（如访问时间和用户等），保存在日志中(文件系统向上层用户提供的服务)2022年5月2日星期一Operating System 操作系统 第八章 文件系统第22页3. 文件系统的实现功能元素文件系统的实现功能元素 文件的分块存储：与外存的存储块相配合 I/O缓冲和调度：性能优化 文件定位：在外存上查找文件的各个存储块 外存存储空间管理：如分配和释放。主要针对可改写的外存如磁盘。 外存设备访问和控制：包括由设备驱动程序支持的各种基本文件系统如硬盘，软盘，CD ROM等(文件系统要实现的功能模块)2022年5月2日星期一Operating

15、System 操作系统 第八章 文件系统第23页文件系统优点 用户使用方便 文件安全可靠 实现文件共享 把数据组织成文件形式加以管理和控制是计算机数据管理的重大发展2022年5月2日星期一Operating System 操作系统 第八章 文件系统第24页8.2 8.2 文件的逻辑组织与存取方法文件的逻辑组织与存取方法 文件的逻辑结构：是指从用户文件的逻辑结构：是指从用户 组织和使用文件时可组织和使用文件时可见的结构。见的结构。 选取文件时应该遵循的原则选取文件时应该遵循的原则 ：（1）能减少修改文件时处理工作量）能减少修改文件时处理工作量（2）能有较快的查找速度）能有较快的查找速度 （3）能

16、尽量节约存储空间）能尽量节约存储空间 （4）便于进行用户操作）便于进行用户操作2022年5月2日星期一Operating System 操作系统 第八章 文件系统第25页一一. . 文件的组织文件的组织可以用两种不同的观点去进行研究文件结构 用户观点: 是研究用户“思维”中的抽象文件，或称逻辑文件，其研究的侧重点在于为用户提供一种逻辑结构清晰、使用简便的逻辑文件形式。用户将按照这种形式去存储、检索和加工有关文件中的信息。 实现观点:是研究驻留在设备“介质”中的实际文件，或称物理文件。它研究的侧重点是选择一些工作性能良好、设备利用率高的物理文件形式。系统将按照这种形式同外部设备打交道并控制信息的

17、传输。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第26页 1.文件的两种结构文件的两种结构 文件的逻辑结构： 从用户角度看到的文件面貌。即用户对信息进行逻辑组织形成的文件结构。 文件的物理结构： 文件的物理结构是指文件在存储介质上的结构（或称组织）。在当代，文件的存储介质是磁盘，包括软盘、硬盘和光盘、磁带，早期还有磁鼓。由于目前的磁带是模拟磁盘的结构，所以文件的物理结构主要是指磁盘上文件的结构。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第27页 2. 逻辑记录与物理记录逻辑记录与物理记录 (1) 逻辑记录 逻辑

18、记录是文件中按信息在逻辑上的独立含义来划分的信息单位。 逻辑记录是对文件进行存取操作的基本单位。 (2) 物理记录(块) 主存和辅存设备信息交换的物理单位，是存储介质上连续信息所组成的一个区域。 (3) 逻辑记录与物理记录的区别与关系 一个是逻辑的概念，一个是物理的概念 逻辑记录最终在存放到物理记录上2022年5月2日星期一Operating System 操作系统 第八章 文件系统第28页8.2.1 文件的逻辑结构 文件逻辑组织的定义文件逻辑组织的定义 从用户的观点出发，为用户提供一种逻辑结构清晰、使用方便的逻辑文件形式。 文件组织的形式文件组织的形式 可分为两种形式：有结构记录式文件和无结

19、构（流式）文件。 记录文件两种形式记录文件两种形式 在逻辑上被看成一组连续的相关记录的集合。记录式文件按其各记录的长度是否相同又可分为等长记录文件和变长记录文件两种。 无结构文件无结构文件 无结构文件则指文件内部不再划分记录，它的基本信息单位是字节或字，其长度是所含字节的数量。相对记录式文件来说，无结构文件无需额外说明，节省存储空间，许多操作系统如UNIX系统中文件的逻辑结构就是采用这种方式。如大量的源程序，库函数等采用的就是流式结构2022年5月2日星期一Operating System 操作系统 第八章 文件系统第29页 (1) 流式文件流式文件(无结构文件无结构文件) 无结构的流式文件是

20、相关的有序字符的集合。文件的长度为所含字符数。 UNIX、DOS、WINDOWS系统中的普通文件都是流式文件。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第30页 (2) 记录式文件记录式文件(结构文件结构文件) 记录式文件是一种结构式文件，文件是记录的集合. 每个记录由彼此相关的域构成。记录可按顺序编号为记录1，记录2，记录n。如果文件中所有记录的长度都相同，则这种文件为定长记录文件。 定长记录文件的长度 = 记录个数x记录长度。 变长记录文件的长度为各记录长度之和。 例如:学生登记表文件 xsdjb.dbf 姓名 学号 籍贯 通信地址 邮政编码 李铭

21、 925678 武昌 武昌关山街125号 430074 司马乐 925679 北京 北京海军路88号 1000342022年5月2日星期一Operating System 操作系统 第八章 文件系统第31页 (3) 两种文件的比较 流式文件就象给一张白纸给用户，用户可将他的信息任意地写到纸上，没有任何格式上的限制。 记录式文件就象给一张表格给用户，用户要按表规定的格式填信息。 显然，结构式文件对用户的限制很大，使用起来就不方便，所以记录式文件被淘汰是理所当然的。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第32页常用的逻辑记录式的结构文件 1.连续结构：

22、按记录生成先后顺序排列（按时间没有按内容，便于追加和更新，不利于随机检索） 2.多重结构：按键值组织多个队列，每个队列中的记录都包含该键值。 有利于按键值检索（sno,sname,ssex,sage) 3.转置结构：把所有与同一键值对应的记录指针连续的置于目录中该键的位置下。 最适合于按键值检索记录 4.顺序结构：所有记录按给定的键所规定的顺序排列的方式 增加和删除记录比较麻烦2022年5月2日星期一Operating System 操作系统 第八章 文件系统第33页8.2.2 文件的存取方法文件的存取方法 文件的存取方法是指用户的逻辑存取方法包括：顺序存取 随机（直接）存取方法 按键存取方法

23、 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第34页顺序存取顺序存取 顺序存取顺序存取：按照文件逻辑地址顺序存取。后一次存取总是在前次存取的基础上进行的。每次存取不必给出存取开始的位置。包括：定长记录读取，变长记录读取，无结构文件读取 定长记录读取操作步骤定长记录读取操作步骤 对于定长记录，读写操作是根据当前记录开始位置作为读写指针rptr值开始读写，修改指针指向下一个相邻的记录。 rptr=rptr+l， 其中，l是记录的长度。 变长记录读取操作步骤变长记录读取操作步骤 对于变长记录文件，则对rptr作修改，指向下一个相邻记录的开始位置：rptr=r

24、ptr+li，其中，li是记录长度。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第35页无结构文件读取操作步骤无结构文件读取操作步骤对于无结构文件，顺序存取是按照读、写文件的位置指针和读写字符的数量决定读写的信息。读写完成后，位置指针自动加上读写信息的长度，使指针指向下段信息。rptrrptrl，其中l是本次读写字节数。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第36页随机（直接）存取方法随机（直接）存取方法随机存取法：随机存取法：允许用户根据记录编号来存取文件的任一记录，而不管上次存取了哪一个记录。 包括：

25、定长记录随机读取定长记录随机读取和变长记录随机读取和变长记录随机读取 定长记录随机读取操作步骤定长记录随机读取操作步骤 欲读写第i个记录(i=0,1,2,)，其首址为： rptri=offset+i*l，其中offset是该文件的首址，l为记录长度。 变长记录随机读取操作步骤变长记录随机读取操作步骤 要读出记录Ri,可以采用索引表结构，欲存取的记录的地址直接在索引表项中得到。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第37页注意：注意： 每次存取操作都要指定存取操作的开始位置。 在系统中提供文件存取操作有： n = read(fd,buffer,siz

26、e); m = write(fd,buffer,size); 这两个操作总是从当前位置开始读（或写），执行顺序存取操作。 leek(fd,offset,mode) 调整文件的读写起始位置的系统调用，若在read、write之前执行leek操作，就调整了文件的读写指针（读写开始的位置），实现了随机存取。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第38页按键存取方法 按关键字存取法按关键字存取法：是根据文件中记录内容进行存取的。 操作步骤操作步骤 按关键字关键字(按键）按键）存取法首先根据用户给定键值搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理

27、地址后进行存取按键存取时的几种搜索算法（1）线性搜索法（逐个比较）（2）散列法（由散列函数直接产生键所对应的逻辑地址,hash）（3）二分法（使用于文件中的键和记录是有序的情况）2022年5月2日星期一Operating System 操作系统 第八章 文件系统第39页8.3文件的物理结构与存储设备文件的物理结构与存储设备 文件的物理结构：文件的物理结构：在文件系统中，文件的存储设备通常划分为若干个大小相等的物理块，每块的长为512或是1024字节，文件信息也同样划分为与存储设备的物理大小相等的逻辑块，因此，块作为文件空间和传送信息的基本单位。 文件的物理结构是指文件在外存上的存放结构文件的物

28、理结构是指文件在外存上的存放结构 常用的文件物理结构常用的文件物理结构 连续结构连续结构 链接（串联）结构链接（串联）结构 索引结构索引结构 多重索引结构多重索引结构 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第40页连续结构连续结构 连续结构连续结构: 若一个逻辑文件的信息存放在文件存储器上相邻物理块中，则称该文件为连续文件，这样的结构称为连续结构 图3连续结构文件 图3连续结构文件 2022年5月2日星期一Operating System 操作系统 第八章 文件系统文件文件A 3 100 r0 r1 r2 磁盘块号磁盘块号100101102文件目录

29、文件目录文件文件A目录项目录项问题：在连续文件结构下，问题：在连续文件结构下，当要存取当要存取 R i 记录时，应如记录时，应如何操作？何操作？2022年5月2日星期一Operating System 操作系统 第八章 文件系统第41页第42页连续文件的特点连续文件的特点优点：优点：结构简单，实现容易，不需要额外的开销。在顺序存取时速度较快。缺点：缺点： 用户创建文件时要给出文件的大小；用户应给出文件的最大长度，为其分配足够的外存空间 不利于文件的动态增加和修改；不允许对文件中间的部分进行插入和删除操作。 注： 连续文件是一种连续结构的文件，对每个文件要求存放在存储介质上的连续的物理块中，存储

30、空间利用率不高。类似于存储管理中的分区 适用于变化不大的顺序访问的文件，在流行的UNIX系统中仍保留了连续文件结构。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第43页链接（串联）结构 链接结构链接结构：一种非连续的存储方式，一个逻辑上连续的文件信息可分散地存放在外存的不连续的若干个物理块中。 实现方法实现方法 在各个物理块中设立一个链接指针，指向下一个物理块的位置。每个物理块的最末一个字(或第一个字)作为链接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为“”。 注： 这种文件结构不要求连续存放。这种文件结构不要求连续存放。

31、 对于记录式文件一块中可包含一个逻辑记录或多个逻对于记录式文件一块中可包含一个逻辑记录或多个逻 辑记录，也可以若干物理块包含一个逻辑记录。辑记录，也可以若干物理块包含一个逻辑记录。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第44页图4 链接结构文件 图4 链接结构文件 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第45页 2. 2. 串联文件的结构串联文件的结构 文件文件A 100 r1 57 r2 r0 150磁盘块号磁盘块号 100磁盘块号磁盘块号 150磁盘块号磁盘块号 57文件目录文件目录文件文件A目录项

32、目录项问题：在串联文件结构下，当要问题：在串联文件结构下，当要存取存取 R i 记录时，应如何操作？记录时，应如何操作？图8-4-3 链接结构文件 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第46页串联文件的特点串联文件的特点 存储空间利用率高； 文件创建时用户不必指出文件的大小； 文件动态扩充和修改容易； 顺序存取效率高，随机存取效率太低，如果访问文件的最后的内容，实际上是要访问整个文件。优点优点 克服了连续结构中要求分配给文件若干连续物理块的缺点，使用灵活，不必事先给出文件最大长度，只要有空闲的物理块，临时在需要时增加长度即可。缺点缺点只适于顺序存

33、取，为了找到后面的信息，必须从头开始，逐一查找每块的链接字，速度慢。每块增加了一个链接指针，为信息管理添加了复杂性。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第47页文件映照文件映照 为了克服链接文件的存取效率太低的问题，人们提出文件映照的技术，即把链接文件中的链接字集中在一结构中，这样既保持了链接文件的优点，也克服了其缺点，DOS、WINDOWS系统就采用了这样结构。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第48页图8-4-4 链接结构文件 2022年5月2日星期一Operating System 操作系统

34、 第八章 文件系统第49页索引结构 索引结构：系统为每个文件建立一张索引表，其中每个表目指出文件逻辑记录所在的物理块号。 图8-5 索引结构系统为每个文件系统为每个文件建立逻辑块号与建立逻辑块号与物理块号的对照物理块号的对照表。这张表称为表。这张表称为该文件的索引表。该文件的索引表。文件由数据文件文件由数据文件和索引表构成。和索引表构成。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第50页文件文件A索引表指针索引表指针文件文件A目录项目录项 r0 r1文件目录文件目录 逻辑块号逻辑块号 物理块号物理块号 0 23 1 19 2 26 3 29 r2 r3

35、磁盘块号磁盘块号 23磁盘块号磁盘块号 19磁盘块号磁盘块号 26磁盘块号磁盘块号 29文件索引表文件索引表2022年5月2日星期一Operating System 操作系统 第八章 文件系统第51页索引文件的特点索引文件的特点 便于直接存取；便于直接存取； 便于文件的增便于文件的增、删删、改；改； 需考虑如何有效地存储和查找索引表。需考虑如何有效地存储和查找索引表。 优点优点文件占有块可不连续，块数可变，便于随机存取文件中的任意记录。 缺点缺点 索引表增加了空间的开销。在存取文件时首先需要到外存取得索引表，才能查表，获得物理块号，这样至少增加了一次访问外存的操作，降低了文件访问速度。 202

36、2年5月2日星期一Operating System 操作系统 第八章 文件系统第52页多重索引结构多重索引结构 多重索引结构：多重索引结构：采用了间接索引方式，第一级索引表的表目指出下一级索引表的位置（物理块号），下一级索引表的表目指出再下一级索引表的位置，这样间接几级，最末一级索引表的表目则指向相应记录所在的物理块号。 多重索引文件多重索引文件 UNIX的索引结构的索引结构 UNIX系统中，文件物理结构采用了直接索引和多级间接索引的组织结构。系统为每个文件设置一个索引数组，该数组共13项，前10项为直接地址项，直接存放该文件所在物理块号。后3项的地址则被分别用来存放间接索引表的地址，即第11

37、项存放一次间接值，第12项存放二次间接值，第13项存放三次间接值。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第53页图 8-6-1 Unix文件物理结构示意图 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第54页图图8-6-2 文件的多重索引结构文件的多重索引结构2022年5月2日星期一Operating System 操作系统 第八章 文件系统第55页文件物理结构的比较文件物理结构的比较 连续文件的优点是不需要额外的空间开销，只要在文件目录中指出文件的大小和首块的块号即可，对顺序的访问效率很高。适应于顺序存取。

38、缺点是动态地增长和缩小系统开销很大；文件创建时要求用户提供文件的大小；存储空间浪费较大。 串联文件克服了连续文件的不足之处，但文件的随机访问系统开销较大。适应于顺序访问的文件。DOS系统中改造了串联文件的结构，使其克服了串联文件的不足，但增加了系统的危险性。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第56页 索引文件既适应于顺序存访问，也适应于随机访问，是一种比较 好的文件物理结构，但要有用于索引表的空间开销和文件索引的时间开销。UNIX系统是使用索引结构成功的例子。 在当前流行的一些UNIX操作系统的版本中，同时支持连续文件结构和索引文件结构。DOS

39、、WINDOWS系统支撑类似于文件映照结构。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第57页UNIX系统文件索引结构举例 1小型文件的索引结构 2大型文件的索引结构 3巨型文件的索引结构2022年5月2日星期一Operating System 操作系统 第八章 文件系统第58页文件存储设备 顺序存取设备（磁带） 直接存取设备（磁盘）2022年5月2日星期一Operating System 操作系统 第八章 文件系统2022年5月2日星期一Operating System 操作系统 第八章 文件系统第59页第60页文件的物理组织、存储介质和存取方法间的

40、关系文件的物理组织、存储介质和存取方法间的关系 文件的存取方法与文件的物理结构和用户使用方法密切相关，文件的物理结构又受存储介质和设备的影响,它们之间的关系如表8-1所示。 表8-1 文件结构、存储介质和存取方法间的关系 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第61页 8.4 存储空间的管理 8.4.1外存的主要技术参数 8.4.2 空闲块的管理 8.4.3 分配策略 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第62页 文件存储空间为系统和多个用户所共享，系统应能自动地统一管理和分配文件存储空间。 问题问题

41、系统应解决如下几个问题：(1) 记住文件存储空间的使用情况；(2) 需给一个文件分配存储空间；(3) 及时回收被删除文件所占的全部存储空间或文件所占的部分存储空间。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第63页存储空间的管理存储空间的管理 8.4.1空白文件目录 8.4.2空闲块链 8.4.3位示图 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第64页8.4.1空闲文件目录 把文件存储空间中一个连续的未分配区域称为空白文件，系统为所有这些空白文件单独建立一个目录，对应于每个空白文件，在这个目录中建立一个表目。

42、 空闲文件目录示意图空闲文件目录示意图 图8_10 空白文件目录示意图 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第65页 空闲文件目录2022年5月2日星期一Operating System 操作系统 第八章 文件系统第66页使用方法使用方法 (1)类似内存分配，在系统为某个文件分配空闲块时，可采用首次适应算法、循环首次适应算法等。 (2)当用户撤消一个文件时，也需要扫描空白文件目录，寻找一个空表目，并将回收的空间的物理块号及物理块数填入该表目中。 适用场合适用场合 （1）这种方法仅适于少量空白区时，若存储空间存在着大量的小的空白区，则目录变得很大，

43、系统效率降低。 （2）适用于建立连续文件。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第67页2空闲块链 图图6.12 空闲块链空闲块链 空闲块链法是将文件存储空间中的所有空闲块用指针链接在一起，该空闲块链的首指针由系统保存在主存。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第68页 使用方法使用方法 （1）当申请者需要空闲块时，系统从链头摘取空闲块，然后调整链首指针。 （2）当回收空闲块时，把释放的空闲块依次链入空闲块链首部。 优点优点 （1）空闲块号的登记不需要占用额外的空间，只是临时借用每组第一个空闲物理块

44、记录下组的空闲块号。 （2）分配和回收物理块工作一般均在内存专用栈区进行，仅在栈区空或满时，才需要启动I/O设备进行栈区的填充或清空，提高了系统效率。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第69页3位示图 图图6.13 位示图位示图位示图是利用二进制的一位来表示文件存储空间中的一个物理块的使用情况，当其值为0时，表示对应物理块为空闲；为1时表示已分配。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第70页使用方法使用方法 （1）当连续分配时，需在位示图中找到足够多的连续为0的二进制位，并把它们对应的块分配出去

45、； （2）以块为单位的分配，则只要扫描到一个为0的二进制位，即可把其相应的块分配出去。适用场合适用场合 位示图方式既可以用连续文件，也可以用于非连续文件2022年5月2日星期一Operating System 操作系统 第八章 文件系统第71页分配策略 空闲块的分配有静态分配和动态分配两种。 在静态分配中，用户在建立文件时宣布文件的大小，系统一次分配其所需要的全部区域。 在动态分配中，用户在建立一个文件时，系统并不分配存储空间，而是在每次写信息时才按所写信息的大小进行分配。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第72页外存的主要技术参数 外存的主

46、要技术参数有：外存的主要技术参数有：（1）容量。）容量。 （2）物理尺寸）物理尺寸 （3）访问方法）访问方法。 （4）传输速率。）传输速率。 （5）查询时间。）查询时间。 （6）延迟时间。）延迟时间。 （7）可拆卸性。）可拆卸性。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第73页8.5 8.5 文件目录结构文件目录结构 一一. .文件目录有关概念文件目录有关概念 1.1.什么是文件目录什么是文件目录 文件目录文件目录即文件名址录。它是一张记录所有文件名即文件名址录。它是一张记录所有文件名及其存放地址、文件的说明和控制信息的表格。是及其存放地址、文件的

47、说明和控制信息的表格。是所有所有文件说明的有序集合，它采用表格形式，每一个文件占文件说明的有序集合，它采用表格形式，每一个文件占一个表目，易称为文件的目录项。一个表目，易称为文件的目录项。 一般情况下，每个文件占用一个表目，即每个文件有一般情况下，每个文件占用一个表目，即每个文件有一个文件的目录项。一个文件的目录项。 文件目录管理文件目录管理就是对文件说明信息的管理，文件系统就是对文件说明信息的管理，文件系统中实现按名存取就是通过文件目录管理来实现的。中实现按名存取就是通过文件目录管理来实现的。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第74页8.5.

48、1文件的组成 从管理角度看，文件由文件说明和文件体组成 文件说明：也称文件控制块（FCB），它包括文件名、文件内部标识、文件物理地址、存取控制和管理信息等 文件体，指文件本身 文件说明组成目录文件，文件系统利用目录文件完成按名存取和对文件的共享和保护。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第75页 1. 文件路径名文件路径名 含义含义 路径名由根目录和所经过的目录文件名、文件名以及分隔符组成。2. 工作目录工作目录 含义含义 把经常使用的文件所在的目录指定为工作目录，若无特殊说明，系统总是从工作目录开始查询，即用户对文件的所有访问都是相对于工作目录

49、。 绝对路径名和相对路径名绝对路径名和相对路径名 从根目录开始的是完整的路径名，称绝对路径名，否则默认为从工作目录开始，称为相对路径名。2022年5月2日星期一Operating System 操作系统 第八章 文件系统2022年5月2日星期一Operating System 操作系统第76页2.2.文件目录的内容文件目录的内容( (1) 1) 文件名：文件名：用户文件名由用户赋予文件标识，系统文件和特殊文件在系统设计时指定。 (2) (2) 文件的逻辑结构文件的逻辑结构说明说明：对于记录式文件，须说明文件的记录是否为变长，记录的长度和数量等信息，对于无结构的流式文件仅说明文件的长度。该文件的

50、记录是否定长、记录长度及记录个数等。 (3) (3) 文件在物理存储介质中的位置。文件在物理存储介质中的位置。对于连续结构和串接结构，只要登记文件的起始块号和指向文件第一个物理块的指针。对于索引结构，要登记该文件索引表的首址。（取取决于文件的物理结构）决于文件的物理结构） 对于连续文件：文件起始块号（即文件的第一个物理块块号）；对于连续文件：文件起始块号（即文件的第一个物理块块号）； 对于串联文件：指向第一个物理块的指针；对于串联文件：指向第一个物理块的指针； 对于索引文件：索引表。对于索引文件：索引表。(4) (4) 存取控制信息：存取控制信息：如文件的存取权限，只有合法的用户才能进行合法的

51、文件操作 文件主和其它用户对该文件的访问权限。文件主和其它用户对该文件的访问权限。(5) (5) 管理信息：管理信息：登记文件的建立时间、日期和上次修改日期等 包含文件创建的日期和时间，最近修改该文件的日期和时间等。(6) (6) 文件的类型：文件的类型：指明文件的属性。如系统文件、用户文件、目录文件等。 (7) 使用计数使用计数 ：表示当前多少进程在使用（打开）该文件。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第77页第78页文件目录的作用文件目录的作用 系统利用目录结构提供的信息对文件实施创建、搜索、删除等各种操作。按名存取文件时，先要找到对应的

52、目录项，验证权限，仅当存取合法时，才能取得存放文件信息的物理地址。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第79页8.5.2 文件目录文件目录如何组织文件目录是文件系统的重要内容之一，下面介绍几种基本的组织方式。1. 单级目录结构单级目录结构 若一个物理卷上的所有文件的目录项都登记在一个目录中，称该目录结构为单级目录结构。最简单的文件目录结构，在系统中是一张线性表，每个文件占一表目，由文件名和文件的说明和管理信息组成。特点特点 单级文件目录的主要功能是实现单级文件目录的主要功能是实现“按名存取按名存取”, , 并且实现容易。并且实现容易。 主要问题是

53、主要问题是 重名重名 问题问题 所谓所谓“重名重名”是指不同用户对不同文件起了相同的名字，即两个或多个是指不同用户对不同文件起了相同的名字，即两个或多个文件只有一个相同的符号名文件只有一个相同的符号名。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第80页优点优点 单级目录在实现上比较容易。 缺点缺点 （1）大容量外部存储器上可存放成千上万个文件，在目录中查询一个文件目录项就会花费较长时间，从而影响系统的效率。 （2）文件名与文件必须一一对应，时常会出现文件重名现象。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第8

54、1页文件名文件名物理地址物理地址其他信息其他信息sqrttestcompilerassemblergabczhang一级文件目录一级文件目录2022年5月2日星期一Operating System 操作系统 第八章 文件系统第82页2. 2. 二级目录结构二级目录结构(1) (1) 什么是二级文件目录什么是二级文件目录 二级目录结构把目录分成主目录（二级目录结构把目录分成主目录（MFD）和用户文件）和用户文件目录（目录（UFD）两级。主目录由用户名和用户文件目录首地）两级。主目录由用户名和用户文件目录首地址组成。每个用户单独建立一个目录，各用户目录登记址组成。每个用户单独建立一个目录，各用户目

55、录登记其下属文件的目录项其下属文件的目录项（它登记该用户建立的所有文件名及其在辅存中的位置和有关说明信息）主目录则登记进主目录则登记进入系统的各个用户文件目录的情况，这样就形成了二级入系统的各个用户文件目录的情况，这样就形成了二级目录的结构。目录的结构。2022年5月2日星期一Operating System 操作系统 第八章 文件系统 （2 2） 二级文件目录结构二级文件目录结构 testabcbe tabe ta文件名文件名 其他信息其他信息地址地址test abcbetaGao的用户文件目录的用户文件目录文件名文件名 其他信息其他信息地址地址sqrt betaWang的用户文件目录的用户

56、文件目录文件名文件名 其他信息其他信息地址地址WangGao主目录主目录sqrt2022年5月2日星期一Operating System 操作系统 第八章 文件系统第83页（3 3） 二级文件目录的特点二级文件目录的特点 解决了命名冲突，即允许在不同用户目录下，文件解决了命名冲突，即允许在不同用户目录下，文件名可以相同。名可以相同。 方法：存取一个文件时要给出文件路径名。方法：存取一个文件时要给出文件路径名。 在二级文件目录下，一个文件的路径名是由用户名在二级文件目录下，一个文件的路径名是由用户名和文件名拼起来得到的。和文件名拼起来得到的。 如如 用户用户wang的文件的文件beta 其路径名

57、为其路径名为“wang：beta” 用户用户gao的文件的文件beta 其路径名为其路径名为“gao：beta”。 2022年5月2日星期一Operating System 操作系统 第八章 文件系统第84页第85页查找文件目录项步骤查找文件目录项步骤 （1）当用户要对一个文件进行存取操作或创建、删除一个文件时，首先从主目录查找用户名，再依用户名查找到该用户的用户文件目录。 （2）在该用户文件目录中对特定文件进行搜索。 优点优点 （1）较好地解决了文件命名冲突的问题。 （2）获得了较高的搜索速度。 缺点缺点 （1）缺乏灵活性。 （2）不能反映每个用户的多任务，多领域层次关系。2022年5月2日

58、星期一Operating System 操作系统 第八章 文件系统第86页3. 3. 多级目录结构多级目录结构 （1 1） 什么是树型文件目录什么是树型文件目录 在多级目录系统中(除最末一级外)，任何一级目录的目录项可以描述一个目录文件，也可以描述一个非目录文件(数据文件)，而数据文件一定在树叶上。这样，就构成了一个树形层次结构。2022年5月2日星期一Operating System 操作系统 第八章 文件系统 （2 2）树型文件目录结构树型文件目录结构( (图图9.11)9.11) abcfedabcahjhjmrgaacid=13id=21id=14id=15id=16id=17id=1

59、8id=19id=20id=1id=2id=3id=4id=11id=12id=5id=8id=9id=10id=6id=7根目录根目录子目录子目录a子目录子目录b子目录子目录c子目录子目录a子目录子目录f子目录子目录e子目录子目录d2022年5月2日星期一Operating System 操作系统 第八章 文件系统第87页 （3 3）文件路径名文件路径名 多级目录中，一个文件的路径名是由根目录到该文件的通路上所有目录文件符号名和该文件的符号名组成的字符串，相互之间用分隔符分隔。 图9.11中id为15的文件 其文件路径名为从根目录开始 “b：f：J”。 文件路径名的作用？ 当用户进程使用路径

60、名来存取文件时，文件系统将根据这个路径名的顺序来查访各级目录，从而确定所要文件的位置。2022年5月2日星期一Operating System 操作系统 第八章 文件系统第88页 （4 4） 解决命名冲突解决命名冲突 在树型文件目录结构中，能更方便地解决问题。在树型文件目录结构中，能更方便地解决问题。 例：图例：图9.119.11中中idid为为1313的文件与的文件与idid为为2020的文件有相同的文的文件有相同的文件名，都为件名，都为a a。 id为为13的文件的文件路径名的文件的文件路径名 ？ id为为20的文件的文件路径名的文件的文件路径名 ？2022年5月2日星期一Operatin