Chap. 12 HW

1. 选择题与简答题

题目内容

UNIX中的文件系统采用（）。

A 网状文件
B 记录式文件
C 索引文件
D 流式文件

设文件F1当前引用计数值为1，先建立F1的符号链接文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是( )

A 0，1
B 1，2
C 1，1
D 2，1

对磁盘而言，输入输出操作的信息传送单位为 ( ) 。

A. 字符
B. 字
C. 块
D. 文件

计算机系统中，屏幕显示分辨率为640×480，若要存储一屏256彩色的图像，需要( )KB存储空间。
什么是文件的物理结构？有哪几种组织方式？
什么是文件的逻辑结构？有哪几种组织方式？

1.1 UNIX中的文件系统采用什么？

答案：

$D \text{ 流式文件}$

UNIX/Linux 普通文件一般被看成连续的字节流，也就是 byte stream。

它不要求文件内部必须是一条条记录，也不要求文件内部必须有复杂的树形、网状结构。

所以 UNIX 文件的逻辑结构通常说成：

$流式文件$

因此答案选：

$D$

1.2 符号链接、硬链接与引用计数

答案：

$C \ 1，1$

初始条件：

文件 $F1$ 当前引用计数为：

$1$

这说明目前只有目录项 $F1$ 指向该文件的 inode。

第一步：建立 $F1$ 的符号链接文件 $F2$ 。

符号链接，也叫软链接。

它本质上是一个新的特殊文件，文件内容保存的是目标路径名，例如保存“F1”这个路径。

所以建立符号链接不会让 $F1$ 的 inode 引用计数增加。

此时：

$F1$ 的引用计数仍为：

$1$

而 $F2$ 自己作为一个独立文件，也有自己的 inode，自己的引用计数为：

$1$

第二步：建立 $F1$ 的硬链接文件 $F3$ 。

硬链接会让新的目录项 $F3$ 直接指向 $F1$ 原来的 inode。

所以 $F1$ 和 $F3$ 实际上是同一个文件实体的两个名字。

此时原文件 inode 的引用计数从：

$1$

变成：

$2$

第三步：删除 $F1$ 。

删除 $F1$ 只是删除目录项 $F1$ ，并不是立刻删除文件内容。

因为 $F3$ 仍然指向原来的 inode。

所以原 inode 的引用计数从：

$2$

变成：

$1$

因此：

$F3$ 对应的原文件 inode 引用计数为：

$1$

而 $F2$ 是符号链接文件，它本身没有被删除，所以它自己的引用计数仍为：

$1$

但是要注意： $F2$ 保存的是路径 $F1$ ，现在 $F1$ 被删了，所以 $F2$ 会变成悬空符号链接。

最终：

$F2 = 1$

$F3 = 1$

答案选：

$C$

1.3 磁盘输入输出操作的信息传送单位

答案：

$C \text{ 块}$

磁盘 I/O 通常不是按字符传输，也不是按字传输，而是按块传输。

一个磁盘块通常包含多个字节，文件系统读写磁盘时，基本单位是：

$block$

也就是：

$块$

所以答案选：

$C$

1.4 640×480，256色图像需要多少KB？

答案：

$300KB$

屏幕分辨率为：

$640 \times 480$

所以总像素数为：

$640 \times 480 = 307200$

256 色表示每个像素有 256 种可能颜色。

因为：

$256 = 2^8$

所以每个像素需要：

$8bit = 1B$

总存储空间为：

$307200 \times 1B = 307200B$

换算成 KB：

$1KB = 1024B$

所以：

$307200 / 1024 = 300KB$

最终答案：

$300KB$

1.5 什么是文件的物理结构？有哪几种组织方式？

文件的物理结构是指文件在外存，也就是磁盘上的实际存放方式。

换句话说，它关心的是：

文件被分成哪些磁盘块？

这些磁盘块在磁盘上如何分布？

操作系统如何记录这些块的位置？

Stallings 第 12 章在 secondary storage management 中讲到，文件在二级存储上由一组 blocks 组成，操作系统或文件管理系统负责给文件分配这些块。

常见的文件物理组织方式主要有三种：

1. 连续分配 Contiguous Allocation

文件占用一组连续的磁盘块。

例如：

$20, 21, 22, 23, 24$

这些块连续存放同一个文件。

优点：

顺序访问速度快。
随机访问也方便。
文件分配表只需要记录起始块号和文件长度。

如果文件从块 $b$ 开始，要访问第 $i$ 块，则物理位置可以直接算：

$b + i - 1$

缺点：

