实验报告四

操作系统实验报告

班级： 学号 姓名： 时间：

实验四 存储管理

常用页面置换算法模拟实验

一、实验目的

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

二、实验内容

设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、最不经常使用算法（LFU） 5、最近未使用算法（NUR）

命中率＝１－页面失效次数／页地址流长度

三、实验过程

1.进入LINUX系统。打开虚拟机，在vi中编写程序，在终端输入文件名（gcc xx.c），输入执行指令，屏幕上无反应，按下^C后，显示最终结果。

2、页面置换算法

当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

常用的页面置换算法有

1、最佳置换算法（Optimal）

2、先进先出法（Fisrt In First Out）

3、最近最久未使用（Least Recently Used） 4、最不经常使用法（Least Frequently Used） 5、最近未使用法（No Used Recently） 3.运行结果:

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

四、回答问题

1、为什么OPT在执行时会有错误产生？

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

当需要淘汰一个内存页面时，这种算法力图选择该进程内存各个页面中永远不再需要的页，若找不到，则选择最久以后才会用到的页。这种算法有最小的缺页率。问题是它需要知道运行进程今后的整个访问踪迹，这往往难以做到，因而它只有理论上的意义。 OPTimal replacement（OPT） 它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。

五、实验总结

从几种算法的命中率看，OPT最高，其次为NUR相对较高，而FIFO与LRU相差无几，最低的是LFU。但每个页面执行结果会有所不同。

① 最佳置换算法(Optimal)，其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 ② 先进先出(FIFO)页面置换算法：

这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

③ LRU置换算法：

④ 最少使用(LFU:Least Frequently Used)置换算法：在采用该算法时，应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。

FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

六、参考程序

#define TRUE 1 #define FALSE 0 #define INVALID -1 #define NULL 0

#define total_instruction 320 /*指令流长*/ #define total_vp 32 /*虚页长*/ #define clear_period 50 /*清0周期*/

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

typedef struct /*页面结构*/ {

int pn,pfn,counter,time; }pl_type;

pl_type pl[total_vp]; /*页面结构数组*/

struct pfc_struct{ /*页面控制结构*/ int pn,pfn;

struct pfc_struct *next; };

typedef struct pfc_struct pfc_type;

pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

int diseffect, a[total_instruction];

int page[total_instruction], offset[total_instruction];

int initialize(int); int FIFO(int); int LRU(int); int LFU(int); int NUR(int); int OPT(int);

