11.2 What are the advantages of the variation of linked allocation that uses a FAT to chain together the blocks of a file ?

链接分配的一个重要变种是文件分配表(FAT)的使用。这个简单而有效的磁盘空间分配方法用于 MS-DOS 操作系统。每个卷的开头部分的磁盘用于存储该表。在该表中,每个磁盘块都有一个条目,并可按块号来索引。FAT 的使用与链表相同。目录条目包含文件首块的块号。通过这个块号索引的表条目包含文件的下一块的块号。这条链会继续下去,直到最后一块;而最后一块的表条目的值为文件结束值。未使用的块用 0 作为表条目的值来表示。为文件分配一个新块只要简单找到第一个值为 0 的 FAT 条目,用新块的地址替换前面文件结束值,用文件结束值替代 0。由块 217、618、339 组成的文件的 FAT 结构如图 3 所示。

文件分配表 图 3 文件分配表

如果不对 FAT 采用缓存,FAT 分配方案可能导致大量的磁头寻道时间。磁头必须移到卷的开头,读入 FAT,找到所需块的位置,再移到块本身的位置。在最坏的情况下,每块都需要移动两次。优点是改善了随机访问时间;因为通过读入 FAT 信息,磁头能找到任何块的位置。

11.3 Consider a system where free space is kept in a free-space list.

a. Suppose that the pointer to the free-space list is lost. Can the system reconstruct the free-space list? Explain your answer.

可以重建。搜索磁盘,找到未使用的空间建立列表。

b. Consider a file system similar to the one used by UNIX with indexed allocation. How many disk I/O operations might be required to read the contents of a small local file at /a/b/c? Assume that none of the disk blocks is currently being cached.

读取 /, a, b, c 所在磁盘块,共需四次。如果缓存命中的话只需要一次。

c. Suggest a scheme to ensure that the pointer is never lost as a result of memory failure.

使用日志文件系统,指针持久化到磁盘。

11.6 Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions:

a. How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)

b. If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?

设 z 为起始块号

连续分配

a

  • 令 逻辑地址 / 512 = x + remainder_y
  • 物理块号 = z + x
  • y 为块内偏移。

b 一次,因为可以直接计算出

链式分配

  • 令 逻辑地址 / 511 = x + remainder_y
  • 顺着链表找到第 X+1 个物理块
  • Y+1 作为块内偏移

b 4 次,因为是第 4 个逻辑块

索引分配

  • 令 逻辑地址 / 512 = x + remainder_y
  • 块号为 index-map
  • y 为块内偏移。

b 2 次,第一次寻找块号,第二次根据块号和块内偏移找到