> For the complete documentation index, see [llms.txt](https://book.bsdcn.org/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://book.bsdcn.org/4.3bsd/di-san-bu-fen-io-xi-tong/7.8.-wen-jian-xi-tong-ming-zi-de-zhuan-huan.md).

# 7.8 文件系统名字的转换

剖析研究表明，在内核中，近四分之一的时间花在路径名翻译例程 `namei()` 上——把路径名翻译成 inode。`namei()` 负责对名字的每个成分做访问检查，以核实当前进程是否具备搜索沿途目录、并按该进程请求的方式访问目标文件的必要权限。`namei()` 由两个嵌套循环组成：外层循环对每个路径名成分走一圈；内层循环在目录中线性搜索特定成分。

用两种缓存技术降低名字翻译的成本。第一种是减少 `namei()` 内层循环的迭代次数，依据是许多程序顺序扫描目录。为改进具有这种行为的进程的性能，系统为每个进程保存最近翻译的路径名中最后成分的目录偏移。如果进程接下来请求翻译的名字在同一目录中，搜索就从找到上一个名字的偏移处开始（而不是从目录开头）。换目录会使缓存失效。对于顺序遍历含 *n* 个文件的目录的程序，搜索时间从 *O*(*n*²) 降到 *O*(*n*)。

展示缓存最大效果的快速基准：对一个含 600 个文件的目录做 `ls -l`。加上每进程缓存，该测试的系统时间减少 85%。不幸的是，最大效果远高于平均效果：缓存命中时有效率 90%，但只有约 25% 的名字能用上它。改进有限的另一个原因是：虽然 `namei()` 本身花的时间大减，但花在它调用的例程上的时间反而更多了——缓存未命中会让同一个目录被访问两次，一次从中部搜到尾部，一次从头搜到中部。

对少量名字的频繁请求，用最近名字翻译的缓存处理效果最好。4.3BSD 的缓存以名字为键，再加上包含该名字的目录的 inode 号与设备号；每个表项都关联一个指针，指向 inode 表中的对应表项。这个缓存的作用是省去 `namei()` 的内层循环：对每个路径名成分，`namei()` 先在最近名字翻译缓存里找需要的名字；名字存在时，目录搜索就可以省去。

需要考虑的一个问题是名字缓存如何持有对 inode 表的引用。正常情况下，进程持有硬引用（hard reference）：把所引用 inode 的引用计数加一。系统只重用引用计数为零的 inode，因此硬引用能保证 inode 指针持续有效。但名字缓存若持有硬引用，它的大小就会被限制在 inode 表大小的某个比例之内——必须为新文件留出一些空闲 inode；持有硬引用还会让内核其他部分无法确认某个设备或文件是否被独占使用。上述原因说明，只要不打算影响 inode 缓存方案的行为，使用硬引用就不可行。因此，名字缓存改持软引用（soft reference），由权能（capability）保护——一个保证唯一的 32 位整数。当所有编号都用尽时，就把所有仍然有效的权能清洗掉，然后从头开始编号。清洗是可行的，因为在内核内存中很容易找到所有权能。名字缓存登记一个表项时，就把该 inode 的权能复制到这个表项里。inode 被重用时，会换发一个新权能。名字缓存命中时，就把表项的权能与它所引用的 inode 的权能比较；两者不符，该表项即失效。由于名字缓存只持有软引用，它的大小就可以不受 inode 表大小的限制。使用权能的最后一个好处是：能让某个 inode 的所有缓存名字失效，而无须搜索整个缓存——给 inode 换发一个新权能即可。

1984 年，伯克利一台通用分时系统在早 8 点到晚 8 点的 12 小时里做了 500,000 到 1,000,000 次名字翻译。两个缓存的性能统计表明，正是高命中率带来了大幅的性能改进：名字缓存命中率 70% 到 80%，目录偏移缓存命中率 5% 到 15%，两者合计的命中率几乎总是 85%。加上这两个缓存后，名字翻译占系统时间的比例从 25% 降到 10% 以下。全系统缓存既缩短了 `namei()` 所调用例程的耗时，也缩短了 `namei()` 自身的耗时（因为需要访问和搜索的目录少了）；有意思的是，尽管单次调用的实际时间下降，`namei()` 自身所占系统时间的百分比反而升高——因为内核花的总时间变少了，较小的绝对时间就成了较大的百分比。

## 习题

7.1 目录项为什么不得跨块？

7.2 硬链接为什么不得跨文件系统？

7.3 描述含绝对路径名的符号链接与含相对路径名的符号链接在解释上的差别。

7.4 解释为什么没有特权的用户不得对目录建硬链接，却可以对目录建符号链接。

7.5 怎样用硬链接访问那些改用符号链接就访问不到的文件？

7.6 系统如何识别符号链接造成的环？提出另一种环检测方案。

7.7 4096 字节块、1024 字节片的文件系统上，一个 31,200 字节的文件分配到多少块和多少片？4096 字节块、512 字节片的文件系统上呢？假设 inode 只有 6 个而不是 12 个直接块指针，再答这两个问题。

7.8 逻辑块与物理块有什么区别？这一区分为什么重要？

7.9 配额与 3.8 节描述的文件大小资源限制有什么不同？

7.10 为什么每个柱面组的信息放在距本柱面组开头各不相同的偏移处？

7.11 32 位字长、最小片 512 字节的机器上，三级间接块为什么用处不大？

7.12 什么是平方散列？描述它在文件系统中的用途，以及为什么用它。

7.13 解释 4.3BSD 文件系统为什么保留 5% 到 10% 的空闲空间。如果空闲空间保留量设为零，会出现什么问题？

7.14 inode 的分配策略为什么与数据块的不同？

7.15 缓冲区头为什么与存放缓冲区内容的内存分开分配？

7.16 最大文件系统块大小如何影响缓冲区高速缓存？

7.17 给出两条理由，说明旧文件系统把基本块大小从 512 字节增加到 1024 字节后，系统吞吐为何提高一倍多。

7.18 描述 4.2BSD 用来改进传统 UNIX 文件系统性能的两种方法。

\*7.19 为什么要有 AGE 链和 LRU 链，而不是所有缓冲区都在 LRU 链上管理？

\*7.20 文件名可以长达 255 字符。全系统名字缓存如何实现才能避免每个表项都分配 255 字节？

\*7.21 进程读大文件时，文件的块会完全填满缓冲区高速缓存，冲掉所有其他内容；系统中其他进程的所有文件系统访问就都得去磁盘上取。描述一种控制缓冲区高速缓存清洗的算法。

\*7.22 讨论两种做法之间的权衡：把内存划给缓冲区高速缓存，和把内存留给虚拟内存系统去满足调页请求。给出一种在缓冲池与虚拟内存系统之间调配内存的策略。

\*7.23 为确保崩溃后（除不可恢复的硬件错误外）文件系统总能确定地恢复，哪些文件系统操作必须同步做？

\*7.24 文件若必须分配在磁盘上一整块连续的空间里，会出现什么问题？要考虑多进程、随机访问以及文件中有空洞所带来的问题。

**7.25** inode 本可作为目录项的一部分动态分配，实际上却在创建文件系统时静态分配。为什么采用后一种做法？

## 参考文献

Elz, 1984. K. R. Elz, “Resource Controls, Privileges, and Other MUSH,” *USENIX Association Conference Proceedings*, pp. 183–191 (June 1984).

Knuth, 1975. D. Knuth, *The Art of Computer Programming, Volume 3—Sorting and Searching*, Addison-Wesley, Reading, MA (1975).

McKusick & Kowalski, 1986. M. K. McKusick & T. J. Kowalski, “Fsck—The UNIX File System Check Program,” pp. 5:1–22 in *UNIX System Manager's Manual, 4.3 Berkeley Software Distribution, Virtual VAX-11 Version*, USENIX Association, Berkeley, CA (1986).

Nevalainen & Vesterinen, 1977. O. Nevalainen & M. Vesterinen, “Determining Blocking Factors for Sequential Files by Heuristic Methods,” *The Computer Journal* **20**(3), pp. 245–247 (August 1977).

Trivedi, 1980. K. Trivedi, “Optimal Selection of CPU Speed, Device Capabilities, and File Assignments,” *Journal of the ACM* **27**(3), pp. 457–473 (July 1980).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://book.bsdcn.org/4.3bsd/di-san-bu-fen-io-xi-tong/7.8.-wen-jian-xi-tong-ming-zi-de-zhuan-huan.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.