容易产生外部碎片。
文件增长困难。
创建文件时可能需要提前知道文件最大长度。

2. 链式分配 Chained Allocation

文件由多个磁盘块组成，每个块中保存指向下一个块的指针。

例如：

$9 \rightarrow 16 \rightarrow 1 \rightarrow 25 \rightarrow 7$

这些块不必连续。

优点：

不要求连续空间。
文件增长比较方便。
不容易产生外部碎片。

缺点：

随机访问效率低。
要访问第 $i$ 块，必须从头沿链找。
指针损坏可能导致后续块丢失。
不符合局部性，连续读文件时可能在磁盘上跳来跳去。

3. 索引分配 Indexed Allocation

为每个文件建立一个索引块，索引块中保存该文件所有数据块的地址。

例如索引块中保存：

$7, 20, 3, 88, 15$

表示文件数据分别存放在这些磁盘块中。

优点：

支持直接访问。
支持顺序访问。
不要求文件块连续。
相比链式分配，随机访问效率更高。

缺点：

索引块本身需要额外空间。
小文件也可能有索引开销。
大文件可能需要多级索引。

Stallings 认为索引分配解决了连续分配和链式分配的许多问题，因此是很常见的文件分配方式。

1.6 什么是文件的逻辑结构？有哪几种组织方式？

文件的逻辑结构是指从用户或应用程序角度看到的文件内部组织方式。

它关心的是：

文件中的数据在逻辑上如何排列？

是字节流？

是一条条记录？

是否有索引？

是否按关键字顺序排列？

Stallings 将 file organization 定义为由访问方式决定的记录逻辑结构。

常见逻辑结构可以分两套说法。

国内教材常见分类

流式文件

文件被看作连续的字节流。

UNIX/Linux 普通文件就是典型例子。

记录式文件

文件由一条条记录组成。

例如学生信息文件、工资表文件、成绩表文件。

记录式文件还可以分为：

定长记录文件

变长记录文件

Stallings 第 12 章常见分类

Stallings 讲了五种基本 file organization：

堆文件 Pile

数据按照到达顺序直接加入文件。

特点：

结构最简单；
适合收集数据；
查找效率较低。

顺序文件 Sequential File

记录按某个关键字顺序排列。

例如按学号递增存放学生记录。

优点：

顺序处理效率高；
适合批处理。

缺点：

插入和删除不方便；
随机查找效率不够高。

索引顺序文件 Indexed Sequential File

既保留顺序文件的顺序结构，又建立索引。

优点：

可以顺序访问；
也可以通过索引较快查找。

索引文件 Indexed File

通过索引来访问记录。

适合需要频繁随机查找的场景。

直接文件或散列文件 Direct / Hashed File

通过散列函数根据关键字直接计算记录存放位置。

例如：

$位置 = h(key)$

优点：

按关键字访问速度很快。

缺点：

可能有冲突；
不适合顺序遍历。

One scheme to avoid the problem of pre-allocation versus waste or lack of contiguity is to allocate portions of increasing size as the file grows. For example, begin with a portion size of one block, and double the portion size for each allocation. Consider a file of n records with a blocking factor of F, and suppose that a simple one-level index is used as a file allocation table.

a. Give an upper limit on the number of entries in the file allocation table as a function of F and n.

b. What is the maximum amount of the allocated file space that is unused at any time?

中文意思：

为了避免预分配造成浪费，或者文件块不连续的问题，可以随着文件增长，按越来越大的 portion 分配空间。

例如：

第一次分配 1 块；

第二次分配 2 块；

第三次分配 4 块；

第四次分配 8 块；

之后每次翻倍。

设文件有 $n$ 条记录，阻塞因子为 $F$ ，即每个磁盘块可以存放 $F$ 条记录。假设使用简单的一级索引作为文件分配表。

a. 求文件分配表中的索引项数量上限。

b. 任意时刻已经分配但未使用的文件空间最大是多少？

答案和讲解

2.a 文件分配表项数上限

阻塞因子 $F$ 表示：

每个磁盘块可以存放：

$F$

条记录。

文件共有：

$n$

条记录。

所以需要的数据块数为：

$B = \lceil n / F \rceil$

这里 $B$ 表示实际至少需要多少个磁盘块。

按题目规则，文件空间分配为：

第一次：

$1$

块。

第二次：

$2$

块。

第三次：

$4$

块。

第四次：

$8$

块。

第 $k$ 次：

$2^{k-1}$

块。

前 $k$ 次分配的总块数为：

$1 + 2 + 4 + \cdots + 2^{k-1}$

这是等比数列，和为：

$2^k - 1$

