多重索引结构课件

第12章文件系统实现第12章文件系统实现1磁盘设备驱动程序磁带设备驱动程序基本文件系统（物理I/O层）基本I/O管理程序逻辑I/O堆顺序索引顺序索引哈希用户程序12.1文件系统结构磁盘设备驱动程序磁带设备驱动程序基本文件系统（物理I/O层）2设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的完成基本文件系统（物理I/O层）：处理与磁盘或磁带交换的数据块。注重的是这些块在外存设备中的位置，而并不知道该文件所涉及的数据或结构的内容。基本I/O管理程序：负责所有文件I/O的开始或结束。选择执行文件的I/O设备，外存的分配，I/O缓冲区的指定逻辑I/O：使用户和应用程序能够访问到记录。物理I/O层处理的是数据块，逻辑I/O处理的是文件记录。它提供一种通用的记录I/O的能力。访问方法层：与用户最近的一层。在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。不同的访问方法反映出不同的文件结构和访问数据的不同方法。12.1文件系统结构设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的312.2目录实现为了实现用户对文件的按名存取，系统要对目录进行查询，找出该文件的文件控制块或者索引节点，进而找到该文件的物理地址。线性列表：顺序检索法。目录文件由目录项构成一个线性表，每个目录项包括文件名和执行数据块的指针。创建新文件：检索该目录，检查是否同名，没有同名，则将新文件的目录项添加到目录末尾删除文件时：检索目录找到该目录项，然后释放分配给它的全部空间，并且清空该项评价：简单易行、速度慢。改善：使用缓存来存放最近用过的目录信息。将目录排序，使用二分检索法，缩短平均查找时间，但会使文件的创建和删除变得复杂12.2目录实现为了实现用户对文件的按名存取，系统要对目录412.2目录实现哈希表：利用线性表存放目录项，利用哈息表进行检索。哈希表根据文件名得到一个值，并返回一个指向线性列表中的元素的指针。冲突问题：两个文件名相同的哈希值。12.2目录实现哈希表：利用线性表存放目录项，利用哈息表进5文件系统目录目录文件文件名文件类型外存地址…作业目录文件软件目录文件娱乐目录文件F1数据文件根目录文件的内容：文件名文件类型外存地址…C目录文件OS目录文件F1.C数据文件F2.C数据文件OS1数据文件作业目录文件的内容：文件系统目录文件名文件类型外存地址…作业目录文件软件目录文件612.3

分配方法连续分配链式分配索引分配12.3分配方法连续分配712.3

分配方法－连续分配连续分配：创建文件时，分配一组连续的块；FAT中每个文件只要一项，说明起始块和文件的长度。对顺序文件有利。优点:

简单。适用于一次性写入的操作支持顺序存取和随机存取，顺序存取速度快所需的磁盘寻道次数和寻道时间最少（因为由于空间的连续性，当访问下一个磁盘块时，一般无需移动磁头，当需要磁头移动，只需要移动一个磁道。缺点:文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）不利于文件插入和删除外部碎片问题（反复增删文件后），使得很难找到空间大小足够的连续块。进行紧缩在创建文件时声明文件的大小。12.3分配方法－连续分配连续分配：创建文件时，分配一组连8磁盘空间的连续分配磁盘空间的连续分配912.3

分配方法－链式分配链式分配：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。FAT中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。优点：提高了磁盘空间利用率,不存在外部碎片问题有利于文件插入和删除有利于文件动态扩充

缺点：存取速度慢，一般仅适于对信息的顺序存取，不适于随机存取:查找某一个块必须从头开始沿指针进行。可靠性问题，如指针出错；更多的寻道次数和寻道时间链接指针占用一定的空间，将多个块组成簇（cluster），按簇进行分配而不是按块进行分配（增加了磁盘碎片）。12.3分配方法－链式分配链式分配：一个文件的信息存放在若10磁盘空间的链式分配磁盘空间的链式分配11使用FAT－文件分配表法－链接分配的变种，如MS-DOS和OS/2。见教材P312使用FAT－文件分配表法－链接分配的变种，如MS-DOS和O12例题一个已经打开的连续文件，要读取其第10号数据块，则需要____次I/O操作；对于链式文件需要____次I/O操作？设某个文件为链式文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。若要存取文件的第1569逻辑字节处的信息，问要访问哪一个磁盘块？例题一个已经打开的连续文件，要读取其第10号数据块，则需要1312.3文件的分配方法－索引分配索引分配：每个文件在FAT中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在一个单独的块中。FAT中该文件的入口指向这一块。

