©2020-2024 ioDraw All rights reserved
<>1、 实验目的
通过对页面、 页表、 地址转换和页面置换过程的模拟， 加深对虚拟页式内存管理系统的页面置换原理和实现过程的理解。
<>2、 实验基本知识及原理
需要调入新页面时， 选择内存中哪个物理页面被置换， 称为置换策略。 页面置换算法的目标：
把未来不再使用的或短期内较少使用的页面调出， 通常应在局部性原理指导下依据过去的统计数据进行预测， 减少缺页次数。
教材给出的常用的页面置换算法包括：
1） 最佳置换算法(OPT)： 置换时淘汰“未来不再使用的”或“在离当前最远位置上出现的”页面。
2） 先进先出置换算法(FIFO)： 置换时淘汰最先进入内存的页面， 即选择驻留在内存时间最长的页面被置换。
3） 最近最久未用置换算法(LRU)： 置换时淘汰最近一段时间最久没有使用的页面， 即选择上次使用距当前最远的页面淘汰
<>3、 实验内容
(1)假设每个页面中可存放 10 条指令， 分配给一作业的内存块（ 页框） 数为 4。
(2)用 C 语言模拟一作业的执行过程， 该作业共有 320 条指令， 即它的地址空间为 32 页， 目前它的所有页都还未调入内存。 在模拟过程中，
如果所访问的指令已在内存， 则显示其物理地址， 并转下一条指令。 如果所访问的指令还未装入内存， 则发生缺页， 此时须记录缺页的次数，
并将相应页调入内存;如果 4 个内存块中均已装入该作业， 则需进行页面置换;最后显示其物理地址， 并转下一条指令。 在所有 320 条指令执行完毕后，
请计算并显示作业运行过程中发生的缺页率。
(3)置换算法请分别考虑 OPT、 FIFO 和 LRU 算法。
(4) 测试用例(作业中指令序列)按下述原则生成:
通过随机数产生一个指令序列， 共 320 条指令。
① 50%的指令是顺序执行的；
② 25%的指令是均匀分布在前地址部分；
③ 25%的指令是均匀分布在后地址部分；
具体的实施方法是：
① 在[0, 319]的指令地址之间随机选取一起点 m；
② 顺序执行一条指令， 即执行地址为 m+1 的指令；
③ 在前地址[0, m+1]中随机选取一条指令并执行， 该指令的地址为 m1;
④ 顺序执行一条指令， 其地址为 m1+1;
⑤ 在后地址[m1+2, 319]中随机选取一条指令并执行；
⑥ 重复上述步骤①~⑤， 直到执行 320 条指令。
将指令序列变换为页地址流
假设： ① 页面大小为 1K； ② 用户内存容量为 4 页； ③用户虚存容量为 32K；
在用户虚存中， 按每 K 存放 10 条指令排列虚存地址， 即 320 条指令在虚存中的存放方式为：
第 0 条~第 9 条指令为第 0 页(对应虚存地址为[0,9]);
第 10 条~第 19 条指令为第 1 页(对应虚存地址为[10,19]);
……
第 310 条~第 319 条指令为第 31 页(对应虚存地址为[310,319]);
按以上方式， 用户指令可组成 32 页。
代码实现：
#include <iostream> #include<bits/stdc++.h> /* 2021-12-21 @浩茫 虚拟内存系统的页面置换算法 */
using namespace std; int a[320];//指令序列 int page[4]= {-1,-1,-1,-1}; //页框数组,-1代表为空
int page_num[4]; //记录每一页的次数 void creat_list() { int m; int i,m1,m2; for(i=0; i<
320;) { m =rand()%(320); //a[i]=m; //i++;//在[0, 319]的指令地址之间随机选取一起点 m a[i]=m+1; i
++;//顺序执行一条指令， 即执行地址为 m+1 的指令； m1 = rand()%(m+2); a[i]=m1; i++;//在前地址[0,
m+1]中随机选取一条指令并执行， 该指令的地址为 m1; a[i]=m1+1; i++;//顺序执行一条指令， 其地址为 m1+1; m2=m1+2+rand
()%(320-m1-2);// 在后地址[m1+2, 319]中随机选取一条指令并执行； a[i]=m2; i++; } } int b[320];
//每一条指令所在的页号 void show_page() { int i; for(i=0; i<320; i++) { b[i]=a[i]/10; } }
int void_page() //判断页框是否为空 { int i; for(i=0; i<4; i++) { if(page[i]==-1)return i
;//返回页框号 } return -1;//不为空 } int jude(int a)//判断是否已经存在该页 { for(int i=0; i<4; i++
) { if(page[i]==a)return i;//返回页框 } return -1;//不存在 } void OPT() { int i,x; int
dst_page=0; for(i=0; i<20; i++ ) { if(jude(b[i])!=-1)//判断页框内是否已经存在该页 { printf(
"第%d条指令%d已在内存中，物理位置：框%d+%d页内偏移\n",i+1,a[i],jude(b[i]),a[i]%10); printf("页框对应页号：
%d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } else { if(
void_page()!=-1) //当页框存在空位时直接放入 { x=void_page(); page[x]=b[i]; printf(
"第%d条指令%d不在内存中，将其放在：框%d+%d页内偏移\n",i+1,a[i],x,a[i]%10); printf("页框对应页号：
%d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } else//页框已满，进行页面置换
{ for(int j=0; j<4; j++) { for(int k=i+1; k<320; k++) { if(page[j]==b[k]) {
page_num[j]=k-i; break; } } } x=0; for(int j=0; j<4; j++) { if(page_num[j]>x) {
x=page_num[j]; dst_page = j ; } } page[dst_page] = b[i]; printf(
"第%d条指令%d不在内存中，页面置换 ",i+1,a[i]); printf("：框%d+%d页内偏移\n",dst_page,a[i]%10);
printf("页框对应页号： %d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } }
} } void LRU() { int i,x; int dst_page=0; for(i=0; i<20; i++ ) { if(jude(b[i])!=
-1)//判断页框内是否已经存在该页 { printf("第%d条指令%d已在内存中，物理位置：框%d+%d页内偏移\n",i+1,a[i],jude(b[i]
),a[i]%10); printf("页框对应页号： %d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3
],b[i]); } else { if(void_page()!=-1) //当页框存在空位时直接放入 { x=void_page(); page[x]=b[
i]; printf("第%d条指令%d不在内存中，将其放在：框%d+%d页内偏移\n",i+1,a[i],x,a[i]%10); printf(
"页框对应页号： %d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } else
//页框已满，进行页面置换 { for(int j=0; j<4; j++) { for(int k=i-1; k>=0; k--) { if(page[j]
==b[k]) { page_num[j]=i-k; break; } } } x=0; for(int j=0; j<4; j++) { if(
page_num[j]>x) { x=page_num[j]; dst_page = j ; } } page[dst_page] = b[i]; printf
("第%d条指令%d不在内存中，页面置换 ",i+1,a[i]); printf("：框%d+%d页内偏移\n",dst_page,a[i]%10);
printf("页框对应页号： %d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } }
} } void FIFO() { int i,x; int dst_page=0; int counter=0;//置换标志位 for(i=0; i<20;
i++ ) { if(jude(b[i])!=-1)//判断页框内是否已经存在该页 { printf(
"第%d条指令%d已在内存中，物理位置：框%d+%d页内偏移\n",i+1,a[i],jude(b[i]),a[i]%10); printf("页框对应页号：
%d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } else { if(
void_page()!=-1) //当页框存在空位时直接放入 { x=void_page(); page[x]=b[i]; counter=(counter+
1)%4; printf("第%d条指令%d不在内存中，将其放在：框%d+%d页内偏移\n",i+1,a[i],x,a[i]%10); printf(
"页框对应页号： %d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } else
//页框已满，进行页面置换 { page[counter] = b[i]; counter=(counter+1)%4; printf(
"第%d条指令%d不在内存中，页面置换 ",i+1,a[i]); printf("：框%d+%d页内偏移\n",dst_page,a[i]%10);
printf("页框对应页号： %d\t%d\t%d\t%d\t\n\n",page[0],page[1],page[2],page[3],b[i]); } }
} } int main() { int i; int j; int n ; cout << "=====虚拟内存页面置换算法=====" << endl;
cout<<"随机产生320条指令序列中......\n"; creat_list(); for(int i=0; i<320; i++) { printf(
"%-3d ",a[i]); if((i+1)%16==0)cout<<"\n"; } cout<<"对应访问的页面为：\n"; show_page();
for(i=0; i<320; i++) { printf("%-2d ",b[i]); if((i+1)%16==0)cout<<"\n"; } while(
true) { cout<<"\n选择你的算法：\n"; cout<<"1、最佳置算法(OPT)\n"; cout<<"2、先进先出置换算法(FIFO)\n";
cout<<"3、最近最久未用置换算法(LRU)\n"; cin>>n; if(n==-1)break; switch(n) { case 1: cout<<
"最佳置算法(OPT)======\n"; OPT(); break; case 2: cout<<"先进先出置换算法(FIFO)======\n"; FIFO
(); break; case 3: cout<<"最近最久未用置换算法(LRU)======\n"; LRU(); break; } } return 0;
}