多重索引结构课件.ppt

1、磁盘设备驱动程序磁盘设备驱动程序磁带设备驱动程序磁带设备驱动程序基本文件系统（物理基本文件系统（物理I/O层）层）基本基本I/O管理程序管理程序逻辑逻辑I/O堆堆顺序顺序索引顺序索引顺序索引索引哈希哈希用户程序用户程序结构结构u设备驱动程序：设备驱动程序：负责启动该设备上的负责启动该设备上的I/O操作，处理操作，处理I/O请求的完成请求的完成u基本文件系统（物理基本文件系统（物理I/O层）：层）：处理与磁盘或磁带交换处理与磁盘或磁带交换的的数据块。数据块。u注重的是这些块在外存设备中的位置，而并不知道该文件所涉及的注重的是这些块在外存设备中的位置，而并不知道该文件所涉及的数据或结构的内容。数据

2、或结构的内容。u基本基本I/O管理程序：管理程序：负责所有文件负责所有文件I/O的开始或结束。选的开始或结束。选择执行文件的择执行文件的I/O设备，外存的分配，设备，外存的分配，I/O缓冲区的指定缓冲区的指定u逻辑逻辑I/O：使用户和应用程序能够访问到使用户和应用程序能够访问到记录记录。u物理物理I/O层处理的是数据块，逻辑层处理的是数据块，逻辑I/O处理的是文件记录。它提供一处理的是文件记录。它提供一种通用的记录种通用的记录I/O的能力。的能力。u访问方法层访问方法层：与用户最近的一层。在应用程序和文件与用户最近的一层。在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。系统及保存数

3、据的设备之间提供了一种标准接口。u不同的访问方法反映出不同的文件结构和访问数据的不同方法。不同的访问方法反映出不同的文件结构和访问数据的不同方法。结构结构u为了实现用户对文件的按名存取，系统要对目录进行查询为了实现用户对文件的按名存取，系统要对目录进行查询，找出该文件的文件控制块或者索引节点，进而找到该文，找出该文件的文件控制块或者索引节点，进而找到该文件的物理地址。件的物理地址。u线性列表：线性列表：顺序检索法。目录文件由目录项构成一个线顺序检索法。目录文件由目录项构成一个线性表，每个目录项包括文件名和执行数据块的指针。性表，每个目录项包括文件名和执行数据块的指针。u创建新文件：创建新文件：

4、检索该目录，检查是否同名，没有同检索该目录，检查是否同名，没有同名，则将新文件的目录项添加到目录末尾名，则将新文件的目录项添加到目录末尾u删除文件时：删除文件时：检索目录找到该目录项，然后释放分检索目录找到该目录项，然后释放分配给它的全部空间，并且清空该项配给它的全部空间，并且清空该项u评价：评价：简单易行、速度慢。简单易行、速度慢。改善：改善：使用缓存来存放使用缓存来存放最近用过的目录信息。将目录排序，使用二分检索最近用过的目录信息。将目录排序，使用二分检索法，缩短平均查找时间，但会使文件的创建和删除法，缩短平均查找时间，但会使文件的创建和删除变得复杂变得复杂u哈希表：哈希表：利用线性表存放

5、目录项，利用哈息表进行检索利用线性表存放目录项，利用哈息表进行检索。哈希表根据文件名得到一个值，并返回一个指向线性。哈希表根据文件名得到一个值，并返回一个指向线性列表中的元素的指针。列表中的元素的指针。u冲突问题：冲突问题：两个文件名相同的哈希值。两个文件名相同的哈希值。u目录目录u目录文件目录文件文件名文件类型外存地址作业目录文件软件目录文件娱乐目录文件F1数据文件根目录文件的内容：根目录文件的内容：文件名文件类型外存地址C目录文件OS目录文件F1.C数据文件F2.C数据文件OS1数据文件作业目录文件的内容：作业目录文件的内容：u连续分配连续分配u链式分配链式分配u索引分配索引分配u连续分配

