实验三虚拟存储管理（OPT，FIFO，LRU，LFU，NUR算法的C++实现）

2022-07-31 23:06:52

实验三虚拟存储管理

实验性质

设计

建议学时

4学时

实验目的

存储管理的主要功能之一是合理地分配空间。请求分页存储管理是常用的虚拟存储管理技术。

本实验的目的是请求分页存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求分页存储管理的页面置换方法。

实验内容

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：

50%的指令是顺序执行的；
25%的指令是均匀分布在前地址部分；
25%的指令是均匀分布在后地址部分。

具体的实施方法是：

在［ 0 , 319 ］［0, 319］［0,319］的指令地址之间随机选取一起点 m m m；
顺序执行一条指令，即执行地址为 m + 1 m+1 m+1 的指令；
在前地址［ 0 , m + 1 ］［0, m+1］［0,m+1］中随机选取一条指令并执行，该指令的地址为 m ′ m' m′；
顺序执行一条指令，其地址为 m ′ + 1 m'+1 m′+1；
在后地址［ m ′ + 2 , 319 ］［m'+2, 319］［m′+2,319］中随机选取一条指令并执行；
重复上述步骤，直至执行 320 320 320 次指令。

（2）将指令序列变换成页地址流

设：1️⃣ 页面大小为1K；2️⃣ 用户内存容量为4页到32页；3️⃣ 用户虚存容量为32K；

在用户虚存中，按每 K K K 存放 10 10 10 条指令排列虚存地址，即 320 320 320 条指令在虚存中的存放方式为: 第 0 0 0 条〜第 9 9 9 条指令为第 0 0 0 页（对应的虚存地址为［ 0 , 9 ］［0, 9］［0,9］）；

第10条〜第19条指令为第1页（对应的虚存地址为［ 10 , 19 ］［10, 19］［10,19］）；

…

第 310 310 310 条〜第 319 319 319 条指令为第 31 31 31 页（对应的虚存地址为［ 310 , 319 ］［310, 319］［310,319］）；

按以上方式，用户指令可组成 32 32 32 页。

（3）计算并输出下述各种算法在不同的内存容量下的命中率。

最佳置换算法（ O P T ）（OPT）（OPT）；
先进先出的算法（ F I F O ）（FIFO）（FIFO）；
最近最少使用算法（ L R U ）（LRU）（LRU）；
最少访问页面算法（ L F U ）（LFU）（LFU）；
最近不经常使用算法（ N U R ）（NUR）（NUR）。

命中率 = 1 − （页面失效次数） / （页地址流长度）命中率 = 1-（页面失效次数）/ （页地址流长度）命中率=1−（页面失效次数）/（页地址流长度）

在本实验中，页地址流的长度为320,页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

随机数产生办法：可以使用系统提供函数 r a n d ( ) rand() rand(),分别进行初始化和产生随机数。例如： s r a n d ( ) srand() srand(); 语句可初始化的一个随机数：

a [ 0 ] = 10 ∗ r a n d ( ) / 32767 ∗ 319 + 1 a[0]=10*rand()/32767*319+1 a[0]=10∗rand()/32767∗319+1;
a [ 1 ] = 10 ∗ r a n d ( ) / 32767 ∗ a [ 0 ] a[1] = 10*rand()/32767*a[0] a[1]=10∗rand()/32767∗a[0];

语句可用来产生 a [ 0 ] a[0] a[0] 与 a [ 1 ] a[1] a[1] 中的随机数。

实验要求

1）上机前仔细编好程序；

2）上机时独立调试程序；

3）提交实验报告，包括纸质稿和电子稿两部分。实验报告要求详见实验报告模板。

代码展示

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <deque>
using namespace std;

// 全局变量定义
const int Page_address_stream = 320;
const int Virtual_page = 32;
vector<int> virtual_page_list(Page_address_stream);

// 页表结构体
struct PageTable
{
    int pageNum;
    // 状态位P，指示该页是否已调入内存
    int P;
    // OPT中记录过多久会被访问
    // LFU中记录在一段时间内被访问次数
    // NUR中记录最近是否被访问
    int A;
};
vector<PageTable> PageTableList(Virtual_page);

// 函数声明
void OPT(int user_memory_capacity);
void FIFO(int user_memory_capacity);
void LRU(int user_memory_capacity);
void LFU(int user_memory_capacity);
void NUR(int user_memory_capacity);
void refresh();

