计算机操作系统第10章 文件管理1

1、第第1010章章 文件系统文件系统n文件系统负责管理外存上的文件，并为用户提供对文件进行文件系统负责管理外存上的文件，并为用户提供对文件进行存取、共享及保护手段。存取、共享及保护手段。1010。1 1 概述概述1010。1 1。1 1 文件和文件系统文件和文件系统n文件（文件（filesfiles）是有名字的、存储在某种介质上的一组有意）是有名字的、存储在某种介质上的一组有意义的信息。名字、信息和介质是文件三个不可缺少的基本要义的信息。名字、信息和介质是文件三个不可缺少的基本要素；素；n作为一种数据结构，文件可划分为记录，记录又可划分为数作为一种数据结构，文件可划分为记录，记录又可划分为数据项

2、，数据项是可以命名和存取的最小逻辑单位；据项，数据项是可以命名和存取的最小逻辑单位；n文件可以有各种不同的分类方法，见文件可以有各种不同的分类方法，见P P214-215214-215。1010。1 1。2 2 文件系统文件系统n文件系统（文件系统（FSFS：File SystemFile System）这个词，在不同的）这个词，在不同的上下文可以有不同的含义（上下文可以有不同的含义（），这里我们把它理），这里我们把它理解为操作系统中与管理文件有关的软件和数据的集解为操作系统中与管理文件有关的软件和数据的集合；合；n文件系统的功能是：文件系统的功能是： 1 1，实现文件的按名存取；，实现文件的

3、按名存取； 2 2，为用户提供接口；，为用户提供接口； 3 3，实施对文件和目录的管理；，实施对文件和目录的管理； 4 4，文件存储空间的分配及回收；，文件存储空间的分配及回收； 4 4，文件的共享及保护；，文件的共享及保护；文件系统的软件体系结构文件系统的软件体系结构n文件系统的软件体系结构从下往上共有五层：文件系统的软件体系结构从下往上共有五层：n基本基本I/OI/O控制层；控制层；n基本文件系统层；基本文件系统层；n基本基本I/OI/O管理程序层；管理程序层；n逻辑文件系统层；逻辑文件系统层；n文件系统接口；文件系统接口；n不同的系统层次的划分可能不一样，上面只是其中不同的系统层次的划分

4、可能不一样，上面只是其中一种划分方法；一种划分方法；n每个层次的功能见每个层次的功能见P P214214的说明。的说明。文件系统的软件体系结构图文件系统的软件体系结构图n层次的上下级关系是按调用原则确定的。层次的上下级关系是按调用原则确定的。文件系统接口逻辑文件系统层基本I/O管理程序层基本文件系统层基本I/O控制层用户存取要求物理磁盘10.2 10.2 文件结构及存储设备文件结构及存储设备n文件结构指文件的组织形式，文件有两种形文件结构指文件的组织形式，文件有两种形式的结构：式的结构：n逻辑结构：逻辑结构：又称文件组织，是从用户观点出发所又称文件组织，是从用户观点出发所看到的文件组织形式；看

5、到的文件组织形式；n物理结构：物理结构：又称文件的存储结构，是文件在外存又称文件的存储结构，是文件在外存上的存储形式。它与存储设备特性、外存分配方上的存储形式。它与存储设备特性、外存分配方式有关；式有关；1010。2 2。1 1 文件的逻辑结构文件的逻辑结构n文件的逻辑结构可分为两类：文件的逻辑结构可分为两类：n记录式文件：是一种有结构文件，由一组相关记录式文件：是一种有结构文件，由一组相关记录组成。又分为：记录组成。又分为：n等长记录文件：又称定长记录文件，是指文件中所等长记录文件：又称定长记录文件，是指文件中所有记录的长度相等；有记录的长度相等；n变长记录文件：是指文件中各记录长度不相等；

