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

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

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

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

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

5、.1.2文件的分类文件的分类（2）按文件的操作保护分类）按文件的操作保护分类n只读文件：只读文件： 只允许进行读操作，不能进行只允许进行读操作，不能进行写操作的文件。写操作的文件。n读写文件：读写文件： 允许文件主和授权用户对其进允许文件主和授权用户对其进行读或写操作的文件。行读或写操作的文件。n只执行文件：只执行文件：该类文件只允许授权的用户调该类文件只允许授权的用户调用执行，而不允许其修改或读出文件的内容。用执行，而不允许其修改或读出文件的内容。76.1.2文件的分类文件的分类（3）按文件的性质分类）按文件的性质分类n普通文件：普通文件： 指一般的用户文件和系统文件。指一般的用户文件和系统

6、文件。n目录文件：目录文件： 管理和实现文件系统的文件目管理和实现文件系统的文件目录项组成的系统文件，对目录文件可以进行录项组成的系统文件，对目录文件可以进行与普通文件一样的各种文件操作。与普通文件一样的各种文件操作。n特别文件：特别文件： 有的系统把设备作为文件统一有的系统把设备作为文件统一管理和使用，并为区别起见，管理和使用，并为区别起见，把设备称为特把设备称为特别文件别文件。例如：。例如：unix/linux86.1.3 文件系统及其功能文件系统是操作系统中负责存取和管理信息的模块，它用统一的方式管理用户和对系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操

7、作方法。它由管理文件所需的数据结构（如文件控制块及存储分配表等）和相应的管理软件以及访问文件的一组操作组成。9文件系统的功能1.使用户可执行创建、修改及删除读写文件的命令。2.使用户在系统控制下共享其他用户的文件，以便用户可共享其它人的工作成果。3.使用户能以合适的方式构造其他文件4.使用户能使用在文件间进行数据传输的命令10文件系统的功能5.为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进行信息的存取和加工。这种逻辑结构是独立于物理存储设备的。 6.为了防止意外事故，文件系统具有转储和恢复文件的能力7.能提供可靠的保护和保密措施11Widows的主流文件

8、系统FAT(File Allocation Table)是“文件分配表”的意 思。对我们来说，它的意义在于对硬盘分区的管理。FAT16、FAT32、NTFS是目前最常见的三种文件系统。12其它文件系统FAT12:是IBM第一台个人电脑中的MS-DOS 1.0使用的文件系统，主要用于软盘。这种系统限制分区的容量最大为16MB但这根本算不上问题，因为软盘容量从来没有达到16MB。 ISO9660：CD-ROM的文件系统，不过现在已经延伸出很多新的文件系统，对它的一些缺点进行了弥补，如Juliet等。 UDF：可读写光盘的文件系统。 Mac HFS：苹果电脑的文件系统，对大容量磁盘有比较好的支持。不

9、过，现在大多数苹果电脑还在使用FAT32文件系统。 136.2 文件的结构与组织通常，用户在使用文件时，只关心文件的逻辑结构。从用户观点观察到的文件组织形式主要有两类：一类是有结构的文件另一类是无结构的流式文件14(1) 逻辑记录逻辑记录(结构结构)逻辑记录是文件中按信息在逻辑上的独立含义来划分的信息单位。逻辑记录是对文件进行存取操作的基本单位。 (2) 物理记录物理记录(结构结构)在存储介质上，由连续信息所组成的一个区域称为块，也叫物理记录。(3) 逻辑记录与物理记录的区别与关系逻辑记录与物理记录的区别与关系一个是逻辑的概念，一个是物理的概念逻辑记录最终在存放到物理记录上上文件的两种结构：文

10、件的两种结构：15文件的逻辑结构文件的逻辑结构1. 记录式文件记录式文件记录式文件是一种有结构的文件。2. 流式文件流式文件流式文件是相关的有序字符的集合。是无结构的。流式文件是按信息的个数或以特殊字符为界进行存取的。161.记录式文件每个记录由彼此相关的域构成。记录可按顺序编号为记录1，记录2，记录n。如果文件中所有记录的长度都相同，则这种文件为定长记录文件。例如:学生登记表文件 xsdjb.dbf姓名 学号 籍贯 通信地址 邮政编码李铭 925678 武昌 武昌关山街125号 430074司马乐 925679 北京 北京海军路88号 100034171.记录式文件记录式文件记录式文件按照记

