操作系统 FIFO 先进先出页面置换算法_先进先出页面置换算法代码

FIFO 先进先出页面置换算法

根据作业序列判断置换，先进先置换的原则。

实现过程：

用vector简单模拟这个过程，不用直接queue模拟，是因为，当判断是否需要置换的时候，queue不好判断在队列中是否存在这个数。vector就方便很多。用一个二维数组存下过程的产生的置换图，换面好输出。

代码:

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



int main(){
    int n,m;    

    vector<int> num;//存储序列页号
    cout<<"请输入作业序列(输入-1停止输入）"<<endl;
    int x;
    while(cin>>x){
        if(x==-1) break;
        num.push_back(x);
    }
    n=num.size();
    cout<<"请输入物理块数： ";
    cin>>m;
    cout<<endl;
    cout<<"页面总数 "<<n<<"物理块数 "<<m<<endl<<endl;

    vector<int> q;//用vector模拟队列，先进先出

    int count=0;//记录置换的次数

    vector<bool>vis(n,0);
    vector<vector<int> > ans(n,vector<int> (m,-1));

    for(int i=0;i<n;i++){
        int ok=false;
        if(q.size()<m){
            q.push_back(num[i]);
            count++;
            vis[i]=1;
        }
        else{
            //从队列中查找是否有当前这个页号，没有就需要置换
            
            for(int j=0;j<q.size();j++){
                if(q[j]==num[i]) {
                    ok=true;
                    break;
                }
            }
            if(!ok){
                q.erase(q.begin());//置换队列头部的数
                q.push_back(num[i]);
                vis[i]=1;
                count++;
            }
        }

        for(int j=0;j<q.size();j++){
            ans[i][j]=q[j];
        }
        
    }
    //把作业情况输出

    cout<<"FIFO: "<<endl;
    cout<<"作业序列  ";
    for(int i=0;i<n;i++) cout<<num[i]<<" ";
    cout<<endl<<endl;

    for(int i=0;i<m;i++){
        if(i==0){
            cout<<"最开始的  ";
        }else if(i==m-1){
            cout<<"最末尾的  ";
        }
        else cout<<"          ";
        for(int j=0;j<n;j++){
            if(ans[j][i]==-1) cout<<"  ";
            else cout<<ans[j][i]<<" ";
        }
        cout<<endl<<endl;
    }
    cout<<"是否置换  ";
    for(int i=0;i<n;i++){
        if(vis[i]) cout<<"X ";
        else cout<<"  ";
    }
    cout<<endl<<endl;
    cout<<"置换率为  "<< count*1.0/n<<endl;
}

/*
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89