第六章郑州轻工业学院 计算机操作系统——文件管理

1、第六章第六章 文件管理文件管理 2 6.1.1 文件及其分类文件及其分类 1.文件的定义文件的定义 文件是计算机系统中信息存放的一种组织形式，文件是计算机系统中信息存放的一种组织形式， 目前尚无严格的定义，下面给出两种有代表性目前尚无严格的定义，下面给出两种有代表性 的解释：的解释： n（1）文件是具有标识符的相关字符流的集合。）文件是具有标识符的相关字符流的集合。 n（2）文件是具有标识符的相关记录（一个有）文件是具有标识符的相关记录（一个有 意义的信息单位）的集合。意义的信息单位）的集合。 3 6.1.1 文件及其分类文件及其分类 这两种解释定义了两种文件形式：前者说明文这两种解释定义了两

2、种文件形式：前者说明文 件是件是由字节组成由字节组成，这是一种无结构的文件，或，这是一种无结构的文件，或 称称流式文件流式文件。 无结构文件由于采用字符流方式，与源程序、无结构文件由于采用字符流方式，与源程序、 目标代码等在形式上是一致的，因此，该方式目标代码等在形式上是一致的，因此，该方式 适用于源程序、目标代码等文件。适用于源程序、目标代码等文件。 目前目前UNIX操作系统，操作系统，MS-DOS系统均采用这系统均采用这 种文件形式。种文件形式。 4 6.1.1 文件及其分类文件及其分类 后者说明文件是后者说明文件是由记录组成由记录组成。而记录则是由一。而记录则是由一 组相关信息项组成。组

3、相关信息项组成。 例如每个学生的登记表可视为一个记录，它包例如每个学生的登记表可视为一个记录，它包 括学生姓名，出生年月，性别，籍贯等信息项。括学生姓名，出生年月，性别，籍贯等信息项。 所有学生登记表组成一个学生文件。所有学生登记表组成一个学生文件。 记录式文件主要用于信息管理。记录式文件主要用于信息管理。 在现代计算机操作系统中，为方便用户，在现代计算机操作系统中，为方便用户，把设把设 备也作为文件来统一管理备也作为文件来统一管理，从某种意义上说已，从某种意义上说已 拓宽了文件的含义。拓宽了文件的含义。 5 6.1.2 文件的分类文件的分类 （1）以文件的）以文件的用途分类用途分类 系统文件

4、：系统文件：由操作系统及其他系统程序和数据组成的由操作系统及其他系统程序和数据组成的 文件。这种文件不对用户开放，仅供系统使用，用户文件。这种文件不对用户开放，仅供系统使用，用户 只能通过操作系统只能通过操作系统提供的系统调用提供的系统调用来使用它们。来使用它们。 库文件：库文件：是指系统为用户提供的各种标准函数，标准是指系统为用户提供的各种标准函数，标准 过程和实用程序等。用户只能使用这些文件，而无权过程和实用程序等。用户只能使用这些文件，而无权 对其进行修改。对其进行修改。 用户文件：用户文件：由用户的信息组成的文件，如源程序文件，由用户的信息组成的文件，如源程序文件， 数据文件等。这种文

5、件的使用和修改权均属于用户。数据文件等。这种文件的使用和修改权均属于用户。 6 6.1.2文件的分类文件的分类 （2）按文件的操作保护分类）按文件的操作保护分类 n只读文件：只读文件： 只允许进行读操作，不能进行只允许进行读操作，不能进行 写操作的文件。写操作的文件。 n读写文件：读写文件： 允许文件主和授权用户对其进允许文件主和授权用户对其进 行读或写操作的文件。行读或写操作的文件。 n只执行文件：只执行文件：该类文件只允许授权的用户调该类文件只允许授权的用户调 用执行，而不允许其修改或读出文件的内容。用执行，而不允许其修改或读出文件的内容。 7 6.1.2文件的分类文件的分类 （3）按文件

6、的性质分类）按文件的性质分类 n普通文件：普通文件： 指一般的用户文件和系统文件。指一般的用户文件和系统文件。 n目录文件：目录文件： 管理和实现文件系统的文件目管理和实现文件系统的文件目 录项组成的系统文件，对目录文件可以进行录项组成的系统文件，对目录文件可以进行 与普通文件一样的各种文件操作。与普通文件一样的各种文件操作。 n特别文件：特别文件： 有的系统把设备作为文件统一有的系统把设备作为文件统一 管理和使用，并为区别起见，管理和使用，并为区别起见，把设备称为特把设备称为特 别文件别文件。例如：。例如：unix/linux 8 6.1.3 文件系统及其功能 文件系统是操作系统中负责存取和

