分页存储管理中，LRU算法，FIFO算法

### 分页存储管理中的LRU和FIFO算法

#### LRU（最近最少使用）算法

在分页存储管理系统中，LRU是一种基于页面访问时间顺序来决定淘汰哪一页的策略。每当发生缺页中断时，操作系统会查找并替换掉最长时间未被使用的那一页[^1]。

对于LRU的具体实现方式，在实际应用中有多种方法：

- **完全LRU**：记录每一页最后一次被访问的时间戳，每次都需要遍历整个页表找到最早的一次访问记录来进行替换操作。

- **近似LRU**：为了提高效率，通常采用栈距离法或其他简化模型来估算页面的历史使用频率，从而减少计算复杂度。

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}
        self.order = []
        self.capacity = capacity
        
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value = self.cache[key]
        # Move accessed item to the end of order list (most recently used)
        self.order.remove(key)
        self.order.append(key)
        return value
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
            self.order.remove(key)
        elif len(self.cache) >= self.capacity:
            oldest_key = self.order.pop(0)
            del self.cache[oldest_key]

        self.cache[key] = value
        self.order.append(key)

此Python代码展示了如何通过字典`cache`保存键值对以及列表`order`维护访问顺序的方式简单模拟了一个LRU缓存机制[^2]。

#### FIFO（先进先出）算法

相比之下，FIFO则更加直观——它总是选择最早进入内存的那个页面作为被淘汰的对象。这意味着当新的页面需要加载到物理内存而当前已满的情况下，最先装入的那一部分会被移除以腾出空间给新来的页面。

尽管其逻辑较为简单易懂，但在某些情况下可能会导致性能不佳的结果，比如存在频繁访问但长期不活跃的数据项时，这些项目可能因为早期装载反而一直占据着宝贵的资源直到最终被迫清除为止。

from collections import deque

class FIFOCache:

    def __init__(self, capacity: int):
        self.queue = deque(maxlen=capacity)
        self.page_set = set()

    def reference_page(self, page_id: str):
        if page_id not in self.page_set and len(self.queue) == self.queue.maxlen:
            removed_page = self.queue.popleft()
            self.page_set.remove(removed_page)

        if page_id not in self.page_set:
            self.queue.append(page_id)
            self.page_set.add(page_id)

def simulate_fifocache_operations():
    fifo_cache = FIFOCache(capacity=3)
    
    operations = ['A', 'B', 'C', 'D', 'E']
    for op in operations:
        print(f"Referencing {op}")
        fifo_cache.reference_page(op)
        print(list(fifo_cache.queue))
        
simulate_fifocache_operations()

上述Python脚本定义了一种简单的FIFO缓存类，并提供了一个函数用于展示一系列页面引用过程中队列的变化情况。

---