|
前言
需要调入新页面时，选择内存中哪个物理页面被置换，称为置换策略。页面置换算法的目标：把未来不再使用的或短期内较少使用的页面调出，通常应在局部性原理指导下依据过去的统计数据进行预测，减少缺页次数。
一、常用的页面置换算法
1）最佳置换算法(OPT)：置换时淘汰“未来不再使用的”或“在离当前最远位置上出现的”页面。
2）先进先出置换算法(FIFO)：置换时淘汰最先进入内存的页面，即选择驻留在内存时间最长的页面被置换。
3）最近最久未用置换算法(LRU)：置换时淘汰最近一段时间最久没有使用的页面，即选择上次使用距当前最远的页面淘汰。
4）时钟算法(Clock)：也称最近未使用算法(NRU, Not Recently Used)，它是 LRU 和 FIFO 的折衷。
二、实验内容
(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 页。
三、教材中对四种算法替换行为的描述
四、C语言代码
#include
#include
int value;//输入value值以确定用户选择的算法
int count[4];//用于LRU算法，存储最近访问的4个页面，count[0]代表最久未使用或修改的页面号
int fifo;//用于FIFO算法
int lru;//用于LRU算法
double count_OPT = 0; //缺页次数
double count_FIFO = 0; //缺页次数
double count_LRU = 0; //缺页次数
int instrAddr[320]; //指令地址流 数组0123456789...319
int pageAddr[320]; //页地址流数组00000000001111111111222222222233333333...31(10),不是顺序的
typedef struct Data //数据域
{
int page; //装进的用户虚存页号
int block; //块号
}data;
typedef struct BlockNode //单向循环链表
{
Data data;
struct BlockNode *next;
} Block, *BlockList;
//定义内存块
BlockList block1;
BlockList block2;
BlockList block3;
BlockList block4;
void init() //初始化
{
block1 = new Block;
block2 = new Block;
block3 = (Block*)malloc(sizeof(Block));
block4 = (BlockList)malloc(sizeof(Block));
//malloc函数用于在内存开辟了一段地址，而这段地址的首地址存在返回的那个指针变量里，由于不知道到底这段地址有多长，
//可以存什么变量，所以它的类型是空的，你可以强制类型转换，使其变成确定长度，固定存放一种数据类型的地址，
//而不管它是哪种类型，其首地址还是原来那个，还是存在一个指针变量中，指针变量就是放指针的嘛，指针是一个地址，
//指针变量是一个我们定义的，用来放那个地址的变量。
//获取Block的字段长度，然后强转为BlockList类型。block4变量就代表地址长度和Block一样所占内存空间同样大小的BlockList
block1->data.page = -1;
block2->data.page = -1;
block3->data.page = -1;
block4->data.page = -1;
block1->data.block = 0;
block2->data.block = 1;
block3->data.block = 2;
block4->data.block = 3;
block1->next = block2;
block2->next = block3;
block3->next = block4;
block4->next = block1;
for(int i = 0; i
BlockList p = block1;
for(int i = 0; i
p->data.page = pageNum;
count_OPT++; //缺页次数+1
// printf("-------------------------------\n");
// printf("| %d |\n",p->data.block);
// printf("-------------------------------\n");
// printf("| 访问第 %d 条指令 %d |\n", pos,instrAddr);
// printf("-------------------------------\n");
// for( int n=0; ndata.block+1, instrAddr % 10+1);
// printf("-------------------------------\n\n");
printf("访问第 %d 条指令 ", pos);
printf("指令地址：%d \n", instrAddr);
printf("指令未存在于内存！页面第一次调入成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条 \n\n", pageNum, instrAddr % 10+1, p->data.block+1, instrAddr % 10+1);
return;
}
if(p->data.page == pageNum)//新访问的指令存在于内存中
{
printf("访问第 %d 条指令 ", pos);
printf("指令地址：%d \n", instrAddr);
printf("指令已存在于内存中！无需进行页面置换！\n用户指令第%d页第%d条的物理地址为："
"第 %d 块第 %d 条 \n\n", pageNum, instrAddr % 10+1, p->data.block+1, instrAddr % 10+1);
return;
}
p = p->next;
}
//OPT置换策略
int allBlockPage[4]; //记录当前页地址
for(int i = 0; i
for(int j = pos; j
nextAddr[i] = j;
break;
}
}
}
int temp = 0; //页地址
int blockPos; //内存块的地址
for(int i = 0; i
temp = nextAddr[i];
blockPos = i;
}
}
for(int i = 0; i
p->data.page = pageNum;
count_OPT++;
printf("访问第 %d 条指令 ", pos);
printf("指令地址：%d \n", instrAddr);
printf("指令未存在于内存中但内存块已满！页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条 \n\n", pageNum, instrAddr % 10+1, p->data.block+1, instrAddr % 10+1);
}
p = p->next;
}
}
void FIFO(int pageNum, int instrAddr, int pos)//先进先出置换算法(FIFO)
{
BlockList p = block1;//指向第一个块
for( int i=0; i
fifo=pos;
if( i==3 )
fifo++;
p->data.page = pageNum;
count_FIFO++;
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令未存在于内存中，页面第一次调入成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
return;
}
if( p->data.page == pageNum )//页面已存在于内存中
{
if( posdata.block+1,instrAddr%10+1);
return;
}
p = p->next;
}
//FIFO替换策略
for( int i=0; inext;
fifo++;
p->data.page = pageNum;
count_FIFO++;
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
}
void LRU(int pageNum, int instrAddr, int pos)//最近最久未用置换算法(LRU)
{
int tem=0;
int mids;
BlockList p = block1;//指向第一个块
for(int i=0;i
p->data.page = pageNum;
count[lru] = pageNum;
lru++;
count_LRU++;
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令未存在于内存中，页面第一次调入成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
return;
}
if( p->data.page ==pageNum )//页面已存在于内存中
{
for(int d=0; d
mids=d;
break;
}
}
if(mids==0)
{
for( int j=0; j
for( int j=1; j
count[2] = count[3];
lru--;
}
if( mids != 3 )
{
count[lru] = pageNum;
lru++;
}
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令已存在于内存中，无需进行页面置换！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n",instrAddr/10,instrAddr%10+1,p->data.block+1,instrAddr%10+1);
return;
}
p = p->next;
}
if( lru==4 )
{
for( int i=0; i
p->data.page = pageNum;
count_LRU++;
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
for( int g=0; g
count[lru] = pageNum;
lru++;
p->data.page = pageNum;
count_LRU++;
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
return;
}
else
{
count[lru] = pageNum;
lru++;
for( int j=0; j
if( p->data.page == count[i] )
{
tem=1;
break;
}
else
tem=0;
}
if( tem==0 )
{
p->data.page = pageNum;
count_LRU++;
printf("访问第 %d 条指令 ",pos);
printf("指令地址：%d\n",instrAddr);
printf("指令未存在于内存中，页面置换成功！\n用户指令第 %d 页第 %d 条的物理地址为："
"第 %d 块第 %d 条\n\n", instrAddr/10, instrAddr%10+1, p->data.block+1, instrAddr%10+1);
return;
}
p=p->next;
}
}
}
void handle() //计算缺页率
{
if( value==1 )
{
printf("**********最佳置换算法(OPT)**********\n\n");
for( int i = 0; i
fifo = 0;
printf("**********先进先出置换算法(FIFO)**********\n\n");
for(int i = 0; i
lru=0;
printf("**********最近最久未用置换算法(LRU)**********\n\n");
for(int i = 0; i
printf("输入下列某一序号以开始执行！\n\n");
printf("1、最佳置换算法(OPT)\n");
printf("2、先进先出置换算法(FIFO)\n");
printf("3、最近最久未用置换算法(LRU)\n\n");
}
int main()
{
// block1 = new Block;
// block2 = new Block;
// block3 = (Block*)malloc(sizeof(Block));
// block4 = (BlockList)malloc(sizeof(Block));
while( true )
{
count_OPT = 0; //记录OPT缺页次数
count_FIFO = 0; //记录FIFO缺页次数
count_LRU = 0; //记录LRU缺页次数
init();//初始化
menu();//菜单
printf("你选择的序号是：");
scanf("%d",&value);
handle();//执行算法的同时计算缺页率
}
return 0;
}
该C语言代码的循环链表初始化和OPT算法部分借鉴了这篇博客。如有不妥告知修改。 欢迎各位前辈对代码批评指正，感谢你的观看！
|