为了容纳文件，必须满足：

$2^k - 1 \ge B$

也就是：

$2^k - 1 \ge \lceil n / F \rceil$

移项：

$2^k \ge \lceil n / F \rceil + 1$

两边取以 2 为底的对数：

$k \ge \log_2(\lceil n / F \rceil + 1)$

所以文件分配表项数上限为：

$\boxed{k = \lceil \log_2(\lceil n / F \rceil + 1) \rceil}$

2.b 最大未使用空间

已经分配但未使用的空间主要出现在刚刚分配一个新 portion 的时候。

因为每次新分配的 portion 都比前一次大一倍，所以最大的浪费发生在最后一次，也就是最大 portion 刚分配出来的时候。

如果文件共用了 $k$ 个索引项，那么最后一次分配的 portion 大小是：

$2^{k-1}$

个块。

所以按块数计，最大未使用空间不超过：

$\boxed{2^{k-1} \text{ 块}}$

其中：

$k = \lceil \log_2(\lceil n / F \rceil + 1) \rceil$

如果换成记录容量：

$\boxed{2^{k-1}F \text{ 条记录容量}}$

如果认为“刚分配后马上写入一条记录”，那么最大未使用记录槽位约为：

$\boxed{2^{k-1}F - 1}$

另一种更精确的最终文件浪费

如果题目问的是“最终文件有 $n$ 条记录时实际浪费多少”，则总分配块数为：

$2^k - 1$

总分配记录容量为：

$F(2^k - 1)$

实际使用记录数为：

$n$

所以最终未使用记录槽位为：

$\boxed{F(2^k - 1) - n}$

但是本题问的是“at any time”的最大未使用空间，所以更常用答案是：

$\boxed{2^{k-1} \text{ 块}}$

第 2 题最终答案

$\boxed{\lceil \log_2(\lceil n / F \rceil + 1) \rceil}$

令：

$k = \lceil \log_2(\lceil n / F \rceil + 1) \rceil$

最大未使用空间为：

$\boxed{2^{k-1} \text{ 块}}$

或：

$\boxed{2^{k-1}F \text{ 条记录容量}}$

若刚写入触发分配的那条记录后再统计，则为：

$\boxed{2^{k-1}F - 1 \text{ 条记录容量}}$

3. 计算最后一个块未装满造成的空间浪费百分比

题目内容

Ignoring overhead for directories and file descriptors, consider a file system in which files are stored in blocks of 16K bytes. For each of the following file sizes, calculate the percentage of wasted file space due to incomplete filling of the last block: 41,600 bytes; 640,000 bytes; 4.064,000 bytes.

中文意思：

忽略目录和文件描述符开销，假设文件系统以 $16K$ 字节为一个块存储文件。对于下面三种文件大小，计算由于最后一个块未装满而造成的空间浪费百分比：

$41600B$

$640000B$

$4064000B$

注意：题目中的 $4.064,000$ 通常应理解为 $4,064,000$ 字节。

答案和讲解

块大小为：

$16K = 16 \times 1024 = 16384B$

计算步骤：

需要块数：

$\lceil 文件大小 / 块大小 \rceil$

实际分配空间：

$需要块数 \times 块大小$

浪费空间：

$实际分配空间 - 文件大小$

浪费百分比：

$\frac{浪费空间}{实际分配空间} \times 100\%$

3.1 文件大小为 $41600B$

需要块数：

$\lceil 41600 / 16384 \rceil = \lceil 2.539 \rceil = 3$

实际分配空间：

$3 \times 16384 = 49152B$

浪费空间：

$49152 - 41600 = 7552B$

浪费百分比：

$\frac{7552}{49152} \times 100\% \approx 15.36\%$

答案：

$\boxed{15.36\%}$

3.2 文件大小为 $640000B$

需要块数：

$\lceil 640000 / 16384 \rceil = \lceil 39.0625 \rceil = 40$

实际分配空间：

$40 \times 16384 = 655360B$

浪费空间：

$655360 - 640000 = 15360B$

浪费百分比：

$\frac{15360}{655360} \times 100\% \approx 2.34\%$

答案：

$\boxed{2.34\%}$

3.3 文件大小为 $4064000B$

先算：

$16384 \times 248 = 4063232B$

还剩：

$4064000 - 4063232 = 768B$

所以需要再多一个块。

需要块数：

$249$

实际分配空间：

$249 \times 16384 = 4079616B$

浪费空间：

$4079616 - 4064000 = 15616B$

浪费百分比：

$\frac{15616}{4079616} \times 100\% \approx 0.383\%$

答案：

$\boxed{0.383\%}$

