第七讲文件系统

1、目的与要求目的与要求：了解文件结构，访问方式，存储结了解文件结构，访问方式，存储结构。掌握文件管理用的文件控制块和文件目录构。掌握文件管理用的文件控制块和文件目录结构。了解文件存储器分区和空间管理。文件结构。了解文件存储器分区和空间管理。文件存放与访问方式，文件目录结构。文件使用和存放与访问方式，文件目录结构。文件使用和控制、文件保护控制、文件保护重点与难点重点与难点：掌握文件系统调用处理及使掌握文件系统调用处理及使 用。了解文件备份与保护、系统的组成和各部用。了解文件备份与保护、系统的组成和各部分功能。分功能。第七讲第七讲 文件系统文件系统1.1.大量的程序和数据需要管理。为了大量的程序和数

2、据需要管理。为了方便使用管理系统的公共程序和数据方便使用管理系统的公共程序和数据以及用户自己的程序和数据而引入文以及用户自己的程序和数据而引入文件。件。为什么引入文件和文件系统为什么引入文件和文件系统2.2.内存空间有限。不是所有的程序和数内存空间有限。不是所有的程序和数据都能常驻内存。据都能常驻内存。3.3.为了对程序和数据实现按名存取。为为了对程序和数据实现按名存取。为了对外存储器空间管理和对其上文件的了对外存储器空间管理和对其上文件的按名访问而引入文件系统按名访问而引入文件系统 。为什么引入文件和文件系统为什么引入文件和文件系统文件系统的基础是什么文件系统的基础是什么? ?大容量磁盘大容

3、量磁盘7.1. 7.1. 概述概述一、什么是文件？一、什么是文件？文件（文件（filefile）是被命名的相关信息的集是被命名的相关信息的集合体。合体。它由创建者定义，通常存放在外存上，它由创建者定义，通常存放在外存上，可以作为一个独立单位来实施相应的操可以作为一个独立单位来实施相应的操作（如打开、关闭、读写等）。作（如打开、关闭、读写等）。二、文件的主要属性包括哪些？二、文件的主要属性包括哪些？ 文件名，文件类型，文件长度，文件名，文件类型，文件长度，创建者，创建时间，修改时间，创建者，创建时间，修改时间，文件定位信息文件定位信息 ，文件所包含的，文件所包含的信息。信息。三、文件的基本特征有

4、哪些？三、文件的基本特征有哪些？文件体内容丰富，可以是源程序、文件体内容丰富，可以是源程序、可执行代码、数据、表格、语言或可执行代码、数据、表格、语言或图像等。图像等。无论何种内容的文件都用一个名无论何种内容的文件都用一个名字唯一标识，并都遵循按名存取原字唯一标识，并都遵循按名存取原则。则。文件具有可重用性和可保存性。文件具有可重用性和可保存性。四、文件的分类四、文件的分类（1 1）按文件的用途分为）按文件的用途分为3 3类：类：系统文系统文件、库文件和用户文件件、库文件和用户文件系统文件。由操作系统及其他系统程系统文件。由操作系统及其他系统程序的信息所组成的文件。序的信息所组成的文件。如操作

5、系统核心目标代码文件，驱如操作系统核心目标代码文件，驱动程序文件，注册库配置文件。动程序文件，注册库配置文件。库文件。指系统提供的实用子程序库，库文件。指系统提供的实用子程序库，用户只能使用不能修改的程序文件。如用户只能使用不能修改的程序文件。如C C语言、语言、PASCALPASCAL语言提供的子程序库，语言提供的子程序库，windowswindows中的中的 .dll .dll，.exe.exe。用户文件。如用户源程序和数据文件，用户文件。如用户源程序和数据文件，各种应用程序用的数据文件。各种应用程序用的数据文件。（2 2）按文件中的数据形式分类）按文件中的数据形式分类源文件源文件目标文件