优点：保持了链接结构的优点,又解决了其缺点：按块分配可以消除外部碎片，按大小可变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式。满足了文件动态增长、插入删除的要求（只要有空闲块）也能充分利用外存空间缺点：较多的寻道次数和寻道时间.索引表本身带来了系统开销，如：内外存空间，存取时间12.3文件的分配方法－索引分配索引分配：每个文件在FAT14磁盘空间的索引分配磁盘空间的索引分配15文件的直接访问：使用连续分配方式文件的顺序访问：采用链接分配对于这些系统，所使用的访问类型必须在文件创建时加以说明。连续分配和索引分配相结合：对于小文件（3块或者4块），采用连续分配，当文件大时，自动切换到索引分配。文件的直接访问：使用连续分配方式连续分配和索引分配相结合：对16索引表指针……文件说明信息逻辑块号物理块号02011522232520152225索引表索引文件的物理结构

索引表组织多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。索引表指针……文件说明信息逻辑块号物理0201152223217举例：文件操作2种方式命令级接口：dir、copy等系统调用：文件系统的程序级接口，用户可以在程序中使用这些系统调用对文件进行各种操作。如建立文件、打开文件、关闭文件、删除文件、读文件、写文件。举例：文件操作2种方式18举例：文件操作建立文件：creat（文件名、文件属性）检查参数合法性：按给定的路径查文件目录，找出用户指定的目录位置，检查目录上是否存在同名文件，若存在则发出错误信息。在指定的目录中找一个空表项作为该文件的目录项，写入指定的文件名。由文件长度确定文件存储所需的物理块数。按规定的物理结构为文件分配存储空间。对连续文件，则分配块连续的空间，对索引文件，现分配索引表用的物理块。在该文件目录项中写入文件的属性、文件的物理块首址等。举例：文件操作建立文件：creat（文件名、文件属性）19举例：文件操作打开文件(open):按指定的文件名检索文件目录，将待访问文件的目录信息读入内存活动文件表中，建立起用户和文件的联系。一旦文件被打开就可以多次使用。直到文件被关闭。举例：文件操作打开文件(open):20多重索引结构大文件：设一个盘块大小为1KB，长度为100KB的文件就需要100个盘块，索引表至少包含100项；若文件大小为1000KB，则相应索引表项要有1000项。设盘块号用4个字节表示，则该索引表至少占用4000B（约4K）。当文件很大时，存在的问题：需要很多的磁盘块索引表很大不能将整个索引表放在内存解决途径：采取多重索引结构多重索引结构大文件：设一个盘块大小为1KB，长度为100KB21索引表指针……文件说明信息记录号物理块号020115222325物理块号索引表20252215…物理块号…物理块号…物理块号…文件信息文件信息……12.3文件的分配方法－多重索引结构索引表指针……文件说明信息记录号物理02011522232522outer-indexindextablefile多重索引结构－图示outer-indexindextablefile多重索23多重索引结构－举例－Unix的索引节点为此，我们可以将文件名和其他信息分开，后者单独形成一个独立的数据结构，称为索引节点（indexnode或者i_node)．对应的目录项就不再是完整的一个FCB,而是由文件名和指向索引节点的指针组成．在引入索引节点之后，一个文件在创建后将立即有与之对应的一个磁盘索引节点．若该文件被调进内存，将立即有对应的一个内存索引结点．为了加速对文件目录的查找，在Unix系统中，将文件名和其它文件说明信息分开，由文件说明信息形成一个称为索引节点的数据结构，而相应的文件目录项只由文件名和对应的索引节点号组成。文件名i节点号多重索引结构－举例－Unix的索引节点为此，我们可以将文件24多重索引结构－举例－Unix的索引节点文件分配以块为基础。按照需要动态进行，不是预定义的。文件在磁盘中的块不一定是连续的。Unix系统为了访问文件，采用索引的方法，索引的一部分保存在该文件的索引节点中。多重索引结构－举例－Unix的索引节点25文件系统索引节点（I节点）文件名索引节点编号gamesmailNewswork文件系统索引节点（I节点）文件名索引节点编号gamesmai26所有类型的Unix文件都是由OS通过索引节点来管理的索引节点是一个控制结构，包含OS所要的关于某个文件的重要信息:文件模式链接计数所有者ID组ID文件大小文件地址（39字节）最后一次被访问最后一次被修改索引节点被修改多重索引结构－举例－Unix的索引节点所有类型的Unix文件都是由OS通过索引节点来管理的多重索引27多重索引结构－举例－Unix的索引节点Unix中通过为每个文件创建一个i节点的方法，巧妙：i节点中包含39个字节的地址信息，这个地址信息被组织成13个3字节的地址或指针。前10个表目是直接索引，指向文件最初的10个数据块。当文件大小小于10块时，可以直接定位到这10个块；第11个表目是一级索引表，指向磁盘中包含下一部分索引的块。第12个表目是二级索引表，第13个表目是三级索引表；对比：在许多文件系统中，如MS－DOS中，使用文件分配表FAT来管理文件的物理盘块：使用FAT的主要问题：整个磁盘的所有文件登记在同一个FAT表中。因此，即使仅打开一个文件，也要使用整个FAT来查找该文件所所分配的盘块，浪费时间。多重索引结构－举例－Unix的索引节点Unix中通过为每个文28多重索引结构课件29在Unix系统中使用1KB的物理块，每个索引表的表目需要用32位来存放物理块地址，因此每个物理块刚好是256个表目，可以映射256个物理块。因此：小文件（≤10块）：只使用直接索引表。中等文件（≤266块）：使用直接索引表与一级索引表大型文件（≤10＋256＋256×256＝65802块）：使用直接索引表与一级和二级索引表。巨型文件：使用全部索引表，可寻址16777216块。Unix的索引节点（i节点）在Unix系统中使用1KB的物理块，每个索引表的表目需要用330举例文件系统采用多级索引结构来搜索文件文件内容。设块长为512字节，每个块号长3字节。如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。（512/3=170)一级索引：170块二级索引：170×170＝28900（块），28900×512＝1450K字节三级索引：170×170×170＝4913000（块），4913000×512＝2456500K字节举例文件系统采用多级索引结构来搜索文件文件内容。设块长为513112.4磁盘空闲空间的管理-位表创建新文件时，系统要为用户的文件分配相应的外存空间；删除一个老文件时，系统要回收该文件所占用的外存空间，供新文件使用。因此，系统需要对外存空闲块进行妥善管理。在分配时，首先知道磁盘中的哪些块是可用的。除了FAT外，还需要一个DAT（diskallocationTable）。实现技术：位图空间块链接法空闲目录法成组块链接法12.4磁盘空闲空间的管理-位表创建新文件时，系统要为用户3212.4空闲空间的管理-位图（位向量）位图（位向量）：使用一个向量，向量中的每位（bit）对应于磁盘中的每一个块（block）0：表示一个空闲块1：表示一个已使用的块。例：2,3,4,5,8,9,10,11,12,13,17,18,25,26,27,…==>0011110011111100011000000111…优点：可以比较容易地找到第一个或一组连续的自由块，适用于任何一种文件分配方法。（而且很多计算机都提供位操作指令）位表小，但长度可变例：对于一个16GB的磁盘，块大小为512字节，则位表占4MB空间。缺点：对于大文件，位图占用内存空间较多，可以按合并4个扇区位一个cluster（簇）的方法。12.4空闲空间的管理-位图（位向量）位图（位向量）：使用33位表的管理：位图可以位于内存或磁盘中，但在磁盘中需要搜索时间，故位表一般位于内存中。即使位于主存中，穷举式搜索会影响文件系统的性能，尤其是当磁盘快满时只剩下很少自由块时问题会很严重。因此，大多数使用位表的文件系统都有一个辅助数据结构，用于汇总位图的子区域的内容。例如：位图可以在逻辑上划分成许多子区域，对于每个子区域，汇总表中包括它的自由块的数目和连续自由块的最大数目。当文件系统需要大量的连续块时，它可以通过扫描汇总表来发现适合的子区域，然后再搜索这个子区域。12.4空闲空间的管理-位图（位向量）位表的管理：12.4空闲空间的管理-位图（位向量）34将文件存储设备上的每个空闲空间看作一个空闲文件，系统为所有空闲文件单独建立一个目录。每个空闲文件在这个目录中占用一个表目。表目的内容包括第一个空闲块的地址（物理块号）、空闲块的数目。如：分配过程：新建文件时，扫描索引，找到符合条件的项，并从表中删除；回收过程：删除文件时，系统回收该文件所占用的盘块，将相应的空闲块的信息填回空闲空间表中，如果释放的区域和和原有空闲区邻接，则将它们合并成一个大的空闲区，记在一个表项中。12.4空闲空间的管理-空闲空间表（索引）将文件存储设备上的每个空闲空间看作一个空闲文件，系统为所有空35适合于连续文件的存放但是，如果有大量的小空闲区，则空闲区表很大，检索效率很低。序号第一个空闲块号空闲块个数物理块号153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-----12.4空闲空间的管理-空闲空间表（索引）适合于连续文件的存放序号第一个空闲块号空闲块物理块号153（36链表：通过使用指向每个空闲区的指针和它们的长度值的一个链将空闲区链接起来。如果需要一个块：从链的头部取出一块，并调整长度；如果是基于可变分区长度分配的，可采用首次适配算法，同样需要调整指针和长度。优点：空间开销小：仅需要一个指向链开始处的指针及第一个分区的长度问题：每次分配一个块时，在将数据写到这个块中之前，需要先读这个块，以发现指向新的第一个空闲块的指针。效率低，开销大。12.4空闲空间的管理-链表链表：通过使用指向每个空闲区的指针和它们的长度值的一个链将空3712.4空闲空间的管理-链表12.4空闲空间的管理-链表38成组块链接法：将外存中的所有空闲块按50块（或n块）划分为一组，用索引表表示；每组的第一块用来存放前一组中各块的块号和总块数；因此，各组间通过链表指针串在一起，构成链表。（把链表和索引相结合。）第一组的块数为49块，最后一组可能不足50块，且最后组的物理块号与总块数只能放在内存的一个专用栈中（如：Unix中超级块中）；对块的分配和释放在栈中进行。栈计数count是栈中的空闲块数目，栈中的元素是空闲块编号。12.4空闲空间的管理-成组块链接法成组块链接法：将外存中的所有空闲块按50块（或n块）划分为一39每组的第一块用来存放前一组中各块的块号和总块数每组的第一块用来存放前一组中各块的块号和总块数40成组块链接法的分配与释放系统启动时的初始化系统中设立有专用的磁盘空间分配/回收用的内存堆栈区，使得空闲块的分配和释放可在内存进行；同时用于空闲块分配和回收的堆栈有堆栈指针Ptr，Ptr的初值等于该组空闲块的总块数。分配时，Ptr＝Ptr－1；回收时，Ptr＝Ptr＋1；空闲块的分配和释放必须互斥进行启动时将卷资源表中的最后一组的信息读入内存堆栈S中。其中0单元存放总块数，栈顶指针值等于总块数3XYZ堆栈S012345…成组块链接法的分配与释放系统启动时的初始化3XYZ堆栈S041成组块链接法的分配与释放空闲块分配过程：当需要一块空闲块时，首先查看栈中是否count==1：若不是，则弹出栈顶元素N（表示可用磁盘块号）分配出去，--count；若是，弹出栈顶元素N，把空闲块N中的块号读入到栈中；返回空闲块编号N（因为所分配的磁盘块号是栈中最后一个可用盘块号，由于在该盘块中存放了下一组的所有盘块号，于是要先将该块的内容读入栈中，然后才能将该块分配出去）释放过程：被释放空闲块为编号N。查看是否栈已满（如count==50）；若不是，则N入栈，++count；若是，则将栈（包括栈计数）写入到空闲块N，然后把N放入栈顶并置count为1。（说明栈已满，须先将栈中所有盘块号复制到新回收的盘块中，再将新回收盘块的编号放到栈中，成为栈中第一个盘块）成组块链接法的分配与释放空闲块分配过程：当需要一块空闲块时，42成组块链接下组指针本组块数本组块号First成组块链接下组指针本组块数本组块号First43例题1．已知一文件系统采用链式文件方式存储文件，存储设备用成组块链接法管理，每组8块。目前系统的状态如下图：1)一进程欲申请10个磁盘块，请给出其得到的磁盘块号序列，并画出分配后的系统状态；并指出完成本次申请，I/O操作的次数。2）在1）基础上，回收一个以50作为起始块号的具有6个块的文件，画出回收后的系统状态图。并指出完成本次回收，I/O操作的次数。