6、：连续分配：创建文件时，分配一组连续的块；创建文件时，分配一组连续的块；FAT中每个文件只要一中每个文件只要一项，说明起始块和文件的长度。项，说明起始块和文件的长度。对顺序文件有利对顺序文件有利。u优点优点:u 简单。适用于一次性写入的操作简单。适用于一次性写入的操作 u 支持顺序存取和随机存取，顺序存取速度快支持顺序存取和随机存取，顺序存取速度快 u 所需的磁盘寻道次数和寻道时间最少（因为由于空间的所需的磁盘寻道次数和寻道时间最少（因为由于空间的连续性，当访问下一个磁盘块时，一般无需移动磁头，当连续性，当访问下一个磁盘块时，一般无需移动磁头，当需要磁头移动，只需要移动一个磁道。需要磁头移动，

7、只需要移动一个磁道。u缺点缺点:u文件不能动态增长（可能文件末尾处的空块已经分配给别文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）的文件）u不利于文件插入和删除不利于文件插入和删除u外部碎片问题（反复增删文件后），外部碎片问题（反复增删文件后），使得很难找到空间大使得很难找到空间大小足够的连续块。进行紧缩小足够的连续块。进行紧缩u在创建文件时声明文件的大小。在创建文件时声明文件的大小。u链式分配：链式分配：一个文件的信息存放在若干不连续的物理一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下块中，各块之间通过指针连接，前一个物理块指向下一个物理块。一

8、个物理块。FATFAT中每个文件同样只需要一项，包括中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个自由块都可文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。以加入到链中。u优点：优点：u提高了磁盘空间利用率提高了磁盘空间利用率,不存在外部碎片问题不存在外部碎片问题u有利于文件插入和删除有利于文件插入和删除u有利于文件动态扩充有利于文件动态扩充u 缺点：缺点：u存取速度慢，一般仅适于对信息的顺序存取，存取速度慢，一般仅适于对信息的顺序存取，不适于随机不适于随机存取存取:查找某一个块必须从头开始沿指针进行。查找某一个块必须从头开始沿指针进行。u可靠性问题，如指针出错

9、；更多的寻道次数和寻道时间可靠性问题，如指针出错；更多的寻道次数和寻道时间u链接指针占用一定的空间，将多个块组成簇（链接指针占用一定的空间，将多个块组成簇（clustercluster），），按簇进行分配而不是按块进行分配（增加了磁盘碎片）。按簇进行分配而不是按块进行分配（增加了磁盘碎片）。使用FAT文件分配表法链接分配的变种，如MS-DOS和OS/2。见教材P312u一个已经打开的连续文件，要读取其第一个已经打开的连续文件，要读取其第1010号数号数据块，则需要据块，则需要_次次I/OI/O操作；对于链式文件操作；对于链式文件需要需要_次次I/OI/O操作？操作？u 设某个文件为链式文件，由

10、设某个文件为链式文件，由5 5个逻辑记录组成个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均，每个逻辑记录的大小与磁盘块大小相等，均为为512512字节，并依次存放在字节，并依次存放在5050、121121、7575、8080、6363号磁盘块上。若要存取文件的第号磁盘块上。若要存取文件的第15691569逻辑字逻辑字节处的信息，问要访问哪一个磁盘块？节处的信息，问要访问哪一个磁盘块？u索引分配：索引分配：每个文件在每个文件在FAT中有一个一级索引，索引包含分中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在一个单独的配给文件的每个分区的入口。文件的索引保存在一个单独

