页面置换算法（FIFO , LRU, OPT）（C++实现模拟）

悠悠 2022-05-21 01:19 341阅读 0赞

## 简述 ##

先输入一个N表示的是，页表大小（最多能存的帧数）。  
之后的序列是最大为9，最小为0的一个申请序列。  
之后的输入一个数字T，表示输入的测试命令的数目。

之后的命令。  
**第一个数表示使用什么页面置换算法。**

*  1 表示FIFO.
 *  2 表示LRU
 *  3 表示OPT

**第二个是什么操作：**

*  get A，B表示运行完第A个序列之后，B在也页表中么？在就输出1，否则0。
 *  pf A表示的是，运行完第A个序列之后，缺页的次数。
 *  seq A表示的是，运行完第A个序列之后，页表的中的序列。

**HINT:(特别需要的情况)**

*  在序列中，只是替换，不修改物理顺序。（也就是例如LRU，访问发送之后，不会修改页表序列中元素的顺序）
 *  opt，在有多种选择的情形下，需要通过LRU的方式来选择替换victim。  
    **测试输入：**

2
    321236
    7
    1 seq 4
    3 seq 4
    3 seq 5
    3 seq 6
    2 pf 3
    2 pf 4
    1 get 1 2

**标准输出**

21
    12
    32
    36
    3
    3
    0

## 代码 ##

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    #include <map>
    #include <vector>
    int N, k;
    string s;
    
    void fifo(int A, string opda, int B = 0) {
        vector<char> v;
        int j, pageFaultTime = 0;
        for (int i = 0; i < A; ++i) {
            for (j = 0; j < v.size(); ++j) {
                if (s[i] == v[j]) break;
            }
            if (j == v.size()) { // page fault
                pageFaultTime += 1;
                if (v.size() == N) { // full
                                     // choose a victim
                    vector<char> nv;
                    for (j = 1; j < v.size(); ++j) {
                        nv.push_back(v[j]);
                    }
                    nv.push_back(s[i]);
                    v = nv;
                }
                else { // no full
                    v.push_back(s[i]);
                }
            }
        }
        if (opda[0] == 's') {
            for (j = 0; j < v.size(); ++j) {
                cout << v[j];
            }
            cout << endl;
        }
        else if (opda[0] == 'p') {
            cout << pageFaultTime << endl;
        }
        else {
            for (j = 0; j < v.size(); ++j) {
                if (v[j] - '0' == B) {
                    cout << 1 << endl;
                    return;
                }
            }
            cout << 0 << endl;
        }
    }
    
    
    void LRU(int A, string opda, int B = 0) {
        vector < pair<char, int> > v;
        int j, pageFaultTime = 0;
        for (int i = 0; i < A; ++i) {
            for (j = 0; j < v.size(); ++j) {
                if (s[i] == v[j].first) {
                    v[j].second = i; // refresh the time stamp
                    break;
                }
            }
            if (j == v.size()) { // page fault
                pageFaultTime += 1;
                if (v.size() == N) { // full
                                     // choose a victim
                    int MIN, MINIndex;
                    for (j = 0; j < v.size(); ++j) {
                        if (j == 0 || MIN > v[j].second) {
                            MIN = v[j].second;
                            MINIndex = j;
                        }
                    }
                    v[MINIndex] = make_pair(s[i], i);
                }
                else { // no full
                    v.push_back(make_pair(s[i], i));
                }
            }
        }
        if (opda[0] == 's') {
            for (j = 0; j < v.size(); ++j) {
                cout << v[j].first;
            }
            cout << endl;
        }
        else if (opda[0] == 'p') {
            cout << pageFaultTime << endl;
        }
        else {
            for (j = 0; j < v.size(); ++j) {
                if (v[j].first - '0' == B) {
                    cout << 1 << endl;
                    return;
                }
            }
            cout << 0 << endl;
        }
    }
    
    
    void OPT(int A, string opda, int B = 0) {
        vector < pair<char, int> > v;
        vector < int > vi;
        map<char, int> timeMap;
        map<char, int>::iterator iter;
        for (int i = 0; i < s.size(); ++i) {
            iter = timeMap.find(s[i]);
            if (iter == timeMap.end()) {
                timeMap.insert(make_pair(s[i], 1));
            }
            else {
                timeMap[s[i]] += 1;
            }
        }
        int j, pageFaultTime = 0;
        for (int i = 0; i < A; ++i) {
            for (int k = 0; k < v.size(); ++k) {
                int moren = 1<<30;
                for (int m = i+1; m < s.size(); ++m) {
                    if (s[m] == v[k].first) {
                        moren = m; break;
                    }
                }
                vi[k] = moren;
            }
            for (j = 0; j < v.size(); ++j) {
                if (s[i] == v[j].first) {
                    v[j].second = i; // refresh the time stamp
                    timeMap[s[i]] -= 1;
                    break;
                }
            }
            if (j == v.size()) { // page fault
                pageFaultTime += 1;
                if (v.size() == N) { // full
                                     // choose a victim
                                     // more than one choice.
                    int MINIndex;
                    for (j = 0; j < v.size(); ++j) {
                        if (j == 0 || vi[j] > vi[MINIndex] || (vi[j] == vi[MINIndex] && v[j].second < v[MINIndex].second)) {
                            MINIndex = j;
                        }
                    }
                    v[MINIndex] = make_pair(s[i], i);
                }
                else { // no full
                    v.push_back(make_pair(s[i], i));
                    vi.push_back(0);
                }
            }
        }
        if (opda[0] == 's') {
            for (j = 0; j < v.size(); ++j) {
                cout << v[j].first;
            }
            cout << endl;
        }
        else if (opda[0] == 'p') {
            cout << pageFaultTime << endl;
        }
        else {
            for (j = 0; j < v.size(); ++j) {
                if (v[j].first - '0' == B) {
                    cout << 1 << endl;
                    return;
                }
            }
            cout << 0 << endl;
        }
    }
    
    int main() {
        cin >> N >> s;
        cin >> k;
        int op, A, B = 0;
        string opda;
        for (int i = 0; i < k; ++i) {
            cin >> op >> opda >> A;
            if (opda[0] == 'g') cin >> B;
            if (op == 1) {
                fifo(A, opda, B);
            }
            else if (op == 2) {
                LRU(A, opda, B);
            }
            else {
                OPT(A, opda, B);
            }
        }
    }

