> 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.3-bsd-unix-cao-zuo-xi-tong-she-ji-yu-shi-xian/di-er-bu-fen-jin-cheng/5.13.-jiao-huan.md).

# 5.13 交换

交换虽然一般力求避免，4.3BSD 仍有几种场合用它来解决调页系统不易解决的问题：或者是严重的资源短缺，或者是用交换实现最高效的操作。下列任一情况发生时，4.3BSD 就做交换：

* 系统内存短缺到调页进程腾内存的速度跟不上需求。例如，多台大进程跑在内存不足以容纳它们最小工作集的机器上，就可能发生内存短缺。
* 系统页映射碎片化，新进程或增长的进程无法为页表分配空间。页表通常不收缩；但进程换出再换入后，多余的空间会被收回。
* 进程完全不活动超过 20 秒。否则这些进程会占着几页内存外加页表的页。

交换有自愿与非自愿之分。自愿交换（如系统页映射碎片化时）由被换出的进程自己发起。非自愿交换则由一个称为交换进程（swapper）的进程发起。

交换操作把进程整个从主存中移走，包括进程页表、数据和栈段中尚不在交换空间的页、user 结构以及正文段。正文段的处理与数据和栈段不同，因为它可能被其他进程共享。

**交换进程**

非自愿交换操作由交换进程——0 号进程——完成。这是系统启动时创建的第一个进程。交换进程的策略体现在 `sched()` 例程中：必要时换出进程，也在内存可用、进程就绪时把进程换回。任一时刻，交换进程处于三种状态之一：

1. **空闲**：没有就绪的被换出进程，也没有理由换出任何东西。这是正常状态。
2. **换入中**：至少一个可运行进程被换出，`sched()` 设法为它找内存。
3. **换出中**：系统缺内存或缺系统页表空间，或者没有足够内存换入进程。此时 `sched()` 挑选进程换出，直到内存短缺缓解。

正常情况下，调页能维持足够的空闲内存，交换进程不活动。进程必须换出自己、或空闲内存变低时，交换进程被唤醒。

**挑选换入的进程**

被换出的可运行进程多于一个时，交换进程的第一个任务就是决定换入谁。这个决定可能影响是否换出另一个进程。每个被换出的进程按以下因素获得一个优先级：

* 被换出的时长
* 被换出时的大小
* 它的 `nice` 值，以及上次运行以来睡眠的时长

一般说来，被换出最久的进程、或因不可运行而被换出的进程最先换入。较大的进程优先级较低，以计入换入换出它们所需的更长时间：既然已经花了功夫把一个大进程换出去腾内存，就该让它在外面待得够久才有收益。选中进程后，交换进程检查空闲内存是否够把它换入。起初要求有进程换出前占用的那么多内存（进程表项中的 `p_swrss`）；进程被换出超过 10 秒后，有一半那么多内存就换入。内存够，进程就回内存。user 结构和页表立即换入，其余的工作集靠从交换设备请求调页装入。因此，承诺给进程的内存并非全都立即用上。为换入的进程预留内存，交换进程设置一个名为 `deficit` 的全局变量，值为最近换入进程预留的页数，人为制造内存需求。设置亏空（deficit）是为了计入进程重启的预期内存量，免得当只够换入一个进程的一块内存可用时，被换出的进程全体涌回。于是，为调度交换与调页而视为空闲的内存量是 `freemem` 减去 `deficit`。这些进程会逐渐把页调入内存，`deficit` 须相应递减。系统不去逐页记账，而是让 `deficit` 每秒递减 10%，直到归零。

**非自愿交换**

系统没有足够内存换入进程，或因别的原因缺内存时，会考虑从内存换出一个进程。下列任一条件下，系统开始换出进程：

* 系统页映射碎片化到无法为某个进程分配页表。
* 至少有两个可运行进程，过去 5 秒和 30 秒的平均空闲内存都低于期望值（`desfree`，见 5.12 节调页参数），且调页速率过高、或短期平均内存低于 `minfree`。
* 一个被换出的进程就绪可运行，而内存中找到一个已睡眠至少 20 秒的进程；或被换出的进程已在外至少 10 秒，而被选来换出的进程已在内存至少 20 秒。

这些准则尽量避免交换，直到调页守护进程明显无法保持足够的空闲内存。交换一旦开始，先试图换出睡眠的或大而低优先级的作业。若仍需继续交换，被选中换出的进程应在外面待得够久，使交换物有所值。最后，有资格被交换的进程应轮流进内存，免得哪个进程被完全冻结。

这些准则以及下一小节所述的准则，多数是在学术环境的大型（50 到 80 个同时用户）分时系统上调优出来的。

**挑选换出的进程**