11、的块中。块中。FAT中该文件的入口指向这一块。中该文件的入口指向这一块。u 优点：优点：u保持了链接结构的优点保持了链接结构的优点,又解决了其缺点：按块分配又解决了其缺点：按块分配可以可以消除外部碎片消除外部碎片，按大小可变的分区分配可以，按大小可变的分区分配可以提提高局部性高局部性。索引分配支持顺序访问文件和直接访问。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式。文件，是普遍采用的一种方式。u满足了文件动态增长、插入删除的要求（只要有空满足了文件动态增长、插入删除的要求（只要有空闲块）闲块）u也能充分利用外存空间也能充分利用外存空间u 缺点：缺点：u较多的寻道次数和寻道时间较

12、多的寻道次数和寻道时间.u索引表本身带来了系统开销，索引表本身带来了系统开销，如：内外存空间，存如：内外存空间，存取时间取时间文件的直接访问：文件的直接访问：使用连续分配方式使用连续分配方式文件的顺序访问：文件的顺序访问：采用链接分配采用链接分配对于这些系统，所使用的访问类型必须在文对于这些系统，所使用的访问类型必须在文件创建时加以说明。件创建时加以说明。连续分配和索引分配相结合：连续分配和索引分配相结合：对于小文件对于小文件（3块或者块或者4块），采用连续分配，当文件块），采用连续分配，当文件大时，自动切换到索引分配。大时，自动切换到索引分配。索引表指针索引表指针文件说明信息文件说明信息逻辑

13、块逻辑块号号物理物理块号块号02011522232520152225索引表索引表索引文件的物理结构索引文件的物理结构 索引表组织索引表组织多级索引多级索引:将一个大文件的所有索引表（二级索引将一个大文件的所有索引表（二级索引)的地的地址放在另一个索引表（一级索引址放在另一个索引表（一级索引)中。中。u2种方式种方式u命令级接口：命令级接口：dirdir、copycopy等等u系统调用：系统调用：文件系统的程序级接口，用户可以文件系统的程序级接口，用户可以在程序中使用这些系统调用对文件进行各种操在程序中使用这些系统调用对文件进行各种操作。作。u如建立文件、打开文件、关闭文件、删除文件、如建立文件

14、、打开文件、关闭文件、删除文件、读文件、写文件。读文件、写文件。u建立文件建立文件：creatcreat（文件名、文件属性）文件名、文件属性）u检查参数合法性：按给定的路径查文件目录，找出用户检查参数合法性：按给定的路径查文件目录，找出用户指定的目录位置，检查目录上是否存在同名文件，若存指定的目录位置，检查目录上是否存在同名文件，若存在则发出错误信息。在则发出错误信息。u在指定的目录中找一个空表项作为该文件的目录项，写在指定的目录中找一个空表项作为该文件的目录项，写入指定的文件名。入指定的文件名。u由文件长度确定文件存储所需的物理块数。由文件长度确定文件存储所需的物理块数。u按规定的物理结构为

15、文件分配存储空间。对连续文件，按规定的物理结构为文件分配存储空间。对连续文件，则分配块连续的空间，对索引文件，现分配索引表用的则分配块连续的空间，对索引文件，现分配索引表用的物理块。物理块。u在该文件目录项中写入文件的属性、文件的物理块首址在该文件目录项中写入文件的属性、文件的物理块首址等。等。u打开文件打开文件(open):u按指定的文件名检索文件目录，将待访问文件按指定的文件名检索文件目录，将待访问文件的目录信息读入内存活动文件表中，建立起用的目录信息读入内存活动文件表中，建立起用户和文件的联系。户和文件的联系。u一旦文件被打开就可以多次使用。直到文件被一旦文件被打开就可以多次使用。直到文

16、件被关闭。关闭。多重索引结构多重索引结构u大文件：大文件：设一个盘块大小为设一个盘块大小为1KB，长度为，长度为100KB的的文件就需要文件就需要100个盘块，索引表至少包含个盘块，索引表至少包含100项；项；若文件大小为若文件大小为1000KB，则相应索引表项要有则相应索引表项要有1000项。设盘块号用项。设盘块号用4个字节表示，则该索引表至少占个字节表示，则该索引表至少占用用4000B（约约4K）。）。u当文件很大时，当文件很大时，存在的问题存在的问题：u需要很多的磁盘块需要很多的磁盘块u索引表很大索引表很大u不能将整个索引表放在内存不能将整个索引表放在内存u解决途径：解决途径：采取多重索

