（7 分）在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法”。假设目录文件存放在磁盘上，每个盘块有 512 字节。文件控制块占 64 字节，其中文件名占 8 个字节。通常将文件控制块分解成两部分，第一部分占 16 字节（包括文件名和文件内部号），第二部分占 48 字节（包括文件内部号和文件其他描述信息）。

（1）假设某一目录文件共有 254 个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数。（访问每个文件的概率相同） （2）一般地，若目录文件分解前占用 $n$ 个盘块，分解后改用 $m$ 个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。（假设 $m$ 和 $n$ 个盘块中都正好装满）

文件概念

[tag_link]

**【答案】** （1）分解前平均访问磁盘次数为 $\frac{2080}{127}$ 次；分解后平均访问磁盘次数为 $\frac{695}{127}$ 次。 （2）访问磁盘次数减少的条件是 $m<n-2$ 。

**【解析】** （1）分解前：每个盘块 512 字节，文件控制块（FCB）占 64 字节，每块可存放 $512÷64=8$ 个 FCB。目录文件共有 254 个 FCB，需占用 32 个盘块（前 31 块每块 8 个 FCB，第 32 块有 6 个 FCB）。查找时顺序扫描盘块，平均访问磁盘次数为找到目标 FCB 所在盘块的平均读取盘块数。设盘块索引 $i$ 从 1 到 32，目标 FCB 在第 $i$ 块的概率为该块 FCB 数除以 254，因此平均次数为：

$$\frac{8\times (1+2+\cdots +31)+6\times 32}{254}=\frac{8\times 496+192}{254}=\frac{4160}{254}=\frac{2080}{127}$$

分解后：第一部分（文件名和内部号）占 16 字节，每块可存放 $512÷16=32$ 个第一部分。254 个第一部分需占用 8 个盘块（前 7 块每块 32 个，第 8 块有 30 个）。检索第一部分时平均访问磁盘次数类似计算：

$$\frac{32\times (1+2+\cdots +7)+30\times 8}{254}=\frac{32\times 28+240}{254}=\frac{1136}{254}=\frac{568}{127}$$

找到第一部分后，还需访问第二部分获取完整 FCB，需 1 次磁盘访问，因此总平均次数为：

$$\frac{568}{127}+1=\frac{695}{127}$$

（2）分解前占用 $n$ 个盘块（装满），平均访问磁盘次数为 $\frac{n+1}{2}$ 。分解后占用 $m$ 个盘块存放第一部分（装满），平均访问第一部分次数为 $\frac{m+1}{2}$ ，加上访问第二部分的 1 次，总平均次数为 $\frac{m+1}{2}+1$ 。访问磁盘次数减少的条件为：

2m+1+1«/span>2n+1

化简得 m+3«/span>n+1 ，即 m«/span>n−2 。