实验三页面置换算法模拟实验.docx
《实验三页面置换算法模拟实验.docx》由会员分享，可在线阅读，更多相关《实验三页面置换算法模拟实验.docx（18页珍藏版）》请在冰点文库上搜索。
实验三页面置换算法模拟实验
计算机科学系
实验报告书
课程名：
《操作系统》
题目：
虚拟存储器管理
页面置换算法模拟实验
班级：
学号：
姓名：
一、实验目的与要求
1.目的：
请求页式虚存管理是常用的虚拟存储管理方案之一。
通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。
2.要求：
本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。
其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。
要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。
程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。
二、实验说明
1．设计中虚页和实页的表示
本设计利用C语言的结构体来描述虚页和实页的结构。
pn
pfn
time
pn
pfn
next
虚页结构实页结构
在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值围是0—9。
pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。
time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。
在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。
pfn代表实页号，取值围（0—n-1）由动态指派的实页数n所决定。
next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。
2．关于缺页次数的统计
为计算命中率，需要统计在20次的虚页访问中命中的次数。
为此，程序应设置一个计数器count，来统计虚页命中发生的次数。
每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页，此虚页被命中，count加1。
最终命中率=count/20*100%。
3．LRU算法中“最近最久未用”页面的确定
为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。
当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。
4．算法中实页的组织
因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。
为了调度算法实现的方便，可以考虑引入free和busy两个链表：
free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。
当所要访问的一个虚页不在实页中时，将产生缺页中断。
此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。
若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：
对于FIFO算法要将busy_head所指的实页从busy链表中取下，分配给该
虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。
三、程序流程图（要求画出非常详细的流程图）
四、主要程序清单/
//动态指定实页个数的页面置换算法,包括FIFO和LRU两个算法。
#include
#include
#include
#include
#defineM10//10个虚页
#defineN20//20个页面的访问序列
#defineL10//最大10个实页。
//定义虚页的结构
typedefstructVirtualPage
{
intpn;
intpfn;
inttime;
}VirtualPage;
//定义实页的结构
typedefstructPage
{
intpn;
intpfn;
structPage*next;
}Page;
structPagepp[M];//定义一个存放10个实页的数组，在底下还要将其串成链表
structVirtualPagevp[M];//定义存放10个虚页的数组
intqueue[N];//定义一个数组，存放随机生成的20个数，表示访问虚页的次序，里面的数值不能超过9
intcount;//存放缺页次数，用来统计缺页率。
本算法没有考虑预调页，只要该页不在存，就认为缺页一次。
intcountime;//用于LRU算法中，找出要淘汰的页。
每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值
intMemoryStatus[L][N];//记录当访问每一个虚页时，存中的5个实页的详细信息。
intNotInMemory[N];//表示每次虚页访问是否在存
structPage*Free,*Free_head,*Free_tail,*Busy,*Busy_tail,*Busy_head,*temp,*temp_small;
voidFIFO（）//先入先出算法的具体实现。
{
inti,j,k,currentpage;//一些临时变量
for（i=0;i直到把20个虚页处理完为止。
{
//当前访问的虚页是哪一页？
由数组queue[i]中的值表示
currentpage=queue[i];
//判断该虚页是否已经调入存
if（vp[currentpage].pfn!
=-1）//表示该页已经在存中，可以直接访问。
同时记录访问该页时对应的实页信息（和前一页相同）
{
for（j=0;j{
MemoryStatus[j][i]=MemoryStatus[j][i-1];
}
NotInMemory[i]=0;
}
else//该页不在存，需要请求调页
{
count=count+1;//缺页数加1
if（Free!
=NULL）//如果Free链表不为空，表示存中还有空的实页，故从Free链表中取队首元素，装入该虚页，并修改相关信息。
{
temp=Free_head;//本程序中用Free表示链表的起始地址，Free_head表示链表中的第一个元素地址。
实际上两者的值永远相等。
Free_head=Free_head->next;
Free=Free_head;
//将虚页currentpage装入temp指向的实页，该实页的编号为temp->pfn
vp[currentpage].pfn=temp->pfn;
temp->pn=currentpage;
//将temp指向的实页插入Busy链表的末尾
temp->next=NULL;
if（Busy==NULL）//如果是第一次把虚页装入实页，则temp就是Busy链表的第一个元素。
{
Busy=temp;
Busy_head=Busy;
Busy_tail=Busy;
}
else//如果不是第一次把虚页装入实页，则将temp插入Busy链表的队尾。
{
Busy_tail->next=temp;
Busy_tail=temp;
}
//修改存状态
for（k=0;k{
MemoryStatus[k][i]=MemoryStatus[k][i-1];
}
MemoryStatus[temp->pfn][i]=currentpage;//虚页currentpage装入了temp->pfn表示的那个实页里
}
else//如果Free链表为空，需要置换一页出去。
由于采用FIFO算法，故取busy链表的队首元素，将其置换出去，修改信息后插入队尾。
{
//将Busy首元素取出，赋给temp
temp=Busy;
Busy_head=Busy->next;
Busy=Busy_head;
//将当前虚页currentpage装入temp指向的实页，修改其信息
vp[temp->pn].pfn=-1;//该页被置换出去了，所以其pfn字段要设置成-1，表示其已经不再存。
vp[currentpage].pfn=temp->pfn;//currentpage被装入存，更新其pfn字段为temp指向的实页。
temp->pn=currentpage;//temp指向的实页，装入了currentpage虚页
//将temp指向的实页插入Busy链表的末尾,此时不用再考虑Busy是否为空了。
temp->next=NULL;
Busy_tail->next=temp;
Busy_tail=temp;
//修改存状态
for（k=0;k{
MemoryStatus[k][i]=MemoryStatus[k][i-1];
}
MemoryStatus[temp->pfn][i]=currentpage;//虚页currentpage装入了temp->pfn表示的那个实页里
}
}
}
}
voidLRU（）
{
inti,j,k,currentpage;//一些临时变量
for（i=0;i直到把20个虚页处理完为止。
{
//当前访问的虚页是哪一页？
由数组queue[i]中的值表示
currentpage=queue[i];
countime=countime+1;//每次访问一个虚页，将该变量值加1
vp[currentpage].time=countime;//设置当前访问的虚页的time值
//判断该虚页是否已经调入存
if（vp[currentpage].pfn!
=-1）//表示该页已经在存中，可以直接访问。
同时记录访问该页时对应的实页信息（和前一页相同）
{
for（j=0;j{
MemoryStatus[j][i]=MemoryStatus[j][i-1];
}
NotInMemory[i]=0;
}
else//该页不在存，需要请求调页
{
count=count+1;//缺页数加1
if（Free!
=NULL）//如果Free链表不为空，表示存中还有空的实页，故从Free链表中取队首元素，装入该虚页，并修改相关信息。
{
temp=Free_head;//本程序中用Free表示链表的起始地址，Free_head表示链表中的第一个元素地址。
实际上两者的值永远相等。
Free_head=Free_head->next;
Free=Free_head;
//将虚页currentpage装入temp指向的实页，该实页的编号为temp->pfn
vp[currentpage].pfn=temp->pfn;
temp->pn=currentpage;
//将temp指向的实页插入Busy链表的末尾
temp->next=NULL;
if（Busy==NULL）//如果是第一次把虚页装入实页，则temp就是Busy链表的第一个元素。
{
Busy=temp;
Busy_head=Busy;
Busy_tail=Busy;
}
else//如果不是第一次把虚页装入实页，则将temp插入Busy链表的队尾。
{
Busy_tail->next=temp;
Busy_tail=temp;
}
//修改存状态
for（k=0;k{
MemoryStatus[k][i]=MemoryStatus[k][i-1];
}
MemoryStatus[temp->pfn][i]=currentpage;//虚页currentpage装入了temp->pfn表示的那个实页里
}
else//如果Free链表为空，需要置换一页出去。
由于采用LRU算法，在busy链表中查找到time值最小的那个元素，置换到链表尾部
{
//查找time值最小的元素，找到后用temp_small指针表示
temp=Busy_head;
temp_small=Busy_head;
while（temp->next!
=NULL）
{
if（vp[temp_small->pn].time>vp[temp->next->pn].time）//若当前元素的time值比下一个元素的time值大，则更新temp_small为指向下一元素
{
temp_small=temp->next;
}
temp=temp->next;
}
//将当前虚页currentpage装入temp_small指向的实页，修改其信息
vp[temp_small->pn].pfn=-1;//该页被置换出去了，所以其pfn字段要设置成-1，表示其已经不再存。
vp[currentpage].pfn=temp_small->pfn;//currentpage被装入存，更新其pfn字段为temp_small指向的实页。
temp_small->pn=currentpage;//temp_small指向的实页，装入了currentpage虚页
//将temp_small指向的实页插入Busy链表的末尾
if（temp_small!
=Busy_tail）//如果temp_small指向的那个元素就是Busy链表的最后一个，则不用做任何操作。
{
if（temp_small==Busy_head）//如果temp_small指向的那个元素是Busy链表的第一个元素，则直接插入链表尾部
{
Busy=Busy_head->next;
Busy_head=Busy;
temp_small->next=NULL;
Busy_tail->next=temp_small;
Busy_tail=temp_small;
}
else//如果temp_small指向的那个元素恰好在Busy链表的中间
{
//首先定位到temp_small的前一个元素
temp=Busy_head;
while（temp->next!
=temp_small）
{
temp=temp->next;
}
//然后将temp_small的前一个元素的next指针指向temp_small指向的下一个元素
temp->next=temp_small->next;
//最后插入尾部，并更新Busy_tail指针
temp_small->next=NULL;
Busy_tail->next=temp_small;
Busy_tail=temp_small;
}
}
//修改存状态
for（k=0;k{
MemoryStatus[k][i]=MemoryStatus[k][i-1];
}
MemoryStatus[temp_small->pfn][i]=currentpage;//虚页currentpage装入了temp->pfn表示的那个实页里
}
}
}
}
voidmain（）
{
inti,j,ppCount;
//由键盘输入实页的个数，并形成Free链表
printf（"请输入系统能提供的物理块（即实页）的个数，数值为2-10之间：
\t"）;
scanf（"%d",&ppCount）;
if（ppCount>10||ppCount<2）
{
printf（"\n\n！
！
！
！
输入的数值不合法，程序终止！
！
！
！
"）;
}
else
{
count=0;
countime=0;
//初始化10个虚页
for（i=0;i{
vp[i].pn=i;
vp[i].pfn=-1;
vp[i].time=0;
}
//初始化这些实页，并将其串成链表
//首先生成第一个元素，并初始化
Free_head=malloc（sizeof（Page））;
Free=Free_head;
Free_tail=Free;
Free_head->pn=-1;
Free_head->pfn=0;
Free_head->next=NULL;
//用一个循环生成后续的元素，并初始化后，成链表
for（i=1;i{
temp=malloc（sizeof（Page））;
temp->pn=-1;
temp->pfn=i;
temp->next=NULL;
Free_tail->next=temp;
Free_tail=temp;
}
//初始化Busy链表
Busy=NULL;
Busy_head=NULL;
Busy_tail=NULL;
//初始化MemoryStatus数组
for（i=0;ifor（j=0;j{
MemoryStatus[i][j]=-1;
}
//初始化NotInMemory数组
for（i=0;i{
NotInMemory[i]=1;
}
//生成20个介于0-9之间的随机数，作为页面访问序列。
并将其显示出来
//srand（（unsigned）time（NULL））;//用时间作为种子，否则每次出来的随机数都一样
for（i=0;i{
queue[i]=rand（）%10;
printf（"|%3d",queue[i]）;
}
printf（"\n"）;
LRU（）;
//FIFO（）;//运行FIFO（）算法
//显示依次访问20个虚页时对应的存状态，即MemoryStatus数组的值。
for（i=0;i{
for（j=0;j{
if（NotInMemory[j]==1）//当访问的这个虚页不在存时，显示将其调入存后的详细存信息
printf（"|%3d",MemoryStatus[i][j]）;
else
printf（"|%3c",32）;//当访问的这个虚页在存时，存状态未发生改变，故无需再显示一遍。
本例用空格代替，其中32是空格的ASCII码
}
}
printf（"\n缺页数为：
%3d",count-ppCount）;
getch（）;
}
}五、程序运行结果
图
（1）
图
（2）
六、实验体会
经过这次操作系统实验我知道了不同的外存调度算法进行页面置换，模拟了3种的算法调度。
我做完了实验之后觉得我自己对虚拟存储器认识增加了不少，虽然在做完实验之后觉的成就感让我很高兴，但是更让我高兴的是在做这个实验的过程中我对书本上的理论知识加深了很多。
虽然在做实验的过程中遇到了很多问题，但是每当我解决完一个问题的时候都会觉得自己的能力提高了很多，真的让人很兴奋！
如果有机会我真的很想多做类似的实验，锻炼一下自己，让自己能够更快地提高。
升级会员 