CSCI3150 L12 交换空间与缺页

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L12 交换空间与缺页 · 原件 L12-内存换入换出-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.1–18 定位：当合法虚拟页不在内存时，硬件报告缺页，OS 协调置换、磁盘与重试。 前后：前接 L11 高级分页；后接 L13 线程。

逐页伴读

p.1 是讲题；p.2–3 标出本讲结束内存虚拟化，随后进入并发。

p.4–6：大地址空间不要求所有页同时驻留

p.4 Require an additional level in the memory hierarchy.

OS needs a place to stash away portions of address space that currently aren’t in great demand.

In modern systems, this role is usually served by a hard disk drive

p.5 Always need to first arrange for the code or data to be in memory before calling a function or accessing data.

Multiple processes rather than a single process

The addition of swap space allows the OS to support the illusion of a large virtual memory for multiple concurrently-running processes

p.6 Reserve some space on the disk for moving pages back and forth.

OS needs to remember page addresses in the swap space, in page-sized unit

内存层次图从寄存器、cache、主存到外存，容量和访问成本不同。虚拟内存把当前不急需的页留在较慢层级，但CPU执行指令或访问数据前，相关页最终仍须驻留可访问的内存。

p.6 图上方只有4个物理框：P0/VPN0、P1/VPN2、P1/VPN3、P2/VPN0；下方swap块0、1放P0/VPN1、2，块2空闲，块3、4放P1/VPN0、1，块5、7放P3/VPN0、1，块6放P2/VPN1。合计11个逻辑页，仅4个驻留。相同VPN属于不同进程，不可只按VPN编号合并。

表（p.6）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

p.7–9：present=0 后，先区分不在场与不合法

p.7 The OS moves out pages to make room for the new pages

The process of picking a page to kick out, or replace is known as page-replacement policy

Add some machinery in the system to support swapping pages to and from the disk.

When the hardware looks in the PTE, it may find that the page is not present in physical memory.

p.8 Accessing page that is not in physical memory.

If a page is not present and has been swapped disk, the OS needs to swap the page into memory in order to service the page fault.

p.9 PTE used for data such as the PFN of the page for a disk address.

p.9 3. Issue disk read based on the address information from the page table or PTE.

p.9 When the OS receives a page fault, it looks in the PTE and issues the request to disk.

在本讲的合法已换出页模型中，Present=0表示目标在磁盘，需要换入；更一般的映射还有其他不驻留原因，不能反推所有Present=0页都存在一个swap副本。

图 p.9 六个箭头依次是引用、陷入OS、发出读盘、页进入空闲框、更新页表、重新执行引用。陷入点和重试点是同一条需要数据的指令，不是跳过失败操作。磁盘读完成前阻塞当前线程，可以让CPU运行别的任务。

p.10–12：硬件检测，软件补齐资源

课件伪代码（p.10，原页片段）

1:  VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2:  (Success, TlbEntry) = TLB_Lookup(VPN)
3:  if (Success == True) // TLB Hit
4:     if (CanAccess(TlbEntry.ProtectBits) == True)
5:      Offset = VirtualAddress & OFFSET_MASK
6:      PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
7:      Register = AccessMemory(PhysAddr)
8:     else RaiseException(PROTECTION_FAULT)

p.10 VPN-Virtual Page Number PFN – Physical Frame Number

课件伪代码（p.11，原页片段）

9:  else // TLB Miss
10:       PTEAddr = PTBR + (VPN * sizeof(PTE))
11:       PTE = AccessMemory(PTEAddr)
12:       if (PTE.Valid == False)
13:     RaiseException(SEGMENTATION_FAULT)
14:       else
15:          if (CanAccess(PTE.ProtectBits) == False)
16:         RaiseException(PROTECTION_FAULT)
17:          else if (PTE.Present == True)
18:          // assuming hardware-managed TLB
19:         TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
20:         RetryInstruction()
21:          else if (PTE.Present == False)
22:     RaiseException(PAGE_FAULT)

p.11 VPN-Virtual Page Number PFN – Physical Frame Number

PTE – Page Table Entry PTBR – Page Table Base Register

课件伪代码（p.12，原页片段）