6、目标文件可执行文件可执行文件（3 3）按存取权限分类）按存取权限分类只读文件只读文件读写文件读写文件可执行文件可执行文件（4 4）按保存时间分类）按保存时间分类临时文件临时文件永久文件永久文件（5 5）按文件的内部构造和处理方式分类）按文件的内部构造和处理方式分类普通文件普通文件-由表示程序、数据或文由表示程序、数据或文本的字符串构成，内部没有固定的结构。本的字符串构成，内部没有固定的结构。目录文件目录文件-由下属文件的目录项构由下属文件的目录项构成的文件。成的文件。特殊文件特殊文件-特指各种外部设备。特指各种外部设备。五、文件存取方法五、文件存取方法 （1 1）顺序存取法）顺序存取法 按照文

7、件的逻辑地址顺序来存取。按照文件的逻辑地址顺序来存取。程序依次访问文件的数据，操作系程序依次访问文件的数据，操作系统自动记录文件访问的当前位置。统自动记录文件访问的当前位置。生活中的例子：生活中的例子：v文件归档时按文件编号顺序存放，文件归档时按文件编号顺序存放，查阅时按文件编号顺序查找。查阅时按文件编号顺序查找。（2 2）随机存取法）随机存取法 程序读程序读/ /写时直接给出要访问数据的写时直接给出要访问数据的逻辑位置（即记录编号，如第几个字逻辑位置（即记录编号，如第几个字节或第几个记录）及长度，由节或第几个记录）及长度，由OSOS将逻将逻辑位置转换成物理位置并访问辑位置转换成物理位置并访问

8、生活中的例子：生活中的例子：v文件存放时按自己的生活习惯把文文件存放时按自己的生活习惯把文件存放于自己易于记忆的地方，取件存放于自己易于记忆的地方，取阅时自己记住（大脑转换）存放的阅时自己记住（大脑转换）存放的地方。地方。（3 3）其他方法（如按键存取法，索引）其他方法（如按键存取法，索引存取法等）存取法等）按键存取法按键存取法文件的存取根据给定的键或记录名进文件的存取根据给定的键或记录名进行。行。生活中的例子：生活中的例子：文件存放时按文件名（如标题）分文件存放时按文件名（如标题）分类存放，取阅时按文件类型查找。类存放，取阅时按文件类型查找。六、文件的存储介质六、文件的存储介质 顺序存储设备

9、顺序存储设备v如：磁带如：磁带 直接存储设备（随机存取设备）直接存储设备（随机存取设备）v如：磁盘、光盘、闪存等如：磁盘、光盘、闪存等7.2 7.2 文件系统的功能与结构文件系统的功能与结构 一、文件系统的概念一、文件系统的概念现代操作系统中都配置较为完备的现代操作系统中都配置较为完备的文件管理系统，简称文件系统。文件管理系统，简称文件系统。或：文件系统，就是操作系统中负或：文件系统，就是操作系统中负责操纵和管理文件的一整套设施，责操纵和管理文件的一整套设施，客观存在实现文件的共享和保护，客观存在实现文件的共享和保护，方便用户方便用户“按名存取按名存取”文件。文件。二、文件系统的功能二、文件系

10、统的功能文件管理文件管理目录管理目录管理文件存储空间管理文件存储空间管理文件的共享与保护文件的共享与保护提供方便的接口提供方便的接口7.3 7.3 文件目录结构和目录查询文件目录结构和目录查询 为管理大量的文件，实现对文件为管理大量的文件，实现对文件信息的信息的“按名存取按名存取”，一般用文件目，一般用文件目录的方法来管理文件，每个文件在文录的方法来管理文件，每个文件在文件目录中有一个目录项。文件目录记件目录中有一个目录项。文件目录记录所有文件的名字及它代表的文件存录所有文件的名字及它代表的文件存放的物理地址。放的物理地址。（一）文件的内涵（一）文件的内涵一个文件由文件说明和文件体组成一个文件