int main( ) {

int s,i,j;

srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/

s=(float)319*rand( )/32767/32767/2+1; //

for(i=0;iif(s<0||s>319) {

printf(\"When i==%d,Error,s==%d\\n\ exit(0); }

a[i]=s; /*任选一指令访问点m*/ a[i+1]=a[i]+1; /*顺序执行一条指令*/

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m' */ a[i+3]=a[i+2]+1; /*顺序执行一条指令*/

s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; if((a[i+2]>318)||(s>319))

printf(\"a[%d+2],a number which is :%d and s==%d\\n\ }

for (i=0;ipage[i]=a[i]/10; offset[i]=a[i]%10; }

for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/ {

printf(\"---%2d page frames---\\n\ FIFO(i); LRU(i); LFU(i); NUR(i); OPT(i); }

return 0; }

int initialize(total_pf) /*初始化相关数据结构*/ int total_pf; /*用户进程的内存页面数*/ {int i;

diseffect=0;

for(i=0;ipl[i].pn=i;

pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/ pl[i].counter=0;

pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/ }

for(i=0;ipfc[i].next=&pfc[i+1];

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

pfc[i].pfn=i;

} /*建立pfc[i-1]和pfc[i]之间的链接*/ pfc[total_pf-1].next=NULL;

pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/

return 0; }

int FIFO(total_pf) /*先进先出算法*/

int total_pf; /*用户进程的内存页面数*/ {

int i,j; pfc_type *p;

initialize(total_pf); /*初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/ for(i=0;iif(pl[page[i]].pfn==INVALID) /*页面失效*/ {

diseffect+=1; /*失效次数*/ if(freepf_head==NULL) /*无空闲页面*/ {

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/ freepf_head->next=NULL; busypf_head=p; }

p=freepf_head->next; /*按FIFO方式调新页面入内存页面*/ freepf_head->next=NULL; freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn;

if(busypf_tail==NULL)

busypf_head=busypf_tail=freepf_head; else {

busypf_tail->next=freepf_head; /*free页面减少一个*/

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

busypf_tail=freepf_head; }

freepf_head=p; } }

printf(\"FIFO:%6.4f\\n\

return 0; }

int LRU (total_pf) /*最近最久未使用算法*/ int total_pf; {

int min,minj,i,j,present_time; initialize(total_pf); present_time=0;

for(i=0;iif(pl[page[i]].pfn==INVALID) /*页面失效*/ {

diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ {

min=32767;

for(j=0;jpl[j].time&&pl[j].pfn!=INVALID) {

min=pl[j].time; minj=j; }

freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元 pl[minj].pfn=INVALID; pl[minj].time=-1;

freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效 pl[page[i]].time=present_time;

freepf_head=freepf_head->next; //减少一个free 页面 }

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

else

pl[page[i]].time=present_time; //命中则增加该单元的访问次数

present_time++; }

printf(\"LRU:%6.4f\\n\return 0; }

int NUR(total_pf) /*最近未使用算法*/ int total_pf;

{ int i,j,dp,cont_flag,old_dp; pfc_type *t;

initialize(total_pf); dp=0;

for(i=0;i{ if (pl[page[i]].pfn==INVALID) /*页面失效*/ {diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ { cont_flag=TRUE; old_dp=dp;

while(cont_flag)

if(pl[dp].counter==0&&pl[dp].pfn!=INVALID) cont_flag=FALSE; else { dp++;

if(dp==total_vp) dp=0;

if(dp==old_dp)

for(j=0;jfreepf_head=&pfc[pl[dp].pfn]; pl[dp].pfn=INVALID; freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; }

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

else

pl[page[i]].counter=1; if(i%clear_period==0)

for(j=0;jprintf(\"NUR:%6.4f\\n\

return 0; }

int OPT(total_pf) /*最佳置换算法*/ int total_pf;

{int i,j, max,maxpage,d,dist[total_vp]; pfc_type *t;

initialize(total_pf);

for(i=0;i{ //printf(\"In OPT for 1,i=%d\\n\

//i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278; if(pl[page[i]].pfn==INVALID) /*页面失效*/ {

diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ {for(j=0;jif(pl[j].pfn!=INVALID) dist[j]=32767; /* 最大\"距离\" */ else dist[j]=0; d=1;

for(j=i+1;jif(pl[page[j]].pfn!=INVALID) dist[page[j]]=d; d++; } max=-1;

for(j=0;jmax=dist[j]; maxpage=j; }

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NULL; pl[maxpage].pfn=INVALID; }

pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } }

printf(\"OPT:%6.4f\\n\

return 0; }

int LFU(total_pf) /*最不经常使用置换法*/ int total_pf; {

int i,j,min,minpage; pfc_type *t;

initialize(total_pf);

for(i=0;i{ if(pl[page[i]].pfn==INVALID) /*页面失效*/ { diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ { min=32767;

for(j=0;j{if(min>pl[j].counter&&pl[j].pfn!=INVALID) {

min=pl[j].counter; minpage=j; }

pl[j].counter=0; }

freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效 pl[page[i]].counter++;

freepf_head=freepf_head->next; //减少一个free 页面 }

天津城建大学计算机与信息工程学院

操作系统实验报告

班级： 学号 姓名： 时间：

else

pl[page[i]].counter++;

}

printf(\"LFU:%6.4f\\n\

return 0; }