1. 文件分配方式

文件的物理结构是指一个文件在外存上的存储组织形式，与外存分配方式有关。是指如何为文件分配磁盘块。常用的磁盘空间分配方 法有三种：连续分配、链接分配和索引分配。有的系统对三种方法都支持，但是更普遍的是一个系统只提供一种方法的支持。

①连续分配。

连续分配是最简单的磁盘空间分配策略，连续分配方法要求每个文件在磁盘上占有一组连续的磁盘区域。磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。用户必须在分配前说明待创建文件所需的存储空间大小，然后系统查找空闲区的管理表格，查看是否有足够大的空闲区供其使用。如果有，就给文件分配所需的存储空间；如果没有，该文件就不能建立，用户进程必须等待。

连续分配

连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快。缺点在于，文件长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加， 就需要大量移动盘块。此外，反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似)，并且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。

②链接分配

链接分配是釆取离散分配的方式，消除了外部碎片，故而显著地提高了 磁盘空间的利用率；又因为是根据文件的当前需求，为它分配必需的盘块，当文件动态增长时，可以动态地再为它分配盘块，故而无需事先知道文件的大小。此外，对文件的增、删、改也非常方便。链接分配又可以分为隐式链接和显式链接两种形式。

• 隐式连接：该实现方案用于链接物理块的指针隐式地放在每个物理块中，目录项中有指向索引顺序文件的第一块盘块和最后一块盘块的指针，此外每个盘块中都含有指向下一盘块的指针。目录包括文件第一块的指针和最后一块的指针。

隐式链接分配的缺点在于无法直接访问盘块，只能通过指针顺序访问文件，以及盘块指针消耗了一定的存储空间。隐式链接分配的稳定性也是一个问题，系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

隐式链接

• 显式链接：该实现方案用于链接物理块的指针显式存放在内存的一张链接表中，每个磁盘设置一张链接表。 该表在整个磁盘仅设置一张，每个表项中存放链接指针，即下一个盘块号。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中，故称该表为文件分配表（File Allocation Table, FAT)。

显示链接

③索引分配

链接分配解决了连续分配的外部碎片和文件大小管理的问题。但是，链 接分配不能有效支持直接访问（FAT除外），需要按照链接指针依次进行查找，这样查找十分缓慢。索引分配解决了这个问题，它把每个文件的所有的盘块号都集中放在一起构成索引块（表）。

索引分配

索引分配方式不仅支持直接访问，而且不会产生外部碎片，文件长度受限制的问题也得到了解决。每个文件都有其索引块，这是一个磁盘块地址的数组。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第i块，通过索引块的第i个条目的指针来查找和读入所需的块。

索引分配支持直接访问，且没有外部碎片问题。其缺点是由于索引块的分配，增加了系统存储空间的开销。索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件。可以釆用以下机制来处理这...

课后习题

 

1. 【2009统考真题】下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。

A. 连续结构

B. 索引结构

C. 链式结构且磁盘块定长

D. 链式结构且磁盘块变长

【答案】B

【解析】文件的物理结构包括连续、链式、索引三种，其中链式结构不能实现随机访问，连续结构的文件不易于扩展。因此随机访问且易于扩展是索引结构的特性。

 

2. 【2010统考真题】设文件索引结点中有7 个地址项，其中4 个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4B，若磁盘索引块和磁盘数据块大小均为256B，则可表示的单个文件最大长度是（ ）。

A. 33KB                       B. 519KB .

C. 1057KB                     D. 16516KB

【答案】C

【解析】每个磁盘索引块和磁盘数据块大小均为256B，每个磁盘索引块有256/4 = 64个地址项。因此，4个直接地址索引指向的数据块大小为4×256B； 2个一级间接索引包含的直接地址索引数为2×(256/4),即其指向的数据块大小为2×(256/4)×256B。1个二级间接索引所包含的直接地址索引数为(256/4)×(256/4),即其所指向的数据块大小为(256/4)×(256/4)×256B。因此，7个地址项所指向的数据块总大小为 4×256 + 2×(256/4)×256 + (256/4)×(256/4)×256 = 1082368B = 1057KB。

 

3. 【2013统考真题】为支持CD-ROM中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（ ）。

A .连续结构                   B .链式结构

C .直接索引结构               D .多级索引结构

【答案】A

【解析】为了实现快速随机播放，要保证最短的查询时间，即不能选取链表和索引结构，因此连续结构最优。

 

4. 【2013统考真题】若某文件系统索引结点（inode）中有直接地址项和间接地址项, 则 下列选项中，与单个文件长度无关的因素是（  ）。