7、管理信息的 模块，它用统一的方式管理用户和对系统信息 的存储、检索、更新、共享和保护，并为用户 提供一整套方便有效的文件使用和操作方法。 它由管理文件所需的数据结构（如文件控制块 及存储分配表等）和相应的管理软件以及访问 文件的一组操作组成。 9 文件系统的功能 1.使用户可执行创建、修改及删除读写文件 的命令。 2.使用户在系统控制下共享其他用户的文件， 以便用户可共享其它人的工作成果。 3.使用户能以合适的方式构造其他文件 4.使用户能使用在文件间进行数据传输的命令 10 文件系统的功能 5.为了实现按名存取，需要有一个用户可见 的文件逻辑结构，用户按照文件逻辑结构所 给定的方式进行信息的

8、存取和加工。这种逻 辑结构是独立于物理存储设备的。 6.为了防止意外事故，文件系统具有转储和 恢复文件的能力 7.能提供可靠的保护和保密措施 11 Widows的主流文件系统 FAT(File Allocation Table)是“文件分配表”的 意 思。对我们来说，它的意义在于对硬盘分区 的管理。 FAT16、FAT32、NTFS是目前最常见的三种文 件系统。 12 其它文件系统 FAT12:是IBM第一台个人电脑中的MS-DOS 1.0使用的 文件系统，主要用于软盘。这种系统限制分区的容量 最大为16MB但这根本算不上问题，因为软盘容量 从来没有达到16MB。 ISO9660：CD-ROM

9、的文件系统，不过现在已经延伸出 很多新的文件系统，对它的一些缺点进行了弥补，如 Juliet等。 UDF：可读写光盘的文件系统。 Mac HFS：苹果电脑的文件系统，对大容量磁盘有比 较好的支持。不过，现在大多数苹果电脑还在使用 FAT32文件系统。 13 6.2 文件的结构与组织 通常，用户在使用文件时，只关心文件的逻辑 结构。从用户观点观察到的文件组织形式主要 有两类： 一类是有结构的文件 另一类是无结构的流式文件 14 (1) 逻辑记录逻辑记录(结构结构) 逻辑记录是文件中按信息在逻辑上的独立含义来划 分的信息单位。 逻辑记录是对文件进行存取操作的基本单位。 (2) 物理记录物理记录(结

10、构结构) 在存储介质上，由连续信息所组成的一个区域称为 块，也叫物理记录。 (3) 逻辑记录与物理记录的区别与关系逻辑记录与物理记录的区别与关系 一个是逻辑的概念，一个是物理的概念 逻辑记录最终在存放到物理记录上上 文件的两种结构：文件的两种结构： 15 文件的逻辑结构文件的逻辑结构 1. 记录式文件记录式文件 记录式文件是一种有结构的文件。 2. 流式文件流式文件 流式文件是相关的有序字符的集合。是无结构的。 流式文件是按信息的个数或以特殊字符为界进行存取 的。 16 1.记录式文件 每个记录由彼此相关的域构成。记录可按顺序 编号为记录1，记录2，记录n。如果文件 中所有记录的长度都相同，则

11、这种文件为定长 记录文件。 例如:学生登记表文件 xsdjb.dbf 姓名 学号 籍贯 通信地址 邮政编码 李铭 925678 武昌 武昌关山街125号 430074 司马乐 925679 北京 北京海军路88号 100034 17 1.记录式文件记录式文件 记录式文件按照记录长度是否相同，又可分为记录式文件按照记录长度是否相同，又可分为 定长记录文件和不定长记录定长记录文件和不定长记录文件两种。文件两种。 （1）定长记录：定长记录：文件中所有记录的长度相等文件中所有记录的长度相等 。 （2）变长记录：变长记录：文件中记录的长度不相等。文件中记录的长度不相等。 定长记录文件的长度 = 记录个数

