页面置换算法FIFO的数据结构

FIFO页面置换算法的数据结构是一个队列，队列中存储了当前内存中的所有页面。当需要置换页面时，选择队列中最先进入的页面进行置换。新进入内存的页面会被加入队列的末尾，而最先进入内存的页面则会被放在队列的最前面。这样，当内存空间不足时，最先进入内存的页面会被最先置换出去，从而保证了内存中的页面都是最近进入的页面。

相关问题

页面置换算法FIFO，结果

### FIFO 页面置换算法概述

FIFO（First-In-First-Out）页面置换算法是最简单的页面置换策略之一。其实质在于总是选择在主存中停留时间最长的页进行替换，即先进入内存的页最先被移除[^2]。

### FIFO 页面置换算法的特点

该算法通过维护一个队列来跟踪所有当前驻留在内存中的页面。每当发生缺页中断时，操作系统会将新请求的页面加载到内存中，并将其放置在队列的末端；与此同时，在队列头部的最旧页面会被淘汰出去。尽管这种方法易于理解和实现，但它并非最优解，因为较早进入系统的页面未必就是将来不会再访问的页面[^1]。

值得注意的是，FIFO 算法存在一种称为 Belady 异常的现象——随着分配给进程的工作集大小增大，缺页率却可能上升而不是下降[^3]。

### C语言下的FIFO页面置换算法实现

下面是一个基于C语言编写的简单版本的FIFO页面置换模拟器：

#include <stdio.h>
#define MAX_PAGES 10    /* 假设最大可容纳的页面数量 */
int fifo_queue[MAX_PAGES];     /* 存储当前缓存内的页面编号 */
int front = -1;                /* 队首指针初始化为无效位置 */
int rear = -1;                 /* 队尾指针同样设置 */

void enqueue(int value){
    if (rear >= MAX_PAGES - 1) {
        printf("Queue Overflow\n");
        return;
    }
    
    if(front == -1 && rear == -1){ // 如果队列为空，则更新front指向第一个元素的位置
        front++;
    }

    fifo_queue[++rear] = value;
}

// 函数用于判断某特定值是否存在于数组内
bool contains(int *arr, int size, int target){
    for(int i=0;i<size;++i){
        if(arr[i]==target)return true;
    }
    return false;
}

int main(){
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};   /* 测试用例序列 */
    int n = sizeof(pages)/sizeof(pages[0]);                  /* 获取测试数据长度 */
    int fault_count = 0;

    for(int i=0 ; i<n ; ++i){
        if(!contains(fifo_queue,rear+1,pages[i])){           /* 若不存在于缓存中...*/
            fault_count++;                                   /* ...则触发一次缺页错误*/

            if(rear>=MAX_PAGES-1){                           /* 当缓存已满时...*/
                front=(front+1)%MAX_PAGES;                   /* ...移动front以覆盖最早的项*/
                rear=(rear+1)%MAX_PAGES;                     /* 同样调整rear保持一致*/
                
                fifo_queue[rear]=pages[i];
            }else{
                enqueue(pages[i]);
            }
            
            printf("Page %d inserted into cache.\n", pages[i]);
        } else {
            printf("Hit on Page %d.\n", pages[i]);
        }
        
        for(int j=front;j<=rear;j++){
            printf("%d ", fifo_queue[j%MAX_PAGES]);
        }
        puts("");
    }

    printf("\nTotal number of page faults: %d\n",fault_count);
}

此程序展示了如何利用循环缓冲区结构来管理固定容量的页面帧集合，并计算在整个过程中发生的缺页次数。每次遇到新的未命中页面都会打印出来并显示当前状态，以便观察者可以清楚地看到每一步的变化情况。

页面置换算法FIFO和LRU

### FIFO 和 LRU 页面置换算法的工作原理

#### FIFO (First-In, First-Out)

FIFO 是一种简单的页面置换算法，其基本思想是按照页面进入内存的时间顺序进行替换。最早进入内存的页面最先被移除。

当发生缺页中断时，操作系统会选择最先进入内存的那个页面将其淘汰并加载新的页面。这种方法实现简单，只需要维护一个队列即可记录页面进入内存的先后次序[^1]。

class FIFOPageReplacement:
    def __init__(self):
        self.queue = []

    def page_fault(self, new_page):
        if new_page not in self.queue:
            if len(self.queue) >= max_pages:  # 当达到最大容量时
                removed_page = self.queue.pop(0)  # 移除最早的页面
            self.queue.append(new_page)

#### LRU (Least Recently Used)

LRU 算法基于程序访问局部性的假设，即最近最少使用的页面在未来一段时间内也不太可能会被再次访问。因此，在发生缺页异常时，优先选择那些距离当前时刻最长未被访问过的页面作为被淘汰的对象。

为了有效地跟踪各个页面最后被访问的时间戳，通常会采用链表结构或其他数据结构来保存这些信息，并随着每次页面访问更新相应的状态。

from collections import OrderedDict

class LRUPageReplacement:
    def __init__(self):
        self.cache = OrderedDict()

    def get(self, key):
        if key in self.cache:
            value = self.cache.pop(key)
            self.cache[key] = value  # 更新位置到最新
            return True
        return False

    def put(self, key):
        if key not in self.cache and len(self.cache) >= max_pages:
            oldest_key = next(iter(self.cache))
            del self.cache[oldest_key]
        self.cache[key] = None

两种算法的主要区别在于：

- **效率**：FIFO 实现起来非常容易，但是性能上不如 LRU；而 LRU 虽然更复杂一些，但在很多情况下能够提供更好的命中率。
- **公平性**：由于 FIFO 不考虑实际使用情况只看进入时间，可能导致某些经常使用的页面也被错误地替换了；相比之下，LRU 更加合理地反映了真实的应用场景需求。
- **适应能力**：对于具有较强空间局部性特征的工作负载来说，LRU 表现出明显的优势，因为它可以更好地保留近期活跃的数据集。