虚拟存储器管理实验报告.docx

虚拟存储器管理实验报告.docx

《虚拟存储器管理实验报告.docx》由会员分享，可在线阅读，更多相关《虚拟存储器管理实验报告.docx（25页珍藏版）》请在冰点文库上搜索。

虚拟存储器管理实验报告

淮海工学院计算机科学系

实验报告书

课程名：

《操作系统》

题目：

虚拟存储器管理

页面置换算法模拟实验

班级：

学号：

姓名：

一、实验目的与要求

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值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。

三、程序流程图

三个模块的流程图

〈1〉登录模块

开始

打开w_input窗口

关闭w_main窗口

点击确定按钮

是

否

点击取消按钮

是

〈2〉参数输入模块

开始

打开w_accept窗口

关闭w_input窗口

点击确定按钮

是

否

点击取消按钮

输入了磁头位置

是

否

输入当前磁头位置

输入了各磁道号

是

否

输入各磁道号位置

确定输入这些数

是

是

否

〈3〉算法实现模块

四、主要程序清单

模块之间的调用关系

登录模块

参数输入模块

点击确定按钮

算法实现模块

点击确定按钮

点击返回按钮

#include

#include

#include

intproducerand（intremainder）;

voidinitprocess（）;

voidchosedisplace（）;

structlinknode*fifo（structlinknode*head,intrandcount）;

voidOptimal（structlinknode*head,intrandprocess）;

structlinknode*LRU（structlinknode*head,intrandprocess）;

structlinknode*initlink（）;

voidchoicestey（）;

intallotment（structlinknode*head）;

boolcheckfifooptimal（structlinknode*head,intcheckpage）;

voidrecover（structlinknode*head,intrandprocess）;

voidrecovermemory（）;

intprocess[10][20];//数组的横坐标为进程序列，纵坐标为每个进程的页号

intprocessallotment[6];//存储每个进程已经分配的块数

intfinishp[6];//标志进程是否完成（1完成0不完成）

intfinishprocess=0;//进程完成的个数

intfindpage[6];//每个进程命中的个数

structlinknode*plinkhead[6];

structlinknode*plink[6];

intmemoryallotment[6];

intstey=0;

structlinknode

{

structlinknode*linkper;//空链表的前驱指针

intpage;

intprocesspage;

intused;

intmemorypage;

structlinknode*linknext;//空链表的后继指针

structlinknode*processper;//进程的前去指针

structlinknode*processnext;//进程的后继指针

};

intmain（）

