超越物理内存：策略

把主存当作磁盘的缓存

空闲帧耗尽后，每次缺页都需要牺牲一个现有页面。可以把RAM看成速度极快但容量有限的缓存，磁盘则是慢速后备存储。因为磁盘访问比内存慢几个数量级，哪怕缺失概率只有百分之一，平均访问时间也会被磁盘主导。因此策略的核心是尽量让即将用到的页面留在内存里。

最优置换及其不可行性

如果事先知道全部未来访问，最佳做法是换出下次使用距离现在最远的那一页。这样能把缺失降到理论最低。现实中操作系统看不到未来，所以该策略只用于离线评估：把候选算法的缺失数和最优缺失数对比，就能知道还有多少改进空间。

先进先出：简单但可能盲目

FIFO维护一个按装入时间排序的队列，总是淘汰在内存中待得最久的页面。实现非常廉价，只需记录进入顺序。它完全不考虑页面装入之后是否继续被访问，因此一个早期进入却仍在频繁使用的页面可能被过早踢出，导致额外缺页。

常见误区

• 把最优算法当成可以在线运行的策略
• 忽视即使很低的缺失率也会让程序变成磁盘瓶颈
• 以为增加页框一定能减少FIFO的缺页（别拉迪异常）

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>

int main(void) {
    int frames = 3;
    int page_refs[] = {1, 2, 3, 4, 1, 2, 5, 1, 2};
    int num_refs = 9;
    int mem[3];
    int count = 0;
    int hit_count = 0;
    printf("Demonstrating FIFO page replacement\n");
    for (int i = 0; i < num_refs; ++i) {
        int pg = page_refs[i];
        int found = 0;
        for (int k = 0; k < count; ++k) {
            if (mem[k] == pg) {
                found = 1;
                break;
            }
        }
        if (found) {
            hit_count++;
            printf("page %d : hit, memory contains", pg);
        } else {
            printf("page %d : miss, memory contains", pg);
            if (count < frames) {
                mem[count] = pg;
                count++;
            } else {
                for (int k = 0; k < frames - 1; ++k) {
                    mem[k] = mem[k + 1];
                }
                mem[frames - 1] = pg;
            }
        }
        for (int k = 0; k < count; ++k) {
            printf(" %d", mem[k]);
        }
        printf("\n");
    }
    printf("Hits = %d out of %d\n", hit_count, num_refs);
    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-22-swapping-policies.c -o example && ./example

预期结果

Demonstrating FIFO page replacement
page 1 : miss, memory contains 1
page 2 : miss, memory contains 1 2
page 3 : miss, memory contains 1 2 3
page 4 : miss, memory contains 2 3 4
page 1 : miss, memory contains 3 4 1
page 2 : miss, memory contains 4 1 2
page 5 : miss, memory contains 1 2 5
page 1 : hit, memory contains 1 2 5
page 2 : hit, memory contains 1 2 5
Hits = 2 out of 9

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

使用3个页框和引用串1,2,3,4,1,2,5,1,2，FIFO会产生几次缺页？

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。