Appearance
题目
设某计算机的逻辑地址空间和物理地址空间均为 64 KB，按字节编址。某进程最多需要 6 页（Page）数据存储空间，页大小为 1 KB。操作系统采用固定分配局部置换策略为此进程分配 4 个页框。
在时刻 260 前，该进程访问情况如下表（"访问位"即"使用位"）：
| 页号 | 页框号 | 装入时刻 | 访问位 |
|---|---|---|---|
| 0 | 7 | 130 | 1 |
| 1 | 4 | 230 | 1 |
| 2 | 2 | 200 | 1 |
| 3 | 9 | 260 | 1 |
当该进程执行到时刻 260 时，要访问逻辑地址 17CAH 的数据。请回答下列问题：
(1) 该逻辑地址对应的页号是多少？
(2) 若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
(3) 采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针按顺时针方向移动，且当前指向 2 号页框）。
题 46 图：CLOCK 指针环绕 4 个页框（顺时针顺序为 2→4→7→9→2），初始指向 2 号页框。
解析
准备：地址结构
64 KB = B，1 KB = B → 页大小 1 KB → 页内偏移占低 10 位、页号占高 6 位：
（1）求页号
把 17CAH 转成二进制：
按 (6, 10) 切：
| 字段 | 二进制 | 十进制 |
|---|---|---|
| 页号（高 6 位） | 000101 | 5 |
| 页内偏移（低 10 位） | 11 1100 1010 | 970 |
答：页号 = 5。
（2）FIFO 置换：找谁最先入
观察表格"装入时刻"那一列：
| 页号 | 装入时刻 |
|---|---|
| 0 | 130 ← 最早 |
| 2 | 200 |
| 1 | 230 |
| 3 | 260 |
FIFO = 替换"在内存中待最久"的页面 → 淘汰页号 0（装入时刻最早），其原页框号 7 被新页 5 占用。
新的页表条目：页号 5 → 页框号 7。
物理地址 = 页框号 << 10 + 页内偏移：
二进制验证：0001 1111 1100 1010 = 1FCAH ✓
编者注（FIFO 易错点）：
- 看的是装入时刻，不是最近访问时刻——LRU 才看最近访问。
- 装入时刻最早的页 0（130 时装入）即使刚才被频繁访问（访问位 1），FIFO 也"无情"地把它换出。这是 FIFO 最大的缺点："不照顾热点页面"，可能换出常用页 → Belady 异常也跟它相关。
（3）CLOCK 置换：扫描访问位
CLOCK 算法步骤：
- 检查指针所指页框的使用位
- 若为 0 → 替换该页面，新页装入后使用位置 1，指针前进一格
- 若为 1 → 使用位清零，指针前进一格，回到步骤 1
- 直到找到使用位为 0 的页框
初始状态：指针指向 2 号页框；所有页框使用位均为 1。
扫描过程逐步追踪
| 轮次 | 指针位置 | 当前位 | 动作 | 操作后位 | 指针下一位 |
|---|---|---|---|---|---|
| 第 1 次 | 2 号 | 1 | 清 0，指针前进 | 0 | 4 号 |
| 第 2 次 | 4 号 | 1 | 清 0，指针前进 | 0 | 7 号 |
| 第 3 次 | 7 号 | 1 | 清 0，指针前进 | 0 | 9 号 |
| 第 4 次 | 9 号 | 1 | 清 0，指针前进 | 0 | 2 号（绕回） |
| 第 5 次 | 2 号 | 0 | 替换！ 装入新页 5、使用位置 1 | 1 | 4 号 |
→ 新页 5 占用 2 号页框。
物理地址 = 2 × 2^10 + 3CAH：
二进制验证：
0000 1011 1100 1010 =
编者注（CLOCK 关键细节）：
CLOCK 必须扫一圈把所有"使用位 1"清成 0，才能在下一圈替换某个页。本题正好需要扫满一圈（4 次清 0 + 1 次替换 = 5 次操作）。如果初始有某个页使用位是 0，就能立刻替换它、不必扫满圈。
被替换的页 = 走了一圈后第一个仍是 0 的页。本题里 4 个页框使用位都是 1，所以"绕回 2 号"时它已经被清成 0，立刻替换。
CLOCK 比 FIFO 公平：FIFO 不管页面是否热门，CLOCK 给每个热门页面"二次机会"（清零后等下次访问时又被置 1）。本题里如果最近某个页被反复访问（如页 0），它的使用位会一直保持 1、不会被换；而 FIFO 会立刻换掉它。
改进型 CLOCK 还看修改位——本题是简单 CLOCK 只看使用位。改进版的额外好处是优先换掉未修改的页（避免回写磁盘）。考研要分清两种 CLOCK：基础版只用 1 位，改进版用 2 位 (A, M)。