交换进程决定非自愿地从内存换出一个进程后，必须挑选牺牲者。用两条准则：进程在内存中睡眠的时长，以及进程的大小。若能找到睡眠超过 20 秒（`maxslp`，即认定睡眠时间“很长”的界限）的进程，睡眠最久的被换出。这样的进程最不可能用好所占的内存，因此即使小也换出。否则必须换出一个可运行或最近运行过的进程。交换的目的是腾内存，因此进程大小是挑选的主要准则。所用算法选出内存中可供换出的四个最大进程。（做裸 I/O 直出进程地址空间的进程、或正在对其地址空间做扩展、退出等操作的进程，可以锁定在内存。）四者之中，在内存驻留最久的被选中换出。空闲内存仍低时，系统会轮番换出这四个最大的进程，每换入一个就再换出一个。当然，若内存短缺缓解，所有进程都会换回内存，内存使用重新交给调页控制。

**换出**

进程按下列步骤换出内存：

1. 把进程的 user 结构映射进内核虚拟内存
2. 为 user 结构和页表分配交换空间
3. 释放映像的正文部分
4. 强制换出进程数据和栈节中全部驻留页
5. 把页表写入交换空间
6. 把 user 结构和内核栈写入交换空间
7. 释放 user 结构
8. 释放页表

这些操作多数在考察 `exit` 时讲过（见 5.10 节）；映射别的进程 user 结构的虚拟内存窗口在 5.7 节和 5.12 节讨论过。交换操作有两个这样的窗口，由 `Xswapmap` 和 `Xswap2map` 映射。窗口使用期间锁定，因为可能同时发生不止一次换出。

除被换出之外，进程的 user 结构和页表始终在内存。进程整个虚拟映像的交换空间是预分配的，但 user 结构和页表的区域只在进程被换出时分配。分配可能失败导致换出失败，因此交换分配在过程早期做。分配单独一块连续的交换空间，大到装下 user 结构、数据页表和栈页表。交换区地址存在 proc 结构元素 `p_swaddr` 中。user 结构放在区域开头，页表紧随其后。注意正文页表另行处理，因为正文页表至多一份副本。

进程最终换回时，知道它大概要吃多少内存很有用。因此换出前把进程当前的驻留集大小记入 proc 结构。随后开始移除进程。过程中唯一微妙的部分与页表的处理有关：需要扩展页表却因系统页表碎片化而无法扩展的进程，预期它回到内存时页表会按新尺寸重排。类似地，做 `exec` 的进程若新映像比原来小，页表需要压缩。两种情况下，交换代码都必须按需细心重排和/或压缩页表。

页表换出后，user 结构写入交换空间并释放。与 `exit()` 中一样，释放当前进程的 user 结构要求系统提升处理器优先级堵住内存分配，直到下一次进程上下文切换。换出若由交换进程执行，无须特别的预防措施。最后，进程的页表资源按 `exit()` 同样的方式释放。当前进程换出自己时，处理器优先级仍高，页表的页不会被重新分配；一旦处理器切换到新进程，优先级回落，内存分配恢复。进程的 SLOAD 标志清除，表示进程不驻留内存；必要时把进程从可运行进程队列摘除。被换出的进程要等换回内存后才能运行。

**换入**

被换出的进程在交换进程的控制下换回内存。过程是换出的逆操作。更简单之处在于它不必理会用户地址空间中的页——进程靠缺页把它们调回。步骤如下：

1. 锁住进程的共享正文，防止变化。
2. 为页表分配资源。
3. 为 user 结构分配内存，从交换空间读回 user 结构。
4. 把页表读入内存。
5. 释放 user 结构和页表的交换空间。
6. 挂接正文区，必要时把正文页表换入。
7. 进程若可运行，放回运行队列。

进程若可运行，它在被换出时已从运行队列摘除，或因 `wakeup()` 调用而未加入——运行队列只装驻留内存的可运行进程。因此刚换入的进程若现在可运行，必须加入运行队列。进程同时重新标记为驻留。进程若在页表扩展期间换出了自己，会给自己标上 SSWAP 标志，表示首次运行时应走替代返回。之所以要替代返回，是因为换出前保存的程序计数器显示不出交换已经完成、进程已重新就绪。该标志置位期间，替代返回的位置（`u.u_ssave`）先标记好，然后清除 SSWAP。进程首次运行时，`resume()` 例程会安排一次非局部跳转（`longjmp()`）。

换入完成后，进程像任何其他进程一样可以运行，只是没有驻留页。它将靠缺页把所需页调入，类似 `exec` 之后的运行，只是多数页很可能从交换设备调入。

**正文映像的交换**