12、记录长度。 变长记录文件的长度为各记录长度之和。 18 记录式文件记录式文件 19 2.无结构的文件无结构的文件 无结构文件无结构文件是指文件内部不再划分记录，是由是指文件内部不再划分记录，是由 一组相关信息组成的有序字符流，即流式文件。一组相关信息组成的有序字符流，即流式文件。 其其长度直接按字节来计算长度直接按字节来计算。 事实上事实上操作系统不知道或不关心文件中存放的操作系统不知道或不关心文件中存放的 内容是什么内容是什么，它所见到的都是一个一个的字节。，它所见到的都是一个一个的字节。 文件中任何信息的含义都由用户级程序解释文件中任何信息的含义都由用户级程序解释。 20 2.无结构的文件

13、无结构的文件 21 两种文件的比较 流式文件就象给一张白纸给用户，用户可将他 的信息任意地写到纸上，没有任何格式上的限 制。 记录式文件就象给一张表格给用户，用户要按 表规定的格式填信息。 显然，结构式文件对用户的限制很大，使用起 来就不方便，所以记录式文件被淘汰是理所当 然的。 22 6.3 外存分配方式 一个文件存储介质，格式化后就分成许多大小 相等的单位存储块（物理盘块），在现代 计算机系统中. 一般来说，每个物理块是一个磁盘的扇区， 512字节。并给每个存储块有个编号，称为物 理块号。 常用的外存分配方式有连续分配，链接分配和 索引分配三种。 23 文件存储空间的分配文件存储空间的分配

14、文件的物理结构 24 一.连续分配 25 1.连续分配连续分配 文件A 3 100 r0 r1 r2 磁盘块号 100101102 文件目录文件目录 文件A 目录项 26 2.连续文件结构的特点连续文件结构的特点 优点：结构简单，实现容易，不需要额 外的开销。 缺点： n用户创建文件时要给出文件的大小； n不利于文件的动态增加和修改； 27 连续结构文件的特点连续结构文件的特点 连续分配的优点是在顺序存取时速度较快，一 次可以存取多个盘块，改进了I/O性能。 所以，它常用于存放系统文件，因为这类文件 往往被从头到尾一次存取。另外，也很容易直 接存取文件中的任意一块 例如，要访问从b块开始的第i

15、块，可以直接从 b+i块开始读取，因此，连续结构方式支持顺 序访问和直接访问。 28 二二.链接分配链接分配 链接分配的文件也称之为链接分配的文件也称之为是串联文件是串联文件 串联文件结构是按顺序由串联的块组成的，即 文件的信息存于若干块物理块中，每个物理块 的最末一个字作为链接字，它指出后继块的物 理地址。 文件的最后一块的链接字为结束标记“”， 它表示文件至本块结束。 类似数据结构的链表 29 链接结构链接结构 文件A 100 r1 57 r2 r0 150 磁盘块号 100 磁盘块号 150 磁盘块号 57 文件目录 文件A 目录项 问题：在串联文件结构下，当要存取R i 记录时，应如何

16、操作? 30 链接结构链接结构文件的特点 这种文件结构不要求连续存放。 对于记录式文件一块中可包含一个逻辑 记录或多个逻辑记录 也可以若干物理块包含一个逻辑记录。 31 链接结构链接结构文件的特点 优点： 1.存储空间利用率高； 2.文件创建时用户不必指出文件的大小； 3.文件动态扩充和修改容易。 缺点：只能按队列中的指针顺序搜索，随机存 取效率太低，如果访问文件的最后的内容，实 际上是要访问整个文件。 32 链接分配的两种形式：链接分配的两种形式： 1. 隐式链接隐式链接 25 123 0 567 4 9 10 11 8 131415 12 171819 16 2122 23 20 25 2

17、6 27 24 293031 28 filestartend jeep925 目 录 10 1 -1 16 在采用隐式链接分配时，在文件目录的每个目录项中， 都须含有指向链接文件的第一个盘块和最后一个盘块 的指针。 而在每个盘块中都含有一个指向下一个盘块的指针。 33 2. 显式链接显式链接 图 6-9 显式链接结构 0 1 2 3 4 5 物理块号 2 FCBFAT 0 4 5 1 34 6 EOF 11 10 5 EOF 0 1 2 3 4 5 6 7 8 9 FATFCB A 4 FCB B 9 图 6-10 MS-DOS的文件物理结构 35 例题: 假定盘块的大小是1KB,硬盘的大小为