**上面的代码主要还是为了实现实验要求，下面的代码就实现了将所有的数据都跑一遍（就是把整个流程都跑一遍，然后还输出下中间过程）**

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    #include <map>
    #include <vector>
    int N, k;
    string s;
    
    void fifo() {
        cout << "FIFO\n";
        vector<char> v; 
        int j, pageFaultTime = 0;
        for (int i = 0; i < s.size(); ++i) {
            for (j = 0; j < v.size(); ++j) {
                if (s[i] == v[j]) break;
            }
            if (j == v.size()) { // page fault
                pageFaultTime += 1;
                if (v.size() == N) { // full
                    // choose a victim
                    vector<char> nv;
                    for (j = 1; j < v.size(); ++j) {
                        nv.push_back(v[j]);
                    }
                    nv.push_back(s[i]);
                    v = nv;
                }
                else { // no full
                    v.push_back(s[i]);
                }
            }
            for (int k = 0; k < v.size(); ++k) {
                cout << v[k]<<" ";
            }
            cout << endl;
        }
    
    }
    
    
    void LRU() {
        cout << "LRU\n";
        vector < pair<char, int> > v;
        int j, pageFaultTime = 0;
        for (int i = 0; i < s.size(); ++i) {
            for (j = 0; j < v.size(); ++j) {
                if (s[i] == v[j].first) {
                    v[j].second = i; // refresh the time stamp
                    break;
                }
            }
            if (j == v.size()) { // page fault
                pageFaultTime += 1;
                if (v.size() == N) { // full
                                     // choose a victim
                    int MIN, MINIndex;
                    for (j = 0; j < v.size(); ++j) {
                        if (j == 0 || MIN > v[j].second) {
                            MIN = v[j].second;
                            MINIndex = j;
                        }
                    }
                    v[MINIndex] = make_pair(s[i], i);
                }
                else { // no full
                    v.push_back(make_pair(s[i], i));
                }
            }
            for (int k = 0; k < v.size(); ++k) {
                cout << v[k].first<<" ";
            }
            cout << endl;
        }
    }
    
    
    void OPT() {
        cout << "OPT\n";
        vector < pair<char, int> > v;
        vector < int > vi;
        map<char, int> timeMap;
        map<char, int>::iterator iter;
        for (int i = 0; i < s.size(); ++i) {
            iter = timeMap.find(s[i]);
            if (iter == timeMap.end()) {
                timeMap.insert(make_pair(s[i], 1));
            }
            else {
                timeMap[s[i]] += 1;
            }
        }
        int j, pageFaultTime = 0;
        for (int i = 0; i < s.size(); ++i) {
            for (int k = 0; k < v.size(); ++k) {
                int moren = 1<<30;
                for (int m = i+1; m < s.size(); ++m) {
                    if (s[m] == v[k].first) {
                        moren = m; break;
                    }
                }
                vi[k] = moren;
            }
            for (j = 0; j < v.size(); ++j) {
                if (s[i] == v[j].first) {
                    v[j].second = i; // refresh the time stamp
                    timeMap[s[i]] -= 1;
                    break;
                }
            }
            if (j == v.size()) { // page fault
                pageFaultTime += 1;
                if (v.size() == N) { // full
                                     // choose a victim
                                     // more than one choice.
                    int MINIndex;
                    for (j = 0; j < v.size(); ++j) {
                        if (j == 0 || vi[j] > vi[MINIndex] || (vi[j] == vi[MINIndex] && v[j].second < v[MINIndex].second)) {
                            MINIndex = j;
                        }
                    }
                    v[MINIndex] = make_pair(s[i], i);
                }
                else { // no full
                    v.push_back(make_pair(s[i], i));
                    vi.push_back(0);
                }
            }
            for (int k = 0; k < v.size(); ++k) {
                cout << v[k].first<<" ";
            }
            cout << endl;
        }
    
    }
    
    int main() {
        cin >> N >> s;
        cin >> k;
        int op, A, B = 0;
        string opda;
        fifo();
        LRU();
        OPT();
    }