A .索引结点的总数                        B .间接地址索引的级数

C .地址项的个数                          D .文件块大小

【答案】A

【解析】四个选项中，只有A 选项是与单个文件长度无关的。

 

5. 【2015统考真题】在文件的索引结点中存放直接索引指针10个，一级和二级索引指针各 1个。磁盘块大小为1KB，每个索引指针占4B。若某文件的索引结点已在内存中，则把该文件偏移量（按字节编址）为 1234和 307400处所在的磁盘块读入内存，需访问的磁盘块个数分别是（ ）。

A. 1, 2                              B. 1, 3

C. 2, 3                              D. 2, 4

【答案】B

【解析】10个直接索引指针指向的数据块大小为10xlKB = 10KB。每个索引指针占4 B ,则每个磁盘块可存放1KB/4B = 256个索引指针，一级索引指针指向的数据块大小为256×1KB = 256KB,二 级索引指针指向的数据块大小为256×256×1KB = KB = 64MB。

按字节编址，偏移量为1234时，因1234B<10KB,由直接索引指针可得到其所在的磁盘块地址。文件的索引结点已在内存中，因此地址可直接得到，因此仅需1次访盘即可。

偏移量为307400时，因 10KB + 256KB < 307400B < 64M B,可知该偏移量的内容在二级索引指针所指向的某个磁盘块中，索引结点已在内存中，因此先访盘2次得到文件所在的磁盘块地址，再访盘1次即可读出内容，共需3次访盘。

 

6. 【2015统考真题】文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的32~127号块中，每个盘块占1024B，盘块和块内字节均从0 开始编号。假设要释放的盘块号为409612，则位图中要修改的位所在的盘块号和块内字节序号分别是（ ）。

A. 81, 1                               B. 81, 2

C. 82, 1                                D. 82, 2

【答案】C

【解析】盘块号= 起始块号+⌊盘块号/(1024×8) ⌋ = 32 + ⌊409612/(1024×8) ⌋ = 32 + 50 = 82 ,这里问的是块内字节号而不是位号，因此还需除以8 (1B = 8位 )，块内字节号=⌊ (盘块号％ (1024×8))/8 ⌋= 1。

 

7. 【2019统考真题】下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（ ）。

I . 位图          Ⅱ.索引结点        Ⅲ.空闲磁盘块链        Ⅳ.文件分配表（FAT）

A . 仅 I、II            B . 仅 I、Ⅲ、IV       C . 仅 I、III        D . 仅 II、Ⅲ、IV

【答案】B

【解析】传统文件系统管理空闲磁盘的方法包括空闲表法、空闲链表法、位示图法和成组链接法，I、Ⅲ正确。文件分配表(FAT)的表项与物理磁盘块一一对应，并且可以用一个特殊的数字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的(当然，规定用-3，-4 来表示也是可行的)。因此文件分配表(FAT)不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的磁盘块，操作系统可以通过FAT对文件存储空间进行管理，IV 正确。索引结点是操作系统为了实现文件名与文件信息分开而设计的数据结构，存储了文件描述信息，索引结点属于文件目录管理部分的内容？Ⅱ错误。

 

8. 【2011统考真题】某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。

1） 在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？说明理由。为定位文件数据块，需要在FCB中设计哪些相关描述字段？

2） 为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？说明理由。

【解析】

1) 在磁盘中连续存放(采取连续结构)，磁盘寻道时间更短，文件随机访问效率更高；在FCB中加入的字段为〈起始块号，块数〉或<起始块号，结束块号〉。

2) 将所有的FCB集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB对应的块，可减少磁头移动和磁盘I/O访问次数。

 

9. 【2016统考真题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT 中。

1） 假定目录树如下图所示，各文件占用的簇号及顺序如下表所示, 其中dir，dir1是目录, file1, file2是用户文件。请给出所有目录文件的内容。

2） 若 FAT的每个表项仅存放簇号，占2B ,则 FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？

3） 系统通过目录文件和FAT实现对文件的按名存取，说明filel的 106, 108两个簇号分别存放在FAT的哪个表项中。

4 ） 假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？

【解析】

1 )两个目录文件dir和dir1的内容如下表所示。

2） FAT的最大长度为2¹⁶×2B = 128KB,文件的最大长度是2¹⁶×4KB = 256MB。

3） file1的簇号106存放在FAT的 100号表项中，簇号108存放在FAT的 106号表项中。

4） 需要访问目录文件dirl所在的48号簇及文件file 1 的 106号簇。

 

10. 【2012统考真题】某文件系统空间的最大容量为4TB （1TB = 2⁴⁰B） , 以磁盘块为基本分配单位。磁盘块大小为IKB。文件控制块（FCB）包含一个512B的索引表区。请回 答下列问题：