第 3 题最终答案

$41600B$ ：

$\boxed{15.36\%}$

$640000B$ ：

$\boxed{2.34\%}$

$4064000B$ ：

$\boxed{0.383\%}$

$6$

每片有两个记录面，所以记录面总数为：

$6 \times 2 = 12$

存储区域内径：

$22cm$

存储区域外径：

$33cm$

道存储密度：

$40 \text{ 道}/cm$

内层位存储密度：

$400b/cm$

转速：

$3000r/min$

4.1 共有多少柱面？

柱面数等于每个记录面上的磁道数。

注意题目给的是内径和外径，不是半径。

所以先求半径：

内半径：

$22 / 2 = 11cm$

外半径：

$33 / 2 = 16.5cm$

存储区域宽度：

$16.5 - 11 = 5.5cm$

道密度为：

$40 \text{ 道}/cm$

所以每个记录面上的磁道数为：

$5.5 \times 40 = 220$

因此柱面数为：

$\boxed{220}$

4.2 盘组总存储量

题目给的是内层位存储密度。

一般这种题按内层磁道容量作为每条磁道容量来算，因为外层磁道虽然周长更长，但通常为了保持统一格式，按内层容量确定每道容量。

内层磁道周长为：

$\pi \times 22 = 22\pi cm$

内层位密度为：

$400b/cm$

所以每条磁道可存储位数为：

$22\pi \times 400 = 8800\pi b$

每个记录面有：

$220$

条磁道。

共有：

$12$

个记录面。

所以盘组总存储量为：

$220 \times 12 \times 8800\pi b$

计算：

$220 \times 12 \times 8800\pi = 23232000\pi b$

近似为：

$23232000\pi \approx 72985480b$

换算为字节：

$72985480 / 8 \approx 9123185B$

约等于：

$9.12MB$

如果按二进制 MiB 计算：

$9123185 / 1024 / 1024 \approx 8.70MiB$

所以盘组总存储量为：

$\boxed{23232000\pi b}$

约为：

$\boxed{72985480b}$

约为：

$\boxed{9.12MB}$

4.3 平均等待时间

这里的平均等待时间通常指平均旋转等待时间，也叫平均旋转延迟。

转速为：

$3000r/min$

换成每秒转数：

$3000 / 60 = 50r/s$

所以一圈时间为：

$1 / 50s = 0.02s = 20ms$

平均等待时间为半圈时间：

$20ms / 2 = 10ms$

所以平均等待时间为：

$\boxed{10ms}$

第 4 题最终答案

柱面数：

$\boxed{220}$

盘组总存储量：

$\boxed{23232000\pi b \approx 72985480b \approx 9.12MB}$

平均等待时间：

$\boxed{10ms}$

$7$

直接地址索引：

$4$

一级间接地址索引：

$2$

二级间接地址索引：

$1$

地址项大小：

$4B$

索引块大小：

$1KB = 1024B$

数据块大小：

$1KB = 1024B$

5.1 一个索引块能存放多少个地址项？

每个地址项大小为：

$4B$

一个索引块大小为：

$1024B$

所以一个索引块能存放的地址项数量为：

$1024 / 4 = 256$

也就是说，一个一级间接索引块可以指向：

$256$

个数据块。

5.2 直接地址索引能表示多少数据？

有 4 个直接地址项。

每个直接地址项直接指向 1 个数据块。

所以直接地址索引可以表示：

$4$

个数据块。

容量为：

$4 \times 1KB = 4KB$

5.3 一级间接地址索引能表示多少数据？

有 2 个一级间接地址项。

每个一级间接地址项指向一个索引块。

每个索引块中有：

$256$

个地址项。

每个地址项指向一个数据块。

所以一级间接索引可以表示的数据块数为：

$2 \times 256 = 512$

容量为：

$512 \times 1KB = 512KB$

5.4 二级间接地址索引能表示多少数据？

二级间接结构是：

inode 中的二级间接地址项

指向一个一级索引块

这个一级索引块中的每个地址项又指向一个二级索引块

每个二级索引块再指向数据块

所以一个二级间接地址项可以表示的数据块数为：

$256 \times 256 = 65536$

容量为：

$65536 \times 1KB = 65536KB$

5.5 单个文件最大长度

总数据块数为：

$4 + 2 \times 256 + 256 \times 256$

计算：

$4 + 512 + 65536 = 66052$

所以最大文件长度为：

$66052 \times 1KB = 66052KB$

换算成字节：

$66052 \times 1024 = 67637248B$

换算成 MiB：

$66052 / 1024 \approx 64.50MiB$

