页面置换算法FIFO算法、LRU算法、OPT算法用c实现

页面置换算法是操作系统中常用的一种内存管理算法，主要用于解决内存不足时的页面置换问题。其中，FIFO算法、LRU算法、OPT算法是常用的三种页面置换算法。它们分别采用了不同的策略来选择需要被替换的页面。

FIFO算法（First In First Out）：是最简单的页面置换算法，它总是选择最早进入内存的页面进行替换。该算法的实现比较简单，可以使用一个先进先出队列来维护内存中的页面。当需要进行页面替换时，从队列头部取出最早进入内存的页面进行替换即可。

以下是用C语言实现FIFO算法的代码：

#define N 3 // 内存中可以容纳的页面数
int main(){
    int page[N] = {0}; // 初始化页面数组
    int head = 0; // 页面队列头部
    int tail = 0; // 页面队列尾部
    int miss = 0; // 缺页次数
    int hit = 0; // 命中次数
    int pages[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; // 待访问的页面序列
    int n = sizeof(pages)/sizeof(int); // 待访问页面序列的长度
    
    for(int i=0; i<n; i++){
        int p = pages[i];
        int flag = 0;
        for(int j=0; j<N; j++){
            if(page[j] == p){
                flag = 1; // 命中
                break;
            }
        }
        if(flag == 1){
            hit++;
        }else{
            miss++; // 缺页
            page[tail] = p;
            tail = (tail+1)%N; // 更新队列尾部
        }
    }
    printf("缺页次数：%d\n", miss);
    printf("命中次数：%d\n", hit);
    return 0;
}

LRU算法（Least Recently Used）：是一种比较常用的页面置换算法，它基于“最近最少使用”的原则选择需要被替换的页面。该算法维护一个链表来记录页面最近一次被访问的时间。每次需要进行页面替换时，选择链表末尾的页面进行替换。

以下是用C语言实现LRU算法的代码：

#define N 3 // 内存中可以容纳的页面数
int main(){
    int page[N] = {0}; // 初始化页面数组
    int time[N] = {0}; // 初始化时间数组
    int miss = 0; // 缺页次数
    int hit = 0; // 命中次数
    int pages[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; // 待访问的页面序列
    int n = sizeof(pages)/sizeof(int); // 待访问页面序列的长度
    
    for(int i=0; i<n; i++){
        int p = pages[i];
        int flag = 0;
        for(int j=0; j<N; j++){
            if(page[j] == p){
                flag = 1; // 命中
                time[j] = i+1; // 更新时间戳
                break;
            }
        }
        if(flag == 1){
            hit++;
        }else{
            miss++; // 缺页
            int min_time = time;
            int min_index = 0;
            for(int j=1; j<N; j++){
                if(time[j] < min_time){
                    min_time = time[j];
                    min_index = j;
                }
            }
            page[min_index] = p; // 替换最久未使用的页面
            time[min_index] = i+1; // 更新时间戳
        }
    }
    printf("缺页次数：%d\n", miss);
    printf("命中次数：%d\n", hit);
    return 0;
}

OPT算法（Optimal Page Replacement）：是一种理论上最优的页面置换算法，它基于未来访问情况选择需要被替换的页面。该算法需要预测每个页面在未来一段时间内是否会被访问，然后选择在未来最长时间内不会被访问的页面进行替换。由于预测未来访问情况很难做到100%准确，因此该算法在实际应用中较少使用。

以下是用C语言实现OPT算法的代码：

#define N 3 // 内存中可以容纳的页面数
int main(){
    int page[N] = {0}; // 初始化页面数组
    int miss = 0; // 缺页次数
    int hit = 0; // 命中次数
    int pages[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; // 待访问的页面序列
    int n = sizeof(pages)/sizeof(int); // 待访问页面序列的长度
    
    for(int i=0; i<n; i++){
        int p = pages[i];
        int flag = 0;
        for(int j=0; j<N; j++){
            if(page[j] == p){
                flag = 1; // 命中
                break;
            }
        }
        if(flag == 1){
            hit++;
        }else{
            miss++; // 缺页
            int max_index = -1;
            int max_future = -1;
            for(int j=0; j<N; j++){
                int future = -1;
                for(int k=i+1; k<n; k++){
                    if(pages[k] == page[j]){
                        future = k-i;
                        break;
                    }
                }
                if(future == -1){
                    max_index = j;
                    break;
                }else{
                    if(future > max_future){
                        max_future = future;
                        max_index = j;
                    }
                }
            }
            page[max_index] = p; // 替换最长时间内不会被访问的页面
        }
    }
    printf("缺页次数：%d\n", miss);
    printf("命中次数：%d\n", hit);
    return 0;
}