6、变长记录文件：是指文件中各记录长度不相等；n流式文件：是一种无结构文件，由字符序列构流式文件：是一种无结构文件，由字符序列构成。流式文件可看做是以一个字符为一个记录成。流式文件可看做是以一个字符为一个记录的文件；的文件；n一个系统的文件是流式的还是记录式的要从系一个系统的文件是流式的还是记录式的要从系统调用指令的参数来判断；统调用指令的参数来判断；9 9。2 2。2 2 文件的物理结构文件的物理结构n文件的物理结构指的是一个文件在外存上的存储组文件的物理结构指的是一个文件在外存上的存储组织形式，它与存储介质的存储特性有关；织形式，它与存储介质的存储特性有关；n文件存储设备通常是块设备，物理块是

7、分配及传输文件存储设备通常是块设备，物理块是分配及传输文件信息的基本单位。物理块的大小与设备有关，文件信息的基本单位。物理块的大小与设备有关，但与逻辑记录的大小无关，因此一个物理块中可以但与逻辑记录的大小无关，因此一个物理块中可以存放若干个逻辑记录，一个逻辑记录也可以存放在存放若干个逻辑记录，一个逻辑记录也可以存放在若干个物理块中；若干个物理块中；n常见的文件物理结构有以下几种形式：常见的文件物理结构有以下几种形式：n顺序结构；顺序结构；n链接结构；链接结构；n索引结构；索引结构；顺序结构顺序结构n顺序结构又称连续结构，它将一个在逻辑上顺序结构又称连续结构，它将一个在逻辑上连续的信息存放在外存

8、连续的物理块中；连续的信息存放在外存连续的物理块中；n以顺序结构存放的文件称为顺序文件或连续以顺序结构存放的文件称为顺序文件或连续文件；文件；n特点：特点：顺序存取速度较快；对等长记录文件顺序存取速度较快；对等长记录文件支持随机访问。但因要求连续存放，会产生支持随机访问。但因要求连续存放，会产生碎片，同时也不利于文件的动态扩充。碎片，同时也不利于文件的动态扩充。链接结构链接结构n链接结构又称串联结构，它将一个逻辑文件链接结构又称串联结构，它将一个逻辑文件的信息存放在外存不连续物理块中，且在每的信息存放在外存不连续物理块中，且在每个物理块中设置一个指向下一个物理块的指个物理块中设置一个指向下一个

9、物理块的指针；针；n采用链接结构存放的文件称为链接文件或串采用链接结构存放的文件称为链接文件或串联文件；联文件；n特点：特点：可解决碎片问题，便于文件动态增长。可解决碎片问题，便于文件动态增长。但只能顺序访问，因而查找效率较低，指针但只能顺序访问，因而查找效率较低，指针占用存储空间。占用存储空间。索引结构索引结构n索引结构将一个逻辑文件的信息存放于外存索引结构将一个逻辑文件的信息存放于外存的若干个物理块中，并为每个文件建立一个的若干个物理块中，并为每个文件建立一个索引表，其中的每个表目存放文件信息所在索引表，其中的每个表目存放文件信息所在的逻辑块号和与之对应的物理块号；的逻辑块号和与之对应的物

10、理块号；n采用索引结构存放的文件称为索引文件；采用索引结构存放的文件称为索引文件；n特点：特点：既可以顺序访问也可以随机访问，但既可以顺序访问也可以随机访问，但增加了存储空间开销，且要两次访问外存。增加了存储空间开销，且要两次访问外存。1010。2 2。3 3 文件的存取方法文件的存取方法n常用的文件存取方法有：常用的文件存取方法有：n顺序存取法；顺序存取法；n直接存取法；直接存取法；n按键存取法；按键存取法；顺序存取法顺序存取法n顺序存取法是按照文件信息的逻辑顺序依次存取；顺序存取法是按照文件信息的逻辑顺序依次存取；n在记录式文件中，顺序存取反映为按记录的排列顺在记录式文件中，顺序存取反映为