例题1．已知一文件系统采用链式文件方式存储文件，存储设备用成44系统磁盘块管理堆栈其中0#单元存放总块数堆栈指针值等于总块数第80#磁盘块第88#磁盘块…0518027937847757667577487388887868584838281……89695949392919089……系统磁盘块管理堆栈第80#磁盘块第88#磁盘块…05180245假定磁盘块的大小为1KB，每个盘块号占4个字节，文件索引节点中的磁盘地址明细表如图所示，如何将下列文件的字节偏移量转换为物理地址？1．90002．140003．35000040962284542031111150101367042891568241011109954952……331452…..…3300333308……3274104289156757601331索引节点练习题0123456789101112假定磁盘块的大小为1KB，每个盘块号占4个字节，文件索引节点46解：（1）

字节偏移量为9000，此时逻辑块号为：9000/1024＝8块内偏移量为：9000－8×1024＝808因逻辑块号小于10，因此该块为直接块。其物理盘块号为367，该块中的第808字节即为文件的第9000字节（2）

字节偏移量为14000，此时逻辑块号为：14000/1024＝13块内偏移量为：14000－13×1024＝688因逻辑块号10<13<266，因此该块为一次间接块。 由图可知，一次间接的盘块号为428，从一次间接块中读出盘块号表，查得其物理块号为952，该块中的第688字节即为文件的第14000字节。解：47(3)字节偏移量为350000，此时

