#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;
class linklist; //前视定义，以便使用友元
class node
{
friend class linklist; //定义linklist类为友元
private:
node * next; //结点指针
int page_number; //页面号
int flag; //标志，是否在主存
int mm_number; //所在主存块号
int unit_number; //单元号
int disk_number; //磁盘位置
public:
node(node *pnext=NULL,int pn=-1,int mmn=-1,int un=-1,int dn=-1) //构造函数
{
next=pnext;
page_number=pn;
flag=0; //设置标志初始值为0，即不在主存
mm_number=mmn;
unit_number=un;
disk_number=dn;
}
~node(){}; //析构函数
};
class linklist
{
private:
node * head; //头指针
public:
linklist() //构造函数
{
head=new node(NULL,-1,-1,-1,-1); //构造头结点，设置初值
}
~linklist(){} //析构函数
void insert(int pn,int mmn,int un,int dn) //插入一个结点,按页面号从小到大排列
{
if(head->next==NULL) //当前链表为空
{
node * newnode=new node(NULL,pn,mmn,un,dn);
head->next=newnode;
}
else
{
node * p=head->next;
node * pt=head; //记录指针p的前一个位置
while(p->page_number<=pn&&p->next!=NULL) //寻找当前插入结点的位置
{
pt=pt->next;
p=p->next;
}
if(p->next==NULL&&p->page_number<=pn) //应该插入的未知结点为最后一个结点
{
node * newnode=new node(NULL,pn,mmn,un,dn);
p->next=newnode;
}
else
{
node * newnode=new node(p,pn,mmn,un,dn);
pt->next=newnode;
}
}
}
void show() //输出当前页表的情况
{
if(head->next==NULL)
cout<<"没有页表!"<<endl;
else
{
cout<<"page_number flag mm_number unit_number disk_number"<<endl;
node * p=head->next;
while(p!=NULL)
{
cout<<" "<<p->page_number<<" "<<p->flag<<" "
<<p->mm_number<<" "<<p->unit_number<<" "<<p->disk_number<<endl;
p=p->next;
}
}
}
void FIFO() //FIFO调度算法
{
int i=0,j=0,n=0,m=0,a[20],b[20];
node * p,* pt,* pc,* pct;
for(i=0;i<20;i++)
{a[i]=rand()%7;
b[i]=-1;
}
cout<<"任务需要调度的页面号序列如下:"<<endl;
for(i=0;i<20;i++)
{cout<<a[i]<<" ";}
cout<<endl;
cout<<endl;
for(i=0;i<20;i++)
{
cout<<"--------------------------------RUN----------------------------------"<<endl;
p=pc=head->next;
pt=pct=head;
while(p->page_number!=a[i]) //寻找当前的页面
{p=p->next;pt=pt->next;}
if(p->flag==1) //未发生缺页中断
{
cout<<"当前调用页面为:"<<p->page_number<<" "<<"未发生缺页中断"<<endl;
cout<<"绝对地址为:"<<p->mm_number<<" * "<<"128"<<" + "<<p->unit_number<<" = "<<p->mm_number*128+p->unit_number<<endl;
cout<<endl;
show();
}
else //发生缺页中断
{
j++; //缺页中断次数加1
b[j-1]=a[i]; //记录缺页中断的页面
if(j<=4)
{
while(pc->flag==1)
{pc=pc->next;pct=pct->next;}
p->mm_number=j-1;
p->flag=1;
if(p->next==NULL)
{pt->next=NULL;p->next=pct->next;pct->next=p;}
else
{pt->next=p->next;p->next=pct->next;pct->next=p;}
}
else
{
n=j;
if(n%4==0)
n=4;
else
n=n%4;
for(m=1;m<n;m++)
{pct=pct->next;pc=pc->next;}
p->mm_number=pc->mm_number;
p->flag=1;
pc->flag=0;
pc->mm_number=-1;
if(p->next==NULL)
{pt->next=NULL;
p->next=pct->next;
pct->next=p;
p->next=pc->next;
pc->next=NULL;
pt->next=pc;
}
else
{pt->next=p->next;
p->next=pct->next;
pct->next=p;
p->next=pc->next;
pc->next=pt->next;
pt->next=pc;
}
}
p=head->next;
while(p->page_number!=a[i])
{p=p->next;}
cout<<"当前调用页面为:"<<p->page_number<<" "<<"发生缺页中断,采用FIFO调度"<<endl;
cout<<"绝对地址为:"<<p->mm_number<<" * "<<"128"<<" + "<<p->unit_number<<" = "<<p->mm_number*128+p->unit_number<<endl;
if(j>4)
{cout<<"淘汰页面为:"<<b[j-5]<<endl;}
cout<<endl;
show();
}
}
cout<<"-----------------------------END-------------------------------"<<endl;
cout<<"发生缺页中断的次数为:"<<j<<endl;
cout<<"发生缺页中断的页面为:";
for(i=0;i<j;i++)
{cout<<b[i]<<" ";}
cout<<endl;
cout<<"所淘汰页面为:";
for(i=0;i<j-4;i++)
{cout<<b[i]<<" ";}
cout<<endl;
cout<<"缺页中断率为:"<<5*j<<"%"<<endl;
}
void clear() //释放空间
{
node * p=head->next;
delete head;
while(p->next!=NULL)
delete p;
}
};
void main()
{
linklist page;
int pn,mmn,un,dn;
for(int i=0;i<7;i++)
{
pn=i;
mmn=-1;
un=rand()%10;
dn=rand()%10;
page.insert(pn,mmn,un,dn);
}
cout<<"主存划分为4块，块号为0号~3号，块大小为128字节"<<endl;
cout<<"共有7个页面，页面号为0号~6号，每页信息如下:"<<endl;
page.show();
page.FIFO();
page.clear();
}