11、按记录的排列顺序来存取；在流式文件中，顺序存取反映为当前读序来存取；在流式文件中，顺序存取反映为当前读写指针的变化方式；写指针的变化方式；n对定长记录的顺序文件，若知道当前记录地址，则对定长记录的顺序文件，若知道当前记录地址，则很易确定下一个记录地址：很易确定下一个记录地址：n rptrrptrrptrrptrL Ln其中其中L L为文件记录的长度，为文件记录的长度，rptrrptr为读写指针。为读写指针。直接存取法直接存取法n直接存取法又称随机存取法，允许按任意顺序存直接存取法又称随机存取法，允许按任意顺序存取文件中的任何一个物理记录；取文件中的任何一个物理记录；n对于定长记录的顺序文件，若

12、知道文件的起始地对于定长记录的顺序文件，若知道文件的起始地址和记录长度，则第址和记录长度，则第i i个记录（个记录（i i0 0，1 1，2 2，）的首地址为：的首地址为：n rptrrptraddraddri iL Ln其中其中addraddr是该文件的首地址，是该文件的首地址，L L为记录长度。为记录长度。按键存取法按键存取法n按键存取法实质上也是直接存取法，它是按键存取法实质上也是直接存取法，它是根据文件记录中的数据项，通常称为关键根据文件记录中的数据项，通常称为关键字，经过某种方法计算处理，转换成相应字，经过某种方法计算处理，转换成相应的物理地址后进行存取。这种方法有时也的物理地址后进

13、行存取。这种方法有时也叫散列存取法，或者相联存取法。叫散列存取法，或者相联存取法。1010。2 2。4 4 文件存储设备文件存储设备n文件的存储设备主要有磁带、磁盘、光文件的存储设备主要有磁带、磁盘、光盘等；盘等；n存储设备的特性可以决定文件的存取方存储设备的特性可以决定文件的存取方法；法；n下面介绍以磁带为代表的顺序存取设备下面介绍以磁带为代表的顺序存取设备和以磁盘为代表的直接存取设备。和以磁盘为代表的直接存取设备。磁带磁带n磁带是一种典型的顺序存取设备。由于磁磁带是一种典型的顺序存取设备。由于磁带机的启动和停止要花费一定的时间，因带机的启动和停止要花费一定的时间，因此在磁带的相邻物理块之间

14、设计有一段间此在磁带的相邻物理块之间设计有一段间隙将它们隔开，如下所示。隙将它们隔开，如下所示。磁带 间隙 第i块 间隙 第i1块 间隙 磁带（续）磁带（续）n磁带的存取速度与信息密度（字符数磁带的存取速度与信息密度（字符数/ /英寸）、磁带带速（英寸英寸）、磁带带速（英寸/ /秒）和块间秒）和块间间隙有关；间隙有关；n如果带速高、信息密度大且所需块间隙如果带速高、信息密度大且所需块间隙（磁头启动和停止时间）小，则磁带存（磁头启动和停止时间）小，则磁带存取速度高。反之，若磁带带速低、信息取速度高。反之，若磁带带速低、信息密度小且所需块间隙（磁带启动和停止密度小且所需块间隙（磁带启动和停止时间）

15、大，则磁带存取速度低。时间）大，则磁带存取速度低。磁盘磁盘n磁盘是典型的直接存取设备；磁盘是典型的直接存取设备；n磁盘一般由若干磁盘片组成，可沿一个方向磁盘一般由若干磁盘片组成，可沿一个方向同轴高速旋转。每个盘面对应一个磁头，磁同轴高速旋转。每个盘面对应一个磁头，磁臂可沿半径方向移动；臂可沿半径方向移动；n磁盘上的一系列同心圆称为磁道，磁道沿径磁盘上的一系列同心圆称为磁道，磁道沿径向又分成大小相等的多个扇区，不同盘片半向又分成大小相等的多个扇区，不同盘片半径相同的所有磁道组成一个柱面；径相同的所有磁道组成一个柱面；n磁盘上的每个物理块可用柱面号，磁头号和磁盘上的每个物理块可用柱面号，磁头号和扇