进程换入换出时，正文部分的处理与数据、栈节不同，因为它可能与其他进程共享。某种程度上，交换期间对正文映像的操作沿袭 `exit` 和 `exec` 期间的动作。进程被换出时，释放它对正文映像的使用，但内存中其他使用该映像的进程可能使它免于被换出。正文映像有两个引用计数：一个计持有正文映像引用的进程数，另一个计其中当前驻留内存的进程数——内存引用计数。进程被换出时，只递减映像的内存引用数。递减后内存引用数仍非零，系统只需把当前进程从使用该映像的进程链表摘除。内存引用数归零，则内存中已无使用该映像的进程，正文映像可以换出。“修改过”（尚未写入交换空间）的驻留页推入正文交换区，方式与脏数据和栈页的换出相同。页表若尚未写入交换空间，也一并换出；这种换出只做一次。

共享正文的进程换回内存时，正文像 `exec` 时一样重新挂接：正文要么已在内存，页表直接复制；要么页表从交换空间的副本换入内存。正文映像的页按需经缺页调入：正文页表换出前若驻留，则从交换空间调回；否则从文件系统调入。两种情况下，正文映像的页若自释放后未被重用，都可以在正文页缓存中找到。

## 习题

5.1 一台机器支持虚拟内存是什么意思？支持虚拟内存通常需要哪些硬件设施？

5.2 请求调页虚拟内存系统中，调页与交换是什么关系？同一系统同时提供两种机制可取吗？能为“两者都提供”给出替代方案吗？

5.3 哪三个策略刻画调页系统？其中哪个策略通常对调页系统的性能没有影响？

5.4 为什么 4.3BSD 的虚拟内存系统不适合支持具有大型稀疏地址空间的进程？

5.5 是什么技术变化使 4.3BSD 在主存中缓存比以往系统更多的数据变得合理？

5.6 4.3BSD 为什么要在 VAX 上仿真 PTE 的引用位？它如何仿真？

5.7 说出核心映射表的三种功能。

5.8 为什么内核栈和 user 结构被显式放在 VAX 虚拟地址空间的 P1 区？

5.9 要从装入映像填充的页，其 PTE 如何识别？PTE 中存有哪类专属这种表项的信息？

5.10 无效页的 PTE 中页号非零时，下列哪些说法一定为真？

a. 该页是按需填充页。

b. 该页可能正在写往磁盘。

c. 该页已分配到主存。

d. 正在该页上仿真引用位。

5.11 4.3BSD 为什么为正文段保留单独的页表副本，而不是只引用一份？

5.12 描述用于管理每进程动态段的交换空间方案的一个缺点。 *提示*：考虑虚拟内存很大的进程按小步扩展时会发生什么。

5.13 什么是影子交换映射？`fork` 系统调用的实现中如何使用它们？

5.14 什么是写时复制？多数 UNIX 应用中，`fork` 系统调用之后几乎立即跟上 `exec`。为什么这一行为使在 `fork` 实现中采用写时复制特别有吸引力？

5.15 解释为什么 `vfork` 系统调用永远会比精巧的 `fork` 实现更高效。

5.16 进程扩展数据段大小时，它真的得到更多主存了吗？虚拟地址空间中新页创建的是什么类型的 PTE？

5.17 进程退出时，它的全部页未必立即放上内存空闲表；解释为什么。

5.18 4.3BSD 虚拟内存系统假设内存到内存复制的开销与直接从文件系统读取相仿。要从文件系统调入的块可能还在文件系统缓冲区高速缓存时，调页前先把缓冲区写盘。对当今某些类型的虚拟内存计算机，这一假设可能远不成立。说出至少一类这样的计算机。对这类计算机，还有哪些假设可能不同？

5.19 什么是成组（klustering）？虚拟内存系统中哪里用到了它？

5.20 4.3BSD 为什么把全局 CLOCK 算法改成用两个时钟指针？

5.21 调页守护进程在虚拟内存系统中起什么作用？调页守护进程用到了哪项普通用户进程没有的设施？

5.22 粘滞位在 4.3BSD 中为什么不再有用？

5.23 给出启动交换的两条理由。

5.24 进程换出前为什么要记录它当前的驻留集大小？

5.25 给出进程试图扩展页表时会被换出的两个条件。

\*5.26 为什么进程的页表除交换操作外从不收缩？

\*5.27 考虑改用两个时钟指针的全局 CLOCK 算法。改变两针之间的距离可取吗？可取的话，给出这样做的算法；不可取的话，解释原因。改变针距期间需要什么预防措施？调页设备过载限制扫描速率时，算法会受到什么影响？

\*5.28 影响选择软件页大小（或成簇因子）的因素有哪些？什么样的机器上较大的页更高效？什么样的机器上较小的页更高效？

