操作系统 实验课

#include<iostream>
#include<string>
#include <time.h>
#include <stdlib.h>
using namespace std;

const int total_instruction=320; /*指令流长*/
const int total_vp=32; /*虚页长*/
const int clear_period=50; /*清0周期*/

typedef struct /*页面结构*/
{
//int pn; //页号 logic number
int pfn; //页面框架号 physical frame number
int counter; //计数器
int time; //时间
}pl_type;

pl_type pl[total_vp]; /*页面线性结构---指令序列需要使用地址*/

typedef struct pfc_struct /*页面控制结构，调度算法的控制结构*/
{
int pn;
int pfn;
struct pfc_struct *next;
}pfc_type;

pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;
int misspage=0, a[total_instruction]; /* a[]为指令序列*/
int page[total_instruction], offset[total_instruction];/*地址信息*/



/*初始化相关数据结构 total_pf表示内存的块数 */
int initialize(int total_pf)
{
misspage=0;
for(int i=0;i<total_vp;i++)
{

pl[i].pfn=-1; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0; /*页面控制结构中的访问次数为0*/
pl[i].time=-1; /*访问的时间*/
}
for(i=0;i<total_pf-1;i++)/*建立pfc[i-1]和pfc[i]之间的链接*/
{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=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(int total_pf) /*先进先出算法total_pf:用户进程的内存页面数*/
{
pfc_type *p;/*中间变量*/
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/
for(int i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==-1) /*页面失效*/
{
misspage+=1; /*失效次数*/
if(!freepf_head) /*无空闲页面*/
{
p=busypf_head->next; //保存忙页面下一个页面
pl[busypf_head->pn].pfn=-1; //把这个页面换出，更新它的数据成员
freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/
freepf_head->next=NULL; /*表明还是缺页*/
busypf_head=p; //更新忙页面的队头指针
}
p=freepf_head->next;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
freepf_head->next=NULL; /*使busy的尾为null*/
if(!busypf_tail)
{
busypf_tail=busypf_head=freepf_head;
}
else
{
//把刚刚换进来的接在busy_tail后面
busypf_tail->next=freepf_head;
busypf_tail=freepf
_head;
}
freepf_head=p; //下一个空页面
}
}
printf("FIFO:%6.4f ",1-(float)misspage/320);
return 0;
}

//LRU算法换出的是最近一段时间最久未使用过的页面

,
//因此需要在页表中给每一页增加一个域,专门用来记录该页面自上次被访问以来所经历的时间T。
//页面每被访问一次,计时清零。要淘汰一个页面时,从内存的现有页面中选出T值最小的一页调出。

int LRU (int total_pf) /*最近最久未使用算法least recently used*/
{
int min,minj,present_time; /*minj为最小值下标*/
initialize(total_pf);
present_time=0;
for(int i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==-1)
{
misspage++;
if(!freepf_head)
{
min=32767;/*设置最大值*/
for(int j=0;j<total_vp;j++) /*找出time的最小值*/
{
if(min>pl[j].time&&pl[j].pfn!=-1)
{
min=pl[j].time;
minj=j;
}
}
freepf_head=&pfc[pl[minj].pfn]; //腾出一个页面
pl[minj].pfn=-1;
pl[minj].time=0;
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 ",1-(float)misspage/320);
return 0;
}

//该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。
//只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。
//否则，访问位置0。系统周期性的对所有引用位清零。
//当需要淘汰一页时，从那些访问位为零的页中选一页淘汰。

int NUR(int total_pf ) /*最近未使用算法Not Used recently count表示*/
{
int dp=0,cont_flag,old_dp; //这个算法中counter用于访问位
initialize(total_pf);
for(int i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==-1)
{
misspage++;
if(!freepf_head)
{
cont_flag=true;
old_dp=dp;

while(cont_flag) //用cont_flag找到一个访问位counter为0的页面
{

if(pl[dp].counter==0&&pl[dp].pfn!=-1)
cont_flag=false;
else //下一个页面
{
dp++;
if(dp==total_vp) //32个页面找完一遍重新开始一个循环
dp=0;
if(dp==old_dp) // dp累积上一次访问到的地方old_dp，然后访问位重新清零 …… 此处隐藏：3713字，全部文档内容请下载后查看。喜欢就下载吧 ……