16、区号表示。扇区号表示。磁盘数据组织和格式示意图磁盘数据组织和格式示意图磁臂磁头43 01234567磁道 第i扇区 间隙 标识字段 间隙 数据字段 间隙 磁盘访问时间磁盘访问时间n磁盘访问时间由三部分组成：磁盘访问时间由三部分组成：n寻道时间：寻道时间：指将磁头从当前位置移动到指定磁道所经历指将磁头从当前位置移动到指定磁道所经历的时间。由启动磁臂时间和磁头移动多条磁道的时间构的时间。由启动磁臂时间和磁头移动多条磁道的时间构成；成；n旋转延迟时间：旋转延迟时间：指扇区移动到磁头下面所经历的时间。指扇区移动到磁头下面所经历的时间。平均旋转延迟时间是每转所需时间的一半；平均旋转延迟时间是每转所需时间

17、的一半；n传输时间：传输时间：指从磁盘上读出数据或向磁盘写入数据所经指从磁盘上读出数据或向磁盘写入数据所经历的时间；历的时间；n由于这三部分操作均涉及机械运动，故磁盘块的访由于这三部分操作均涉及机械运动，故磁盘块的访问时间约为问时间约为0.010.010.10.1s s之间，其中寻道时间所占的之间，其中寻道时间所占的比例最大。比例最大。存储设备、存取方法与物理结构间的关系存储设备、存取方法与物理结构间的关系 n文件的物理结构与文件存储器的特性和存取方法密切相关；文件的物理结构与文件存储器的特性和存取方法密切相关；n磁带是一种顺序存取设备，适合采用顺序结构存放文件，磁带是一种顺序存取设备，适合采

18、用顺序结构存放文件，相应的存取方法通常是顺序存取法；相应的存取方法通常是顺序存取法；n磁盘属于直接存取存储设备，前述的几种物理结构都可以磁盘属于直接存取存储设备，前述的几种物理结构都可以采用。存取方法也可以多种多样。采用。存取方法也可以多种多样。存储设备磁 盘磁 带物理结构顺序结构链接结构索引结构顺序结构存取方法顺序、直接顺序顺序、直接顺序磁盘调度算法磁盘调度算法n磁盘是可以被多个进程磁盘是可以被多个进程“同时同时”使用的设备。当有多个进使用的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法确定它程都请求访问磁盘时，应采用一种适当的调度算法确定它们的执行顺序，以使各进程对磁盘的平均

19、访问时间（主要们的执行顺序，以使各进程对磁盘的平均访问时间（主要是寻道时间）最短。这些调度算法有：是寻道时间）最短。这些调度算法有： 1 1，先来先服务，先来先服务FCFSFCFS； 2 2，最短寻道时间优先，最短寻道时间优先SSTFSSTF； 3 3，扫描法，扫描法SCANSCAN； 4 4，循环扫描法，循环扫描法CSCANCSCAN； 下面逐一介绍。设从下面逐一介绍。设从100100号磁道开始，磁盘访问请求的执号磁道开始，磁盘访问请求的执行顺序为：行顺序为：5555、5858、3939、1818、9090、160160、150150、3838、184184；先来先服务算法先来先服务算法n先

20、来先服务算法按先来先服务算法按进程请求访问磁盘进程请求访问磁盘的先后次序进行调的先后次序进行调度。特点是简单易度。特点是简单易行，但未对寻道进行，但未对寻道进行优化。行优化。n平均寻道长度为：平均寻道长度为：55.355.314618410150112387016072902118193935845移动距离55下一磁道号最短寻道时间优先算法最短寻道时间优先算法n最短寻道时间优先算最短寻道时间优先算法选择与当前磁头所法选择与当前磁头所在磁道距离最近的请在磁道距离最近的请求作为下一次服务的求作为下一次服务的对象；对象；n特点：寻道性能比特点：寻道性能比FCFSFCFS好，但可能会使好，但可能会使某

21、些请求总也得不到某些请求总也得不到服务；服务；n平均寻道长度为：平均寻道长度为：27.627.6241841321501016020181381639355325810移动距离90下一磁道号扫描法扫描法-SCANSCANnSCANSCAN算法在磁头当前移算法在磁头当前移动方向上选择与当前磁动方向上选择与当前磁头所在磁道距离最近的头所在磁道距离最近的请求作为下一次服务的请求作为下一次服务的对象。因这种算法中磁对象。因这种算法中磁头移动规律颇似电梯的头移动规律颇似电梯的运行，故又称为电梯调运行，故又称为电梯调度算法；度算法；n特点：具有较好的寻道特点：具有较好的寻道性能，能避免进程饥饿，性能，能避

