存储管理的主要功能之一是合理地分配空间。请求分页存储管理是常用的虚拟存储管理技术。
本实验的目的是请求分页存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请 求分页存储管理的页面置换方法。
(1) 通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成:
50%的指令是顺序执行的;
25%的指令是均匀分布在前地址部分;
25%的指令是均匀分布在后地址部分。
具体的实施方法是:
(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)); }