1:   PFN = FindFreePhysicalPage()
2:   if (PFN == -1) // no free page found
3:      PFN = EvictPage() // run replacement algorithm
4:   DiskRead(PTE.DiskAddr, pfn) // sleep (waiting for I/O)
5:   PTE.present = True // update page table with present
6:   PTE.PFN = PFN // bit and translation (PFN)
7:   RetryInstruction() // retry instruction

p.12 The OS must find a physical frame for the soon-be-faulted-in page to reside within.

If there is no such page, waiting for the replacement algorithm to run and kick some pages out of memory.

p.10先查TLB，命中且权限允许就访存；p.11未命中才查PTE：valid=0是非法映射，权限不符是保护错误，present=1就填TLB并重试，合法且不驻留才进入缺页处理。

p.12 OS先找空闲框，若无则选择牺牲页，必要时写回它，再读入目标。随后设置目标PTE的Present和PFN，确保旧映射与TLB状态一致，再重试。伪代码略掉了错误处理、写回等实现细节，不能把一次 EvictPage() 理解成无成本删除数据。

补充：一次无空闲框的缺页需要先保住谁的数据。 设P需要页A，所有框都在用，策略选择页B所在框（自取字母）。先判断B是否被修改以及是否已有可恢复的后备副本；需要写回时，必须在复用该框之前保存B的新内容。否则把A读入同一框会覆盖B最后一份正确数据。干净且可从可靠后备存储重建的B可以免去这次写回，并不是所有“干净页”都无条件可以凭空恢复。

这个数据保护顺序不等于内核必须逐句照搬的唯一实现顺序。若其他线程、进程或CPU仍能写B，就不能只做一次写回，再任其继续修改直到复用框；否则最后一次修改仍会丢失。内核必须通过同步、映射/权限与相关TLB协调，阻止继续修改或可靠追踪并处理再次变脏，使保存的数据与最终收回的页状态一致；I/O期间也不能把尚在使用的框交给A。

在已排除这些并发访问的简化演示里，可把必要条件串起来看：B需要保留的内容已安全保存，B旧驻留映射和缓存转换已撤销，框才可供A读入；读成功后把A的PTE指向此框并设驻留。只有这些条件满足，原指令才能重试。若设备读失败，不能谎称A已到位；失败也是必须处理的结果。被阻塞进程等待的是有效数据，不是仅仅等一次I/O通知。

“重试”不是从整个程序开头重跑，也不是把故障指令跳过去。硬件异常机制保留足够的执行状态，让同一条尚未完成的访存重新执行；若原来是加载操作，跳过它会让后续计算使用错误旧值。

按原伪代码展开每一个出口：先由虚拟地址高位取得 VPN。TLB 命中后，权限失败直接报保护异常；权限成功则取低位 offset，把 PFN 左移页内位数再合并 offset，完成目标访存。TLB miss 时，先算 PTBR + VPN × sizeof(PTE) 取得页表项地址，再读取 PTE。Valid 为假报非法地址异常；Valid 真但权限不足报保护异常；两者都通过且 Present 真，才填入 TLB 并重新执行；Present 假才报告 PAGE_FAULT。

OS 的 p.12 分支依次是 FindFreePhysicalPage、必要时 EvictPage、DiskRead、把 Present 设真、写入新 PFN、RetryInstruction。原码混用 PFN/pfn 和 Present/present 的大小写，是讲义伪代码记号，不能直接当大小写敏感语言的可编译程序。特别注意：失败指令重试前必须已经有可用数据和有效映射；只把 Present 改真却尚未读完数据，会让硬件把空框当作已换入的页。

p.13–14：何时回收、淘汰谁，是两个决定

p.13 OS waits until memory is entirely full, and only then replaces a page to make room for some other page – Unrealistic

OS should proactively keep a small portion of memory free more proactively.

Swap Daemon, Page Daemon

There are fewer than LW pages available, a background thread that is responsible for freeing memory runs.

The thread evicts pages until there are HW pages available.

(LW – Low Watermark; HW – High Watermark)

p.14 Replacement Policy (Which pages to evict from memory)

p.14 Goal in picking a replacement policy cache is to minimize the number of misses.

The number of hits and misses let us calculate the average memory access time(AMAT).

LRU (Least Recently Used) – A common approach (based on the history)

