引言
在操作系统中，当物理内存不足以容纳所有进程页面时，页面置换算法（Page Replacement Algorithm）决定了哪个页面应该被换出到磁盘，为新的页面腾出空间。一个好的置换算法能显著减少 页面故障（Page Fault），从而提升系统性能。本文将用 Java 实现三种经典页面置换算法：FIFO（先进先出）、Clock（时钟/第二次机会） 和 工作集（Working Set） 算法，并通过模拟器对比它们的性能差异。
页面置换的核心问题
当进程访问的页面不在物理内存中时，触发页面故障。此时操作系统必须：
1. 找到一个空闲页框，或选择一个牺牲页换出
2. 将所需页面从磁盘读入内存
3. 更新页表，恢复进程执行
选择”牺牲页”的策略就是页面置换算法的核心。
算法一：FIFO（First-In-First-Out）
思想：最早进入内存的页面最先被换出。
实现：使用队列维护页面进入顺序。
Belady异常：FIFO 可能出现物理页框增加但页面故障反而增加的异常现象。
import java.util.*;
/**
* FIFO 页面置换算法
* 最早进入内存的页面最先被换出
*/
public class FIFOPageReplacement {
private final int capacity; // 物理页框数量
private final Queue<Integer> queue; // 维护页面进入顺序
private final Set<Integer> pages; // 当前内存中的页面集合
private int pageFaults = 0;
private int pageHits = 0;
public FIFOPageReplacement(int capacity) {
this.capacity = capacity;
this.queue = new LinkedList<>();
this.pages = new HashSet<>();
}
/**
* 访问页面
* @param page 请求的页面号
* @return true=命中, false=缺页
*/
public boolean access(int page) {
if (pages.contains(page)) {
pageHits++;
return true; // 页面命中
}
// 页面缺失
pageFaults++;
if (pages.size() >= capacity) {
// 内存已满，淘汰最早进入的页面
int victim = queue.poll();
pages.remove(victim);
System.out.println(" 缺页! 淘汰页面: " + victim + "，装入页面: " + page);
} else {
System.out.println(" 缺页! 直接装入页面: " + page);
}
queue.offer(page);
pages.add(page);
return false;
}
public void printStats() {
System.out.println("FIFO 统计 — 缺页次数: " + pageFaults +
", 命中次数: " + pageHits +
", 缺页率: " + String.format("%.2f%%",
100.0 * pageFaults / (pageFaults + pageHits)));
}
public static void main(String[] args) {
int[] referenceString = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
FIFOPageReplacement fifo = new FIFOPageReplacement(3);
System.out.println("FIFO 页面置换模拟 (页框数=3):");
for (int page : referenceString) {
System.out.print("访问页面 " + page + " -> ");
fifo.access(page);
}
fifo.printStats();
}
}
算法二：Clock（第二次机会）算法
思想：为每个页面设置访问位（Reference Bit）。当需要淘汰页面时，从指针位置开始扫描：
– 若访问位为 0，直接淘汰
– 若访问位为 1，给予”第二次机会”（置为 0），继续扫描
这是 LRU 的近似实现，兼顾了效率与性能。
import java.util.*;
/**
* Clock (第二次机会) 页面置换算法
* 使用访问位和循环指针实现LRU近似
*/
public class ClockPageReplacement {
static class PageFrame {
int pageNumber; // 页面号
boolean referenceBit; // 访问位 (R位)
PageFrame(int pageNumber) {
this.pageNumber = pageNumber;
this.referenceBit = true; // 刚装入时置1
}
}
private final int capacity;
private final PageFrame[] frames; // 循环页框数组
private final Map<Integer, Integer> pageToIndex; // 页面号 -> 页框索引
private int hand; // 时钟指针
private int pageFaults = 0;
private int pageHits = 0;
public ClockPageReplacement(int capacity) {
this.capacity = capacity;
this.frames = new PageFrame[capacity];
this.pageToIndex = new HashMap<>();
this.hand = 0;
}
public boolean access(int page) {
if (pageToIndex.containsKey(page)) {
// 页面命中，设置访问位
int idx = pageToIndex.get(page);
frames[idx].referenceBit = true;
pageHits++;
return true;
}
// 页面缺失
pageFaults++;
if (pageToIndex.size() >= capacity) {
// 寻找牺牲页
int victimIdx = findVictim();
int victimPage = frames[victimIdx].pageNumber;
pageToIndex.remove(victimPage);
System.out.println(" 缺页! 淘汰页面: " + victimPage +
" (R=" + frames[victimIdx].referenceBit + ")" +
"，装入页面: " + page);
frames[victimIdx] = new PageFrame(page);
pageToIndex.put(page, victimIdx);
} else {
// 有空闲页框
int idx = pageToIndex.size();
frames[idx] = new PageFrame(page);
pageToIndex.put(page, idx);
System.out.println(" 缺页! 直接装入页面: " + page);
}
return false;
}
/**
* 时钟扫描寻找牺牲页
*/
private int findVictim() {
while (true) {
PageFrame current = frames[hand];
if (!current.referenceBit) {
// 访问位为0，淘汰该页
int victim = hand;
hand = (hand + 1) % capacity;
return victim;
}
// 给予第二次机会，清除访问位
current.referenceBit = false;
hand = (hand + 1) % capacity;
}
}
public void printStats() {
System.out.println("Clock 统计 — 缺页次数: " + pageFaults +
", 命中次数: " + pageHits +
", 缺页率: " + String.format("%.2f%%",
100.0 * pageFaults / (pageFaults + pageHits)));
}
public static void main(String[] args) {
int[] referenceString = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
ClockPageReplacement clock = new ClockPageReplacement(3);
System.out.println("Clock 页面置换模拟 (页框数=3):");
for (int page : referenceString) {
System.out.print("访问页面 " + page + " -> ");
clock.access(page);
}
clock.printStats();
}
}
算法三：工作集（Working Set）算法
思想：进程在一段时间内集中访问的页面集合称为”工作集”。工作集算法只保留最近 Δ 个时间单位内被访问过的页面，其余页面可被换出。
优势：能适应进程局部性变化，防止抖动（Thrashing）。
import java.util.*;
/**
* 工作集 (Working Set) 页面置换算法
* 只保留最近 Δ 个时间单位内访问过的页面
*/
public class WorkingSetPageReplacement {
static class PageEntry {
int pageNumber;
int lastAccessTime; // 上次访问时间
PageEntry(int pageNumber, int time) {
this.pageNumber = pageNumber;
this.lastAccessTime = time;
}
}
private final int capacity; // 最大页框数
private final int delta; // 工作集窗口大小（时间单位）
private final Map<Integer, PageEntry> pages; // 当前内存中的页面
private int currentTime = 0;
private int pageFaults = 0;
private int pageHits = 0;
public WorkingSetPageReplacement(int capacity, int delta) {
this.capacity = capacity;
this.delta = delta;
this.pages = new LinkedHashMap<>(); // 保持插入顺序
}
public boolean access(int page) {
currentTime++;
// 首先清理工作集窗口外的页面
cleanWorkingSet();
if (pages.containsKey(page)) {
// 命中，更新时间戳
pages.get(page).lastAccessTime = currentTime;
pageHits++;
return true;
}
// 缺页
pageFaults++;
// 如果达到容量上限，需要淘汰（理论上工作集大小应 <= capacity）
if (pages.size() >= capacity) {
// 淘汰最久未访问的页面（窗口内）
int victim = findLRUVictim();
pages.remove(victim);
System.out.println(" 缺页! 淘汰页面: " + victim +
"，装入页面: " + page +
" [当前工作集大小=" + pages.size() + "]");
} else {
System.out.println(" 缺页! 直接装入页面: " + page +
" [当前工作集大小=" + (pages.size() + 1) + "]");
}
pages.put(page, new PageEntry(page, currentTime));
return false;
}
/**
* 清理超出工作集窗口的页面
*/
private void cleanWorkingSet() {
Iterator<Map.Entry<Integer, PageEntry>> it = pages.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, PageEntry> entry = it.next();
if (currentTime - entry.getValue().lastAccessTime > delta) {
System.out.println(" [工作集清理] 页面 " + entry.getKey() +
" 超出窗口 (t=" + entry.getValue().lastAccessTime + ")");
it.remove();
}
}
}
private int findLRUVictim() {
int victim = -1;
int oldestTime = Integer.MAX_VALUE;
for (Map.Entry<Integer, PageEntry> entry : pages.entrySet()) {
if (entry.getValue().lastAccessTime < oldestTime) {
oldestTime = entry.getValue().lastAccessTime;
victim = entry.getKey();
}
}
return victim;
}
public void printStats() {
System.out.println("工作集统计 — 缺页次数: " + pageFaults +
", 命中次数: " + pageHits +
", 缺页率: " + String.format("%.2f%%",
100.0 * pageFaults / (pageFaults + pageHits)));
}
public static void main(String[] args) {
int[] referenceString = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
WorkingSetPageReplacement ws = new WorkingSetPageReplacement(3, 4);
System.out.println("工作集页面置换模拟 (页框数=3, Δ=4):");
for (int page : referenceString) {
System.out.print("访问页面 " + page + " -> ");
ws.access(page);
}
ws.printStats();
}
}
综合对比模拟器
/**
* 页面置换算法综合对比
*/
public class PageReplacementComparison {
public static void main(String[] args) {
// 典型的页面访问序列，体现局部性原理
int[] referenceString = {
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, // 第一轮
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, // 重复访问
6, 7, 8, 9, 6, 7, 8, 9, 6, 7, 8, 9 // 新工作集
};
int[] capacities = {2, 3, 4};
System.out.println("========== 页面置换算法性能对比 ==========\n");
for (int cap : capacities) {
System.out.println("----- 物理页框数 = " + cap + " -----");
// FIFO
FIFOPageReplacement fifo = new FIFOPageReplacement(cap);
for (int p : referenceString) fifo.access(p);
fifo.printStats();
// Clock
ClockPageReplacement clock = new ClockPageReplacement(cap);
for (int p : referenceString) clock.access(p);
clock.printStats();
// Working Set
WorkingSetPageReplacement ws = new WorkingSetPageReplacement(cap, 5);
for (int p : referenceString) ws.access(p);
ws.printStats();
System.out.println();
}
}
}
算法对比分析
| 算法 | 实现复杂度 | 缺页率 | 是否存在Belady异常 | 适用场景 |
|---|---|---|---|---|
| FIFO | 简单 | 较高 | 是 | 教学演示、简单系统 |
| Clock | 中等 | 中等 | 否 | 通用操作系统（Linux/Windows采用变体） |
| Working Set | 较复杂 | 低 | 否 | 需要防止抖动的交互式系统 |
| LRU | 较复杂 | 低 | 否 | 理论最优（实际用Clock近似） |
| OPT | 不可实现 | 最低 | 否 | 理论下界基准 |
实际系统中的应用
- Linux：使用改进的 Clock 算法（LRU 近似），结合 Active/Inactive 链表
- Windows：工作集模型，动态调整进程工作集大小
- 数据库：常结合 LRU 与 LFU，针对缓冲区管理优化
总结
页面置换算法是操作系统内存管理的核心。FIFO 简单直观但存在 Belady 异常；Clock 算法在实现效率和性能之间取得了最佳平衡，被现代操作系统广泛采用；工作集算法则能动态适应程序行为变化，有效防止抖动。理解这些算法，有助于我们深入掌握操作系统的工作原理，也能在编写缓存系统时借鉴这些经典思想。