17、引结构采取多重索引结构索引表指针索引表指针文件说明信息文件说明信息记录号记录号物理物理块号块号020115222325物理块号物理块号索引表索引表20252215物理块号物理块号物理块号物理块号物理块号物理块号文件信息文件信息文件信息文件信息多重索引结构多重索引结构 outer-indexindex tablefile多重索引结构图示多重索引结构图示多重索引结构举例多重索引结构举例u为此，我们可以将文件名和其他信息分开，后者单独形成一个独为此，我们可以将文件名和其他信息分开，后者单独形成一个独立的数据结构，称为索引节点（立的数据结构，称为索引节点（index node或者或者i_node)对应

18、的对应的目录项就不再是完整的一个目录项就不再是完整的一个FCB,而是由文件名和指向索引节点的而是由文件名和指向索引节点的指针组成指针组成u在引入索引节点之后，一个文件在创建后将立即有与之对应的一在引入索引节点之后，一个文件在创建后将立即有与之对应的一个磁盘索引节点若该文件被调进内存，将立即有对应的一个内个磁盘索引节点若该文件被调进内存，将立即有对应的一个内存索引结点存索引结点u为了加速对文件目录的查找，在为了加速对文件目录的查找，在Unix系统中，将文件系统中，将文件名和其它文件说明信息分开，名和其它文件说明信息分开，由文件说明信息形成一由文件说明信息形成一个称为索引节点的数据结构个称为索引节

19、点的数据结构，而，而相应的文件目录项只相应的文件目录项只由文件名由文件名和和对应的索引节点号组成。对应的索引节点号组成。文件名i节点号多重索引结构举例多重索引结构举例u文件分配以文件分配以块块为基础。按照需要为基础。按照需要动态动态进行，不是预定义的。进行，不是预定义的。u文件在磁盘中的块不一定是连续的。文件在磁盘中的块不一定是连续的。uUnix系统为了访问文件，系统为了访问文件，采用索引的方法采用索引的方法，索引的一部分保索引的一部分保存在该文件的索引节点中。存在该文件的索引节点中。u索引节点（索引节点（I节点）节点）文件名文件名索引节点编号索引节点编号gamesmailNewsworku所

20、有类型的所有类型的Unix文件都是由文件都是由OS通过索引节点来管理通过索引节点来管理的的u索引节点索引节点是一个控制结构，包含是一个控制结构，包含OS所要的关于某个所要的关于某个文件的重要信息文件的重要信息:u文件模式文件模式u链接计数链接计数u所有者所有者IDu组组IDu文件大小文件大小u文件地址文件地址（39字节）字节）u最后一次被访问最后一次被访问u最后一次被修改最后一次被修改u索引节点被修改索引节点被修改多重索引结构举例多重索引结构举例多重索引结构举例多重索引结构举例uUnix中通过为每个文件创建一个中通过为每个文件创建一个i节点节点的方法，巧妙：的方法，巧妙：ui节点中包含节点中包

21、含39个字节的地址信息个字节的地址信息，这个地址信息被组织成，这个地址信息被组织成13个个3字节的地址或指针。字节的地址或指针。u前前10个表目是直接索引，指向文件最初的个表目是直接索引，指向文件最初的10个数据块。个数据块。当文件大小小于当文件大小小于10块时，可以直接定位到这块时，可以直接定位到这10个块；个块；u第第11个表目是一级索引表，指向磁盘中包含下一部分索个表目是一级索引表，指向磁盘中包含下一部分索引的块。引的块。u第第12个表目是二级索引表，个表目是二级索引表，u第第13个表目是三级索引表；个表目是三级索引表；u对比：对比：在许多文件系统中，在许多文件系统中，如如MSDOS中，