11、由文件说明和文件体组成（二）文件控制块（二）文件控制块说明部分的全部信息集中起来，以一说明部分的全部信息集中起来，以一个数据结构的形式表示，称此结构为个数据结构的形式表示，称此结构为文件控制块文件控制块（FCBFCB）。因此，文件包含）。因此，文件包含文件控制块和文件体。文件控制块和文件体。（三）（三）FCBFCB的主要内容：的主要内容：(1)(1)文件名文件名(2)(2)文件类型文件类型(3)(3)文件位置文件位置(4)(4)文件大小文件大小(5)(5)保护信息保护信息(6)(6)使用计数使用计数(7)(7)时间时间（四）文件目录的组成（四）文件目录的组成所有文件的文件控制块的有序集合，所有

12、文件的文件控制块的有序集合，就构成了就构成了文件目录文件目录。完全由文件控制块构成的文件称为完全由文件控制块构成的文件称为目录文件目录文件。例：例：MS-DOSMS-DOS的文件控制块的文件控制块在在MS-DOSMS-DOS系统中，一个文件控制块系统中，一个文件控制块有有1616个字节长，其中包含文件名，个字节长，其中包含文件名，扩展名、属性、时间、日期、首块扩展名、属性、时间、日期、首块号和文件大小。如下图示：号和文件大小。如下图示：文件名文件名扩展名扩展名保留保留大小大小属性属性时间时间日期日期首块号首块号文件目录文件目录例：例：MS-DOSMS-DOS的文件目录的文件目录例：例：MS-D

13、OSMS-DOS的目录文件的目录文件将上例文件目录以一个名字存储起来得将上例文件目录以一个名字存储起来得到的文件称目录文件。到的文件称目录文件。每个磁盘设备都有一个且只有一个根目每个磁盘设备都有一个且只有一个根目录文件录文件, ,但可以有很多子目录文件但可以有很多子目录文件WINDOWSWINDOWS系统以文件夹图标标示。系统以文件夹图标标示。 7.3.2 7.3.2 文件的目录结构文件的目录结构1.1.一级目录结构一级目录结构 为外存上的全部文件设立一张线性排为外存上的全部文件设立一张线性排列的目录表，包含所有文件的列的目录表，包含所有文件的FCBFCB。每建。每建立一个新文件即在目录中增加

14、一个立一个新文件即在目录中增加一个FCBFCB，每当删除一个文件即删除对应的每当删除一个文件即删除对应的FCBFCB，当，当要访问一个文件时，先按文件名在目录要访问一个文件时，先按文件名在目录中找到对应的文件中找到对应的文件FCBFCB。然后由它的。然后由它的FCBFCB映射其存放的物理地址。（见下图示）映射其存放的物理地址。（见下图示） FCB1 FCB2 FCB3 FCBn 文件1 文件2 文件3 文件n 一级目录结构示意图一级目录结构示意图FCBnn2.2.二级目录结构二级目录结构 设一个设一个主目录主目录MFDMFD，然后为系统的每个然后为系统的每个用户设用户设用户目录用户目录UFDU

15、FD。用户目录是用户。用户目录是用户所有文件所有文件FCBFCB的集合，主目录中存放每的集合，主目录中存放每个用户目录的用户目录名和个用户目录的用户目录名和UFDUFD的索引的索引表等（当我们把表等（当我们把UFDUFD看做是一个文件，看做是一个文件，这个文件的内容是用户所有文件这个文件的内容是用户所有文件FCBFCB的的集合，集合，MFDMFD中则包含每个中则包含每个UFDUFD文件的文件的FCBFCB，见下图示）。见下图示）。 CAT BO A TEST X TEST DATA A A A DATA User1 User2 User4 User3 主文件目录 用户文件目录 文件 二级目录结