11、录长度是否相同，又可分为记录式文件按照记录长度是否相同，又可分为定长记录文件和不定长记录定长记录文件和不定长记录文件两种。文件两种。 （1）定长记录：定长记录：文件中所有记录的长度相等文件中所有记录的长度相等 。 （2）变长记录：变长记录：文件中记录的长度不相等。文件中记录的长度不相等。定长记录文件的长度 = 记录个数记录长度。变长记录文件的长度为各记录长度之和。18记录式文件记录式文件192.无结构的文件无结构的文件无结构文件无结构文件是指文件内部不再划分记录，是由是指文件内部不再划分记录，是由一组相关信息组成的有序字符流，即流式文件。一组相关信息组成的有序字符流，即流式文件。其其长度直接按

12、字节来计算长度直接按字节来计算。事实上事实上操作系统不知道或不关心文件中存放的操作系统不知道或不关心文件中存放的内容是什么内容是什么，它所见到的都是一个一个的字节。，它所见到的都是一个一个的字节。文件中任何信息的含义都由用户级程序解释文件中任何信息的含义都由用户级程序解释。202.无结构的文件无结构的文件21两种文件的比较流式文件就象给一张白纸给用户，用户可将他的信息任意地写到纸上，没有任何格式上的限制。记录式文件就象给一张表格给用户，用户要按表规定的格式填信息。显然，结构式文件对用户的限制很大，使用起来就不方便，所以记录式文件被淘汰是理所当然的。226.3 外存分配方式一个文件存储介质，格式

13、化后就分成许多大小相等的单位存储块（物理盘块），在现代计算机系统中.一般来说，每个物理块是一个磁盘的扇区，512字节。并给每个存储块有个编号，称为物理块号。常用的外存分配方式有连续分配，链接分配和索引分配三种。23文件存储空间的分配文件存储空间的分配文件的物理结构24一.连续分配251.连续分配连续分配 文件A 3 100 r0 r1 r2 磁盘块号100101102文件目录文件目录文件A目录项262.连续文件结构的特点连续文件结构的特点 优点：结构简单，实现容易，不需要额外的开销。缺点：n用户创建文件时要给出文件的大小；n不利于文件的动态增加和修改；27连续结构文件的特点连续结构文件的特点连

14、续分配的优点是在顺序存取时速度较快，一次可以存取多个盘块，改进了I/O性能。所以，它常用于存放系统文件，因为这类文件往往被从头到尾一次存取。另外，也很容易直接存取文件中的任意一块例如，要访问从b块开始的第i块，可以直接从b+i块开始读取，因此，连续结构方式支持顺序访问和直接访问。 28二二.链接分配链接分配链接分配的文件也称之为链接分配的文件也称之为是串联文件是串联文件串联文件结构是按顺序由串联的块组成的，即文件的信息存于若干块物理块中，每个物理块的最末一个字作为链接字，它指出后继块的物理地址。文件的最后一块的链接字为结束标记“”，它表示文件至本块结束。类似数据结构的链表29链接结构链接结构文

15、件A 100 r1 57 r2 r0 150磁盘块号 100磁盘块号 150磁盘块号 57文件目录文件A目录项问题：在串联文件结构下，当要存取R i 记录时，应如何操作?30链接结构链接结构文件的特点这种文件结构不要求连续存放。对于记录式文件一块中可包含一个逻辑记录或多个逻辑记录也可以若干物理块包含一个逻辑记录。31链接结构链接结构文件的特点优点：1.存储空间利用率高；2.文件创建时用户不必指出文件的大小；3.文件动态扩充和修改容易。缺点：只能按队列中的指针顺序搜索，随机存取效率太低，如果访问文件的最后的内容，实际上是要访问整个文件。32链接分配的两种形式：链接分配的两种形式：1. 隐式链接隐

16、式链接 25123056749101181314151217181916212223202526272429303128filestartendjeep925目 录101-116在采用隐式链接分配时，在文件目录的每个目录项中，都须含有指向链接文件的第一个盘块和最后一个盘块的指针。而在每个盘块中都含有一个指向下一个盘块的指针。332. 显式链接显式链接 图 6-9 显式链接结构 012345物理块号2FCBFAT0451346EOF11105EOF0123456789FATFCB A4FCB B9图 6-10 MS-DOS的文件物理结构35例题:假定盘块的大小是1KB,硬盘的大小为500MB，采

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

18、出。在整个磁盘，且必须按顺序读出。索引结构解决了这个问题。索引结构解决了这个问题。索引分配要求系索引分配要求系统为每个文件建立统为每个文件建立一张索引表一张索引表。索引结构创建的文件索引结构创建的文件也称之为也称之为索引文件索引文件383、索引结构、索引结构索引结构文件索引结构文件是另一种形式的非连续文件，文件数据存放的存储介质上的物理块号与文件的逻辑块号一一对应，并建立这样对应关系的数据结构文件索引表393、索引结构、索引结构访问文件时，根据文件的逻辑块号查文件索引表，找到对应的物理块号，然后，进行访问。文件由索引表和数据文件构成。这种文件称为索引文件。非常类似于书本，它由书目录和正文组成4

