操作系统实验2.doc

实验二 模拟比较页面置换页算法及缺页率
班级： 信息092 学号： 200912030204 姓名： 郭梦瑶 实验日期： 6月6日
一、实验目的和学时
1. 实验目的
（1）掌握先进先出页面置换算法；
（2）掌握最近最久未使用页面置换算法；
（3）掌握改进的CLOCK页面置换算法，了解其他页面置换算法；
（4）熟悉C/C++或其他语言编程。
2、实验学时：6学时
二、实验内容
编写程序，设置不同的页面数，使用不同的页面替换策略算法进行模拟页面替换。先进先出，最近最久未使用页面置换算法等，并计算缺页率。
三、实验环境
1．PC微机
2．Windows 操作系统
3．C/C++或其他语言开发环境
四、实验算法程序及结果
1. 程序运行输出的部分界面如下

2. C语言程序源代码

#include <stdio.h>
#include <stdlib.h>
#include<time.h>

int add[256]/*地址*/,page[256]/*页面*/;
int k,j,ram,t;
float rate;/*缺页率*/

struct s1
{ int page;
int free;
int tag;
} fifo[33],opt[33],lru[33];

struct s2
{ int time;};
void address();
float FIFO(int ram);/*先进先出*/
float LRU(int ram);/*最近最久未使用页面置换*/
float OPT(int ram);/*理想型*/

int main()
{ int i,p[256];/*页号*/
address();
for (k=1; k<=8;) /*页面大小: 1k,2k,4k,8K*/
{ printf("the size of a page is %d k\n ",k);
printf("the page num is ...\n");
for (i=0; i<256; i++)
{p[i]=add[i]/(k*1024);
printf("%d ",p[i]);
}j=0;
for (i=0; i<256; i++)
{ while (p[i]==p[i+1])i++;
page[j]=p[i];
j++;}
printf("\nafter connect the same
pages the page num is:\n");
for (i=0; i<j; i++)
printf("%d ",page[i]);
printf("\n");
getchar();
for (ram=1; ram<=32; ram++)
{ if (ram==10) getchar();
printf("\nblock=%d pages= %d,absent rate: ",ram,j);
printf("FIFO=%0.2f%% ",FIFO(ram));
printf("LRU =%0.2f%% ",LRU(ram));
printf("OPT =%0.2f%% ",OPT(ram));
}
k=k*2;
getchar();
}
return 0;
}

void address()
{ int i,x;
add[0]=1000;
srand((int)time(0));
for (i=1; i<=255; i++)
{ x=rand()%1024;
if ((x>=0)&&(x<512))
add[i]=add[i-1]+1;
if ((x>=512)&&(x<768))
add[i]=rand()%(add[i-1]-1)+1;
if ((x>=768)&&(x<1024))
add[i]=add[i-1]+rand()%(30*1024-add[i-1]-1)+1;
}}
float FIFO(int ram)
{ int absent=0,t=0,i,z,l,yn;
for (i=0; i<ram; i++)
{ fifo[i].page=-1;
fifo[i].free=1;
fifo[i].tag=0;}
i=0;
while (i<j)
{ yn=0;
for (z=0; z<ram; z++) /*the page is in the ram?*/
if (fifo[z].page==page[i])
{
yn=1;
for (z=0; z<ram; z++)
if (fifo[z].free==0)
fifo[z].tag+=1;
}
if (yn!=1)
{ absent+=1; /*count the absent page*/
l=0;
while ((l<ram)&&(fifo[l].free==0))
l++;
if ((l<ram)&&(fifo[l].free==1))
{ fifo[l].page=page[i];
fifo[l].free=0;
for (l=0; l<ram; l++)
if (fifo[l].free==0 )
fifo[l].tag+=1;
}
else /*there is no free ram*/
{ t=0;
for (l=0; l<ram; l++)
if ( fifo[l].tag<fifo[t].tag)
t=l;
fifo[t].page=page[i];
fifo[t].free=0;
fifo[t].tag=1;
l=0;
}}
i++;}
rate=(float)absent/j*100;
return rate;
}

float LRU(int ram)
{ int absent=0,yn,t,i,l,z,now=0;
struct s2 P[250];
for (i=0;i<j;i++)
P[i].time=0;
for (i=0; i<ram; i++)
{ lru[i].page=-1;
lru[i].free=1;
}
i=0;
while(i<j)
{ for(l=0; l<ram; l++)
yn=0;
{ for(z=0; z<ram; z++)
if (lru[z].page==page[i])
{ now+=1;
P[lru[z].page].time=now;
yn=1;
}
if (yn!=1)
{ absent+=1; now+=1;
l=0;
while ((l<=ram)&&(lru[l].free==0))
l++;
if ((l<=ram)&&(lru[l].free==1))
{ lru[l].page=page[i];
P[lru[l].page].time=now;
lru[l].free=0;
}
else /*there is no ram*/
{ t=0;
for (l=0; l<ram; l++)
if ( P[lru[l].page].time<P[lru[t].page].time)
t=l;
lru[t].page=page[i];
P[lru[t].page].time=now;
}}}
i++;}
rate=(float)absent/j*100;
return rate;
}
float OPT(int ram)
{
int yn,t,absent=0,i,l1,k,l;
for(i=0;i<ram;i++)
{opt[i].page=-1;
opt[i].free=1;
opt[i].tag=0;}
i=0;
while(i<j) /*the page in the ram?*/
{yn=0;
for(l1=0;l1<ram;l1++)

if(page[i]==opt[l1].page)
{
yn=1;
for(k=0;k<ram;k++)
opt[k].tag-=1;
}
if(yn!=1)
{
absent+=1;l=0;
while((l<ram)&&(opt[l].free==0))l++;
if((l<=ram)&&(opt[l].free==1))
{
opt[l].page=page[i];
opt[l].free=0;
opt[l].tag-=1;
for(l=0;l<ram;l++)opt[l].tag-=1;
}
else
{
for(l=0;l<ram;l++)
{
t=i;
while(t<j&&opt[l].page!=page[t])
{t++;
opt[l].tag+=1;}
}t=0;
for(l=0;l<ram;l++)
if(opt[l].tag>opt[t].tag)t=l;
opt[t].page=page[i];
opt[t].tag=1;
}}
i++;}
rate=(float)absent/j*100;
return rate;
}

五、实验心得体会
此次实验通过编写程序，设置不同的页面数，使用不同的页面替换策略算法进行模拟页面替换，让我掌握先进先出页面置换算法；掌握最近最久未使用页面置换算法；掌握改进的CLOCK页面置换算法，了解其他页面置换算法；同时进一步熟悉了C++语言编程，受益很大。