22、免进程饥饿，但不利于两端磁道的请但不利于两端磁道的请求；求； n平均寻道长度为：平均寻道长度为：27.827.82018163913835532589490241841016050移动距离150下一磁道号循环扫描算法循环扫描算法CSCANCSCANnCSCANCSCAN算法是算法是SCANSCAN算算法的改良，它规定磁法的改良，它规定磁头单向服务。例如，头单向服务。例如，自里向外移动时服务，自里向外移动时服务，自外向里时空跑，如自外向里时空跑，如此循环进行扫描；此循环进行扫描；n特点：该算法消除了特点：该算法消除了对两端磁道请求的不对两端磁道请求的不公平；公平；n平均寻道长度为：平均寻道长度为

23、：35.835.832901655358139203816618241841016050移动距离150下一磁道号10.3 10.3 文件存储空间的分配与管理文件存储空间的分配与管理1010。3 3。1 1 文件存储空间的分配文件存储空间的分配n文件存储空间的分配常采用以下两种策略：文件存储空间的分配常采用以下两种策略：n静态分配：静态分配：在文件建立时一次分配所需的全部空间；在文件建立时一次分配所需的全部空间；n动态分配：动态分配：在运行中根据需要进行分配和回收；在运行中根据需要进行分配和回收；n文件存储空间的分配通常以块或簇为单位，一个簇文件存储空间的分配通常以块或簇为单位，一个簇是几个连续

24、的物理块；是几个连续的物理块；n常用的文件存储空间分配方式有：常用的文件存储空间分配方式有：n连续分配；连续分配；n链接分配；链接分配；n索引分配；索引分配；连续分配示意图连续分配示意图n为文件分配连续的为文件分配连续的磁盘空间；磁盘空间；n用户必须在分配前用户必须在分配前说明待创建文件所说明待创建文件所需的存储空间大小。需的存储空间大小。然后系统查找空闲然后系统查找空闲区管理表，若有就区管理表，若有就给文件分配所需的给文件分配所需的存储空间，否则文存储空间，否则文件不能建立。件不能建立。 0 1 2 3 4 5 6 7 8 9101112131415161718192021222324252

25、62728293031323334文件文件A目录目录文件名文件名 起始块号起始块号 长度长度 A 2 3 B 9 5 C 18 8文件文件B文件文件C链接分配链接分配n链接分配有两种实现方案：链接分配有两种实现方案：n以扇区为单位的链接分配；以扇区为单位的链接分配；n以区段（簇）为单位的链接分配；以区段（簇）为单位的链接分配；n以扇区为单位的链接分配：以扇区为单位的链接分配：n按文件的要求分配若干个磁盘扇区，属于同一文件的各按文件的要求分配若干个磁盘扇区，属于同一文件的各扇区按文件记录的逻辑次序用链接指针链接起来；扇区按文件记录的逻辑次序用链接指针链接起来；n当文件增长时就为文件分配新的空闲扇

26、区，并将其链接当文件增长时就为文件分配新的空闲扇区，并将其链接到文件链上；同样当文件缩短时将释放的扇区归还给系到文件链上；同样当文件缩短时将释放的扇区归还给系统；统；n特点：消除了碎片，不需要压缩。但查找慢，链接指针特点：消除了碎片，不需要压缩。但查找慢，链接指针的存储及维护有一些开销；的存储及维护有一些开销；链接分配示意图链接分配示意图 0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334文件文件B目录目录文件名文件名 起始块号起始块号 长度长度 B 1 5 以区段（或簇）为单位分配以区段（或簇）为单位分配