19、0多重索引多重索引41索引文件结构索引文件在存储区中占两个区：索引区和数据区。索引区存放索引表，数据区存放数据文件本身。访问索引文件需要两步操作 查文件索引，由逻辑块号查得物理块号 由此磁盘物理块号而获得所要求的信息。 42索引文件结构索引文件的特点索引文件的特点 易于文件的增删 直接读写任意记录索引表的组织索引表的组织多级索引多级索引43索引文件实例分析索引文件实例分析UNIX文件索引方式文件索引方式019101112直接寻址块直接寻址块一级间接块直接寻址块一级间接块二级间接块直接寻址一级间接二级间接三级间接44华中科技大学2000年某文件系统采用索引文件结构，假定文件索引表的每个表项占3个

20、字节，存放一个磁盘块的块号（磁盘块的大小为512B）。试问1）该文件系统能管理的最大磁盘空间是多少字节2）若采用2级或3级索引该文件系统能管理的最大磁盘空间又是多少字节？45分析由于索引表占用一个大小为512B的磁盘，所以该文件系统的索引表可以管理512/3=170个表项，而每一个表项对应一个物理块，因此该文件系统可以管理的最大磁盘空间为170*512B=87040B=85K若采用二级索引，则是：170*170*512B=7225KB若采用三级索引，则是：170*170*170*512B=2456500KB=2398.93M46例题：存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB中共

21、有13个地址项，第09个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址。则： （1）该文件系统允许文件的最大长度是多少？ （2）将文件的字节偏移量5000，15000和150000转换为物理块号和块内偏移量。476.3 文件目录通常，在计算机系统中，大量的文件被存储在磁盘上。为了对存储在磁盘上的众多文件进行有效的控制和管理，必须对它们加以妥善组织。这种组织是通过文件目录来实现的，文件目录是一种数据结构，用来标识文件系统中的文件及其物理地址

22、，供检索时使用。48文件目录的组成文件名：符号文件名名，如music、game、file等。文件类型：指明文件属性是普通文件，还是目录文件或特别文件，是系统文件还是用户文件等。文件的物理位置：文件在物理设备上的位置，如文件存放在哪台设备的哪些盘块上。文件的大小：当前文件大小（以字节、字或块为单位）和允许的最大长度。保护信息：对文件读、写及执行等操作的控制权限标志。使用计数：表示当前有多少个进程正在使用或打开了该文件。时间和日期：这个信息反映了文件创建、最后修改、最后使用等情况，可用于对文件实施保护和监控等496.3.1 文件控制块和文件目录文件控制块和文件目录而文件目录信息也叫文件控制块（而文

23、件目录信息也叫文件控制块（file control block ,FCB），它是操作系统），它是操作系统为管理文件而设置的数据结构，存放了为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件为管理文件所需的所有有关信息（文件属性）。属性）。 文件控制块是文件存在的标志文件控制块是文件存在的标志，它通常，它通常由文件属性信息组成。由文件属性信息组成。50FCB的外部表现：文件的属性512.文件目录文件目录为了对众多的文件进行分门别类的管理，提高为了对众多的文件进行分门别类的管理，提高文件检索的效率，现代操作系统往往文件检索的效率，现代操作系统往往将文件的将文件的文件控制块集中在一

24、起进行管理文件控制块集中在一起进行管理。这种这种FCB的有序集合就称为文件目录的有序集合就称为文件目录，文件控，文件控制块就是其中的目录项（构成文件目录的项制块就是其中的目录项（构成文件目录的项目）。目）。另外，为了实现对文件目录的管理，另外，为了实现对文件目录的管理，通常将文通常将文件目录以文件的形式保存在外存，这个文件就件目录以文件的形式保存在外存，这个文件就叫目录文件。叫目录文件。523.索引结点的引入索引结点的引入为了减少系统开销，采用了把文件名与文件描述信为了减少系统开销，采用了把文件名与文件描述信息分开的办法，息分开的办法，即使文件描述信息单独形成一个称即使文件描述信息单独形成一个

25、称为索引结点的数据结构为索引结点的数据结构，简称为，简称为i结点。结点。文件名索引结点编号文件名1文件名2图 6-15 UNIX的文件目录 53例题：在某个文件系统中，每个盘块为512字节，文件控制块占64个字节，其中文件名占8个字节。如果索引结点编号占2个字节，对一个存放在磁盘上的256个目录项的目录，试比较引入索引结点前后，为找到其中一个文件的FCB，平均其中磁盘的次数。546.3文件目录文件目录为了方便用户的使用，提高文件系统的效率，也必须对系统内的所有文件目录进行组织。在现代操作系统中，目录的基本组织方式有：n一级目录n二级目录n树形目录556.3.2 一级目录一级目录一级目录是最简单