\*5.29 考虑分布在多个磁盘分区上的交换空间。分区大小悬殊对交换块交错方案有什么影响？描述一种比 4.3BSD 所用方案更能利用磁盘空间的替代方案。

**5.30** 4.3BSD 虚拟内存系统为进程的全部地址空间分配足够的交换空间。有些机器（如工作站）的物理内存比交换空间还多，使交换空间预分配不可取。设计一种按需分配交换空间的每进程交换映射。这种方案可能出现什么问题？

**5.31** 讨论在虚拟内存体系结构与 VAX 截然不同的计算机上实现类似 4.3BSD 的虚拟内存系统。例如，考虑一台有“反转页表”的机器——每个硬件页有一个寄存器、存放该页所表示的虚拟地址的页表。

## 参考文献

Babaoglu et al., 1979. Ö. Babaoglu, W. N. Joy, & J. Porcar, “Design and Implementation of the Berkeley Virtual Memory Extensions to the UNIX Operation System,” Technical Report, CS Division, EECS Dept., University of California, Berkeley, CA (December 1979).

Babaoglu, 1981. Ö. Babaoglu, “Virtual Storage Management in the Absence of Reference Bits,” PhD Thesis, CS Division, EECS Dept., University of California, Berkeley, CA (1981).

Babaoglu & Joy, 1981. Ö. Babaoglu & W. N. Joy, “Converting a Swap-Based System to Do Paging in an Architecture Lacking Page-Referenced Bits,” *Proceedings of the Eighth Symposium on Operating Systems Principles*, pp. 78–86 (December 1981).

Belady, 1966. L. A. Belady, “A Study of Replacement Algorithms for Virtual Storage Systems,” *IBM Systems Journal* **5**(2), pp. 78–101 (1966).

Coffman & Denning, 1973. E. G. Coffman, Jr. & P. J. Denning, *Operating Systems Theory*, Prentice-Hall, Englewood Cliffs, NJ (1973).

Corbato, 1968. F. J. Corbato, “A Paging Experiment with the Multics System,” Project MAC Memo MAC-M-384, Massachusetts Institute of Technology, Boston, MA (July, 1968).

DEC, 1980. DEC, *VAX Hardware Handbook*, Digital Equipment Corporation, Maynard, MA (1980).

Denning, 1970. P. J. Denning, “Virtual Memory,” *Computer Surveys* **2**(3), pp. 153–190 (September, 1970).

Easton & Franaszek, 1979. M. C. Easton & P. A. Franaszek, “Use Bit Scanning in Replacement Decisions,” *IEEE Transactions on Computing* **28**(2), pp. 133–141 (February 1979).

Gingell et al., 1987. R. A. Gingell, J. P. Moran, & W. A. Shannon, “Virtual Memory Architecture in SunOS,” *USENIX Association Conference Proceedings*, pp. 81–94 (June 1987).

Intel, 1984. Intel, “Introduction to the iAPX 286,” Order Number 210308, Intel Corporation, Santa Clara, CA (1984).

Joy, 1980. W. N. Joy, “Comments on the Performance of UNIX on the VAX,” Technical Report, University of California Computer System Research Group, Berkeley, CA (April 1980).

Kashtan, 1980. D. L. Kashtan, “UNIX and VMS: Some Performance Comparisons,” Technical Report, SRI International, Menlo Park, CA (February 1980).

Kenah & Bate, 1984. L. J. Kenah & S. F. Bate, *VAX/VMS Internals and Data Structures*, Digital Press, Bedford, MA (1984).

King, 1971. W. F. King, “Analysis of Demand Paging Algorithms,” *IFIP*, pp. 485–490, North Holland (1971).

Lazowska & Kelsey, 1978. E. D. Lazowska & J. M. Kelsey, “Notes on Tuning VAX/VMS.,” Technical Report 78-12-01, Department of Computer Science, University of Washington, Seattle, WA (December 1978).

London & Reiser, 1978. T. B. London & J. F. Reiser, “A UNIX Operating System for the DEC VAX-11/780 Computer,” Technical Report TM-78-1353-4, Bell Laboratories, Murray Hill, NJ (July 1978).

Marshall, 1979. W. T. Marshall, “A Unified Approach to the Evaluation of a Class of ‘Working Set Like’ Replacement Algorithms,” PhD Thesis, Department of Computer Engineering, Case Western Reserve University, Cleveland, OH (May 1979).

Organick, 1975. E. I. Organick, *The Multics System: An Examination of Its Structure*, MIT Press, Cambridge, MA (1975).


---

# 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.3-bsd-unix-cao-zuo-xi-tong-she-ji-yu-shi-xian/di-er-bu-fen-jin-cheng/5.13.-jiao-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.