操作系統——頁置換算法（FIFO，OPT，LRU）

分別使用FIFO、OPT、LRU三種置換算法來模擬頁面置換的過程。（Linux、Windows下皆可）
輸入：  3  //頁幀數

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1  //待處理的頁
輸出：頁面置換過程中各幀的變化過程和出現頁錯誤的次數
[cpp]
#include<iostream>  
using namespace std; 
int input[20]= {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}; 
class page 
{ 
public: 
    int num; 
    int mark; 
    page() 
    { 
        num=0; 
        mark=21; 
    } 
}; 
void FIFO() 
{ 
    cout<<"------FIFO-----------"<<endl; 
    int error=0; 
    page frame[3];//頁幀  
    for(int i=0;i<3;i++)//處理前三個引用  
    { 
        frame[i].num=input[i]; 
        error++; 
        cout<<frame[i].num<<" | "; 
        for(int j=0;j<=i;j++) 
            cout<<frame[j].num<<' '; 
        cout<<endl; 
    } 
    for(int i=3;i<20;i++) 
    { 
        int j; 
        for(j=0;j<3;j++) 
            if(input[i]==frame[j].num) 
            { 
                cout<<input[i]<<endl; 
                break; 
            } 
        if(j==3) 
        { 
            error++; 
            frame[((error-1)%3)].num=input[i];//換掉最舊的頁  
            cout<<input[i]<<" | "; 
            for(int k=0;k<3;k++) 
                cout<<frame[k].num<<' '; 
            cout<<endl; 
        } 
    } 
    cout<<"Frame Error:"<<error<<endl<<endl; 
} 
void OPT() 
{ 
    cout<<"------OPT------------"<<endl; 
    int error=0; 
    page frame[3]; 
    for(int i=0;i<3;i++)//處理前三個引用  
    { 
        frame[i].num=input[i]; 
        error++; 
        cout<<frame[i].num<<" | "; 
        for(int j=0;j<=i;j++) 
            cout<<frame[j].num<<' '; 
        cout<<endl; 
    } 
    for(int i=3;i<20;i++) 
    { 
        int j; 
        for(j=0;j<3;j++) 
            if(input[i]==frame[j].num) 
            { 
                cout<<input[i]<<endl; 
                break; 
            } 
        if(j==3) 
        { 
            error++; 
            for(j=0;j<3;j++) 
            { 
                frame[j].mark=21; 
                for(int k=20;k>=i;k--)//向後遍歷，找到最長時間不用的頁  
                { 
                    if(frame[j].num==input[k]) 
                        frame[j].mark=k; 
                } 
            } 
            if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark) 
                frame[0].num=input[i]; 
            else if(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark) 
                frame[1].num=input[i]; 
            else 
                frame[2].num=input[i]; 
            cout<<input[i]<<" | "; 
            for(int k=0;k<3;k++) 
                cout<<frame[k].num<<' '; 
            cout<<endl; 
        } 
    } 
    cout<<"Frame Error:"<<error<<endl<<endl; 
} 
void LRU() 
{ 
    cout<<"------LRU------------"<<endl; 
    int error=0; 
    page frame[3]; 
    for(int i=0;i<3;i++)//處理前三個引用  
    { 
        frame[i].num=input[i]; 
        error++; 
        cout<<frame[i].num<<" | "; 
        for(int j=0;j<=i;j++) 
            cout<<frame[j].num<<' '; 
        cout<<endl; 
    } 
    for(int i=3;i<20;i++) 
    { 
        int j; 
        for(j=0;j<3;j++) 
            if(input[i]==frame[j].num) 
            { 
                cout<<input[i]<<endl; 
                break; 
            } 
        if(j==3) 
        { 
            error++; 
            for(j=0;j<3;j++) 
            { 
                frame[j].mark=0; 
                for(int k=0;k<=i;k++)//向前遍歷，找到最近最少使用的  
                { 
                    if(frame[j].num==input[k]) 
                        frame[j].mark=k; 
                } 
            } 
            if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark) 
                frame[0].num=input[i]; 
            else if(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark) 
                frame[1].num=input[i]; 
            else 
                frame[2].num=input[i]; 
            cout<<input[i]<<" | "; 
            for(int k=0;k<3;k++) 
                cout<<frame[k].num<<' '; 
            cout<<endl; 
        } 
    } 
    cout<<"Frame Error:"<<error<<endl<<endl; 
} 
int main() 
{ 
    FIFO(); 
    OPT(); 
    LRU(); 
}