26、的目录结构。在这种组织方式下，一级目录是最简单的目录结构。在这种组织方式下，全部文件都登记在同一目录中。全部文件都登记在同一目录中。其特点是简单、易于理解和实现，但那也存在以下的其特点是简单、易于理解和实现，但那也存在以下的缺陷：缺陷：查找速度慢、不允许重名和不便于文件的共享查找速度慢、不允许重名和不便于文件的共享566. 3. 2 二级目录二级目录n为改变一级目录文件目录命名冲突，并提高为改变一级目录文件目录命名冲突，并提高对目录文件检索速度而将目录分为两级：对目录文件检索速度而将目录分为两级：n一级称为主文件目录，给出用户名一级称为主文件目录，给出用户名，用户子，用户子目录所在的物理位置；

27、目录所在的物理位置；n二级称为用户文件目录二级称为用户文件目录，给出该用户所有文，给出该用户所有文件的件的FCB。n文件主目录（文件主目录（MFD）的表目按用户分）的表目按用户分，每每个用户有一个用户文件目录（个用户有一个用户文件目录（UFD）576.2.3 两级目录两级目录586.2.3 两级目录两级目录n在二级目录结构中，用户引用特定的文件时，在二级目录结构中，用户引用特定的文件时，系统只需搜索他自己的系统只需搜索他自己的UFD，因此，不同用，因此，不同用户可拥有具有相同名称的文件，户可拥有具有相同名称的文件，只要每个只要每个UFD内的所有文件名称惟一即可。内的所有文件名称惟一即可。n当用

28、户创建文件时，操作系统当用户创建文件时，操作系统也只搜索该用也只搜索该用户的户的UFD以确定具有相同名字的文件是否存以确定具有相同名字的文件是否存在在。n当删除文件时，操作系统只在局部当删除文件时，操作系统只在局部UFD中对中对其进行搜索，因此，它并不会删除另一个用其进行搜索，因此，它并不会删除另一个用户的具有相同名称的文件。户的具有相同名称的文件。596.2.3 两级目录的特点两级目录的特点二级目录的优点：解决了名称冲突和文件共享问题，提高了搜索速度，查找时间也降低了。但是，它仍有一定的缺陷：缺少灵活性、不能反映现实世界中的多层关系。因此就产生了多级目录结构606.3.3 树型目录（多级目录

29、结构）树型目录（多级目录结构）又称为多级目录结构，它是二级目录结又称为多级目录结构，它是二级目录结构的扩充。构的扩充。这种多层次的目录结构如同一棵倒置的这种多层次的目录结构如同一棵倒置的树，主目录就是树根，称为树，主目录就是树根，称为根目录根目录每一个树枝结点就是一个子目录每一个树枝结点就是一个子目录，每一，每一片树叶描述的一个文件。片树叶描述的一个文件。616.3.3 树型目录树型目录626.3.3 树型目录树型目录在树形目录结构中，在树形目录结构中，一个文件的全一个文件的全名名将包括从根目录开始到文件为止将包括从根目录开始到文件为止的通路上遇到的所有子目录路径。的通路上遇到的所有子目录路径

30、。各子目录名之间用各子目录名之间用正斜线正斜线“/”或反或反斜线斜线“”隔开，其中，子目录名组隔开，其中，子目录名组成的部分又称为路径名。成的部分又称为路径名。636.3.3 树型目录树型目录系统内的每个文件都有惟一的路径名。系统内的每个文件都有惟一的路径名。路径名路径名是从根经过所有子目录再到指定文件的路径。是从根经过所有子目录再到指定文件的路径。路径名有两种形式：路径名有两种形式：绝对路径名和相对路径名绝对路径名和相对路径名。n绝对路径名绝对路径名从根目录开始并给出路径上的目录名直从根目录开始并给出路径上的目录名直到指定的文件到指定的文件n相对路径名相对路径名从当前目录开始定义一个路径。从

31、当前目录开始定义一个路径。n UNIX/Linux也使用相对路径名和绝对路径名来标识也使用相对路径名和绝对路径名来标识文件或目录，只不过文件和目录之间采用文件或目录，只不过文件和目录之间采用“/”来分隔，来分隔，而不是而不是DOS的的“” 。 646.2.4 树型目录树型目录树形目录当前目录/root/spell/mail请问first的相对路径和绝对路径分别是什么？656.3.3 树型目录树型目录在上图所示的树形目录中，如果当前目录是/root/spell/mail，那么相对路径名prt/first和绝对路径名root/spell/mail/prt/first指向相同的文件。666.4文件存

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

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

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

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

36、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块，则位示图共需要多少个字来表示？ A) 15 B) 16 C) 31 D)

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

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