〔OS〕页面置换算法

C++ 实现的 FIFO、OPT、LRU、CLOCK 四种页面置换算法。

/**页面置换算法**/
/**by Darius**/
#include <bits/stdc++.h>
using namespace std;

vector<int> pages, mem;
int pagesNum, Size, temp;

void FIFO()
{
    queue<int> que;
    map<int, int> mp;
    while(!que.empty()) que.pop();
    mp.clear(), mem.clear();
    int cnt = 0, f = 0;
    for(auto pagesItem : pages)
    {
        cout << pagesItem << " : ";
        if(mp[pagesItem] == 0)
        {
            cnt++, f = 1;
            if(mem.size() < Size)
            {
                mem.push_back(pagesItem);
                que.push(pagesItem);
                mp[pagesItem] = 1;
            }
            else
            {
                temp = que.front();
                que.pop();
                auto memIter = find(mem.begin(), mem.end(), temp);
                mem.insert(memIter, pagesItem);
                que.push(pagesItem);
                mp[pagesItem] = 1;
                memIter = find(mem.begin(), mem.end(), temp);
                mem.erase(memIter);
                mp[temp] = 0;
            }
        }
        else f = 0;
        for(auto it : mem) cout << it << ' ';
        if(f) cout << "缺页";
        cout << endl;
    }
    cout << "FIFO 缺页中断次数: " << cnt << endl;
    cout << "FIFO 缺页率: "<< cnt / (1.0*pagesNum) << '
' << endl;
}
void OPT()
{
    vector<int> tmp;
    map<int, int> mp;
    tmp.clear(), mp.clear(), mem.clear();
    int cnt = 0, f = 0;
    for(auto pagesIter = pages.begin(); pagesIter != pages.end(); pagesIter++)
    {
        cout << *pagesIter << " : ";
        if (mp[*pagesIter] == 0)
        {
            cnt++, f = 1;
            if (mem.size() < Size)
            {
                mem.push_back(*pagesIter);
                mp[*pagesIter] = 1;
                tmp = mem;
            }
            else
            {
                for(auto ixIter = pagesIter + 1; ixIter != pages.end(); ixIter++)
                {
                    if(tmp.size() == 1) break;
                    auto tmpIter = find(tmp.begin(), tmp.end(), *ixIter);
                    if(tmpIter != tmp.end()) tmp.erase(tmpIter);
                }
                auto tmpIter = tmp.begin();
                auto memIter = find(mem.begin(), mem.end(), *tmpIter);
                mem.insert(memIter, *pagesIter);
                memIter = find(mem.begin(), mem.end(), *tmpIter);
                mp[*memIter] = 0;
                mem.erase(memIter);
                mp[*pagesIter] = 1;
                tmp = mem;
            }
        }
        else f = 0;
        for(auto it : mem) cout << it << ' ';
        if(f) cout << "缺页";
        cout << endl;
    }
    cout << "OPT 缺页中断次数: " << cnt << endl;
    cout << "OPT 缺页率: "<< cnt / (1.0*pagesNum) << '
' << endl;
}
void LRU()
{
    vector<int> tmp;
    map<int, int> mp;
    mem.clear(), tmp.clear(), mp.clear();
    int cnt = 0, f = 0;
    for(auto pagesItem : pages)
    {
        cout << pagesItem << " : ";
        if (mp[pagesItem] == 0)
        {
            cnt++, f = 1;
            if (mem.size() < Size)
            {
                mem.push_back(pagesItem);
                mp[pagesItem] = 1;
                tmp.push_back(pagesItem);
            }
            else
            {
                auto tmpIter = tmp.begin();
                auto memIter = find(mem.begin(), mem.end(), *tmpIter);
                mem.insert(memIter, pagesItem);
                memIter = find(mem.begin(), mem.end(), *tmpIter);
                mem.erase(memIter);
                mp[*tmpIter] = 0;
                mp[pagesItem] = 1;
                tmp.erase(tmpIter);
                tmp.push_back(pagesItem);
            }
        }
        else
        {
            f = 0;
            auto tmpIter = find(tmp.begin(), tmp.end(), pagesItem);
            tmp.erase(tmpIter);
            tmp.push_back(pagesItem);
        }
        for(auto it : mem) cout << it << ' ';
        if(f) cout << "缺页";
        cout << endl;
    }
    cout << "LRU 缺页中断次数: " << cnt << endl;
    cout << "LRU 缺页率: "<< cnt / (1.0*pagesNum) << '
' << endl;
}
const int N = 1005;
int nru[N], page_in_block[N], block[N];
void CLOCK()
{
    int index = 1, cnt = 0, f = 0;
    memset(block, -1, sizeof block);
    for(auto pagesItem : pages)
    {
        f = cnt;
        if(page_in_block[pagesItem]) nru[page_in_block[pagesItem]] = 1;
        else
        {
            while(true)
            {
                if(index > Size) index = 1;
                if(block[index] == -1)
                {
                    nru[index] = 1;
                    page_in_block[pagesItem] = index;
                    block[index++] = pagesItem;
                    cnt++;
                    break;
                }
                if(block[index] == pagesItem)
                {
                    nru[index++] = 1;
                    break;
                }
                else
                {
                    if(nru[index] == 0)
                    {
                        nru[index] = 1;
                        page_in_block[block[index]] = 0;
                        page_in_block[pagesItem] = index;
                        block[index++] = pagesItem;
                        cnt++;
                        break;
                    }
                    else nru[index++] = 0;
                }
            }
        }
        for(int i = 1; i <= Size; ++i)
        {
            if(block[i] == -1) continue;
            cout << block[i] << ' ';
        }
        if(cnt > f) cout << "缺页";
        cout << endl;
    }
    cout << "CLOCK 缺页中断次数: " << cnt << endl;
    cout << "CLOCK 缺页率: "<< cnt / (1.0*pagesNum) << '
' << endl;
}

int main()
{
    cout << "请输入页面序列长度和物理块数:"; 
    cin >> pagesNum >> Size;
    cout << "请输入页面访问序列:";
    for(int i = 0; i < pagesNum; ++i)
        cin >> temp, pages.push_back(temp);
    cout << endl; 
    FIFO();
    OPT();
    LRU();
    CLOCK();
    return 0;
}