逻辑块号为：350000/1024＝341

块内偏移量为：350000－341×1024＝816因逻辑块号266<341<65802，因此该块为二次间接块。由图可知，二次间接块的盘块号为9156。由于一个一次间接块中可容纳256个块号，341-10-256＝75因此，字节偏移量350000在二次间接块的第0个一次间接块的第75个表项中，其盘块号为333，该块中的第816字节即为文件的第350000字节。(3)字节偏移量为350000，此时48有一个磁盘组共有10个盘面，每个盘面上有100个磁道，每个磁道有16个扇区，假定分配以扇区为单位。若使用位示图管理磁盘空间，则位示图需要占用多少空间（16×100×108=2000字节）若空闲文件目录的每个表项占用5个字节，则什么时候空闲文件目录所占空间大于位示图所占空间？20005＝400有一个磁盘组共有10个盘面，每个盘面上有100个磁道，每个磁49本章作业12.112.412.512.6本章作业12.150第12章文件系统实现第12章文件系统实现51磁盘设备驱动程序磁带设备驱动程序基本文件系统（物理I/O层）基本I/O管理程序逻辑I/O堆顺序索引顺序索引哈希用户程序12.1文件系统结构磁盘设备驱动程序磁带设备驱动程序基本文件系统（物理I/O层）52设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的完成基本文件系统（物理I/O层）：处理与磁盘或磁带交换的数据块。注重的是这些块在外存设备中的位置，而并不知道该文件所涉及的数据或结构的内容。基本I/O管理程序：负责所有文件I/O的开始或结束。选择执行文件的I/O设备，外存的分配，I/O缓冲区的指定逻辑I/O：使用户和应用程序能够访问到记录。物理I/O层处理的是数据块，逻辑I/O处理的是文件记录。它提供一种通用的记录I/O的能力。访问方法层：与用户最近的一层。在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。不同的访问方法反映出不同的文件结构和访问数据的不同方法。12.1文件系统结构设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的5312.2目录实现为了实现用户对文件的按名存取，系统要对目录进行查询，找出该文件的文件控制块或者索引节点，进而找到该文件的物理地址。线性列表：顺序检索法。目录文件由目录项构成一个线性表，每个目录项包括文件名和执行数据块的指针。创建新文件：检索该目录，检查是否同名，没有同名，则将新文件的目录项添加到目录末尾删除文件时：检索目录找到该目录项，然后释放分配给它的全部空间，并且清空该项评价：简单易行、速度慢。改善：使用缓存来存放最近用过的目录信息。将目录排序，使用二分检索法，缩短平均查找时间，但会使文件的创建和删除变得复杂12.2目录实现为了实现用户对文件的按名存取，系统要对目录5412.2目录实现哈希表：利用线性表存放目录项，利用哈息表进行检索。哈希表根据文件名得到一个值，并返回一个指向线性列表中的元素的指针。冲突问题：两个文件名相同的哈希值。12.2目录实现哈希表：利用线性表存放目录项，利用哈息表进55文件系统目录目录文件文件名文件类型外存地址…作业目录文件软件目录文件娱乐目录文件F1数据文件根目录文件的内容：文件名文件类型外存地址…C目录文件OS目录文件F1.C数据文件F2.C数据文件OS1数据文件作业目录文件的内容：文件系统目录文件名文件类型外存地址…作业目录文件软件目录文件5612.3

