第1关：页面置换算法-FIFO-OPT-LRU

### 页面置换算法 FIFO、OPT 和 LRU 的实现与比较 #### FIFO（先进先出）算法 FIFO 是一种简单的页面置换算法，其核心思想是选择最早进入内存的页面进行替换。当发生缺页中断时，该算法会优先淘汰驻留在内存中最久的一页。 其实现逻辑如下： 1. 使用队列来记录当前内存中的页面顺序。 2. 当新页面需要加载到内存中且内存已满时，移除队首页面并将其替换成新的页面。 3. 新页面会被加入到队尾。 以下是 FIFO 算法的一个简单 Python 实现[^1]: ```python def fifo(pages, frame_size): memory = [] page_faults = 0 for page in pages: if page not in memory: if len(memory) >= frame_size: memory.pop(0) # 移除最早的页面 memory.append(page) page_faults += 1 return page_faults ``` #### OPT（最优）算法 OPT 被认为是一种理想化的页面置换策略，因为它基于未来的信息做出决策。具体来说，在发生缺页中断时，它会选择在未来最长一段时间内不会被使用的页面进行替换。然而，由于这种预测能力通常无法在实际系统中实现，因此 OPT 更多地用于理论分析和性能对比。 其实现过程较为复杂，因为需要提前知道后续所有的页面请求序列。下面是一个假设性的伪代码描述[^1]: ```python def opt(pages, frame_size): memory = [] page_faults = 0 future_accesses = {page: [] for page in set(pages)} # 预处理每一页未来的访问位置 for idx, page in enumerate(pages): future_accesses[page].append(idx) for i, page in enumerate(pages): if page not in memory: if len(memory) >= frame_size: # 找到离下次访问最远的页面 farthest_page = None max_distance = -1 for p in memory: next_access_idx = future_accesses[p][0] if future_accesses[p] and future_accesses[p][0] > i else float('inf') if next_access_idx > max_distance: max_distance = next_access_idx farthest_page = p memory.remove(farthest_page) memory.append(page) page_faults += 1 return page_faults ``` #### LRU（最近最少使用）算法 LRU 基于这样一个原则：如果某个页面很久没有被访问过，则可以推测它可能也不会很快再次被使用。因此，在发生缺页中断时，LRU 将淘汰那些距离上次访问时间间隔最大的页面。 为了高效地维护这些信息，一般采用哈希表配合双向链表的数据结构来进行管理。下面是 LRU 的一个简化版本实现[^1]: ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cache = OrderedDict() self.capacity = capacity def get(self, key): if key not in self.cache: return -1 value = self.cache[key] self.cache.move_to_end(key) # 更新为最新访问 return value def put(self, key, value): if key in self.cache: del self.cache[key] elif len(self.cache) >= self.capacity: self.cache.popitem(last=False) # 删除最旧项 self.cache[key] = value def lru_simulator(pages, frame_size): cache = LRUCache(frame_size) page_faults = 0 for page in pages: if cache.get(page) == -1: page_faults += 1 cache.put(page, True) return page_faults ``` #### 性能比较 三种算法各有优缺点： | 特性 | FIFO | OPT | LRU | |--------------|--------------------------|-------------------------|---------------------| | **优点** | 实现简单 | 缺页率最低 | 较接近最佳效果 | | **缺点** | 可能导致 Belady 异常 | 不可预见未来数据流 | 维护成本较高 | | **适用场景** | 对实时性和资源消耗敏感 | 主要用于理论研究或模拟 | 多数现代操作系统中 | 尽管 OPT 提供了理论上最好的性能表现，但由于依赖不可知的未来事件，所以并不适合真实环境下的应用；相比之下，FIFO 易于部署但存在局限性，而 LRU 则通过合理折衷实现了较好的综合效益[^1]。