16、构示意图二级目录结构示意图二级目录结构实现二级目录结构实现(1)(1)可以把主目录和二级用户目录放可以把主目录和二级用户目录放于外存头部，也可以把二级目录当于外存头部，也可以把二级目录当一般文件存放。一般文件存放。(2) (2) 将用户名与文件名连到一起组将用户名与文件名连到一起组成路经名成路经名, ,访问时给出路径名。访问时给出路径名。例如：例如：/OS/test.c/OS/test.c。3.3.多级目录结构（树形目录结构）多级目录结构（树形目录结构）任何一级目录中的任何一级目录中的FCBFCB既可以描既可以描述次一级的子目录，又可以描述述次一级的子目录，又可以描述一个文件。一个文件。( (

17、见下图见下图) ) root programs mail e p hex count recorder list find prt last fist copy all list obj spell prog mail start dict spell bin find count hex recorder addr 树型目录结构示意图树型目录结构示意图树型目录结构的特点：树型目录结构的特点：v利于文件分类，从文件路径名可看出利于文件分类，从文件路径名可看出文件类别；文件类别；v查找文件查找文件FCBFCB耗费时间，要得到文件耗费时间，要得到文件FCBFCB，必须从根查起；，必须从根查起；v惟

18、一确定文件的路径名太长，故引入惟一确定文件的路径名太长，故引入当前目录当前目录 概念，提供相对于当前目录概念，提供相对于当前目录的的相对路径名相对路径名可加速文件可加速文件FCBFCB的查找，的查找，进程控制块存有当前目录信息。进程控制块存有当前目录信息。4.4.无环图目录结构无环图目录结构当一个文件副本可以同时分到两个不当一个文件副本可以同时分到两个不同目录（类别）时，即同一个文件有同目录（类别）时，即同一个文件有两条路径名或多条路径名时出现无环两条路径名或多条路径名时出现无环图目录结构。图目录结构。( (见下图见下图) ) root dict spell list root rade W7

19、 list count p 无环图目录结构示意图无环图目录结构示意图图中目录图中目录dictdict与与 spellspell共享文件共享文件count,count,共享子目录共享子目录p.p.图中目录图中目录dictdict与其子与其子目录目录p p共享文件共享文件root.root.无环图目录结构的特点：无环图目录结构的特点：vUnixUnix的文件系统采用这种结构的文件系统采用这种结构v优点优点: :方便文件共享，分类；方便文件共享，分类；v缺点缺点: :两个或多个两个或多个FCBFCB的一致性难以保的一致性难以保证（如删除文件时，当文件修改而引证（如删除文件时，当文件修改而引起起FCB

20、FCB内容变化时）。内容变化时）。 5. 5.无环图目录结构无环图目录结构一种变通的实现方一种变通的实现方法法 符号链接符号链接建立多个符号链文件，该文件内容为建立多个符号链文件，该文件内容为要访问文件的路径名。要访问文件的路径名。当访问符号链文件时，读出文件中的当访问符号链文件时，读出文件中的路径名，再重新从根查找路径名代表路径名，再重新从根查找路径名代表的文件的文件FCB。无环图目录结构dictcountcountrootspellroot/dict/countcountlistroot/dict/countcountroot/dict/countcountroot/dict/countc

21、ount目录目录dictdict与与spellspell目录共享目录目录共享目录count,count,只在只在spellspell目录中指明目录中指明countcount的路径的路径7.4 7.4 文件和目录的操作文件和目录的操作 （略）（略）7.5 7.5 文件系统的实现文件系统的实现 7.5.1.7.5.1.文件系统的格式文件系统的格式（略）（略） 7.5.2 7.5.2 文件存储分配文件存储分配目前常用的文件分配方法有：连续分配、目前常用的文件分配方法有：连续分配、链接分配和索引分配三种。链接分配和索引分配三种。 1.1.连续分配连续分配-把一组连续的盘块分把一组连续的盘块分配给一个文

22、件。配给一个文件。采用连续分配方法可把逻辑文件中的采用连续分配方法可把逻辑文件中的信息顺序地存放到一组相邻的物理盘信息顺序地存放到一组相邻的物理盘块中，这样形成的物理文件称为连续块中，这样形成的物理文件称为连续文件（或顺序文件）。文件（或顺序文件）。连续分配举例连续分配举例 存存储储器器0123456789101112 1314151617 1819202122 2324文件分配表文件分配表 连续文件的优缺点连续文件的优缺点v优点：顺序访问容易、速度快。优点：顺序访问容易、速度快。v缺点：缺点：要求有连续的存储空间。要求有连续的存储空间。必须事先知道文件的长度。必须事先知道文件的长度。2.2.

