分别使用OPT、FIFO和LRU算法模拟页面置换。代码

这里给出C++代码实现：

#include<bits/stdc++.h>
using namespace std;

//定义页面大小
const int page_size = 3;

// OPT 算法
int OPT(int pages[], int n, int start){
    int cnt = 0, pos = -1;
    int next[page_size+5];
    memset(next, 0, sizeof(next));
    for(int i = start; i < n; i++){
        bool is_find = false;
        for(int j = 0; j < page_size; j++){
            if(pages[i] == next[j]){
                is_find = true;
                break;
            }
        }
        if(is_find) continue;
        cnt++;
        if(cnt <= page_size){
            next[cnt-1] = pages[i];
        }else{
            for(int j = 0; j < page_size; j++){
                int k = i+1;
                while(k < n){
                    if(next[j] == pages[k]){
                        if(k > pos){
                            pos = k;
                            next[j] = pages[i];
                        }
                        break;
                    }
                    k++;
                }
                if(k == n){
                    pos = k;
                    next[j] = pages[i];
                    break;
                }
            }
        }
    }
    return cnt;
}

// FIFO 算法
int FIFO(int pages[], int n, int start){
    int cnt = 0, head = 0, tail = 0;
    int next[page_size+5];
    memset(next, 0, sizeof(next));
    for(int i = start; i < n; i++){
        bool is_find = false;
        for(int j = 0; j < page_size; j++){
            if(pages[i] == next[j]){
                is_find = true;
                break;
            }
        }
        if(is_find) continue;
        cnt++;
        if(cnt <= page_size){
            next[tail++] = pages[i];
        }else{
            next[head] = pages[i];
            head = (head+1)%page_size;
            tail = (tail+1)%page_size;
        }
    }
    return cnt;
}

// LRU 算法
int LRU(int pages[], int n, int start){
    int cnt = 0;
    int next[page_size+5];
    memset(next, 0, sizeof(next));
    for(int i = start; i < n; i++){
        bool is_find = false;
        for(int j = 0; j < page_size; j++){
            if(pages[i] == next[j]){
                is_find = true;
                for(int k = j; k > 0; k--){
                    next[k] = next[k-1];
                }
                next[0] = pages[i];
                break;
            }
        }
        if(is_find) continue;
        cnt++;
        if(cnt <= page_size){
            for(int j = cnt-1; j > 0; j--){
                next[j] = next[j-1];
            }
            next[0] = pages[i];
        }else{
            for(int j = page_size-1; j > 0; j--){
                next[j] = next[j-1];
            }
            next[0] = pages[i];
        }
    }
    return cnt;
}

int main(){
    //测试数据
    int pages[] = {1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};
    int n = sizeof(pages)/sizeof(pages[0]);

    //调用 OPT 算法
    cout<<"OPT算法结果："<<OPT(pages, n, 0)<<endl;

    //调用 FIFO 算法
    cout<<"FIFO算法结果："<<FIFO(pages, n, 0)<<endl;

    //调用 LRU 算法
    cout<<"LRU算法结果："<<LRU(pages, n, 0)<<endl;

    return 0;
}