22、使用文件分配表中，使用文件分配表FAT来管理文件的物理盘块来管理文件的物理盘块：u使用使用FAT的主要问题：整个磁盘的所有文件登记在同一个的主要问题：整个磁盘的所有文件登记在同一个FAT表中。因此，即使仅打开一个文件，也要使用整个表中。因此，即使仅打开一个文件，也要使用整个FAT来查找该文件所所分配的盘块，浪费时间。来查找该文件所所分配的盘块，浪费时间。u在在Unix系统中使用系统中使用1KB的物理块，每个索引的物理块，每个索引表的表目需要用表的表目需要用32位来存放物理块地址，因位来存放物理块地址，因此每个物理块刚好是此每个物理块刚好是256个表目，可以映射个表目，可以映射256个物理块。因

23、此：个物理块。因此：u小文件小文件（1010块）：只使用直接索引表。块）：只使用直接索引表。u中等文件中等文件（266266块块）：使用直接索引表与一）：使用直接索引表与一级索引表级索引表u大型文件大型文件（10102562562562562562566580265802块块）：使用直接索引表与一级和二级索引表。）：使用直接索引表与一级和二级索引表。u巨型文件：巨型文件：使用全部索引表，可寻址使用全部索引表，可寻址16777216块。块。u文件系统采用多级索引结构来搜索文件文件内容文件系统采用多级索引结构来搜索文件文件内容。设块长为。设块长为512字节，每个块号长字节，每个块号长3字节。如果字

24、节。如果不考虑逻辑块号在物理块中所占的位置，分别求不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。二级索引和三级索引时可寻址的文件最大长度。u（512/3=170)u一级索引：一级索引：170块块u二级索引：二级索引：17017028900（块），（块），289005121450K字节字节u三级索引：三级索引：1701701704913000（块），（块），4913000 5122456500K字节字节u创建新文件时，系统要为用户的文件分配相应创建新文件时，系统要为用户的文件分配相应的外存空间；删除一个老文件时，系统要回收的外存空间；删除一个老文件时，系统要

25、回收该文件所占用的外存空间，供新文件使用。因该文件所占用的外存空间，供新文件使用。因此，系统需要对外存空闲块进行妥善管理。此，系统需要对外存空闲块进行妥善管理。u在分配时，首先知道磁盘中的哪些块是可用的在分配时，首先知道磁盘中的哪些块是可用的。除了。除了FAT外，还需要一个外，还需要一个DAT（disk allocation Table）。实现技术：。实现技术：u位图位图u空间块链接法空间块链接法u空闲目录法空闲目录法u成组块链接法成组块链接法u位图（位向量）：位图（位向量）：使用一个向量，向量中的每位（使用一个向量，向量中的每位（bit）对应于磁盘中的每一个块（对应于磁盘中的每一个块（blo

26、ck）u0：表示一个表示一个空闲块空闲块u1：表示一个表示一个已使用的块。已使用的块。例：例：2,3,4,5,8,9,10,11,12,13,17,18,25,26,27,=0011110011111100011000000111u优点：优点：u可以比较可以比较容易地找到第一个或一组连续的自由容易地找到第一个或一组连续的自由块，适用于任何一块，适用于任何一种文件分配方法。（而且很多计算机都提供位操作指令）种文件分配方法。（而且很多计算机都提供位操作指令）u位表小，但长度可变位表小，但长度可变u例：对于一个例：对于一个16GB的磁盘，块大小为的磁盘，块大小为512 字节，则位表占字节，则位表占4