分配方法连续分配链式分配索引分配12.3分配方法连续分配5712.3

分配方法－连续分配连续分配：创建文件时，分配一组连续的块；FAT中每个文件只要一项，说明起始块和文件的长度。对顺序文件有利。优点:

简单。适用于一次性写入的操作支持顺序存取和随机存取，顺序存取速度快所需的磁盘寻道次数和寻道时间最少（因为由于空间的连续性，当访问下一个磁盘块时，一般无需移动磁头，当需要磁头移动，只需要移动一个磁道。缺点:文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）不利于文件插入和删除外部碎片问题（反复增删文件后），使得很难找到空间大小足够的连续块。进行紧缩在创建文件时声明文件的大小。12.3分配方法－连续分配连续分配：创建文件时，分配一组连58磁盘空间的连续分配磁盘空间的连续分配5912.3

分配方法－链式分配链式分配：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。FAT中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。优点：提高了磁盘空间利用率,不存在外部碎片问题有利于文件插入和删除有利于文件动态扩充

缺点：存取速度慢，一般仅适于对信息的顺序存取，不适于随机存取:查找某一个块必须从头开始沿指针进行。可靠性问题，如指针出错；更多的寻道次数和寻道时间链接指针占用一定的空间，将多个块组成簇（cluster），按簇进行分配而不是按块进行分配（增加了磁盘碎片）。12.3分配方法－链式分配链式分配：一个文件的信息存放在若60磁盘空间的链式分配磁盘空间的链式分配61使用FAT－文件分配表法－链接分配的变种，如MS-DOS和OS/2。见教材P312使用FAT－文件分配表法－链接分配的变种，如MS-DOS和O62例题一个已经打开的连续文件，要读取其第10号数据块，则需要____次I/O操作；对于链式文件需要____次I/O操作？设某个文件为链式文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。若要存取文件的第1569逻辑字节处的信息，问要访问哪一个磁盘块？例题一个已经打开的连续文件，要读取其第10号数据块，则需要6312.3文件的分配方法－索引分配索引分配：每个文件在FAT中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在一个单独的块中。FAT中该文件的入口指向这一块。