27、n以区段（或簇）为单位分配以区段（或簇）为单位分配是连续分配和非连续分配的结是连续分配和非连续分配的结合，现广为使用。区段由若干个连续扇区组成，文件所分合，现广为使用。区段由若干个连续扇区组成，文件所分各区段可以用链接指针、索引表等方法来管理；各区段可以用链接指针、索引表等方法来管理；n文件分配表文件分配表FATFAT是该分配方法用以记录磁盘分配现状的数是该分配方法用以记录磁盘分配现状的数据结构；该表整个磁盘仅设一张，其结构如下屏所示。表据结构；该表整个磁盘仅设一张，其结构如下屏所示。表的序号是物理块号，从的序号是物理块号，从0 0开始直至开始直至N N1 1（N N为盘块总数）；为盘块总数）

28、；每个表项中的内容为存放文件的下一个盘块号；文件的首每个表项中的内容为存放文件的下一个盘块号；文件的首地址（第一个盘块号）存放在该文件的目录中。从目录中地址（第一个盘块号）存放在该文件的目录中。从目录中找到文件的首地址后，根据找到文件的首地址后，根据FAT就能找到文件在磁盘上的就能找到文件在磁盘上的所有物理块号；所有物理块号；文件分配表示意图文件分配表示意图n文件控制块（文件控制块（FCBFCB）保存的块号是）保存的块号是2 2，通过查，通过查FATFAT，可获得该，可获得该文件的块号序列为：文件的块号序列为：2 2，4 4，5 5，1 1；FCB 0 4 5 1 2FAT物理块号物理块号01

29、2345文件分配表讨论（文件分配表讨论（1 1）n假定磁盘块的大小为假定磁盘块的大小为1 1KBKB，对于对于1.21.2MBMB的软盘，其文件分配表的软盘，其文件分配表FATFAT需要占用多少存储空间？需要占用多少存储空间？ 该软盘共有盘块：该软盘共有盘块：1.21.2M/1K=1.2KM/1K=1.2K（个）个） 又又 1 1K K1.2K1.2K2K2K， 故故1.21.2K K个盘块号要用个盘块号要用1111位二进制表示，为了方便存取，每位二进制表示，为了方便存取，每个盘块号用个盘块号用1212位二进制描述，即文件分配表的每个表目为位二进制描述，即文件分配表的每个表目为1.51.5个字

30、节；个字节； FAT FAT要占用的存储空间总数为：要占用的存储空间总数为： 1.5 1.51.21.2K=1.8KBK=1.8KB。文件分配表讨论（文件分配表讨论（2 2）n若硬盘容量为若硬盘容量为200200MBMB时，每个盘块仍为时，每个盘块仍为1K1K，FATFAT需要占用多少需要占用多少空间？空间？ 硬盘共有盘块：硬盘共有盘块： 200 200M/1K=200KM/1K=200K 又又 128 128K K200K200K256K256K， 故故200200K K个盘块号要用个盘块号要用1818位二进制表示。为方便文件分配表位二进制表示。为方便文件分配表的存取，每个表目用的存取，每个

31、表目用2020位二进制表示，即文件分配表的每个位二进制表示，即文件分配表的每个表目大小为表目大小为2.52.5个字节；个字节； FAT FAT要占用的存储空间总数为：要占用的存储空间总数为： 2.5 2.5200200K=500KBK=500KB。索引分配索引分配n链接分配方式虽解决了连续分配方式中存在的问题，链接分配方式虽解决了连续分配方式中存在的问题，但又出现了新的问题：但又出现了新的问题：n寻址时有寻址时有“拉链拉链”的时间开销；的时间开销；n链接指针要占用一定数量的磁盘空间；链接指针要占用一定数量的磁盘空间；n在索引分配方法中，系统为每个文件分配一个索引在索引分配方法中，系统为每个文件

32、分配一个索引块，索引块中存放索引表，索引表中的每个表项对块，索引块中存放索引表，索引表中的每个表项对应分配给文件的一个物理块；应分配给文件的一个物理块； 索引分配方法支持直接访问，寻址速度快；索引分配方法支持直接访问，寻址速度快； 索引块要占用一定的存储空间，存取文件需要两索引块要占用一定的存储空间，存取文件需要两次访问外存；次访问外存；索引分配示意图索引分配示意图 0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334文件文件B目录目录文件名文件名 索引地址索引地址 B 24 183142801234索引表二

