#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NUL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清零周期*/
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];
void initialize();
void FIFO();
void LRU();
void OPT();
int main()
{
int S,i;
srand((int)getpid());
S=(int)rand()%390;
for(i=0;i<total_instruction;i+=1) /*产生指令队列*/
{
a[i]=S; /*任选一指令访问点*/
a[i+1]=a[i]+1; /*顺序执行一条指令*/
a[i+2]=(int)rand()%390; /*执行前地址指令m’*/
a[i+3]=a[i+2]+1; /*执行后地址指令*/
S=(int)rand()%390;
}
for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf("%2d page frames",i);
FIFO(i);
LRU(i);
OPT(i);
printf("\n");
}
return 0;
}
void FIFO(total_pf) /*FIFO(First in First out)ALGORITHM*/
int total_pf; /*用户进程的内存页面数*/
{
int i;
pfc_type *p, *t;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NUL; /*忙页面队列头,对列尾链接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NUL) /*无空闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/
freepf_head=busypf_head;
freepf_head->next=NUL;
busypf_head=p;
}
p=freepf_head->next; /*按方式调新页面入内存页面*/
freepf_head->next=NUL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NUL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%d",diseffect);
}
void LRU(total_pf)
int total_pf;
{
int min,minj,i,j,present_time;
initialize(total_pf);present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲页面*/
{
min=32767;
for(j=0;j<total_vp;j++)
if(min>pl[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=NUL;
}
pl[page[i]].pfn=freepf_head->pfn;
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page[i]].time=present_time;
present_time++;
}
printf("LRU:%d",diseffect);
}
void OPT(total_pf) /*OPT(Optimal Replacement)ALGORITHM*/
int total_pf;
{
int i,j,max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID)
{
diseffect++;
if(freepf_head==NUL)
{
for(j=0;j<total_vp;j++)
if(pl[j].pfn!=INVALID)
dist[j]=32767;
else
dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{
if(pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if(max<dist[j])
{
max=dist[j];maxpage=j;}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NUL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
}
printf("OPT:%d",diseffect);
}
void initialize(total_pf) /*初始化相关数据结构*/
int total_pf; /*用户进程的内存页面数*/
{
int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;pl[i].pfn=INVALID; /*置页面控制结构中的页号,页面为空*/
pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0,时间为-1*/
}
for(i=1;i<total_pf;i++)
{
pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之间的连接*/
}
pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/
}
chucun.zip_LRU_chucun
版权申诉
72 浏览量
2022-09-21
04:53:01
上传
评论
收藏 2KB ZIP 举报
weixin_42653672
- 粉丝: 93
- 资源: 1万+
最新资源
- 基于pytorch+Unet进行MRI肝脏图像分割源码+数据集+模型.zip
- 在Android Studio中开发一个Android App项目步骤
- 基于yolov8实现进行物体跟踪源码.zip
- Java多线程学习Java多线程学习Java多线程学习Java多线程学习.txt
- 算法数据结构-动态规划算法(Dynamic Programming)超详细总结加应用案例讲解.txt
- 2024最强秋招八股文(精简、纯手打)2024最强秋招八股文(精简、纯手打).txt
- 基于tensorflow多特征融合的微表情识别python源码.zip
- 基于yolov8实现人脸检测的python源码+运行说明.zip
- Micron Memory DDR3 SDRAM 全系列AD集成库(原理图库+PCB封装库).IntLib
- 基于tensorflow多特征融合的微表情识别python源码+详细使用说明.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