18、500MB， 采用显式链接分配方式时，其FAT需占用多少 存储空间？如果文件A占用硬盘的第11，12， 16，14四个盘块，试画出文件A中各盘块的链 接情况及FAT的情况。 36 例题： 假设盘块大小为1KB，盘块号需占4个字节。请 分别解释在连续分配方式，隐式链接分配方式 和显式链接分配方式中如何将文件的字节偏移 量3500转换为物理块号和块内位移量。 37 3、索引结构、索引结构 链接结构解决了连续分配的外部碎片和大小链接结构解决了连续分配的外部碎片和大小 声明的问题，但是，声明的问题，但是，链接结构不能有效地支链接结构不能有效地支 持直接访问持直接访问，这是因为块指针与块一起分布这是因为

19、块指针与块一起分布 在整个磁盘，且必须按顺序读出。在整个磁盘，且必须按顺序读出。 索引结构解决了这个问题。索引结构解决了这个问题。索引分配要求系索引分配要求系 统为每个文件建立统为每个文件建立一张索引表一张索引表。 索引结构创建的文件索引结构创建的文件也称之为也称之为索引文件索引文件 38 3、索引结构、索引结构 索引结构文件索引结构文件是另一种形式的非连续 文件，文件数据存放的存储介质上的 物理块号与文件的逻辑块号一一对应， 并建立这样对应关系的数据结构 文件索引表 39 3、索引结构、索引结构 访问文件时，根据文件的逻辑块号查文 件索引表，找到对应的物理块号，然后， 进行访问。 文件由索引

20、表和数据文件构成。这种文件称为 索引文件。 非常类似于书本，它由书目录和正文组成 40 多重索引多重索引 41 索引文件结构 索引文件在存储区中占两个区：索引区 和数据区。索引区存放索引表，数据区 存放数据文件本身。 访问索引文件需要两步操作 查文件索引，由逻辑块号查得物理 块号 由此磁盘物理块号而获得所要求的 信息。 42 索引文件结构 索引文件的特点索引文件的特点 易于文件的增删 直接读写任意记录 索引表的组织索引表的组织多级索引多级索引 43 索引文件实例分析索引文件实例分析UNIX文件索引方式文件索引方式 0 1 9 10 11 12 直接寻址块 直接寻址块 一级间接块 直接寻址块一级

21、间接块二级间接块 直接 寻址 一级间接 二级间接 三级间接 44 华中科技大学2000年 某文件系统采用索引文件结构，假定文件索引 表的每个表项占3个字节，存放一个磁盘块的 块号（磁盘块的大小为512B）。试问 1）该文件系统能管理的最大磁盘空间是多少 字节 2）若采用2级或3级索引该文件系统能管理的 最大磁盘空间又是多少字节？ 45 分析 由于索引表占用一个大小为512B的磁盘，所以 该文件系统的索引表可以管理512/3=170个表 项，而每一个表项对应一个物理块，因此该文 件系统可以管理的最大磁盘空间为 170*512B=87040B=85K 若采用二级索引，则是： 170*170*512

22、B=7225KB 若采用三级索引，则是： 170*170*170*512B=2456500KB=2398.93M 46 例题： 存放在某个磁盘上的文件系统采用混合索引分配方式， 其FCB中共有13个地址项，第09个地址项为直接地 址，第10个地址项为一次间接地址，第11个地址项为 二次间接地址，第12个地址项为三次间接地址。如果 每个盘块的大小为512字节，若盘块号需要用3个字节 来描述，而每个盘块最多存放170个盘块地址。则： （1）该文件系统允许文件的最大长度是多少？ （2）将文件的字节偏移量5000，15000和150000转换 为物理块号和块内偏移量。 47 6.3 文件目录 通常，在

23、计算机系统中，大量的文件被 存储在磁盘上。为了对存储在磁盘上的 众多文件进行有效的控制和管理，必须 对它们加以妥善组织。 这种组织是通过文件目录来实现的，文 件目录是一种数据结构，用来标识文件 系统中的文件及其物理地址，供检索时 使用。 48 文件目录的组成 文件名：符号文件名名，如music、game、file等。 文件类型：指明文件属性是普通文件，还是目录文件 或特别文件，是系统文件还是用户文件等。 文件的物理位置：文件在物理设备上的位置，如文件 存放在哪台设备的哪些盘块上。 文件的大小：当前文件大小（以字节、字或块为单位） 和允许的最大长度。 保护信息：对文件读、写及执行等操作的控制权限

