请求分页式存储管理算法

### 分页式存储管理算法实现与原理

#### 1. 分页式存储管理基本概念
分页式存储管理系统将逻辑地址空间划分为固定大小的单位，称为页面(Page)，同样也将物理地址空间划分成相同大小的块(Frame)[^3]。这种机制允许作业存放在若干个不相邻的分区中，从而减少了因内存碎片化带来的资源浪费。

#### 2. 地址转换过程
在分页系统中，每个进程拥有自己的页表(Page Table)，用于记录各页面对应的物理帧位置。当CPU生成一条访问请求时，MMU（Memory Management Unit）会自动完成从逻辑地址到物理地址的映射操作。具体来说，逻辑地址由两部分组成：页号(Page Number, PN) 和页内偏移量(Offset)；而物理地址则对应于实际存在于RAM中的某个特定位置，即帧号(Frame Number, FN)+Offset[^4]。

// C语言伪代码展示如何计算物理地址
int get_physical_address(int logical_addr){
    int page_size = PAGE_SIZE; // 页面大小定义为常数
    int pn = logical_addr / page_size;
    int offset = logical_addr % page_size;

    struct PageTableEntry pte = page_table[pn];
    
    if (pte.valid_bit == 0){ 
        handle_page_fault(pn); // 处理缺页异常
    }
    
    return pte.frame_number * page_size + offset;
}

#### 3. 缺页中断及其处理流程
如果所需的数据不在当前的工作集里，则会产生一次缺页中断(Page Fault Interrupt)。此时操作系统需要暂停正在运行的任务，并启动专门的服务例程来加载缺失的部分至可用的空间内。之后更新相应的页表项并恢复被中断前的状态继续执行原指令[^1]。

#### 4. 页面替换策略
为了有效利用有限数量的物理帧，当发生缺页错误且无空闲帧可供分配时，就需要依据一定的规则决定淘汰哪一个旧页面以便腾出地方给新到来者。常见的几种页面置换算法包括：

- **FIFO**（先进先出）
按照进入时间顺序依次替换最早载入的那个页面。

- **LRU**（最近最少使用）
优先考虑那些长时间未被使用的页面作为候选对象进行驱逐。

- **CLOCK**
基于局部性原理的一种优化版本，它会在环形缓冲区上标记已扫描过的页面直到找到合适的牺牲品为止。

class ClockPageReplacement:
    def __init__(self):
        self.pages = {}
        self.hand = 0
    
    def access(self, frame_id):
        """模拟对某一页框ID的引用"""
        if frame_id not in self.pages:
            evicted_frame = None
            
            while True:
                current_frame = list(self.pages.keys())[self.hand]
                
                if self.pages[current_frame]['referenced']:
                    self.pages[current_frame]['referenced'] = False
                
                else:
                    del self.pages[current_frame]
                    evicted_frame = current_frame
                    break
                    
                self.hand = (self.hand + 1) % len(self.pages)

            self.pages[frame_id] = {'referenced':True,'modified':False}

        elif 'referenced' in self.pages[frame_id]:
            self.pages[frame_id]['referenced'] = True
        
        return evicted_frame