### FIFO 替换算法简介 FIFO（First In First Out）替换算法是一种简单的页面置换策略，在计算机组成原理的内存管理中广泛应用。该算法按照页进入缓存的时间顺序来决定淘汰哪一页，最早进入的页最先被淘汰[^2]。 ### FIFO 替换算法的设计思路 当发生缺页中断时，操作系统会查找物理内存中的空闲帧；如果没有可用的空闲帧，则依据FIFO原则选择最先进入内存的数据块予以移除，并加载新的数据块到腾出来的空间里。这种机制简单易懂，但可能不是最优的选择，因为并不考虑各页面未来的访问频率或模式。 ### Python 实现 FIFO 页面替换模拟器 下面是一个基于Python编写的简易版FIFO页面替换算法演示程序： ```python class FIFOCache: def __init__(self, capacity): self.cache = [] self.capacity = capacity def access_page(self, page_number): if page_number not in self.cache: print(f"Missed! Page {page_number} is loaded.") if len(self.cache) >= self.capacity: removed_page = self.cache.pop(0) print(f"Page {removed_page} was replaced by page {page_number}.") self.cache.append(page_number) else: print(f"Hit! Page {page_number} already exists.") def fifo_demo(): pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] cache_size = 3 fifo_cache = FIFOCache(cache_size) for page in pages: fifo_cache.access_page(page) fifo_demo() ``` 此代码定义了一个`FIFOCache`类用来表示具有固定大小capacity的一级高速缓冲存储器(Cache)，并通过列表维护当前已载入Cache内的页面编号序列。每当尝试访问某特定页面时(`access_page`)，如果发现请求的目标不在现有记录之中即触发一次“未命中”，此时需判断是否达到预设的最大容纳量(capacity); 若已达上限则依照先进先出的原则弹出队列头部元素并加入新成员至尾部位置; 否则直接追加即可。对于那些已经在Cache中存在的页面查询操作而言，则视为“命中”。 通过调用`fifo_demo()`函数可以观察一系列给定页面引用串作用于指定尺寸Cache上的具体行为表现形式，从而帮助理解FIFO替换过程的工作方式及其特点。