// 主函数
int main()
{
    refresh();
    // 随机种子
    srand((unsigned int)time(NULL));
    vector<int> lst;
    // 随机生成指令序列
    for (int i = 0; i < Page_address_stream; i += 4)
    {
        // 随机起点 m
        int m = rand() % (Page_address_stream);
        // 顺序执行：地址（m+1）
        lst.push_back(m + 1);
        // 前地址中选择地址为 m2 的执行
        int m2 = rand() % (m + 2);
        lst.push_back(m2);
        // 顺序执行：地址（m2+1）
        lst.push_back(m2 + 1);
        // 后地址中选择指令执行
        lst.push_back(rand() % (Page_address_stream - (m2 + 2)) + (m2 + 2));
    }
    // 打印指令序列
    // for (int i = 0; i < Page_address_stream; i++)
    // {
    //     printf("%d\t", lst[i]);
    //     if ((i + 1) % 4 == 0)
    //     {
    //         cout << endl;
    //     }
    // }

    // 将指令序列变换成页地址流
    // 每条指令对应一个页和页偏移
    for (int i = 0; i < Page_address_stream; i++)
    {
        virtual_page_list[i] = lst[i] / 10;
    }
    // 算法测试
    printf("Page Frames\tOPT\t\tFIFO\t\tLRU\t\tLFU\t\tNUR\n");
    for (int i = 4; i <= Virtual_page; i++)
    {
        printf("%d\t\t", i);
        OPT(i);
        FIFO(i);
        LRU(i);
        LFU(i);
        NUR(i);
        cout << endl;
    }
    system("pause");
    return 0;
}

void refresh()
{
    // 页表数组赋值
    for (int i = 0; i < Virtual_page; i++)
    {
        PageTableList[i].pageNum = i;
        PageTableList[i].P = 0;
        PageTableList[i].A = 0;
    }
}

void OPT(int user_memory_capacity)
{
    refresh();
    deque<int> q;
    int missing_page = 0;
    for (int i = 0; i < Page_address_stream; i++)
    {
        int cur_page = virtual_page_list[i];
        // 如果当前页不在内存中
        if (PageTableList[cur_page].P == 0)
        {
            missing_page++;
            // 如果内存没满
            if (q.size() < user_memory_capacity)
            {
                PageTableList[cur_page].P = 1;
                q.push_back(cur_page);
            }
            // 内存已经满了,删除最长时间内不再访问元素
            else
            {
                int del_page;
                for (int j = i + 1; j < Page_address_stream; j++)
                {
                    int far_page = virtual_page_list[j];
                    if (PageTableList[far_page].P == 1 && PageTableList[far_page].A == 0)
                    {
                        PageTableList[far_page].A = j - i;
                        del_page = far_page;
                    }
                }
                // 查看是否有页在内存当中但后续再也用不到的情况
                // 这种情况下其实页表的A应该为无穷大，反而是我们应该去删除的
                for (int idx = 0; idx < q.size(); idx++)
                {
                    if (PageTableList[q[idx]].P == 1 && PageTableList[q[idx]].A == 0)
                    {
                        PageTableList[q[idx]].A = 1e5;
                        del_page = q[idx];
                        break;
                    }
                }
                // 页表A重置
                for (int i = 0; i < Virtual_page; i++)
                {
                    PageTableList[i].A = 0;
                }
                PageTableList[del_page].P = 0;
                int local = 0;
                for (; local < q.size(); local++)
                {
                    if (q[local] == del_page)
                    {
                        break;
                    }
                }
                q.erase(q.begin() + local);
                PageTableList[cur_page].P = 1;
                q.push_back(cur_page);
            }
        }
    }
    printf("%.4f\t\t", 1 - ((double)missing_page / Page_address_stream));
}

void FIFO(int user_memory_capacity)
{
    refresh();
    // 用deque模拟queue
    deque<int> q;
    int missing_page = 0;
    for (int i = 0; i < Page_address_stream; i++)
    {
        int cur_page = virtual_page_list[i];
        // 如果当前页不在内存中
        if (PageTableList[cur_page].P == 0)
        {
            missing_page++;
            // 如果内存没满
            if (q.size() < user_memory_capacity)
            {
                PageTableList[cur_page].P = 1;
                q.push_back(cur_page);
            }
            // 内存已经满了，弹出队首
            else
            {
                PageTableList[q.front()].P = 0;
                q.pop_front();
                PageTableList[cur_page].P = 1;
                q.push_back(cur_page);
            }
        }
    }
    printf("%.4f\t\t", 1 - ((double)missing_page / Page_address_stream));
}