第 5 题最终答案

可表示的单个文件最大长度为：

$\boxed{66052KB}$

也就是：

$\boxed{67637248B}$

约等于：

$\boxed{64.50MiB}$

6. UNIX/Linux 文件访问偏移 263168 字节处数据需要几次间接？

题目内容

一个UNIX/Linux文件，如果一个盘块的大小为1KB，每个盘块占4个字节，那么，若进程欲访问偏移为263168字节处的数据，需经过几次间接？

注意：

题目中的“每个盘块占4个字节”应理解为“每个盘块号/地址项占4个字节”。

答案和讲解

已知：

盘块大小：

$1KB = 1024B$

每个盘块号，也就是每个地址项大小：

$4B$

目标偏移量：

$263168B$

6.1 先求该偏移位于第几个逻辑块

逻辑块号从 0 开始编号。

目标逻辑块号为：

$\lfloor 263168 / 1024 \rfloor$

因为：

$1024 \times 257 = 263168$

所以该偏移正好位于逻辑块：

$257$

的起始位置。

如果从 1 开始数，它就是第：

$257 + 1 = 258$

个数据块。

6.2 一个间接索引块可以存多少个块号？

一个索引块大小为：

$1024B$

每个块号大小为：

$4B$

所以一个索引块可以存放块号数：

$1024 / 4 = 256$

也就是说，一个一级间接索引块可以指向：

$256$

个数据块。

6.3 判断需要几次间接

UNIX/Linux inode 通常使用：

直接地址项

一级间接地址项

二级间接地址项

三级间接地址项

Stallings 中 UNIX inode 也采用 direct pointers 加 single、double、triple indirect pointers 的方式。

常见 UNIX/Linux inode 有 12 个直接块地址。

直接块覆盖逻辑块：

$0 \sim 11$

一级间接块可以再覆盖：

$256$

个数据块。

所以一级间接覆盖逻辑块：

$12 \sim 267$

因为：

$12 + 256 - 1 = 267$

目标逻辑块号为：

$257$

它落在：

$12 \sim 267$

范围内。

因此它只需要通过一级间接索引访问。

所以需要经过：

$\boxed{1 \text{ 次间接}}$

补充说明

即使某些传统 UNIX 使用 10 个直接块地址，结论仍然一样。

如果有 10 个直接块：

直接块覆盖：

$0 \sim 9$

一级间接覆盖：

$10 \sim 265$

目标逻辑块：

$257$

仍然在一级间接范围内。

所以答案依然是：

$\boxed{1 \text{ 次间接}}$

第 6 题最终答案

访问偏移：

$263168B$

对应逻辑块号：

$257$

需要经过：

$\boxed{1 \text{ 次间接}}$

也就是：

$\boxed{一级间接索引}$

汇总答案

第 1 题

UNIX 文件系统采用：

$\boxed{D \text{ 流式文件}}$

F2 和 F3 的引用计数分别为：

$\boxed{C \ 1，1}$

磁盘 I/O 信息传送单位：

$\boxed{C \text{ 块}}$

一屏 256 色图像存储空间：

$\boxed{300KB}$

文件物理结构：

$\boxed{\text{文件在磁盘上的实际存放方式}}$

常见方式：

$\boxed{\text{连续分配、链式分配、索引分配}}$

文件逻辑结构：

$\boxed{\text{用户角度看到的文件内部组织方式}}$

常见方式：

$\boxed{\text{流式文件、记录式文件、堆文件、顺序文件、索引顺序文件、索引文件、直接/散列文件}}$

第 2 题

$\boxed{\lceil \log_2(\lceil n / F \rceil + 1) \rceil}$

令：

$k = \lceil \log_2(\lceil n / F \rceil + 1) \rceil$

最大未使用空间为：

$\boxed{2^{k-1} \text{ 块}}$

或：

$\boxed{2^{k-1}F \text{ 条记录容量}}$

第 3 题

$41600B$ ：

$\boxed{15.36\%}$

$640000B$ ：

$\boxed{2.34\%}$

$4064000B$ ：

$\boxed{0.383\%}$

第 4 题

柱面数：

$\boxed{220}$

总存储量：

$\boxed{23232000\pi b \approx 72985480b \approx 9.12MB}$

平均等待时间：

$\boxed{10ms}$

第 5 题

最大文件长度：

$\boxed{66052KB}$

也就是：

$\boxed{67637248B}$

约为：

$\boxed{64.50MiB}$

第 6 题

需要：

$\boxed{1 \text{ 次间接}}$

即：

$\boxed{\text{一级间接索引}}$