课件2013第六章文件管理

计算机操作系统杨为民m0304abc@126.com汤小丹等编著26.2.3索引文件对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i×L然而，对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则36.2.3索引文件为了解决这一问题，可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于记录该记录的长度L及指向该记录的指针(指向该记录在逻辑地址空间的首址)。由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地实现直接存取。图6-4示出了索引文件(IndexFile)的组织形式。4图6-4索引文件的组织6.2.3索引文件56.2.4索引顺序文件索引顺序文件(IndexSequentialFile)可能是最常见的一种逻辑文件形式。它是顺序文件和索引文件相结合的产物。它将顺序文件中的所有记录分为若干个组(例如，50个记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。索引顺序文件如图6-5所示。6图6-5索引顺序文件6.2.4索引顺序文件76.2.5直接文件和哈希文件1.直接文件对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Keytoaddresstransformation)。组织直接文件的关键，在于用什么方法进行从记录值到物理地址的转换。86.2.5直接文件和哈希文件2．哈希(Hash)文件这是目前应用最为广泛的一种直接文件。它利用Hash函数(或称散列函数)，可将记录键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块，如图6-6所示。例如，若令K为记录键值，用A作为通过Hash函数H的转换所形成的该记录在目录表中对应表目的位置，则有关系A=H(K)。通常，把Hash函数作为标准函数存于系统中，供存取文件时调用。9图6-6Hash文件的逻辑结构6.2.5直接文件和哈希文件2.哈希(Hash)文件106.3外存分配方式6.3.1连续分配1．连续分配方式连续分配(ContinuousAllocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2……。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图6-7示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count文件的第一个盘块号是0，文件长度为2，因此是在盘块号为0和1的两盘块中存放文件1的数据。116.3外存分配方式图6-7磁盘空间的连续分配6.3.1连续分配126.3外存分配方式如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(repackroutine)，由它将磁盘A上的大量文件拷贝到一张软盘B或几张软盘(C，D，…)上，并释放原来的A盘，使之成为一个空闲盘。然后再将软盘B(C，D，…)上的文件拷回A盘上。这种方法能将含有多个文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。136.3外存分配方式2.连续分配的主要优缺点连续分配的主要优点如下：(1)顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的文件中的第i个盘块的内容，就可直接访问b+i号盘块。(2)顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。146.3外存分配方式连续分配的主要缺点如下：(1)要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。(2)必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。即使事先知道文件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存储空间长期地空闲着。156.3.2链接分配1．隐式链接在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。图6-8中示出了一个占用5个盘块的链接式文件。在相应的目录项中，指示了其第一个盘块号是9，最后一个盘块号是25。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块9中设置了第二个盘块的盘块号是16；在16号盘块中又设置了第三个盘块的盘块号1。如果指针占用4个字节，对于盘块大小为512字节的磁盘，则每个盘块中只有508个字节可供用户使用。16图6-8磁盘空间的链接式分配6.3.2链接分配1.隐式链接176.3.2链接分配隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块……，就这样顺序地查找直至第i块。当i=100时，须启动100次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。186.3.2链接分配2．显式链接这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，如图6-9所示。表的序号是物理盘块号，从0开始，直至N-1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT(FileAllocationTable)。19图6-9显式链接结构6.3.2链接分配2.显式链接206.3.4索引分配

1.单级索引分配链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了另外两个问题，即：(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。当磁盘容量较大时，FAT可能要占用数兆字节以上的内存空间，这是令人难以接受的。21图6-11索引分配方式6.3.4索引分配226.3.4索引分配2．多级索引分配当OS为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。23图6-12两级索引分配6.3.4索引分配2.多级索引分配246.3.4索引分配3．混合索引分配方式所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIXSystemⅤ的索引结点中，共设置了13个地址项，即iaddr(0)～iaddr(12)，如图6-13所示。在BSDUNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。25图6-13混合索引方式6.3.4索引分配266.3.4索引分配

(1)直接地址。为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用iaddr(0)-iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据的盘块的盘块号。假如每个盘块的大小为4KB，当文件不大于40KB时，便可直接从索引结点中读出该文件的全部盘块号。276.3.4索引分配

(2)一次间接地址。对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1K个盘块号，因而允许文件长达4MB。286.3.4索引分配(3)多次间接地址。当文件长度大于4MB+40KB时(一次间址与10个直接地址项)，系统还须采用二次间址分配方式。这时，用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达4GB。同理，地址项iaddr(12)作为三次间接地址，其所允许的文件最大长度可达4TB。29对目录管理的要求如下：(1)实现“按名存取”。(2)提高对目录的检索速度。(3)文件共享。(4)允许文件重名。6.4目录管理30图6-14MS-DOS的文件控制块6.4.1文件控制块和索引结点1.文件控制块(1)基本信息类①文件名； ②文件物理位置；③文件逻辑结构； ④文件的物理结构(2)存取控制信息类(3)使用信息类31图6-15UNIX的文件目录文件名索引结点编号文件名1文件名2……6.4.1文件控制块和索引结点2.索引结点1)索引结点的引入326.4.1文件控制块和索引