void LRU(int user_memory_capacity)
{
    refresh();
    // 用deque模拟stack
    deque<int> q;
    int missing_page = 0;
    for (int i = 0; i < Page_address_stream; i++)
    {
        int cur_page = virtual_page_list[i];
        // 如果当前页不在内存中
        if (PageTableList[cur_page].P == 0)
        {
            missing_page++;
            // 如果内存没满
            if (q.size() < user_memory_capacity)
            {
                PageTableList[cur_page].P = 1;
                q.push_back(cur_page);
            }
            // 内存已经满了，弹出队首
            else
            {
                // 弹出栈底元素（最久未访问）
                PageTableList[q.front()].P = 0;
                q.pop_front();
                PageTableList[cur_page].P = 1;
                q.push_back(cur_page);
            }
        }
        // 当前页在内存中，则将该页从栈中取出，放入栈顶
        else
        {
            // 找到该页下标
            int idx = 0;
            for (; idx < q.size(); idx++)
            {
                if (q[idx] == cur_page)
                {
                    break;
                }
            }
            // 弹出该页
            q.erase(q.begin() + idx);
            // 放入栈顶
            q.push_back(cur_page);
        }
    }
    printf("%.4f\t\t", 1 - ((double)missing_page / Page_address_stream));
}

void LFU(int user_memory_capacity)
{
    refresh();
    deque<int> q;
    int missing_page = 0;
    for (int i = 0; i < Page_address_stream; i++)
    {
        int cur_page = virtual_page_list[i];
        // 如果当前页不在内存中
        if (PageTableList[cur_page].P == 0)
        {
            missing_page++;
            // 如果内存没满
            if (q.size() < user_memory_capacity)
            {
                PageTableList[cur_page].P = 1;
                PageTableList[cur_page].A++;
                q.push_back(cur_page);
            }
            // 内存已经满了，弹出访问频次最少的
            else
            {
                int minimum_frequency = PageTableList[q[0]].A;
                int min_idx = 0;
                for (int j = 1; j < q.size(); j++)
                {
                    // 不能等于，因为如果频次相同肯定踢掉在内存呆更久的那个
                    if (minimum_frequency > PageTableList[q[j]].A)
                    {
                        minimum_frequency = PageTableList[q[j]].A;
                        min_idx = j;
                    }
                }
                PageTableList[q[min_idx]].P = 0;
                PageTableList[q[min_idx]].A = 0;
                q.erase(q.begin() + min_idx);
                PageTableList[cur_page].P = 1;
                PageTableList[cur_page].A++;
                q.push_back(cur_page);
            }
        }
        // 当前页在内存中，该页访问次数加一
        else
        {
            PageTableList[cur_page].A++;
        }
    }
    printf("%.4f\t\t", 1 - ((double)missing_page / Page_address_stream));
}

void NUR(int user_memory_capacity)
{
    refresh();
    deque<int> q;
    int missing_page = 0;
    // 循环数组中指针p
    int p = 0;
    for (int i = 0; i < Page_address_stream; i++)
    {
        int cur_page = virtual_page_list[i];
        // 如果当前页不在内存中
        if (PageTableList[cur_page].P == 0)
        {
            missing_page++;
            // 如果内存没满
            if (q.size() < user_memory_capacity)
            {
                PageTableList[cur_page].P = 1;
                PageTableList[cur_page].A = 1;
                q.push_back(cur_page);
            }
            // 内存已经满了
            else
            {
                while (1)
                {
                    if (PageTableList[q[p]].A == 0)
                    {
                        PageTableList[q[p]].P = 0;
                        q[p] = cur_page;
                        PageTableList[cur_page].P = 1;
                        PageTableList[cur_page].A = 1;
                        p++;
                        if (p == user_memory_capacity)
                        {
                            p = 0;
                        }
                        break;
                    }
                    else
                    {
                        PageTableList[q[p]].A = 0;
                        p++;
                        if (p == user_memory_capacity)
                        {
                            p = 0;
                        }
                    }
                }
            }
        }
        // 当前页在内存中,访问位置1
        else
        {
            PageTableList[cur_page].A = 1;
        }
    }
    printf("%.4f\t\t", 1 - ((double)missing_page / Page_address_stream));
}

码农公寓

实验三 虚拟存储管理