23、链接分配链接分配-把逻辑上连续的把逻辑上连续的文件文件不连续地存放于不同的盘块上，并使不连续地存放于不同的盘块上，并使用指针按文件数据顺序将其链接起来。用指针按文件数据顺序将其链接起来。按链接分配方法形成的文件称链接文按链接分配方法形成的文件称链接文件或串连文件。件或串连文件。文件链式结构例文件链式结构例11282316R0R0R1R1R2R2R3R3R4R4逻辑文件逻辑文件ABCABC文件分配表文件分配表链接文件的优点链接文件的优点可以充分利用磁盘中零散的空闲块，可以充分利用磁盘中零散的空闲块，提高外存空间的利用率。提高外存空间的利用率。消除外部碎片。消除外部碎片。但访问或查找只能顺着指针链

24、进行但访问或查找只能顺着指针链进行, ,速度较慢速度较慢, ,当需要的磁盘块较多时当需要的磁盘块较多时, ,链条很长链条很长. .3.3.索引分配索引分配-为每个文件分配一个为每个文件分配一个索引表，把分配给该文件的所有盘块索引表，把分配给该文件的所有盘块号都记录在该索引表中，索引表本身号都记录在该索引表中，索引表本身也存放在一个盘块中。也存放在一个盘块中。按这种分配方式存储的文件就是索引按这种分配方式存储的文件就是索引文件。文件。 文件索引结构存存储储器器FCB索引表索引表12043112823161128231619索引文件优点索引文件优点 主要是提高了文件的查找速度，主要是提高了文件的查

25、找速度，也不会产生外部碎片，当文件较也不会产生外部碎片，当文件较大时，索引分配方式优于链接分大时，索引分配方式优于链接分配方式。配方式。 4 4、多重索引分配：如果索引表过大，、多重索引分配：如果索引表过大，可以组织成如下的多级索引表，这样单可以组织成如下的多级索引表，这样单个索引表可以定长，利于实现，下面是个索引表可以定长，利于实现，下面是多级索引表示意图多级索引表示意图二级索引表二级索引表一级索引表一级索引表数据块数据块多重索引多重索引分配例：分配例：UNIXUNIX的文的文件系统采件系统采用多重索用多重索引分配方引分配方式。式。UnixUnix系统多重索引分配例系统多重索引分配例：设盘块

26、大小为：设盘块大小为1KB1KB，盘块号用盘块号用4 4个字节表示。个字节表示。对于一般文件来说，其大小多数在对于一般文件来说，其大小多数在10KB10KB以内，可以利用直接项立即得到存放数据的以内，可以利用直接项立即得到存放数据的盘块号，因而存取速度较快。直接项能够存盘块号，因而存取速度较快。直接项能够存放的最大文件长度为放的最大文件长度为10KB10KB。对于大于对于大于10KB10KB的中小型文件，可对的中小型文件，可对1010块块以上的部分采用一次间接（它至多可以放以上的部分采用一次间接（它至多可以放1KB1KB4=1024B4=1024B4=2564=256个盘块），一次间接允个盘块

27、），一次间接允许文件长达许文件长达2562561KB=256KBKB=256KB。对于大于对于大于266KB266KB（10KB+256KB10KB+256KB）的中大）的中大型文件，超过型文件，超过266KB266KB的部分，则接着采用二次的部分，则接着采用二次间接（它至多可以放间接（它至多可以放256256256256个盘块号），个盘块号），二次间接允许文件长达二次间接允许文件长达2562562562561KB=64MB1KB=64MB。对于大于对于大于10KB+256KB+64MB10KB+256KB+64MB的巨型文件，的巨型文件，则接着采用三次间接（它最多可以放则接着采用三次间接（它