24、标 志。 使用计数：表示当前有多少个进程正在使用或打开了 该文件。 时间和日期：这个信息反映了文件创建、最后修改、 最后使用等情况，可用于对文件实施保护和监控等 49 6.3.1 文件控制块和文件目录文件控制块和文件目录 而文件目录信息也叫文件控制块（而文件目录信息也叫文件控制块（file control block ,FCB），它是操作系统），它是操作系统 为管理文件而设置的数据结构，存放了为管理文件而设置的数据结构，存放了 为管理文件所需的所有有关信息（文件为管理文件所需的所有有关信息（文件 属性）。属性）。 文件控制块是文件存在的标志文件控制块是文件存在的标志，它通常，它通常 由文件属性

25、信息组成。由文件属性信息组成。 50 FCB的外部表现：文件的属性 51 2.文件目录文件目录 为了对众多的文件进行分门别类的管理，提高为了对众多的文件进行分门别类的管理，提高 文件检索的效率，现代操作系统往往文件检索的效率，现代操作系统往往将文件的将文件的 文件控制块集中在一起进行管理文件控制块集中在一起进行管理。 这种这种FCB的有序集合就称为文件目录的有序集合就称为文件目录，文件控，文件控 制块就是其中的目录项（构成文件目录的项制块就是其中的目录项（构成文件目录的项 目）。目）。 另外，为了实现对文件目录的管理，另外，为了实现对文件目录的管理，通常将文通常将文 件目录以文件的形式保存在外

26、存，这个文件就件目录以文件的形式保存在外存，这个文件就 叫目录文件。叫目录文件。 52 3.索引结点的引入索引结点的引入 为了减少系统开销，采用了把文件名与文件描述信为了减少系统开销，采用了把文件名与文件描述信 息分开的办法，息分开的办法，即使文件描述信息单独形成一个称即使文件描述信息单独形成一个称 为索引结点的数据结构为索引结点的数据结构，简称为，简称为i结点。结点。 文件名索引结点编号 文件名1 文件名2 图 6-15 UNIX的文件目录 53 例题： 在某个文件系统中，每个盘块为512字节，文 件控制块占64个字节，其中文件名占8个字节。 如果索引结点编号占2个字节，对一个存放在 磁盘上

27、的256个目录项的目录，试比较引入索 引结点前后，为找到其中一个文件的FCB，平 均其中磁盘的次数。 54 6.3文件目录文件目录 为了方便用户的使用，提高文件系统的 效率，也必须对系统内的所有文件目录 进行组织。 在现代操作系统中，目录的基本组织方 式有： n一级目录 n二级目录 n树形目录 55 6.3.2 一级目录一级目录 一级目录是最简单的目录结构。在这种组织方式下，一级目录是最简单的目录结构。在这种组织方式下， 全部文件都登记在同一目录中。全部文件都登记在同一目录中。 其特点是简单、易于理解和实现，但那也存在以下的其特点是简单、易于理解和实现，但那也存在以下的 缺陷：缺陷：查找速度慢

28、、不允许重名和不便于文件的共享查找速度慢、不允许重名和不便于文件的共享 56 6. 3. 2 二级目录二级目录 n为改变一级目录文件目录命名冲突，并提高为改变一级目录文件目录命名冲突，并提高 对目录文件检索速度而将目录分为两级：对目录文件检索速度而将目录分为两级： n一级称为主文件目录，给出用户名一级称为主文件目录，给出用户名，用户子，用户子 目录所在的物理位置；目录所在的物理位置； n二级称为用户文件目录二级称为用户文件目录，给出该用户所有文，给出该用户所有文 件的件的FCB。 n文件主目录（文件主目录（MFD）的表目按用户分）的表目按用户分，每每 个用户有一个用户文件目录（个用户有一个用户

29、文件目录（UFD） 57 6.2.3 两级目录两级目录 58 6.2.3 两级目录两级目录 n在二级目录结构中，用户引用特定的文件时，在二级目录结构中，用户引用特定的文件时， 系统只需搜索他自己的系统只需搜索他自己的UFD，因此，不同用，因此，不同用 户可拥有具有相同名称的文件，户可拥有具有相同名称的文件，只要每个只要每个 UFD内的所有文件名称惟一即可。内的所有文件名称惟一即可。 n当用户创建文件时，操作系统当用户创建文件时，操作系统也只搜索该用也只搜索该用 户的户的UFD以确定具有相同名字的文件是否存以确定具有相同名字的文件是否存 在在。 n当删除文件时，操作系统只在局部当删除文件时，操作

