CSCI3150 T09 换页算法演算
课程：CSCI3150 Introduction to Operating Systems · 2025T2 本讲：T09 换页算法演算 · 原件 T09-页面置换算法-2025T2.pptx（本地课件） · PDF页码副本（本地课件） p.1–14 定位：在同一引用序列上比较频率、最近时间与CLOCK引用位。 前后：衔接 L11 TLB置换、L12缺页。
逐页伴读
p.1–3：页置换与整进程swap分清
p.1 Tutorial 9: Swapping Algorithms
CSCI3150 Introduction to Operating Systems, Spring 2026
p.2 Assignment 3
23:59:59 p.m., Mar 29
New commit update on Piazza: added ai_declaration.txt
p.3 Swapping is a memory management technique where a process is temporarily moved from main memory (RAM) to secondary storage (Disk) and then brought back into memory for continued execution.
Roll Out / Roll In: Used in priority-based scheduling; lower-priority processes are "swapped out" so higher-priority ones can be loaded.
Backing Store: Fast disk space large enough to accommodate copies of all memory images.
封面3月19日，作业提醒属于历史Spring2026。p.3以整个进程换出介绍swapping，但本篇实际表格计算的是页/缓存项替换；两者粒度不同。以下把十六进制标签视为独立缓存项，课件未给行长，不能另行推断相邻地址共用一行。
p.4–5：每种策略保留的历史不同
p.5 Recap:
Remove the items that are used least frequently to make room for new items.
The LFU algorithm is based on the idea that items accessed less frequently in the past are less likely to be needed in the future.
FIFO看入驻先后，LRU看最近一次访问，LFU看频次，OPT看未来最远下一次访问。OPT可作已知序列的离线比较下界，在线系统不能预知任意未来。FIFO可能出现增加容量反而更多缺失的Belady异常；本例没有给FIFO容量对比，不能把其他表当其证明。
LFU可能保住过去常用但现在不再用的项；还必须约定同频怎么选以及被淘汰后计数是否保留。
表（p.4）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。
| Algorithm | Logic | Pro / Con |
|---|---|---|
| FIFO | Oldest page in memory is replaced first. | Simple to implement / Suffers from Belady’s Anomaly. |
| LRU (Least Recently Used) | Replaces the page that hasn't been used for the longest time. | Highly efficient / Requires hardware support (counters/stacks). |
| Optimal (OPT) | Replaces the page that will not be used for the longest period in the future. | Lowest miss rate (requires future knowledge). |
| LFU (Least Frequently Used) | Replaces the page with the smallest reference count. | Focuses on frequency, no-longer-used pages. |
p.6–7：LFU完整题面与同频规则
p.6 Consider the need to access the following addresses in order and there are 5 cache lines in the cache：
0x1A2B, 0x3C4D, 0x1A2B, 0x5E6F, 0x7A8B, 0x9A8B, 0x7A9F, 0x7A8B, 0x7CAB, 0x1A2B, 0x3C4D
p.7 1. Checking for Cache Hit:
Iterates through each cache line to check for a hit.
On Hit: Increments the line’s frequency counter. Outputs a cache hit message.
- Handling Cache Miss: If no matching line is found, it’s a cache miss. Proceed to find a suitable line to store the new data.
Finding a Replacement Line:
Search for Empty Line. First preference is to find an empty line.
If no empty line is available, searches for the line with the lowest frequency.
Set the the new line’s frequency counter to 1. Output a cache miss message.
原序列（容量5，初始为空）：1A2B,3C4D,1A2B,5E6F,7A8B,9A8B,7A9F,7A8B,7CAB,1A2B,3C4D，每项均是十六进制标签。命中频次加一，新装入频次置1。原图在同频时替换固定槽中靠前项；本次按最低槽号平局规则复现，而不是暗用LRU平局。
第3步1A2B命中变2；第7步替换频次1的3C4D；第8步7A8B命中变2；第9步同频时又替换刚装的7A9F而非更旧的5E6F；第10步1A2B命中变3；第11步替换7CAB。共3hit、8miss，命中率3/11≈27.27%。逐步全表。
LFU 原序列全表
| 步 | 访问 | H/M | 被替换 | 固定槽0–4（状态） | 下一指针 |
|---|---|---|---|---|---|
| 1 | 1A2B | M | 空位 | 1A2B(1), 空(0), 空(0), 空(0), 空(0) | — |
| 2 | 3C4D | M | 空位 | 1A2B(1), 3C4D(1), 空(0), 空(0), 空(0) | — |
| 3 | 1A2B | H | — | 1A2B(2), 3C4D(1), 空(0), 空(0), 空(0) | — |
| 4 | 5E6F | M | 空位 | 1A2B(2), 3C4D(1), 5E6F(1), 空(0), 空(0) | — |
| 5 | 7A8B | M | 空位 | 1A2B(2), 3C4D(1), 5E6F(1), 7A8B(1), 空(0) | — |
| 6 | 9A8B | M | 空位 | 1A2B(2), 3C4D(1), 5E6F(1), 7A8B(1), 9A8B(1) | — |
| 7 | 7A9F | M | 3C4D | 1A2B(2), 7A9F(1), 5E6F(1), 7A8B(1), 9A8B(1) | — |
| 8 | 7A8B | H | — | 1A2B(2), 7A9F(1), 5E6F(1), 7A8B(2), 9A8B(1) | — |
| 9 | 7CAB | M | 7A9F | 1A2B(2), 7CAB(1), 5E6F(1), 7A8B(2), 9A8B(1) | — |
| 10 | 1A2B | H | — | 1A2B(3), 7CAB(1), 5E6F(1), 7A8B(2), 9A8B(1) | — |
| 11 | 3C4D | M | 7CAB | 1A2B(3), 3C4D(1), 5E6F(1), 7A8B(2), 9A8B(1) | — |
命中3次、未命中8次。
回正文。
p.8–10：LRU时间戳在命中时也刷新
p.8 Recap
Least Recently Used (LRU) algorithm is a Greedy algorithm where least recently used pages are to be replaced.
The LRU algorithm is based on the idea that the pages that have been used the least recently are the ones that are least likely to be used again in the near future.
p.10 Each access increments the global time by one.
- Checking for Cache Hit:
Iterates through each cache line to check for a hit.
On Hit: Updates the last access time of the cache line to the current global time. Outputs a cache hit message.
- Handling Cache Miss: If no matching line is found, it’s a cache miss. Proceeds to find a suitable line to store the new data.
Search for Empty Line. First preference is to find an empty line.
If no empty line is available, searches for the line with the smallest last access time.
Set the new line's last access time to the current global time. Output a cache miss message.
沿用完整同一序列与容量，时间从1逐次加1，命中更新最近访问时间。第7步淘汰时间2的3C4D；第8步7A8B命中更新时间8；第9步淘汰时间3的1A2B；第10步再访问1A2B已miss，淘汰时间4的5E6F；第11步淘汰时间6的9A8B。
只有第3、8步命中，2hit、9miss，命中率18.18%。该序列LFU更好不代表LFU普遍优于LRU；它们对未来的估计依据不同。逐步全表。
补充：用同一次命中看清三种历史。 原序列第8步再次访问7A8B，LFU把它的累计频次从1变2，LRU把最后访问时间改成8，CLOCK只把引用位置1。三个字段都叫“最近用过的信息”，但保存粒度完全不同：LFU计多次，LRU保留精确最近次序，CLOCK只记自上次清位以来是否又用过。
因此CLOCK见1清0并不是淘汰，也不是把这一页的数据清零；它是在收回一次“再给机会”的标记。接着继续扫描，真正遇到0才替换。做表时把“数据标签、引用位、扫描指针”写在不同列，能防止误把指针经过当作一次用户访问。
自测：本例CLOCK与LRU都是9次miss，是否可把二者中间表格互换？
不可以。第7步LRU淘汰3C4D，CLOCK淘汰1A2B，缓存内容已不同。总次数相等只是对这条有限序列的统计巧合；若后续再访问其中一个刚被不同策略保留的标签，命中情况便可能分叉。
LRU 原序列全表
| 步 | 访问 | H/M | 被替换 | 固定槽0–4（状态） | 下一指针 |
|---|---|---|---|---|---|
| 1 | 1A2B | M | 空位 | 1A2B(1), 空(0), 空(0), 空(0), 空(0) | — |
| 2 | 3C4D | M | 空位 | 1A2B(1), 3C4D(2), 空(0), 空(0), 空(0) | — |
| 3 | 1A2B | H | — | 1A2B(3), 3C4D(2), 空(0), 空(0), 空(0) | — |
| 4 | 5E6F | M | 空位 | 1A2B(3), 3C4D(2), 5E6F(4), 空(0), 空(0) | — |
| 5 | 7A8B | M | 空位 | 1A2B(3), 3C4D(2), 5E6F(4), 7A8B(5), 空(0) | — |
| 6 | 9A8B | M | 空位 | 1A2B(3), 3C4D(2), 5E6F(4), 7A8B(5), 9A8B(6) | — |
| 7 | 7A9F | M | 3C4D | 1A2B(3), 7A9F(7), 5E6F(4), 7A8B(5), 9A8B(6) | — |
| 8 | 7A8B | H | — | 1A2B(3), 7A9F(7), 5E6F(4), 7A8B(8), 9A8B(6) | — |
| 9 | 7CAB | M | 1A2B | 7CAB(9), 7A9F(7), 5E6F(4), 7A8B(8), 9A8B(6) | — |
| 10 | 1A2B | M | 5E6F | 7CAB(9), 7A9F(7), 1A2B(10), 7A8B(8), 9A8B(6) | — |
| 11 | 3C4D | M | 9A8B | 7CAB(9), 7A9F(7), 1A2B(10), 7A8B(8), 3C4D(11) | — |
命中2次、未命中9次。
回正文。
p.11–13：CLOCK让近期访问者再获一次机会
p.11 Recap
An approximation of the Least Recently Used (LRU) algorithm. Requires less overhead than true LRU implementations because it doesn’t need to keep a detailed history of page accesses.
Easy to implement with small hardware requirements (only a use bit).
p.13 Cache Hit Scenario:
The Clock Pointer will not be moved forward
If the requested data is found, update the reference bit to 1. No replacement occurs.
Cache Miss Scenario:
Search for empty line. First preference is to find an empty line.
If no empty line.
Iterates the cache lines and set the reference bit from 1 to 0.
Replace the first line whose reference bit is 0. Set the reference bit of the new line to 1.
Move clock pointer to the next line for future accesses.
原规则命中置引用位1但不移动指针；miss先用空槽，满后从指针开始扫描：见1清0继续，见0替换，新项置1，指针移到下一槽。这里初始指针槽0，装空槽后也向前，和图一致。
第7步所有位原为1，扫描一整圈清0后淘汰槽0的1A2B，装7A9F，指针1；第8步7A8B命中把槽3位重新置1，指针仍1。第9步换槽1的3C4D；第10步换槽2的5E6F；第11步从槽3见1清0，再到槽4见0，淘汰9A8B。结果2hit、9miss，与本例LRU总数相同，但第7步牺牲者已不同，不能说算法相同。逐步全表。
CLOCK 原序列全表
| 步 | 访问 | H/M | 被替换 | 固定槽0–4（状态） | 下一指针 |
|---|---|---|---|---|---|
| 1 | 1A2B | M | 空位 | 1A2B(1), 空(0), 空(0), 空(0), 空(0) | 1 |
| 2 | 3C4D | M | 空位 | 1A2B(1), 3C4D(1), 空(0), 空(0), 空(0) | 2 |
| 3 | 1A2B | H | — | 1A2B(1), 3C4D(1), 空(0), 空(0), 空(0) | 2 |
| 4 | 5E6F | M | 空位 | 1A2B(1), 3C4D(1), 5E6F(1), 空(0), 空(0) | 3 |
| 5 | 7A8B | M | 空位 | 1A2B(1), 3C4D(1), 5E6F(1), 7A8B(1), 空(0) | 4 |
| 6 | 9A8B | M | 空位 | 1A2B(1), 3C4D(1), 5E6F(1), 7A8B(1), 9A8B(1) | 0 |
| 7 | 7A9F | M | 1A2B | 7A9F(1), 3C4D(0), 5E6F(0), 7A8B(0), 9A8B(0) | 1 |
| 8 | 7A8B | H | — | 7A9F(1), 3C4D(0), 5E6F(0), 7A8B(1), 9A8B(0) | 1 |
| 9 | 7CAB | M | 3C4D | 7A9F(1), 7CAB(1), 5E6F(0), 7A8B(1), 9A8B(0) | 2 |
| 10 | 1A2B | M | 5E6F | 7A9F(1), 7CAB(1), 1A2B(1), 7A8B(1), 9A8B(0) | 3 |
| 11 | 3C4D | M | 9A8B | 7A9F(1), 7CAB(1), 1A2B(1), 7A8B(0), 3C4D(1) | 0 |
命中2次、未命中9次。
回正文。
补充：引用位保存的历史比“最近访问时刻”粗。 原序列第 7 步扫描开始时，每个槽的引用位都是 1；这只能说明它们自上次清位之后被引用过，不能从五个 1 判断谁最后访问。CLOCK 先清一圈，再按指针规则选择，就解释了为什么它可以淘汰一个并非精确 LRU 的页。
第 8 步命中 7A8B 后重新置 1，使它在第 11 步扫描时得到一次再机会；并没有把槽搬到某个“队尾”。手算表保持物理槽号固定，分别更新槽内页、引用位、指针即可。若像 LRU 一样在每次命中后重排所有槽，再沿原指针扫描，就混用了两个算法的状态定义，哪怕最后 miss 次数碰巧相同，轨迹也已经错了。
p.14：练习收束
Q&A页。手算前先写初始容量、平局规则、时间/引用位更新规则和指针初值；每次引用都记录hit/miss与状态，最后用hit+miss=11核对。Tutorial中新展开的LFU与CLOCK保留在本文，按v4.2默认不新增主讲记忆条目。
本讲核心考点
- [C] 在给定平局与初值下完整推演LFU、LRU、CLOCK。
- [C] 区分频次、时间戳和引用位，命中也更新对应状态。
- [C] 说明相同缺失次数不代表相同替换轨迹。
附录
完整演算已放回相应页的正文，原链接锚点继续保留。
来源与证据
-
原件：T09-页面置换算法-2025T2.pptx（本地课件）；PDF副本（本地课件） p.1–14。本文页码均为 PDF 页号。
-
考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无
-
2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。