6.3　例题解答

例1　有128000条学生考试成绩的数据需要存放在磁盘上，并供用户按考号查询成绩。已知磁盘块大小为4KB，一个存储块号占4B，每条学生考试成绩的数据为一个记录。要求所设计的文件结构在进行成绩查询时访问的磁盘次数尽量少。1）请设计存放该批数据的逻辑结构和物理结构。2）计算在该文件结构下每次文件检索平均需要访问的磁盘块数（假设文件的目录已在内存，文件在外存）。每条数据的结构如表6-1所示。

答：1）文件的结构：

文件的逻辑结构采用记录式结构。每条记录有3个字段，由表6-1知，每条记录的长度为32B。128000条记录需要占用的空间大小为：128000×32=4096000B。每个磁盘块可存放4×1024/32=128条记录，则128000条记录需要的磁盘块数为128000/128=1000个。

文件的物理结构可采用一级索引结构。每个索引块最多存放4×1024/4=1024个磁盘块号。

2）在该文件结构下每次文件检索平均需要访问的磁盘块数为2，即第一次访问索引块，第二次访问文件块。

例2　假设某文件包含100个磁盘块，0#～99#，并且FCB已经在内存中。在分别完成下列不同要求时，计算采用连续文件分配方式和链接文件分配方式下，各执行磁盘I/O操作的次数（假定每次读或写一个磁盘块就是一次磁盘操作，并且在连续文件分配方式下，文件头部之前没有空闲块，文件尾部之后有空闲块）。

1）在文件第50块前添加一个磁盘块，但不需要向其中写数据。

2）删除第50块磁盘块。

3）在文件开始处添加一个磁盘块，需要向其中写数据。

答：1）采用连续文件分配方式：100次；采用链接文件分配方式：49次。

2）采用连续文件分配方式：98次；采用链接文件分配方式：2次。

3）采用连续文件分配方式：201次；采用链接文件分配方式：1次。

例3　某操作系统的文件管理采用直接索引和多级索引混合的方式，文件索引表共有16项，其中9项是直接索引项，4项是一级间接索引项，3项是二次间接索引项，假定每个物理块的大小是1KB，每个索引项占2B。请问该文件系统最大的文件可以达到多少KB？

答：每个索引项占2B，故一个物理块最多有1K/2=512个索引项。

该文件系统最大的文件=直接索引+一级间接索引+二级间接索引

=9×1KB+4×512×1KB+3×512×512×1KB

=788489KB

例4　设某文件系统采用两级目录结构，主目录有5个子目录，每个子目录中有20个目录项。在相同目录数的情况下，若采用单级目录结构，所需平均检索目录项数是两级目录结构平均检索目录项数的多少倍?

答：该文件系统一共有5×20=100个目录。

采用单级目录结构所需平均检索目录项数为100/2=50；采用两级结构平均检索目录项数为5/2+20/2=12.5；因此，是50/12.5=4倍。

例5　简述文件连续分配的优缺点。

答：连续分配要求为每一个文件分配一组连续的磁盘块。优点是：1）实现简单，容易进行顺序访问。因为记录每个文件所使用的磁盘块是连续的，只需要记住第一块的磁盘地址和文件的块数。给定了第一块的编号，简单的加法就可以找到任何其他块的编号。2）读操作性能较好。只需要对第一块进行一次寻址，就可以从磁盘上读出整个文件。

然而，连续分配也存在缺点，该方案要求有连续的存储空间，可能会导致磁盘碎片的产生，进而降低磁盘利用率。因为，随着文件的删除，会在磁盘上留下许多空闲块，而新文件都是在先前文件的磁盘结尾写入，这样，随着时间的推移，磁盘最终会被写满。此外，该分配方案需要事先知道文件的长度，不利于文件的增长扩充。

例6　有些档案系统允许磁盘存储将分配在不同级别的粒度。举例来说，一个文件系统可以分配4KB的磁盘空间作为单一的一个4字节的块，或8个512字节的块。如何能利用这种灵活性来提高性能？对自由空间管理做出哪些修改以支持这一功能?

答：此项计划将减少内部分裂。如果文件是5KB，然后可以分配4KB的块和两个相邻的512字节的块。除了维持一个位图的自由块，还要增加一个表记录哪些块是4KB，哪些是512B，并且记录哪些已经分配，哪些是空闲，并且能够在文件建立，删除时分配这些块。

例7　给出操作系统中常见的实现文件静态共享的方式。

答：文件静态共享的方式主要有以下3种：

1）采用全路径名方法访问他人文件，直接通过目录文件找到他人文件，即绕道法。

2）采用目录表间链接，即使用一个用户目录中的表项，直接指向另一个目录中的表项，访问时直接从该目录表项访问，为链接法。

3）采用基本文件目录的组织方式进行共享。该方法将所有文件目录分成两部分，一部分是基本文件目录，包括文件的结构信息、物理块号、存取控制和管理信息等；另一部分是符号文件目录表，包括文件名和文件内部标志符。

例8　试想一个文件系统类似UNIX使用索引分配，读取文件a/b/c需要多少次I/O操作？假设此时没有任何的磁盘块缓存在内存中。

答：一共需要4次。

第一次是加载inode在二级间址块读取一级索引地址，即指向a的地址；

第二次是在一级索引中读取二级索引地址，即指向b的地址；

第三次是在二级索引中读取数据地址，即指向c的地址；

第四次是读取数据，即文件c。