[数据结构与算法]操作系统——页面置换算法模拟

Opt&FIFO

#include <iostream>
#include <time.h>
#include <vector>

using namespace std;

void calculate(vector<int> pg, int hit)
{
    cout << "命中次数：" << hit << endl;
    cout << "未命中次数：" << pg.size() - hit << endl;
    cout << "缺页率：" << (pg.size() - hit) * 100 / pg.size() << "%" << endl;
}

bool serach(vector<int> &frame, int key)
{
    for (auto &fr : frame)
    {
        if (key == fr)
            return true;
    }
    return false;
}

int to_used_optimal(vector<int> frame, vector<int> pg, int index)
{
    int res = -1, farthest = index + 1;

    for (int i = 0; i < frame.size(); i++)
    {
        int j;
        for (j = index; j < pg.size(); j++)
        {
            if (pg[j] == frame[i])
            {
                if (j > farthest)
                {
                    farthest = j;
                    res = i;
                }
                break;
            }
        }
        if (j == pg.size())
            return i;
    }
    return res == -1 ? 0 : res;
}

void Optimal(vector<int> pg, int fn)
{
    vector<int> frame;
    int hit = 0;

    for (int i = 0; i < pg.size(); i++)
    {

        if (serach(frame, pg[i]))
        {
            hit++;
            continue;
        }

        if (frame.size() < fn)
            frame.push_back(pg[i]);
        else
        {
            int res = to_used_optimal(frame, pg, i);
            frame[res] = pg[i];
        }
    }
    calculate(pg, hit);
}

void FIFO(vector<int> pg, int fn)
{
    vector<int> frame;
    int hit = 0;

    int index = 0; // 逻辑变量
    for (int i = 0; i < pg.size(); i++)
    {
        if (serach(frame, pg[i]))
        {
            hit++
            continue;
        }

        if (frame.size() < fn)
        {
            frame.push_back(pg[i]);
        }
        else
        {

            frame[index % fn] = pg[i];
            index++;
        }
    }
    calculate(pg, hit);
}

void memu()
{
    cout << "*********************************" << endl;
    cout << "*           | ￣▽￣ |           *" << endl;
    cout << "*"
         << "                               "
         << "*" << endl;
    cout << "*"
         << "                               "
         << "*" << endl;
    cout << "*"
         << "          1.Show  Opt          "
         << "*" << endl;
    cout << "*"
         << "          2.Show FIFO          "
         << "*" << endl;
    cout << "*"
         << "          3.Show  ALL          "
         << "*" << endl;
    cout << "*"
         << "                               "
         << "*" << endl;
    cout << "*"
         << "                               "
         << "*" << endl;
    cout << "*********************************" << endl;
}

int main()
{
    vector<int> pg;
    srand((unsigned)time(NULL));
    int pn, fn, visit_num;
    cout << "请输入访问次数：";
    cin >> visit_num;
    cout << "请输入页的数量pn：";
    cin >> pn;
    for (int i = 0; i < visit_num; i++)
    {
        int rand_num = rand() % pn;
        pg.push_back(rand_num);
    }
    // 看一下随机数
    cout << "电脑随机生成页面走向" << endl;
    for (auto &c : pg)
    {
        cout << c << " ";
    }
    puts("");

    cout << "请输入内存块数：";
    cin >> fn;

    cout << "请选择你要替换的算法，选择如下" << endl;
    memu();
    int num;
    cout << "请输入你的选择";
    cin >> num;
    switch (num)
    {
    case 1:
    {
        cout << "最佳置换算法" << endl;
        Optimal(pg, fn);
        break;
    }
    case 2:
    {
        cout << "先进先出算法" << endl;
        FIFO(pg, fn);
        break;
    }
    case 3:
    {
        cout << "最佳置换算法" << endl;
        Optimal(pg, fn);
        cout << "-----------------------" << endl;
        cout << "先进先出算法" << endl;
        FIFO(pg, fn);
        break;
    }
    }
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