30、系统只在局部UFD中对中对 其进行搜索，因此，它并不会删除另一个用其进行搜索，因此，它并不会删除另一个用 户的具有相同名称的文件。户的具有相同名称的文件。 59 6.2.3 两级目录的特点两级目录的特点 二级目录的优点：解决了名称冲突 和文件共享问题，提高了搜索速度， 查找时间也降低了。 但是，它仍有一定的缺陷：缺少灵 活性、不能反映现实世界中的多层 关系。 因此就产生了多级目录结构 60 6.3.3 树型目录（多级目录结构）树型目录（多级目录结构） 又称为多级目录结构，它是二级目录结又称为多级目录结构，它是二级目录结 构的扩充。构的扩充。 这种多层次的目录结构如同一棵倒置的这种多层次的目录结

31、构如同一棵倒置的 树，主目录就是树根，称为树，主目录就是树根，称为根目录根目录 每一个树枝结点就是一个子目录每一个树枝结点就是一个子目录，每一，每一 片树叶描述的一个文件。片树叶描述的一个文件。 61 6.3.3 树型目录树型目录 62 6.3.3 树型目录树型目录 在树形目录结构中，在树形目录结构中，一个文件的全一个文件的全 名名将包括从根目录开始到文件为止将包括从根目录开始到文件为止 的通路上遇到的所有子目录路径。的通路上遇到的所有子目录路径。 各子目录名之间用各子目录名之间用正斜线正斜线“/”或反或反 斜线斜线“”隔开，其中，子目录名组隔开，其中，子目录名组 成的部分又称为路径名。成的部

32、分又称为路径名。 63 6.3.3 树型目录树型目录 系统内的每个文件都有惟一的路径名。系统内的每个文件都有惟一的路径名。 路径名路径名是从根经过所有子目录再到指定文件的路径。是从根经过所有子目录再到指定文件的路径。 路径名有两种形式：路径名有两种形式：绝对路径名和相对路径名绝对路径名和相对路径名。 n绝对路径名绝对路径名从根目录开始并给出路径上的目录名直从根目录开始并给出路径上的目录名直 到指定的文件到指定的文件 n相对路径名相对路径名从当前目录开始定义一个路径。从当前目录开始定义一个路径。 n UNIX/Linux也使用相对路径名和绝对路径名来标识也使用相对路径名和绝对路径名来标识 文件或

33、目录，只不过文件和目录之间采用文件或目录，只不过文件和目录之间采用“/”来分隔，来分隔， 而不是而不是DOS的的“” 。 64 6.2.4 树型目录树型目录 树形目录 当前目录/root/spell/mail 请问first的相对路径和绝 对路径分别是什么？ 65 6.3.3 树型目录树型目录 在上图所示的树形目录中，如果当前目录是 /root/spell/mail， 那么相对路径名prt/first 和绝对路径名root/spell/mail/prt/first指向相同 的文件。 66 6.4文件存储空间的管理文件存储空间的管理 存储空间管理是文件系统的重要任务之一。只 有有效地进行存储空间

34、管理，才能保证多个用 户共享文件存储设备和得以实现文件的按名存 取。 由于文件存储设备是分成若干个大小相等的物 理块，并以块为单位来交换信息的，因此，文 件存储空间的管理实质上是一个空闲块的组织 和管理问题，它包括空闲块的组织，空闲块的 分配与空闲块的回收等几个问题。 67 6.4文件存储空间的管理文件存储空间的管理 有4种不同的空闲块管理方法。它们是： (1) 空闲文件表； (2) 空闲块链； (3) 位示图； (4) 成组链接法。 下面介绍这几种空闲空间的分配方法。 68 1、空闲文件表： 简单的空闲块管理方法就是简单的空闲块管理方法就是把文件存储把文件存储 设备中的设备中的空闲块的块号空