Replaces the least-recently-used page.

空闲页低于Low Watermark时唤醒后台回收，达到High Watermark时停下。补充算例：LW=20、HW=40，检测到18页空闲，若期间无新分配，至少回收22页；回到20就停不符合高水位目标。实际并发分配会改变这个数量。

选择谁时，LRU利用近期访问历史，把最久未用页视为较不急需。它不具有预知未来能力。p.14可见公式为：

这里 $T_D$ 是miss引入的额外磁盘代价，不能再把已计入的内存时间重复加一次。补充演算：内存100 ns、额外缺页代价10 ms、缺页率百万分之一，先把10 ms换为10,000,000 ns，AMAT=100+10=110 ns；缺页率万分之一则为1100 ns，已是原来的11倍。即使缺页看似少，磁盘代价仍会主导。

补充：完整故障路径与额外罚时不能混用。 上面的原式把磁盘时间作为正常访存之外的额外成本；如果题目给的是发生故障时从开始到完成的总耗时，就要按两条互斥的完整路径加权。先确定时间的定义，再选公式。

算一遍（数字是我为演示取的，讲义没给）：假设正常访问共需 100ns，一次需要磁盘处理的缺页从故障到访问完成共需 10ms，即 10000000ns；每一万次访问中一次发生这种故障，概率为 0.0001。按互斥的两条完整路径计费，平均为 $0.9999\times100+0.0001\times10000000=1099.99$ns，约为正常路径的 11 倍。这里故障路径已含完成本次访问的成本，不再额外重复加 100ns。

为什么上段得到 1100ns，而这里得到 1099.99ns？差的 0.01ns 正是故障概率 0.0001 乘正常访问的 100ns：前一种约定在 10ms 以外还计入正常访问，后一种已把它包含在 10ms 内。两者不是算术矛盾，而是给定时间的定义不同。若把完整故障耗时设为 10000100ns，再按加权路径计算，就会重新得到 1100ns。实际题目应遵守自己的成本约定，不要为了数字接近而混着代入。

p.15–16：提前读取与合并写回

p.15 The OS predicts that a page will be used, and thus brings it in beforehand.

p.16 Collect a number of pending writes together in memory and write them to disk in one write.

Perform a single large write more efficiently than many small ones.

图 p.15 已取入Page1，预测接下来访问Page2而预取；准确时减少后续等待，错误时白花I/O和内存。空间局部性支持这种预测，却不保证它永远正确。

p.16把多页待写数据集中成较大的I/O，减少许多小写的固定开销。它改变传输组织，不改变哪些数据必须保留，也不等于调用返回即已可靠落盘。

p.17–18：为什么进程越多，CPU反而越闲

p.17 Memory is oversubscribed and the memory demand of the set of running processes exceeds the available physical memory.

Decide not to run a subset of processes.

Reduced set of processes working sets fit in memory.

p.18 Swapping

Reserve some space on the disk for moving pages back and forth.

The OS moves out pages to make room for the new pages when there is not enough memory space

Page fault occurs when accessing a page not in memory but in the swap area

Page Replacing

When to replace: LW/HW eviction

How to replace: LRU

Next: Concurrency

图横轴是并发程度，纵轴CPU利用率；前段更多任务可填补I/O等待，过某点后工作集之和超出可用物理内存，频繁互相挤出即将再用的页，CPU把时间耗在等待换页上，曲线下降。这是thrashing（抖动），不应简单继续增加任务。

课件给出的处理方向是减少同时运行的进程集合，使其工作集能放入内存。p.18把机制与策略分开：swap与缺页提供机制，水位决定时机，置换策略决定牺牲者。下一讲则处理多个执行流共享同一状态时的正确性。

本讲核心考点

• [C] 沿缺页图说明检测、阻塞、换入、更新与重试。
• [C] 区分TLB miss、非法映射、权限错误和合法页缺席。
• [C] 按统一时间单位计算AMAT并解释小缺页率的大代价。
• [C] 比较水位回收、LRU、预取、聚合写与抖动控制的不同目的。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

• 原件：L12-内存换入换出-2022未核.pptx（本地课件）；PDF副本（本地课件） p.1–18。本文页码均为 PDF 页号。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。