yuanma.txt

设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率：

1、先进先出算法（FIFO） 

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

#define mSIZE 3 
#define pSIZE 8 

static int memery[mSIZE] = {0}; 
static int process[pSIZE] = {0}; 
//static int process[pSIZE] = {2,3,2,1,5,2,4,5,3,2,5,2}; 
//static int process[pSIZE] = {7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1}; 

void build(); //生成一个随机数序列 
void FIFO(); //最近最久未使用(LRU)置换算法 

int main(int argc, char *argv[]) 
{ 
printf("产生随机序列如下：\n"); 
build(); 
printf("先进先出(FIFO)页面置换算法 \n"); 
FIFO(); 
system("PAUSE"); 
return 0; 
} 

void build() 
{ 
int i = 0; 
for(i=0; i<pSIZE; i++) 
{ 
process[i] = (int)(10.0*rand()/(RAND_MAX+1.0) + 1); 
printf("%d ",process[i]); 
} 
printf("\n"); 
} 
void FIFO() 
{ 
int time[mSIZE] = {0}; 
int i = 0, j = 0; 
int m = -1, n = -1; 
int max = -1,maxtime = 0; 
int count = 0; 

for(i = 0; i<pSIZE; i++) 
{ 
//找第一个空闲的物理块 
for(j=0; j<mSIZE; j++) 
{ 
if(memery[j] == 0) 
{ 
m = j; 
break; 
} 
} 

//找与进程相同的标号 
for(j = 0; j < mSIZE; j++) 
{ 
if(memery[j] == process[i]) 
{ 
n = j; 
} 
} 
//找time值最大的 
for(j = 0; j < mSIZE;j++) 
{ 
if(time[j]>maxtime) 
{ 
maxtime = time[j]; 
max = j; 
} 
} 

if(n == -1) //不存在相同进程 
{ 
if(m != -1) //存在空闲物理块 
{ 
memery[m] = process[i]; 
time[m] = 0; 
for(j = 0;j <= m; j++) 
{ 
time[j]++; 
} 
m = -1; 
} 
else //不存在空闲物理块 
{ 
memery[max] = process[i]; 
time[max] = 0; 
for(j = 0;j < mSIZE; j++) 
{ 
time[j]++; 
} 
max = -1; 
maxtime = 0; 
count++; 
} 
} 
else //存在相同的进程 
{ 
memery[n] = process[i]; 
for(j = 0;j < mSIZE; j++) 
{ 
time[j]++; 
} 
n = -1; 
} 
for(j = 0 ;j < mSIZE; j++) 
{ 
printf("%d ",memery[j]); 
} 
printf("\n"); 
} 
printf("页面换算次数为：%d\n",count); 
} 

2、最近最久未使用算法（LRU） 

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

#define mSIZE 3 
#define pSIZE 8 

static int memery[mSIZE] = {0}; 
static int process[pSIZE] = {0}; 
//static int process[pSIZE] = {2,3,2,1,5,2,4,5,3,2,5,2}; 
//static int process[pSIZE] = {7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1}; 

void build(); //生成一个随机数序列 
void LRU(); //最近最久未使用(LRU)置换算法 

int main(int argc, char *argv[]) 
{ 
printf("产生随机序列如下：\n"); 
build(); 
printf("最近最久未使用(LRU)置换算法 \n"); 
LRU(); 
system("PAUSE"); 
return 0; 
} 
void build() 
{ 
int i = 0; 
for(i=0; i<pSIZE; i++) 
{ 
process[i] = (int)(10.0*rand()/(RAND_MAX+1.0) + 1); 
printf("%d ",process[i]); 
} 
printf("\n"); 
} 
void LRU() 
{ 
int flag[mSIZE] = {0}; 
int i = 0, j = 0; 
int m = -1, n = -1; 
int max = -1,maxflag = 0; 
int count = 0; 

for(i = 0; i<pSIZE; i++) 
{ 
//找第一个空闲的物理块 
for(j=0; j<mSIZE; j++) 
{ 
if(memery[j] == 0) 
{ 
m = j; 
break; 
} 
} 
//找与进程相同的标号 
for(j = 0; j < mSIZE; j++) 
{ 
if(memery[j] == process[i]) 
{ 
n = j; 
} 
} 
//找flag值最大的 
for(j = 0; j < mSIZE;j++) 
{ 
if(flag[j]>maxflag) 
{ 
maxflag = flag[j]; 
max = j; 
} 
} 

if(n == -1) //不存在相同进程 
{ 
if(m != -1) //存在空闲物理块 
{ 
memery[m] = process[i]; 
flag[m] = 0; 
for(j = 0;j <= m; j++) 
{ 
flag[j]++; 
} 
m = -1; 
} 
else //不存在空闲物理块 
{ 
memery[max] = process[i]; 
flag[max] = 0; 
for(j = 0;j < mSIZE; j++) 
{ 
flag[j]++; 
} 
max = -1; 
maxflag = 0; 
count++; 
} 
} 
else //存在相同的进程 
{ 
memery[n] = process[i]; 
flag[n] = 0; 
if(m != -1) //若存在空闲物理块 
{ 
flag[m] = 0; 
} 
for(j = 0;j < mSIZE; j++) 
{ 
flag[j]++; 
} 
max = -1; 
maxflag = 0; 
n = -1; 
} 
for(j = 0 ;j < mSIZE; j++) 
{ 
printf("%d ",memery[j]); 
} 
printf("\n"); 
} 
printf("页面换算次数为：%d\n",count); 
}