实验三 虚拟存储管理
实验性质
设计
建议学时
4学时
实验目的
存储管理的主要功能之一是合理地分配空间。请求分页存储管理是常用的虚拟存储管理技术。
本实验的目的是请求分页存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请 求分页存储管理的页面置换方法。
实验内容
（1） 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
50%的指令是顺序执行的；
25%的指令是均匀分布在前地址部分；
25%的指令是均匀分布在后地址部分。
具体的实施方法是：
在［ 0 , 319 ］的指令地址之间随机选取一起点 m ；
顺序执行一条指令，即执行地址为 m + 1 的指令；
在前地址［ 0 , m + 1 ］中随机选取一条指令并执行，该指令的地址为 m ；
顺序执行一条指令，其地址为 m ′ + 1在后地址［ m ′ + 2 , 319 ］ 中随机选取一条指令并执行；
重复上述步骤，直至执行 320 次指令。
（2） 将指令序列变换成页地址流
设：1️⃣ 页面大小为1K；2️⃣ 用户内存容量为4页到32页；3️⃣ 用户虚存容量为32K；
在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为: 第 0 条〜第 9 条指令为第 0页（对应的虚存地址为［ 0 , 9 ］ 第10条〜第19条指令为第1页（对应的虚存地址为［ 10 , 19 ］
…
第 310 条〜第 319 条指令为第 31页（对应的虚存地址为［ 310 , 319 ］
按以上方式，用户指令可组成 32页。
（3） 计算并输出下述各种算法在不同的内存容量下的命中率。
最佳置换算法（ O P T ） ；
先进先出的算法（ F I F O ）；
最近最少使用算法（ L R U ） ；
最少访问页面算法（ L F U ）；
最近不经常使用算法（ N U R ） 。
命 中 率 = 1 − （ 页 面 失 效 次 数 ） / （ 页 地 址 流 长 度 ）
在本实验中，页地址流的长度为320,页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
随机数产生办法：可以使用系统提供函数 r a n d ( ),分别进行初始化和产生随机数。例如：s r a n d ( ) 语句可初始化的一个随机数：
a [ 0 ] = 10 ∗ r a n d ( ) / 32767 ∗ 319 + 1
a [ 1 ] = 10 ∗ r a n d ( ) / 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)); }
