第5章.md

作业：第5章

2022年10月4日，2022年10月22日，2022年10月28日。

$$ \newcommand\SI[2]{#1\ \mathrm{#2}} % siunitx (package) $$

1 名词解释

文件目录

记录所有文件的名字及其控制块的映射表。

文件控制块

包含文件的说明、管理控制信息的一段数据。它唯一标志了文件。

文件逻辑结构

用户界面的文件组织方式。它一定是连续的，内部可以是无结构字节流，也可是有结构记录。

链接（结构）文件

一种文件物理结构，它允许逻辑连续的文件存储于不连续的物理块，每个物理块中除了文件内容，还存放下一物理块的地址。（最后一块除外）

2 分解文件控制块

在实现文件系统时，每个盘块为512B。假设目录文件存放在磁盘上，文件控制块占64B。

为加快文件目录的检索速度，可利用“文件控制块分解法”。通常将文件控制块分解成两部分，第1部分占10B（包括文件名和文件内部号），其中文件名占8B；第二部分占56B（包括文件内部号和文件其他描述信息）。

假设某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件中的某一文件控制块的平均访问磁盘次数。

• 分解前

  所有 FCB 所占盘块数 = FCB 数量 × 每个 FCB 的大小 / 每个盘块的大小 $= 254 \times \SI{64}{B} / \SI{512}{B} = 31.75 \approx 32$。

  查找 FCB 需要依次遍历这些盘块。若认为目标 FCB 均匀分布于这些盘块，则平均访问次数为 $32 / 2 = 16$ 次。

• 分解后

  同上计算所有 FCB（只含第一部分）所占盘块数（只需将 $\SI{64}{B}$ 改为 $\SI{10}{B}$），得 $4.96\ldots \approx 5$。

  此时要先遍历这些盘块（平均 $5/2 = 2.5$ 次），然后根据找到文件内部号直接访问第二部分（1 次）。因此总平均次数为 $2.5 + 1 = 3.5$ 次。

3 逻辑结构

a 直接访问和顺序访问文件的记录是固定长度的，都是S字节。求记录N的第一个字节的逻辑位置。

都从 1 开始。

逻辑结构总是连续，故位置为 $(N-1) S + 1$（字节）。

b 程序刚刚从顺序访问的文件中读取第1个记录。接下来将要读第10个记录。此程序应该要读多少个记录，才能读入第10个记录？

再读 9 个记录（第 2–10 个）会读入第 10 个记录。

c 如何将 b 中的顺序访问改为直接访问，结果是什么？

下次读取直接就可是第 10 个记录。

4 物理结构

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

若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？F的文件控制块内容会发生哪些改变？

存在两类操作。

• 将 F 之前的记录向前挪一条。

  “前后均有足够的空闲磁盘空间”，F 更靠前，向前扩充更方便。

  每次挪动读写各一次，需要挪动原来的第 1–29 条记录，共 29 条。因此这类操作需要 $2 \times 29 = 58$ 次访问。

• 写入 F。

  需要一次访问。

所以一共需要 59 次访问。

---

文件控制块内容基本不变，只有总大小（或长度）、最后修改时间等改变。

若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块？

1. 找到原有第 29 条记录。

   需要从头遍历，访问 29 次。

2. 将 F 的指针改为原有第 30 条记录（地址存储在原有第 29 条记录），访问一次。

3. 将原有第 29 条记录的指针改为 F，访问一次。

所以共需 31 次访问。

5 索引节点

考虑由索引节点表示的UNIX文件的组织。在每个索引节点中，假定有12个直接块指针，分别有一个一级、二级和三级间接指针。此外，假定系统盘块的大小为8KB。如果盘块指针用32位表示，其中8位用于标识物理磁盘号，24位用于标识磁盘块号，那么：

1. 该系统支持的最大文件大小是多少？

   • 盘块 $\SI{8}{kB}$，每个指针 $\SI{32}{b}$，故每盘块可存 $\SI{8}{kB} / \SI{32}{b} = \SI{2}{k}$ 个盘块的地址。
   • 每个 $n$ 级指针可存 $\qty(\SI{2}{k})^n$ 个盘块的地址。

   所以每个索引可存 $12 \times \qty(\SI{2}{k})^0 + \qty(\SI{2}{k})^1 + \qty(\SI{2}{k})^2 + \qty(\SI{2}{k})^3 = \SI{8}{G} + \SI{4}{M} + \SI{2}{k} + 12$ 个盘块的地址。

   又，每盘块 $\SI{8}{kB}$，故单文件最大大小为二者之积，等于 $\SI{64}{TB} + \SI{32}{GB} + \SI{16}{MB} + \SI{96}{kB} \approx \SI{64}{TB}$。

2. 假定主存中除了文件索引节点外没有别的信息，访问在位置12 423 956的字节时，需要访问磁盘多少次？

   关键是看这个字节所在盘块对应几级指针。沿索引访问次数就是级数，总次数再加上实际访问内存那一次。

   认为按地址顺序、题目描述顺序依次填充索引，那么这一字节位于的盘块号是 $\SI{12,423,956}{B} / \SI{8}{kB} = 1516.59\ldots \approx 1516$。12 个直接块指针负责 0–11 块；一级间接指针负责 11 – $(\SI{2}{k} +10)$ 块，1516 块位于它这一段。

   因此需要访问两次。