C/C++教程

实验三 虚拟存储管理(OPT,FIFO,LRU,LFU,NUR算法的C++实现)

本文主要是介绍实验三 虚拟存储管理(OPT,FIFO,LRU,LFU,NUR算法的C++实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

实验三 虚拟存储管理

实验性质

  • 设计

建议学时

  • 4学时

实验目的

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

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

实验内容

(1) 通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成:

  1. 50%的指令是顺序执行的;

  2. 25%的指令是均匀分布在前地址部分;

  3. 25%的指令是均匀分布在后地址部分。

具体的实施方法是:

  1. 在 [ 0 , 319 ] [0, 319] [0,319]​​的指令地址之间随机选取一起点 m m m​;
  2. 顺序执行一条指令,即执行地址为 m + 1 m+1 m+1​ 的指令;
  3. 在前地址 [ 0 , m + 1 ] [0, m+1] [0,m+1]​​​​中随机选取一条指令并执行,该指令的地址为 m ′ m' m′​​;
  4. 顺序执行一条指令,其地址为 m ′ + 1 m'+1 m′+1​​​;
  5. 在后地址 [ m ′ + 2 , 319 ] [m'+2, 319] [m′+2,319]​中随机选取一条指令并执行;
  6. 重复上述步骤,直至执行 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) 计算并输出下述各种算法在不同的内存容量下的命中率。

  1. 最佳置换算法 ( O P T ) (OPT) (OPT);

  2. 先进先出的算法 ( F I F O ) (FIFO) (FIFO);

  3. 最近最少使用算法 ( L R U ) (LRU) (LRU);

  4. 最少访问页面算法 ( L F U ) (LFU) (LFU)​;

  5. 最近不经常使用算法 ( 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));
}
这篇关于实验三 虚拟存储管理(OPT,FIFO,LRU,LFU,NUR算法的C++实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!