27、MB空间。空间。u缺点：缺点：u对于大文件，位图占用内存空间较多，可以按合并对于大文件，位图占用内存空间较多，可以按合并4个扇区位一个个扇区位一个cluster（簇）的方法。簇）的方法。u位表的管理：位表的管理：u位图可以位于内存或磁盘中，但在磁盘中需要搜索位图可以位于内存或磁盘中，但在磁盘中需要搜索时间，时间，故位表一般位于内存中。故位表一般位于内存中。u即使位于主存中，穷举式搜索会影响文件系统的性即使位于主存中，穷举式搜索会影响文件系统的性能，尤其是当磁盘快满时只剩下很少自由块时问题能，尤其是当磁盘快满时只剩下很少自由块时问题会很严重。会很严重。u因此，大多数使用位表的文件系统都有因此，大

28、多数使用位表的文件系统都有一个辅助数一个辅助数据结构据结构，用于汇总位图的子区域的内容用于汇总位图的子区域的内容。u例如：例如：位图可以在逻辑上划分成许多子区域，位图可以在逻辑上划分成许多子区域，对对于每个子区域，汇总表中包括它的自由块的数目于每个子区域，汇总表中包括它的自由块的数目和连续自由块的最大数目。和连续自由块的最大数目。u当文件系统需要大量的连续块时，它可以通过扫当文件系统需要大量的连续块时，它可以通过扫描汇总表来发现适合的子区域，然后再搜索这个描汇总表来发现适合的子区域，然后再搜索这个子区域。子区域。u将文件存储设备上的每个空闲空间看作一个空闲文将文件存储设备上的每个空闲空间看作一

29、个空闲文件，系统为所有空闲文件单独建立一个目录。件，系统为所有空闲文件单独建立一个目录。每个每个空闲文件在这个目录中占用一个表目。表目的内容空闲文件在这个目录中占用一个表目。表目的内容包括第一个空闲块的地址（物理块号）、空闲块的包括第一个空闲块的地址（物理块号）、空闲块的数目。如：数目。如：u分配过程：分配过程：新建文件时，扫描索引，找到符合条件新建文件时，扫描索引，找到符合条件的项，并从表中删除；的项，并从表中删除；u回收过程：回收过程：删除文件时，系统回收该文件所占用的删除文件时，系统回收该文件所占用的盘块，将相应的空闲块的信息填回空闲空间表中，盘块，将相应的空闲块的信息填回空闲空间表中，

30、如果释放的区域和和原有空闲区邻接，则将它们合如果释放的区域和和原有空闲区邻接，则将它们合并成一个大的空闲区，记在一个表项中。并成一个大的空闲区，记在一个表项中。u适合于连续文件的存放适合于连续文件的存放u但是，如果有大量的小空闲区，则空闲区表很大，但是，如果有大量的小空闲区，则空闲区表很大，检索效率很低。检索效率很低。序号序号第一个空第一个空闲块号闲块号空闲块空闲块个数个数物理块号物理块号153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-u链表：链表：通过使用指向每个空闲区的指针和它们的通过使用指向每个空闲区的指针和它们的长度值的一个

31、链将空闲区链接起来。长度值的一个链将空闲区链接起来。u如果需要一个块：如果需要一个块：从链的头部取出一块，并调整长从链的头部取出一块，并调整长度；如果是基于可变分区长度分配的，可采用首次度；如果是基于可变分区长度分配的，可采用首次适配算法，同样需要调整指针和长度。适配算法，同样需要调整指针和长度。u优点：优点：空间开销小：仅需要一个指向链开始处的指空间开销小：仅需要一个指向链开始处的指针及第一个分区的长度针及第一个分区的长度u问题：问题：u每次分配一个块时，在将数据写到这个块中每次分配一个块时，在将数据写到这个块中之前，需要先读这个块，以发现指向新的第之前，需要先读这个块，以发现指向新的第一个