优点：保持了链接结构的优点,又解决了其缺点：按块分配可以消除外部碎片，按大小可变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式。满足了文件动态增长、插入删除的要求（只要有空闲块）也能充分利用外存空间缺点：较多的寻道次数和寻道时间.索引表本身带来了系统开销，如：内外存空间，存取时间12.3文件的分配方法－索引分配索引分配：每个文件在FAT64磁盘空间的索引分配磁盘空间的索引分配65文件的直接访问：使用连续分配方式文件的顺序访问：采用链接分配对于这些系统，所使用的访问类型必须在文件创建时加以说明。连续分配和索引分配相结合：对于小文件（3块或者4块），采用连续分配，当文件大时，自动切换到索引分配。文件的直接访问：使用连续分配方式连续分配和索引分配相结合：对66索引表指针……文件说明信息逻辑块号物理块号02011522232520152225索引表索引文件的物理结构

索引表组织多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。索引表指针……文件说明信息逻辑块号物理0201152223267举例：文件操作2种方式命令级接口：dir、copy等系统调用：文件系统的程序级接口，用户可以在程序中使用这些系统调用对文件进行各种操作。如建立文件、打开文件、关闭文件、删除文件、读文件、写文件。举例：文件操作2种方式68举例：文件操作建立文件：creat（文件名、文件属性）检查参数合法性：按给定的路径查文件目录，找出用户指定的目录位置，检查目录上是否存在同名文件，若存在则发出错误信息。在指定的目录中找一个空表项作为该文件的目录项，写入指定的文件名。由文件长度确定文件存储所需的物理块数。按规定的物理结构为文件分配存储空间。对连续文件，则分配块连续的空间，对索引文件，现分配索引表用的物理块。在该文件目录项中写入文件的属性、文件的物理块首址等。举例：文件操作建立文件：creat（文件名、文件属性）69举例：文件操作打开文件(open):按指定的文件名检索文件目录，将待访问文件的目录信息读入内存活动文件表中，建立起用户和文件的联系。一旦文件被打开就可以多次使用。直到文件被关闭。举例：文件操作打开文件(open):70多重索引结构大文件：设一个盘块大小为1KB，长度为100KB的文件就需要100个盘块，索引表至少包含100项；若文件大小为1000KB，则相应索引表项要有1000项。设盘块号用4个字节表示，则该索引表至少占用4000B（约4K）。当文件很大时，存在的问题：需要很多的磁盘块索引表很大不能将整个索引表放在内存解决途径：采取多重索引结构多重索引结构大文件：设一个盘块大小为1KB，长度为100KB71索引表指针……文件说明信息记录号物理块号020115222325物理块号索引表20252215…物理块号…物理块号…物理块号…文件信息文件信息……12.3文件的分配方法－多重索引结构索引表指针……文件说明信息记录号物理02011522232572outer-indexindextablefile多重索引结构－图示outer-indexindextablefile多重索73多重索引结构－举例－Unix的索引节点为此，我们可以将文件名和其他信息分开，后者单独形成一个独立的数据结构，称为索引节点（indexnode或者i_node)．对应的目录项就不再是完整的一个FCB,而是由文件名和指向索引节点的指针组成．在引入索引节点之后，一个文件在创建后将立即有与之对应的一个磁盘索引节点．若该文件被调进内存，将立即有对应的一个内存索引结点．为了加速对文件目录的查找，在Unix系统中，将文件名和其它文件说明信息分开，由文件说明信息形成一个称为索引节点的数据结构，而相应的文件目录项只由文件名和对应的索引节点号组成。文件名i节点号多重索引结构－举例－Unix的索引节点为此，我们可以将文件74多重索引结构－举例－Unix的索引节点文件分配以块为基础。按照需要动态进行，不是预定义的。文件在磁盘中的块不一定是连续的。Unix系统为了访问文件，采用索引的方法，索引的一部分保存在该文件的索引节点中。多重索引结构－举例－Unix的索引节点75文件系统索引节点（I节点）文件名索引节点编号gamesmailNewswork文件系统索引节点（I节点）文件名索引节点编号gamesmai76所有类型的Unix文件都是由OS通过索引节点来管理的索引节点是一个控制结构，包含OS所要的关于某个文件的重要信息:文件模式链接计数所有者ID组ID文件大小文件地址（39字节）最后一次被访问最后一次被修改索引节点被修改多重索引结构－举例－Unix的索引节点所有类型的Unix文件都是由OS通过索引节点来管理的多重索引77多重索引结构－举例－Unix的索引节点Unix中通过为每个文件创建一个i节点的方法，巧妙：i节点中包含39个字节的地址信息，这个地址信息被组织成13个3字节的地址或指针。前10个表目是直接索引，指向文件最初的10个数据块。当文件大小小于10块时，可以直接定位到这10个块；第11个表目是一级索引表，指向磁盘中包含下一部分索引的块。第12个表目是二级索引表，第13个表目是三级索引表；对比：在许多文件系统中，如MS－DOS中，使用文件分配表FAT来管理文件的物理盘块：使用FAT的主要问题：整个磁盘的所有文件登记在同一个FAT表中。因此，即使仅打开一个文件，也要使用整个FAT来查找该文件所所分配的盘块，浪费时间。多重索引结构－举例－Unix的索引节点Unix中通过为每个文78多重索引结构课件79在Unix系统中使用1KB的物理块，每个索引表的表目需要用32位来存放物理块地址，因此每个物理块刚好是256个表目，可以映射256个物理块。因此：小文件（≤10块）：只使用直接索引表。中等文件（≤266块）：使用直接索引表与一级索引表大型文件（≤10＋256＋256×256＝65802块）：使用直接索引表与一级和二级索引表。巨型文件：使用全部索引表，可寻址16777216块。Unix的索引节点（i节点）在Unix系统中使用1KB的物理块，每个索引表的表目需要用380举例文件系统采用多级索引结构来搜索文件文件内容。设块长为512字节，每个块号长3字节。如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。（512/3=170)一级索引：170块二级索引：170×170＝28900（块），28900×512＝1450K字节三级索引：170×170×170＝4913000（块），4913000×512＝2456500K字节举例文件系统采用多级索引结构来搜索文件文件内容。设块长为518112.4磁盘空闲空间的管理-位表创建新文件时，系统要为用户的文件分配相应的外存空间；删除一个老文件时，系统要回收该文件所占用的外存空间，供新文件使用。因此，系统需要对外存空闲块进行妥善管理。在分配时，首先知道磁盘中的哪些块是可用的。除了FAT外，还需要一个DAT（diskallocationTable）。实现技术：位图空间块链接法空闲目录法成组块链接法12.4磁盘空闲空间的管理-位表创建新文件时，系统要为用户8212.4空闲空间的管理-位图（位向量）位图（位向量）：使用一个向量，向量中的每位（bit）对应于磁盘中的每一个块（block）0：表示一个空闲块1：表示一个已使用的块。例：2,3,4,5,8,9,10,11,12,13,17,18,25,26,27,…==>0011110011111100011000000111…优点：可以比较容易地找到第一个或一组连续的自由块，适用于任何一种文件分配方法。（而且很多计算机都提供位操作指令）位表小，但长度可变例：对于一个16GB的磁盘，块大小为512字节，则位表占4MB空间。缺点：对于大文件，位图占用内存空间较多，可以按合并4个扇区位一个cluster（簇）的方法。12.4空闲空间的管理-位图（位向量）位图（位向量）：使用83位表的管理：位图可以位于内存或磁盘中，但在磁盘中需要搜索时间，故位表一般位于内存中。即使位于主存中，穷举式搜索会影响文件系统的性能，尤其是当磁盘快满时只剩下很少自由块时问题会很严重。因此，大多数使用位表的文件系统都有一个辅助数据结构，用于汇总位图的子区域的内容。例如：位图可以在逻辑上划分成许多子区域，对于每个子区域，汇总表中包括它的自由块的数目和连续自由块的最大数目。当文件系统需要大量的连续块时，它可以通过扫描汇总表来发现适合的子区域，然后再搜索这个子区域。12.4空闲空间的管理-位图（位向量）位表的管理：12.4空闲空间的管理-位图（位向量）84将文件存储设备上的每个空闲空间看作一个空闲文件，系统为所有空闲文件单独建立一个目录。每个空闲文件在这个目录中占用一个表目。表目的内容包括第一个空闲块的地址（物理块号）、空闲块的数目。如：分配过程：新建文件时，扫描索引，找到符合条件的项，并从表中删除；回收过程：删除文件时，系统回收该文件所占用的盘块，将相应的空闲块的信息填回空闲空间表中，如果释放的区域和和原有空闲区邻接，则将它们合并成一个大的空闲区，记在一个表项中。12.4空闲空间的管理-空闲空间表（索引）将文件存储设备上的每个空闲空间看作一个空闲文件，系统为所有空85适合于连续文件的存放但是，如果有大量的小空闲区，则空闲区表很大，检索效率很低。序号第一个空闲块号空闲块个数物理块号153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-----12.4空闲空间的管理-空闲空间表（索引）适合于连续文件的存放序号第一个空闲块号空闲块物理块号153（86链表：通过使用指向每个空闲区的指针和它们的长度值的一个链将空闲区链接起来。如果需要一个块：从链的头部取出一块，并调整长度；如果是基于可变分区长度分配的，可采用首次适配算法，同样需要调整指针和长度。优点：空间开销小：仅需要一个指向链开始处的指针及第一个分区的长度问题：每次分配一个块时，在将数据写到这个块中之前，需要先读这个块，以发现指向新的第一个空闲块的指针。效率低，开销大。12.4空闲空间的管理-链表链表：通过使用指向每个空闲区的指针和它们的长度值的一个链将空8712.4空闲空间的管理-链表12.4空闲空间的管理-链表88成组块链接法：将外存中的所有空闲块按50块（或n块）划分为一组，用索引表表示；每组的第一块用来存放前一组中各块的块号和总块数；因此，各组间通过链表指针串在一起，构成链表。（把链表和索引相结合。）第一组的块数为49块，最后一组可能不足50块，且最后组的物理块号与总块数只能放在内存的一个专用栈中（如：Unix中超级块中）；对块的分配和释放在栈中进行。栈计数count是栈中的空闲块数目，栈中的元素是空闲块编号。12.4空闲空间的管理-成组块链接法成组块链接法：将外存中的所有空闲块按50块（或n块）划分为一89每组的第一块用来存放前一组中各块的块号和总块数每组的第一块用来存放前一组中各块的块号和总块数90成组块链接法的分配与释放系统启动时的初始化系统中设立有专用的磁盘空间分配/回收用的内存堆栈区，使得空闲块的分配和释放可在内存进行；同时用于空闲块分配和回收的堆栈有堆栈指针Ptr，Ptr的初值等于该组空闲块的总块数。分配时，Ptr＝Ptr－1；回收时，Ptr＝Ptr＋1；空闲块的分配和释放必须互斥进行启动时将卷资源表中的最后一组的信息读入内存堆栈S中。其中0单元存放总块数，栈顶指针值等于总块数3XYZ堆栈S012345…成组块链接法的分配与释放系统启动时的初始化3XYZ堆栈S091成组块链接法的分配与释放空闲块分配过程：当需要一块空闲块时，首先查看栈中是否count==1：若不是，则弹出栈顶元素N（表示可