三种页面置换算法 缺页率

### 三种页面置换算法的缺页率性能分析

#### FIFO 页面置换算法
FIFO (First-In, First-Out)，即先进先出页面置换算法，在这种策略下，最先加载到内存中的页面会被优先淘汰。当新页面需要载入而物理块已满时，会移除最早进入缓存的页面。

对于给定的页面引用串 `7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1` 和三个物理块的情况下，采用FIFO算法计算得到总的缺页次数为15次[^2]。

def fifo_page_replacement(pages, capacity):
    memory = []
    page_faults = 0
    
    for page in pages:
        if page not in memory:
            if len(memory) >= capacity:
                memory.pop(0)
            memory.append(page)
            page_faults += 1
            
    return page_faults

#### LRU 页面置换算法
LRU (Least Recently Used), 即最近最少使用页面置换算法，该方法会选择在过去一段时间内最久未使用的页面作为被淘汰的对象。这种方法更贴近实际应用模式，通常能提供较好的命中率。

针对相同的页面流和条件，利用LRU算法得出总缺页数为12次。

from collections import OrderedDict

def lru_page_replacement(pages, capacity):
    cache = OrderedDict()
    page_faults = 0
    
    for page in pages:
        if page not in cache:
            if len(cache) >= capacity:
                cache.popitem(last=False)
            page_faults += 1
        else:
            del cache[page]
            
        cache[page] = None
        
    return page_faults

#### OPT 页面置换算法
OPT (Optimal Page Replacement)，也称为最优页面替换算法，总是选择将来最长不被访问的那个页面进行替换，理论上可以获得最小化缺页频率的效果。然而，由于其依赖于未来的数据预测，因此在现实中难以实现，主要用于理论研究和对比其他算法效率的标准之一。

同样条件下，通过OPT算法模拟的结果显示仅有9次缺页发生[^1]。

import sys

def opt_page_replacement(pages, capacity):
    frame_set = set()  
    frame_list = []    
    fault_num = 0      
    next_use_index = [None]*len(pages)

    for i in range(len(pages)):
        for j in range(i, len(pages)):
            if pages[j] != pages[i]:
                continue
            elif next_use_index[i] is None or next_use_index[i]>j:
                next_use_index[i]=j
                
    for i in range(len(pages)):   
        if pages[i] not in frame_set: 
            if len(frame_set)<capacity:
                frame_set.add(pages[i])
                frame_list.append(pages[i])                
            else:
                farthest=-1
                will_remove=None
                for k in frame_set:
                    use_time=next_use_index.index(None)if(next_use_index[frame_list.index(k)]is None)else next_use_index[frame_list.index(k)]
                    if(use_time>farthest):                    
                        farthest=use_time
                        will_remove=k
                        
                frame_set.remove(will_remove)
                frame_list.remove(will_remove)
                frame_set.add(pages[i])
                frame_list.append(pages[i])

            fault_num+=1 

    return fault_num

综上所述，不同类型的页面置换算法对系统的缺页率有着显著影响。从上述例子可以看出，在相同的工作负载下，OPT表现最好，其次是LRU，最后是FIFO。值得注意的是，虽然FIFO简单易行，但在某些情况下可能会导致Belady异常现象的发生，即增加更多的可用帧反而增加了缺页中断的数量[^3]。