35、闲块的块号统一放在一个称统一放在一个称 为空闲文件目录的物理块中为空闲文件目录的物理块中。 其中空闲文件目录的每个表项对应一个其中空闲文件目录的每个表项对应一个 由多个空闲块构成的空闲区，它包括由多个空闲块构成的空闲区，它包括空空 闲块个数，空闲块号和第一个空闲块号闲块个数，空闲块号和第一个空闲块号 等。等。 69 1、空闲文件表 70 2、空闲块链、空闲块链 空闲块链是一种较常用的空闲块管理方法。空闲块链是一种较常用的空闲块管理方法。 空闲块链把文件存储设备上的所有空闲块链把文件存储设备上的所有空闲块链接空闲块链接 在一起在一起 当申请者需要空闲块时，分配程序从当申请者需要空闲块时，分配程序

36、从链头开始链头开始 摘取所需要的空闲块，然后调整链首指针摘取所需要的空闲块，然后调整链首指针。 反之，当回收空闲块时，把释放的空闲块逐个反之，当回收空闲块时，把释放的空闲块逐个 插入链尾上。插入链尾上。 71 2.空闲块链空闲块链 空闲块链示意图 r1 57 r2 r0 150 rn 72 3.位示图位示图 系统首先从系统首先从内存中分配若干个字节内存中分配若干个字节，为每个文，为每个文 件存储设备建立件存储设备建立一张位示图一张位示图。 这张位示图反映每个文件存储设备的使用情况。这张位示图反映每个文件存储设备的使用情况。 在位示图中，每个文件存储设备的物理块都对在位示图中，每个文件存储设备的

37、物理块都对 应一个比特位。应一个比特位。 n如果该位为如果该位为“0”，则表示所对应的块是空闲，则表示所对应的块是空闲 块；块； n反之，如果该位为反之，如果该位为“1”，则表示所对应的块，则表示所对应的块 已被分配出去。已被分配出去。 73 图 6-21 位示图 3.位示图位示图 74 盘块的分配：盘块的分配： (1) 顺序扫描位示图，从中找出一个或一组其值为“0” 的二进制位(“0”表示空闲时)。 (2) 将所找到的一个或一组二进制位， 转换成与之相应 的盘块号。假定找到的其值为“0”的二进制位，位于位示 的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j 式中， n代

38、表每行的位数。 (3) 修改位示图， 令mapi,j=1。 3.位示图位示图 75 盘块的回收：盘块的回收： (1) 将回收盘块的盘块号转换成位示图中的行号和列 号。 转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1 (2) 修改位示图。 令map i,j=1。 3.位示图位示图 76 例题：例题： 在页式存储管理中，可以用位示图表示内存空闲块状 况。假设字长为32位，每一位(编号为0-31)与一个内 存块对应，取值可为0或1。当取值为1时表示对应块已 被占用，当取值为0时表示对应块为空闲。 (1) 如果内存可分配区被划分为1024块，则位示图共 需要多少个字来表示？

39、A) 15 B) 16 C) 31 D) 32 答案：D (2) 已知某一位的字号是5，位号为14，假设字号也从 0开始编号。则对应的内存块号是多少？（假设内存块 从0开始编号） A) 70 B) 105 C) 173 D) 224 答案：C 77 例题： 有一计算机系统利用下图所示的位示图来管理空 闲块（行、列号均从0开始），如果块号从1开 始，每个盘块大小为1kb。 1.现要为文件分配两个盘块，具体说明分配过程。 2.若要释放磁盘的第300块，应如何处理？ 78 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 1 1

40、1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79 4. 成组链接法成组链接法 1. 空闲盘块的组织空闲盘块的组织 100 400 399 301 300 100 300 299 202 201 299 100 400 399 201301 99 0 7999 7901 7900 7899 7801 7999 7901 空闲盘块号 栈 S.free 0 1 98 99

41、 图 6-22 空闲盘块的成组链接法 80 2. 空闲盘块的分配与回收空闲盘块的分配与回收 在分配时，首先检查空闲盘块号栈是否上锁，如未上锁， 便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户， 然后将栈顶指针下移一格。 若该盘块号已是栈底， 即该块是当前组中可分配的盘块。 由于在该盘块号所对应的盘块中记有下一组可用的盘块号列 表，因此，须将其读入栈中，作为新的一组空闲块，并把原 栈底对应的盘块分配出去(其中的有用数据已读入栈中)。 81 在系统回收空闲盘块时，将回收盘块的盘块号记入空 闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空 闲盘块号数目已达100时， 表示栈已满，便将现有栈中的 100个盘块号， 记入新回收的盘块中，再将其盘块号作为新 栈底。 82 例题： 某个系统采用成组链接法来管理磁盘的空闲空 间，目前磁盘的状态如图。 1