1） 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件的最大长度是多少字节？

2） 假设索引表区采用如下结构：第0~7字节采用<起始块号，块数〉格式表示文件创建时预分配的连续存储空间。其中起始块号占6 B ,块数占2 B ,剩余504B采用直接索引结构，一个索引项占6B，则可支持的单个文件的最大长度是多少字节？为使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

【解析】

1） 文件系统中所能容纳的磁盘块总数为4TB/1KB = 2³²。要完全表示所有磁盘块，索引项中的块号最少要占32/8 = 4B。而索引表区仅采用直接索引结构，因此512B的索引表区能容纳512B/4B = 128个索引项。每个索引项对应一个磁盘块，所以该系统可支持的单个文件最大长度是128×1KB = 128KB。

2） 这里考查的分配方式不同于我们熟悉的三种经典分配方式，但题目中给出了详细的解释。所求的单个文件最大长度一共包含两部分：预分配的连续空间和直接索引区。连续区块数占2 B ,共可表示2¹⁶个磁盘块，即2²⁶B。直接索引区共504B/6B =84个索引项。所以该系统可支持的单个文件最大长度是2²⁶B+84KB.为了使单个文件的长度达到最大，应使连续区的块数字段表示的空间大小尽可能接近系统最大容量4TB。分别设起始块号和块数占4 B ,这样起始块号可以寻址的范围是2³²个磁盘块，共4TB，即整个系统空间。同样，块数字段可以表示最多2³²个磁盘块，共4TB。

 

11. 【2014统考真题】文件F 由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录。请回答下列问题，并说明理由。

1） 若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均

有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？ F 的文件

控制块内容会发生哪些改变？

2） 若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成

上述插入操作需要访问多少次磁盘块？若每个存储块大小为1KB,其中4B存放链接

指针，则该文件系统支持的文件最大长度是多少？

【解析】

1） 系统采用顺序分配方式时，插入记录需要移动其他的记录块，整个文件共有200条记录,要插入新记录作为第30条，而存储区前后均有足够的磁盘空间，且要求最少的访问存储块数，则要把文件前29条记录前移，若算访盘次数，移动一条记录读出和存回磁盘各是一次访盘，29条记录共访盘58次，存回第30条记录访盘1次，共访盘59次。

F 的文件控制区的起始块号和文件长度的内容会因此改变。

2） 文件系统采用链接分配方式时，插入记录并不用移动其他记录，只需找到相应的记录，修改指针即可。插入的记录为其第30条记录，因此需要找到文件系统的第29块，一共需要访盘29次，然后把第29块的下块地址部分赋给新块，把新块存回磁盘会访盘1次,然后修改内存中第29块的下块地址字段，再存回磁盘，一共访盘31次。

4B共 32位，可以寻址2³² = 4GB块存储块，每块的大小为1KB，即1024B，其中下块地址部分占4 B，数据部分占1020B，因此该系统的文件最大长度是4GB×l020B = 4080GB。

 

12. 【2018统考真题】某文件系统采用索引结点存放文件的属性和地址信息，簇大小为4KB。每个文件索引结点占64B ,有 11个地址项，其中直接地址项8 个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题：

1） 该文件系统能支持的最大文件长度是多少？ （给出计算表达式即可）

2） 文件系统用1M （1M = 2²⁰）个簇存放文件索引结点，用512M个簇存放文件数据。若一个图像文件的大小为5600B,则该文件系统最多能存放多少个这样的图像文件？

3） 若文件的大小为6KB，文件F2的大小为40KB，则该文系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？

【解析】

1） 簇大小为4KB ,每个地址项长度为4 B ,因此每簇有4KB/4B = 1024个地址项。最大文件的物理块数可达8 + 1×1024 + 1×1024² + 1×1024³每个物理块（簇）大小为4KB ,因此 最大文件长度为（8 + 1×1024 + 1×1024² + 1×1024³）×4KB = 32KB + 4MB + 4GB + 4TB。

2） 文件索引结点总个数为1Mx4KB/64B = 64M, 5600B的文件占2 个簇，512M个簇可存放 的文件总个数为512M/2 = 256M。可表示的文件总个数受限于文件索引结点总个数，因此能存储64M个大小为5600B的图像文件

3） 文件F1的大小为6KB <4KB×8 = 32KB，因此获取文件F l的最后一个簇的簇号只需要访问索引结点的直接地址项。文件F2大小为40KB, 4KB×8<40KB <4KB×8 + 4KB×1024，因此获取F2的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。