32、空闲块的指针。一个空闲块的指针。u效率低，开销大。效率低，开销大。u成组块链接法：成组块链接法：将外存中的所有空闲块按将外存中的所有空闲块按50块（或块（或n块）划分为一组，用块）划分为一组，用索引表索引表表示；每组的第一块表示；每组的第一块用来存放前一组中各块的块号和总块数；因此，各用来存放前一组中各块的块号和总块数；因此，各组间通过链表指针串在一起，构成组间通过链表指针串在一起，构成链表链表。（把链表。（把链表和索引相结合。）和索引相结合。）u 第一组的块数为第一组的块数为49块，最后一组可能不足块，最后一组可能不足50块，块，且最后组的物理块号与总块数只能放在内存的一个且最后组的物理块号

33、与总块数只能放在内存的一个专用栈中（如：专用栈中（如：Unix中超级块中）；中超级块中）；u 对块的分配和释放在栈中进行。对块的分配和释放在栈中进行。栈计数栈计数count是栈是栈中的空闲块数目，栈中的元素是空闲块编号。中的空闲块数目，栈中的元素是空闲块编号。成组块链接法成组块链接法每组的第一块用来存放前一组中各块的块号和总块数u系统启动时的初始化系统启动时的初始化u系统中设立有专用的磁盘空系统中设立有专用的磁盘空间分配间分配/回收用的回收用的内存堆栈区内存堆栈区，使得空闲块的分配和释放，使得空闲块的分配和释放可在内存进行；同时用于空可在内存进行；同时用于空闲块分配和回收的堆栈有闲块分配和回收

34、的堆栈有堆堆栈指针栈指针Ptr，Ptr的初值等于的初值等于该组空闲块的总块数。分配该组空闲块的总块数。分配时，时，Ptr Ptr1；回收时回收时，Ptr Ptr1；空闲块的空闲块的分配和释放必须互斥进行分配和释放必须互斥进行u启动时将卷资源表中的最后启动时将卷资源表中的最后一组的信息读入内存堆栈一组的信息读入内存堆栈S中。其中中。其中0单元存放总块数，单元存放总块数，栈顶指针值等于总块数栈顶指针值等于总块数3XYZ堆栈堆栈S0 1 2 3 4 5 u空闲块分配过程空闲块分配过程：当需要一块空闲块时，首先查看栈中：当需要一块空闲块时，首先查看栈中是否是否count=1：u若不是若不是，则弹出栈顶

35、元素，则弹出栈顶元素N（表示可用磁盘块号）分配出表示可用磁盘块号）分配出去，去，-count；u若是，若是，弹出栈顶元素弹出栈顶元素N，把空闲块把空闲块N中的块号读入到栈中；中的块号读入到栈中；返回空闲块编号返回空闲块编号N（因为所分配的磁盘块号是栈中最后一因为所分配的磁盘块号是栈中最后一个可用盘块号，由于在该盘块中存放了下一组的所有盘块个可用盘块号，由于在该盘块中存放了下一组的所有盘块号，于是要先将该块的内容读入栈中，然后才能将该块分号，于是要先将该块的内容读入栈中，然后才能将该块分配出去）配出去）u释放过程：释放过程：被释放空闲块为编号被释放空闲块为编号N。查看是否栈已满（查看是否栈已满（

36、如如count=50）；）；u若不是，若不是，则则N入栈，入栈，+count；u若是，若是，则将栈（包括栈计数）写入到空闲块则将栈（包括栈计数）写入到空闲块N，然后把然后把N放放入栈顶并置入栈顶并置count为为1。（说明栈已满，须先将栈中所有盘。（说明栈已满，须先将栈中所有盘块号复制到新回收的盘块中，再将新回收盘块的编号放到块号复制到新回收的盘块中，再将新回收盘块的编号放到栈中，成为栈中第一个盘块）栈中，成为栈中第一个盘块）41350187Super Blockcount50040400351.049count50450401.049count460.045count#350#400Last