28、最多可以放256256256256256256个盘块号），三次间接允许的个盘块号），三次间接允许的文件长达文件长达2562562562562562561KB=16GB1KB=16GB。小结：小结：UNIXUNIX采用这种多重索引分配方式，采用这种多重索引分配方式，一个文件的最大容量是：一个文件的最大容量是：10KB+256KB+64MB+16GB10KB+256KB+64MB+16GB11亿字节亿字节。例：在例：在UnixUnix系统中，假定磁盘块大小是系统中，假定磁盘块大小是1KB1KB，每，每个盘块号占个盘块号占4B4B，文件索引节点中的磁盘地址明，文件索引节点中的磁盘地址明细表如下图所示

29、，请将下列文件的字节偏移量细表如下图所示，请将下列文件的字节偏移量转换为物理地址（写出计算过程）。转换为物理地址（写出计算过程）。（1 1）80008000（2 2）1300013000（3 3）350000350000409622845428931111150101367174289156824直直接接地地址址一次间接一次间接二次间接二次间接三次间接三次间接1091011954952428#9156#3314523300333308331#01747576012345678910111201220052554095255v 解：（解：（1）8000/1024=7（表示整除），（表示整除），8

30、000%1024=832（表示取模）（表示取模） 使用直接地址，其物理地址是：使用直接地址，其物理地址是：101#块内的块内的832号地址。号地址。v（2）13 000/1024=12，13 000%1024=712 逻辑块数逻辑块数12超出直接地址范围（超出直接地址范围（10），但是小），但是小于于266 (=10+256),利用一次间接。从利用一次间接。从428#块中块中得到相应的物理块号为得到相应的物理块号为954。所以，其物理地。所以，其物理地址是：址是：954#块内的块内的712号地址。号地址。v （3）解：）解：v350 000/1024=341，350 000%1 024=816