33、级索引和多级索引二级索引和多级索引n当文件很大，其索引表的大小超过了一个物理块时，可以当文件很大，其索引表的大小超过了一个物理块时，可以将索引表本身作为一个文件，再为其建立一个将索引表本身作为一个文件，再为其建立一个“索引表索引表”，该该“索引表索引表”是文件索引的索引，从而构成了二级索引；是文件索引的索引，从而构成了二级索引；n第一级索引表的表目指向第二级索引，第二级索引表的表第一级索引表的表目指向第二级索引，第二级索引表的表目指向文件信息所在的物理块号。以此类推可再逐级建立目指向文件信息所在的物理块号。以此类推可再逐级建立索引，进而构成多级索引；索引，进而构成多级索引；n在两级索引分配方式

34、下，如果每个盘块的大小为在两级索引分配方式下，如果每个盘块的大小为1 1KBKB，每每个盘块号占个盘块号占4 4字节，则：字节，则： 一个索引块中可以存放：一个索引块中可以存放： 1 1KB/4=256KB/4=256个盘块号个盘块号 两级索引最多可以存放的盘块数为：两级索引最多可以存放的盘块数为： 256 256256=64256=64K K个盘块号个盘块号 因此可以允许的最大文件长度为：因此可以允许的最大文件长度为： 64 64K K1KB=64MB1KB=64MB两级索引分配示意图两级索引分配示意图第二级索引第二级索引磁盘空间磁盘空间主索引 3607401125 105 106 254

35、012105106254356357985 356 357 740 985985 11253601010。3 3。2 2 空闲存储空间的管理空闲存储空间的管理n为了实现文件存储空间的分配，首先应记为了实现文件存储空间的分配，首先应记住空闲存储空间的现状；住空闲存储空间的现状；n常用的空闲存储空间管理方法有：常用的空闲存储空间管理方法有：n空闲文件目录；空闲文件目录；n空闲块链；空闲块链；n位示图；位示图；空闲文件目录空闲文件目录n文件存储设备上的一个连续空闲区可以看作一个空闲文件，文件存储设备上的一个连续空闲区可以看作一个空闲文件，又称空白文件或自由文件；又称空白文件或自由文件；n空闲文件目录

36、法为所有空闲文件建立一个目录，每个空闲文空闲文件目录法为所有空闲文件建立一个目录，每个空闲文件在该目录中占一个表目，其中至少包括：空闲区序号、第件在该目录中占一个表目，其中至少包括：空闲区序号、第一个空闲块块号、空闲块数目等信息；一个空闲块块号、空闲块数目等信息；n下面给出了一个空闲目录的例子：下面给出了一个空闲目录的例子：序号序号第一个空闲块号第一个空闲块号空闲块个数空闲块个数物理块号物理块号153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-空闲文件目录法的空闲空间管理空闲文件目录法的空闲空间管理n当请求分配存储空间时，系统依次扫描

37、空闲文件目录，直到当请求分配存储空间时，系统依次扫描空闲文件目录，直到找到一个能满足要求的空闲文件为止。若该文件大小大于申找到一个能满足要求的空闲文件为止。若该文件大小大于申请空间量则还要进行划分；请空间量则还要进行划分；n当回收存储空间时，也需要顺序扫描空闲文件目录，寻找一当回收存储空间时，也需要顺序扫描空闲文件目录，寻找一个空表目，并将释放空间的第一个物理块号以及释放空间的个空表目，并将释放空间的第一个物理块号以及释放空间的块数填到这个表目中。若释放空间与已有空闲文件邻接，则块数填到这个表目中。若释放空间与已有空闲文件邻接，则需进行合并；需进行合并；n显然，只要将动态分区管理方法中的算法稍作修改，即可用显然，只要将动态分区管理方法中的算法稍作修改，即可用于空闲文件目录方法；于空闲文件目录方法；n特点：仅当文件存储空间中只有