37、 One.成组块链接 下组指针 本组块数本组块号First1已知一文件系统采用链式文件方式存储文件，存储设备已知一文件系统采用链式文件方式存储文件，存储设备用成组块链接法管理，每组用成组块链接法管理，每组8块。目前系统的状态如下图块。目前系统的状态如下图：1)一进程欲申请一进程欲申请10个磁盘块，请给出其得到的磁盘块号序个磁盘块，请给出其得到的磁盘块号序列，并画出分配后的系统状态；并指出完成本次申请，列，并画出分配后的系统状态；并指出完成本次申请，I/O操作的次数。操作的次数。2）在）在1）基础上，回收一个以）基础上，回收一个以50作为起始块号的具有作为起始块号的具有6个块个块的文件，画出回收

38、后的系统状态图。并指出完成本次回的文件，画出回收后的系统状态图。并指出完成本次回收，收，I/O操作的次数。操作的次数。系统磁盘块管理系统磁盘块管理堆栈堆栈其中其中0#单元存放单元存放总块数总块数堆栈指针值等于堆栈指针值等于总块数总块数第第80#磁磁盘块盘块第第 8 8#磁磁盘块盘块051802793784775766757748738888786858483828189695949392919089假定磁盘块的大小为假定磁盘块的大小为1KB，每个盘块号占每个盘块号占4个字节，文件索引节个字节，文件索引节点中的磁盘地址明细表如图所示，如何将下列文件的字节偏点中的磁盘地址明细表如图所示，如何将下列

39、文件的字节偏移量转换为物理地址？移量转换为物理地址？1 9000 2 14000 3 35000040962284542031111150101367042891568241011109954952331452.33003333083274104289156757601331索索引引节节点点练练习习题题0123456789101112解：解：（1）字节偏移量为字节偏移量为9000，此时，此时逻辑块号为：逻辑块号为：9000/10248块内偏移量为：块内偏移量为：900081024808因逻辑块号小于因逻辑块号小于10，因此该块为直接块。其物理盘块号，因此该块为直接块。其物理盘块号为为367，该

40、块中的第，该块中的第808字节即为文件的第字节即为文件的第9000字节字节（2）字节偏移量为字节偏移量为14000，此时，此时逻辑块号为：逻辑块号为：14000/102413块内偏移量为：块内偏移量为：14000131024688因逻辑块号因逻辑块号1013266，因此该块为一次间接块。，因此该块为一次间接块。由图可知，一次间接的盘块号为由图可知，一次间接的盘块号为428，从一次间，从一次间接块中读出盘块号表，查得其物理块号为接块中读出盘块号表，查得其物理块号为952，该块，该块中的第中的第688字节即为文件的第字节即为文件的第14000字节。字节。(3)字节偏移量为字节偏移量为350000，

41、此时，此时 逻辑块号为逻辑块号为：350000/1024341 块内偏移量为块内偏移量为：3500003411024816因逻辑块号因逻辑块号26634165802，因此该块为，因此该块为二次间接块二次间接块。由图可知，二次间接块的盘块号为由图可知，二次间接块的盘块号为9156。由于一个一次。由于一个一次间接块中可容纳间接块中可容纳256个块号，个块号，341-10-25675 因此，字节偏移量因此，字节偏移量350000在二次间接块的第在二次间接块的第0个个一次间接块的第一次间接块的第75个表项中，其盘块号为个表项中，其盘块号为333，该块中，该块中的第的第816字节即为文件的第字节即为文件的第350000字节。字节。u有一个磁盘组共有有一个磁盘组共有10个盘面，每个盘面上有个盘面，每个盘面上有100个磁道，每个磁道，每个磁道有个磁道有16个扇区，假定分配以扇区为单位。个扇区，假定分配以扇区为单位。u若使用位示图管理磁盘空间，则位示图需要占用多少空间若使用位示图管理磁盘空间，则位示图需要占用多少空间（1610010 8=2000字节）字节）u若空闲文件目录的每个表项占用若空闲文件目录的每个表项占用5个字节，则什么时候空闲个字节，则什么时候空闲文件目录所占空间大于位示图所占空间？文件目录所占空间大于位示图所占空间？u2000 5400u12.1u12.4u12.5u12.6