31、 逻辑块数逻辑块数341超出一次间接地址范围超出一次间接地址范围(266)，但，但是小于是小于65 802(=10+256+65536），利用二次），利用二次间接。间接。341-（10+256）=75，75/256=0，75%256=75。v从从9156#块中找到第块中找到第0项对应的物理块项对应的物理块331，再，再从从331块中找到下标为块中找到下标为75的项，进而得到物理的项，进而得到物理块号块号333。所以，其物理地址是：。所以，其物理地址是：333#块内的块内的816号地址。号地址。7.5.3 空闲存储空间的管理目前常用的磁盘空闲空间管理技术主要目前常用的磁盘空闲空间管理技术主要有：

32、有：1.1.空闲空间表法空闲空间表法2.2.空闲块链接法空闲块链接法3.3.位示图法位示图法4.4.成组链接法。成组链接法。1.1.空闲空间表法空闲空间表法(1)(1)空闲空间表。为了记载磁盘上哪些盘块空闲空间表。为了记载磁盘上哪些盘块是空闲的，文件系统需要创建空闲空间表。是空闲的，文件系统需要创建空闲空间表。如图：如图：(2)(2)空闲块分配。空闲块分配。在新建文件时，要为它分配盘空间。在新建文件时，要为它分配盘空间。为此系统检索空闲空间表，按一定算为此系统检索空闲空间表，按一定算法找到合适文件大小的表项分配出去，法找到合适文件大小的表项分配出去，并在文件分配表中登记。如果对应空并在文件分配

33、表中登记。如果对应空闲区的大小恰好是所申请的，就把该闲区的大小恰好是所申请的，就把该从表中删除；如果该区大于所需数量，从表中删除；如果该区大于所需数量，则把分配后剩余的部分记在表项中。则把分配后剩余的部分记在表项中。空闲块分配例如：空闲块分配例如：空闲空间表前述图。新建文件空闲空间表前述图。新建文件ABCABC，大小为，大小为3KB3KB时，系统在空闲空间表中找到第时，系统在空闲空间表中找到第1 1项的空间能项的空间能满足，故将序号满足，故将序号1 1的空闲空间分配出去的空闲空间分配出去3 3块，余块，余下的下的1 1块继续留在空闲空间表并修改数据，并块继续留在空闲空间表并修改数据，并将分配出

34、去的盘块登记在文件分配表中。设分将分配出去的盘块登记在文件分配表中。设分配前文件分配表如下表：配前文件分配表如下表：分配前的文件分配表分配前的文件分配表修改空闲空间表：修改空闲空间表：修改文件分配表修改文件分配表 (3)(3)空闲块回收空闲块回收在删除文件时，系统回收该文件占用的盘块，在删除文件时，系统回收该文件占用的盘块，且把相应的空闲块信息填回空闲空间表中。如且把相应的空闲块信息填回空闲空间表中。如果释放的盘区和原有的空闲区相邻接，则合并果释放的盘区和原有的空闲区相邻接，则合并成一个大的空闲区，记在一个表项中。成一个大的空闲区，记在一个表项中。如图：若删除文件如图：若删除文件C C，则要在

35、此文件分配表中删，则要在此文件分配表中删除文件除文件C C的目录项。的目录项。并修改空闲空间表。并修改空闲空间表。由于文件由于文件C C的盘块与表的盘块与表中的序号中的序号2 2相邻接，故相邻接，故合并成一个大空闲区。合并成一个大空闲区。修改空闲空间表：修改空闲空间表：修改文件分配表修改文件分配表 2.2.空闲块链接法空闲块链接法 这种方法与串这种方法与串连文件结构相似，连文件结构相似，只是链接的是空只是链接的是空闲块而已。闲块而已。 分配与回收。分配与回收。（略）（略）3.3.位示图法位示图法 它利用一串二进位值反映磁盘空间的分配它利用一串二进位值反映磁盘空间的分配情况，也称位向量法。每个盘

36、块都对应一个情况，也称位向量法。每个盘块都对应一个二进制位。如果盘块是空闲的，对应位是二进制位。如果盘块是空闲的，对应位是1 1；如果已经分出去，则对应位是如果已经分出去，则对应位是0 0。例如：设下列盘块是空闲的：例如：设下列盘块是空闲的：2,3,4,5,8,9,10,11,12,13,17,18,25,26,22,3,4,5,8,9,10,11,12,13,17,18,25,26,27 7, ,则位示图向量是：则位示图向量是：00111100111111000110000001110011110011111100011000000111如何构造位示图？如何构造位示图？ 根据一个磁盘的总盘块

37、数决定位示图由多少根据一个磁盘的总盘块数决定位示图由多少字组成。字组成。例：假定有一个盘组共有例：假定有一个盘组共有100100个柱面（编号为个柱面（编号为0-0-9999），每个柱面有），每个柱面有8 8个磁道（编号为个磁道（编号为0-70-7），每个），每个盘面分为盘面分为4 4个扇区（编号为个扇区（编号为0-30-3）。那么，整个磁）。那么，整个磁盘空间共有盘空间共有4 48 8100=3200100=3200个磁盘块可用来存储个磁盘块可用来存储信息。如果用字长信息。如果用字长3232位的字来构造位示图，共需位的字来构造位示图，共需100100个字。如下图示：个字。如下图示：位示图如下位

38、示图如下: : 如果磁盘块的块号按柱面顺序来编号如果磁盘块的块号按柱面顺序来编号, ,则第则第0 0柱面柱面第第0 0盘面上的块号是盘面上的块号是0,1,2,3,0,1,2,3,第第0 0柱面第柱面第1 1盘面上的盘面上的块号是块号是4,5,6,7,4,5,6,7,依次计算依次计算, ,第第0 0柱面上共有柱面上共有3232块块, ,编编号为号为031,031,第第1 1柱面的块号就为柱面的块号就为32633263于是于是, ,位位示图中第示图中第i i个字的第个字的第j j位对应的块号为位对应的块号为: :块号块号=i=i32+j 块空间分配过程。块空间分配过程。（1 1）当有文件要存放到磁

39、盘上时）当有文件要存放到磁盘上时, ,查找位示图中查找位示图中为为“0”0”的位的位, ,表示对应的磁盘块空闲可供使用。表示对应的磁盘块空闲可供使用。根据查到的位号和字号就可计算出块号，同时在根据查到的位号和字号就可计算出块号，同时在该位上填上占用标志该位上填上占用标志“1”1”。（2 2）磁盘定位。根据块号计算出本块所在的柱）磁盘定位。根据块号计算出本块所在的柱面号，盘面号（磁头号）和扇区号。面号，盘面号（磁头号）和扇区号。柱面号柱面号=块号块号/32/32磁头号磁头号=（块号（块号 MOD 32MOD 32）/4/4扇区号扇区号= =（块号（块号 MOD 32MOD 32）MOD 4MOD

40、 4块空间回收（删除）过程。块空间回收（删除）过程。（1 1）当删除文件归还存储空间时，可以根据归）当删除文件归还存储空间时，可以根据归还的位置推算出块号和在位示图中的位置：还的位置推算出块号和在位示图中的位置：块号块号= =柱面号柱面号32+32+磁头号磁头号4+扇区号扇区号字号字号=块号块号/32/32位号位号= =块号块号 MOD 32MOD 32（2 2）把位示图中对应的位号、字号所在位的占）把位示图中对应的位号、字号所在位的占用标志改为用标志改为“0”0”。例例1有一计算机系统采用如下表所示的位示图（字号、有一计算机系统采用如下表所示的位示图（字号、位号都从位号都从0开始编号）来管理

41、空闲盘块。如果盘块从开始编号）来管理空闲盘块。如果盘块从0开开始编号，每个盘块的大小为始编号，每个盘块的大小为1KB。（1）现要为文件分配两个盘块，试具体说明分配过程。）现要为文件分配两个盘块，试具体说明分配过程。（2）若要释放磁盘的第）若要释放磁盘的第300块，应如何处理？块，应如何处理？【解解】 （1）为某文件分配两个盘块的过程如下：）为某文件分配两个盘块的过程如下：顺序检索位示图，从中找到第一个值为顺序检索位示图，从中找到第一个值为0的二进制的二进制位，得到其字号位，得到其字号i1=1，位号，位号j1=5;第二个值为第二个值为0的二的二进制位，得到其字号进制位，得到其字号i2=1,位号位

42、号j2=10。计算出找到的两个空闲块的盘块号分别为：计算出找到的两个空闲块的盘块号分别为： b1i116j1=116521 b2i216j211610=26修改位示图，令修改位示图，令Map1,5=Map1,10=1，并，并将对应块将对应块21, 26分配出去。分配出去。（2）释放磁盘的第）释放磁盘的第300块时，应进行如下处理：块时，应进行如下处理： 计算出磁盘第计算出磁盘第300块所对应二进制位的字号块所对应二进制位的字号i和位和位号号j：i=300/1618，j=300 Mod 1612 修改位示图，令修改位示图，令Map18,12=0,表示对应块为空表示对应块为空闲块。闲块。4.4.空

43、闲块成组链接法。空闲块成组链接法。（1 1）空闲块成组链接）空闲块成组链接 此法是把所有空闲盘块按固定数量分组，例如每此法是把所有空闲盘块按固定数量分组，例如每50个空闲块为一组，组中的第个空闲块为一组，组中的第1块为块为“组长组长”块。块。第第1组的组的50个空闲块块号放在第个空闲块块号放在第2组的组长块中，而组的组长块中，而第第2组的其余组的其余49块是完全空闲的。第块是完全空闲的。第2组的组的50个块号个块号又放在第三组的组长块中。依此类推，组与组之间又放在第三组的组长块中。依此类推，组与组之间形成链接关系。最后一组的块号（可能不足形成链接关系。最后一组的块号（可能不足50块）块）通常放在内存的一个专用栈（即文件系统超级块中通常放在内存的一个专用栈（即文件系统超级块中的空闲块号栈）结构中。这样，平常对盘块的分配的空闲块号栈）结构中。这样，平常对盘块的分配和释放在栈中（或构成新的一组）进行，如下图。和释放在栈中（或构成新的一组）进行，如下图。UNIX系统中就采用这种方法。系统中就采用这种方法。（2）空闲块分配）空闲块分配 当需要为新建文件分配空闲盘块时，总当需要为新建文件分配空闲盘块时，总是先把超级块中表