{

structlinknode*head=initlink（）;

initprocess（）;

choicestey（）;

intre=allotment（head）;

if（re==0）

{printf（"内存分配出现问题。

"）;system（"pause"）;}

chosedisplace（）;

recovermemory（）;

system（"pause"）;

}

voidrecovermemory（）

{

intn=0;

printf（"是否回收全部已分配的内存空间?

\n回收输入1，不回收输入2\n"）;

scanf（"%d",&n）;

if（n==1）

{

for（inti=1;i<=5;i++）

recover（plinkhead[i],i）;

}

if（n==2）

printf（"您这么做会浪费内存空间"）;

}

voidrecover（structlinknode*head,intrandprocess）

{

while（head!

=0）

{

head->used=0;

head=head->processnext;

}

}

voidchoicestey（）

{

printf（"请选择置换算法\n"）;

printf（"1表示FIFO\n2表示Optimal\n3表示LRU\n"）;

boolflag=true;

while（flag）

{

scanf（"%d",&stey）;

switch（stey）

{

case1:

{printf（"您选择的是FIFO替换算法\n"）;flag=false;break;}

case2:

{printf（"您选择的是Optimal替换算法\n"）;flag=false;break;}

case3:

{printf（"您选择的是LRU替换算法\n"）;flag=false;break;}

default:

printf（"输入错误，请重新输入\n"）;

}

}

}

voidchosedisplace（）//选择置换算法

{

structlinknode*head;

intrandcount;//进程序号

boolfind;

while（finishprocess<5）

{

randcount=producerand（5）;

while（processallotment[randcount]

{

find=false;

head=plinkhead[randcount];

if（stey==1||stey==2）

find=checkfifooptimal（head,process[randcount][processallotment[randcount]+1]）;

if（find==true）

{

findpage[randcount]++;

}

if（find==false）//如果在链表中没找到当前的页数

{

switch（stey）

{

case1:

{

plinkhead[randcount]=fifo（plinkhead[randcount],randcount）;

break;

}

case2:

{

Optimal（plinkhead[randcount],randcount）;

break;

}

case3:

{

plinkhead[randcount]=LRU（plinkhead[randcount],randcount）;

break;

}

}

}

processallotment[randcount]++;

}

if（finishp[randcount]==0）

{

finishprocess++;

finishp[randcount]=1;

}

}

structlinknode*p;

printf（"进程执行完后内存分配情况：

\n"）;

for（inti=1;i<=5;i++）

{

p=plinkhead[i];

while（p!

=0）

{

printf（"内存块号：

%d\t进程号：

%d\t号：

%d\n",p->memorypage,p->processpage,p->page）;

p=p->processnext;

}

}

for（inti=1;i<=5;i++）

{

printf（"进程序列%d",i）;

printf（"\t进程总页数为%d\t命中页为%d\t",process[i][0],findpage[i]）;

printf（"进程的命中率为%.0f%%\n",（（float）findpage[i]）*100/process[i][0]）;

}

}

boolcheckfifooptimal（structlinknode*head,intcheckpage）

{

while（head!

=0）//遍历链表查单当前页是否在链表中

{

if（head->page==checkpage）

{

returntrue;

}

else

{

head=head->processnext;

}

}

returnfalse;

}

structlinknode*LRU（structlinknode*head,intrandprocess）

{

structlinknode*bhead;

bhead=head;

while（head->processnext!

=0）

{

if（head->page==process[randprocess][processallotment[randprocess]+1]）

break;

elsehead=head->processnext;

}

if（head->page!

=process[randprocess][processallotment[randprocess]+1]）//没找到

{

bhead->page=process[randprocess][processallotment[randprocess]+1];

head->processnext=bhead;

bhead->processper=head;

bhead=bhead->processnext;

bhead->processper=0;

head=head->processnext;

head->processnext=0;

plink[randprocess]=plink[randprocess]->processnext;

returnbhead;

}

else//找到了

{

if（head==bhead）//头

{

head->processper=plink[randprocess];

plink[randprocess]->processnext=head;

plink[randprocess]=plink[randprocess]->processnext;

head=head->processnext;

head->processper=0;

plink[randprocess]->processnext=0;

findpage[randprocess]++;

returnhead;

}

else

{

if（head->processnext==0）//尾

{

findpage[randprocess]++;

returnbhead;

}

else//中间

{

head->processnext->processper=head->processper;

head->processper->processnext=head->processnext;

head->processnext=0;

head->processper=plink[randprocess];

plink[randprocess]->processnext=head;

plink[randprocess]=plink[randprocess]->processnext;

findpage[randprocess]++;

returnbhead;

}

}

}

}

voidOptimal（structlinknode*head,intrandprocess）

{

structlinknode*maxp;

maxp=head;

intmax=1,i;

while（head!

=0）

{

for（i=processallotment[randprocess]+1;i<=process[randprocess][0];i++）

{

if（process[randprocess][i]==head->page）

{

break;

}

}

if（i>max）

{

max=i;

maxp=head;

}

head=head->processnext;

}

maxp->page=process[randprocess][processallotment[randprocess]+1];

}

structlinknode*fifo（structlinknode*head,intrandprocess）

{

structlinknode*phead;//改变后的头指针

phead=head;

head->page=process[randprocess][processallotment[randprocess]+1];

while（head->processnext!

=0）

{

head=head->processnext;

}

head->processnext=phead;

phead->processper=head;

phead=phead->processnext;

head=head->processnext;

head->processnext=0;

phead->processper=0;

returnphead;

}

intallotment（structlinknode*head）//为进程分配内存

{

intallotsum=0;//已经分配完进程的个数

intrandprocess;//当前要分配内存的进程标号

boolboolallot[6];

for（inti=1;i<6;i++）

{

processallotment[i]=0;

boolallot[i]=false;

memoryallotment[i]=0;

}

while（allotsum<=4）//判断是否全部进程都分配完

{

randprocess=producerand（5）;//随即生成进程标号

if（boolallot[randprocess]==false）//判断进程是否分配完

{

if（head->used==0）

{

if（processallotment[randprocess]==0）

{

plinkhead[randprocess]=head;

plink[randprocess]=head;

plink[randprocess]->processper=0;

plink[randprocess]->processnext=0;

head->processpage=randprocess;

plink[randprocess]->page=process[randprocess][1];

head->used=1;

printf（"内存块号：

%d\t进程号：

%d\t页号：

%d\n",head->memorypage,head->processpage,head->page）;

head=head->linknext;

memoryallotment[randprocess]++;

findpage[randprocess]++;

}

else

{

boolchecksame=checkfifooptimal（plinkhead[randprocess],process[randprocess][processallotment[randprocess]+1]）;

if（checksame==false）

{

head->used=1;

head->processnext=0;

head->processper=plink[randprocess];

plink[randprocess]->processnext=head;

head->processpage=randprocess;

head->page=process[randprocess][processallotment[randprocess]+1];

plink[randprocess]=plink[randprocess]->processnext;

printf（"内存块号：

%d\t进程号：

%d\t页号：

%d\n",head->memorypage,head->processpage,head->page）;

head=head->linknext;

memoryallotment[randprocess]++;

findpage[randprocess]++;

}

else

{

if（stey==3）

plinkhead[randprocess]=LRU（plinkhead[randprocess],randprocess）;

elsefindpage[randprocess]++;

}

}

processallotment[randprocess]++;

}

else

{

printf（"进程%d分配失败\n",randprocess）;

return0;

}

if（head==0）

{

printf（"进程%d分配失败\n",randprocess）;

return0;

}

if（processallotment[randprocess]==process[randprocess][0]）

{

printf（"进程%d分配成功\n",randprocess）;

allotsum++;

boolallot[randprocess]=true;

finishprocess++;

finishp[randprocess]=1;

}

else

if（memoryallotment[randprocess]==4）

{

allotsum++;

boolallot[randprocess