任务四、请求分页存储管理（虚拟存储）一、实验目的通过请求分页存储管理的设计，让学生了解虚拟存储器的概念和实现方法。
进行运行时不需要将所有的页面都调入内存，只需将部分调入内存，即可运行，在运行的过程中若要访问的页面不在内存时，则需求有请求调入的功能将其调入。
假如此时若内存没有空白物理块，则通过页面置换的功能将一个老的不用的页面淘汰出来，其中淘汰的算法有多种。
二、实验内容模拟仿真请求分页调度算法，其中淘汰的算法可选下列其一1、先进先出算法2、最近最久算法3、CLOCK算法三、实验代码#include<iostream>#include<vector>using namespace std;int n;typedef struct Queue{int time;int data;struct Queue *next;}Queue,*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;//fifo=======================================void InitQueue(LinkQueue &Q);void FiFoEnQueueRear(LinkQueue &Q,int e,vector<int> &v);void FiFoDeQueueFront(LinkQueue &Q);inline void PrintQueue(LinkQueue &Q);void FiFoFiFoDoQueueEarly(LinkQueue &Q,int a,vector<int> &v);void FiFoDoQueue(LinkQueue &Q,int a,vector<int> &v);inline int PanDuan(LinkQueue &Q,int a);inline int YeMianCount(LinkQueue &Q);void fifo();//lru=============================================void InitQueue(LinkQueue &Q);void EnQueueMid(LinkQueue &Q,int e,QueuePtr p,vector<int> &v);void EnQueueTheFist(LinkQueue &Q,int e);void PrintQueue(LinkQueue &Q);//void ZhiZhenInit(int n);void DoQueueEarly(LinkQueue &Q,int e,vector<int> &v);void EnQueueRear(LinkQueue &Q,int e,QueuePtr p,vector<int> &v);//void DeQueueFront(LinkQueue &Q);QueuePtr ZhiZhen(LinkQueue &Q,int e);void EnQueue(LinkQueue &Q,int e,vector<int> &v);//void DeQueue(LinkQueue &Q,QueuePtr p);int PanDuan(LinkQueue &Q,int a);int YeMianCount(LinkQueue &Q);void lru();QueuePtr OptimalZhiZhen(LinkQueue &Q,int e);//求出需要置换的页面的上一个页面的位置void EnQueue(LinkQueue &Q,int e,vector<int> &v,int i,vector<int> &vc);inline int YeMianCount(LinkQueue &Q);//使用内敛函数，提高性能inline int Destance(vector<int> &v,int i);inline void SubbDestance(LinkQueue &Q);//=================================================int main(){int k;for(;;){cout<<"请选择！"<<endl;cout<<"1——FiFo算法"<<endl;cout<<"2——LRU算法"<<endl;cout<<"0——退出"<<endl;cin>>k;if(k==0)break;else{switch(k){case 1:fifo();break;case 2:lru();break;default:cout<<" 请从以上的选择中选择一个选项！！"<<endl;}}}}//fifo========================================void InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(Queue));if(!Q.front)cout<<"initqueue worng!"<<endl;Q.front->next=NULL;//return OK;}void FiFoEnQueueRear(LinkQueue &Q,int e,vector<int> &v){ QueuePtr p;p=(QueuePtr)malloc(sizeof(Queue));if(!p)cout<<"cannot malloc EnQueue of the p"<<endl;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;v.push_back(e);//cout<<p->data;//return OK;}void FiFoDeQueueFront(LinkQueue &Q){QueuePtr p;if(Q.front==Q.rear)cout<<"the Queue is empty,cannot delete !!"<<endl;p=Q.front->next;Q.front->next=p->next;free(p);if(Q.rear==p)Q.rear=Q.front;//return OK}void PrintQueue(LinkQueue &Q){QueuePtr p;if(Q.front==Q.rear)cout<<"the Queue is empty,cannot print!"<<endl;p=Q.front;for(p=Q.front;p->next!=NULL;p=p->next){cout<<p->next->data<<" ";}cout<<endl;//retrun OK;}void FiFoFiFoDoQueueEarly(LinkQueue &Q,int a,vector<int> &v){ QueuePtr p;int count=0;//设置标志位，记录重复的个数。
假如COUNT为0，表示没有重复int b,c;b=a;c=PanDuan(Q,b);//p=Q.front;if(c==1){FiFoEnQueueRear(Q,b,v);PrintQueue(Q);if(v[v.size()-1]!=a)v.push_back(a);}else{cout<<endl;};//v.push_back(a);//cout<<a<<""<<endl;}void FiFoDoQueue(LinkQueue &Q,int a,vector<int> &v){ QueuePtr p;int count=1;//p=Q.front;int b,c;b=a;c=PanDuan(Q,b);//p=Q.front;if(c==1){FiFoEnQueueRear(Q,b,v);FiFoDeQueueFront(Q);PrintQueue(Q);}else{cout<<endl;};//return OK;}int PanDuan(LinkQueue &Q,int a){QueuePtr p;for(p=Q.front;p->next!=Q.rear->next;p=p->next){if(p->next->data!=a){}elsereturn 0;}return 1;}int YeMianCount(LinkQueue &Q){QueuePtr p;int count=0;for(p=Q.front;p->next!=Q.rear->next;p=p->next) count+=1;return count;}void fifo(){vector<int> a;vector<int> v;LinkQueue Q;int m,n,b,c;InitQueue(Q);m=n=b=c=0;cout<<"请输入页块数"<<endl;cin>>n;cout<<"请输入序列的个数"<<endl;cin>>m;cout<<"请输入序列"<<endl;for(int i=0;i<m;++i){cin>>c;a.push_back(c);//cout<<a[i]<<" ";}cout<<"开始页面置换"<<endl;b=a[0];//cout<<b;FiFoEnQueueRear(Q,b,v);PrintQueue(Q);//cout<<"#"<<endl;for(i=1;i<n;i++){b=a[i];//cout<<b<<endl;FiFoFiFoDoQueueEarly(Q,b,v);//PrintQueue(Q);//cout<<endl;}for(i=n;i<m;++i){b=a[i];c=YeMianCount(Q);if(c<n){FiFoFiFoDoQueueEarly(Q,b,v);//PrintQueue(Q);}else{FiFoDoQueue(Q,b,v)//PrintQueue(Q);}//cout<<endl;}cout<<"缺叶顺序为："<<endl;for(i=0;i<m;++i)cout<<v[i]<<" ";cout<<endl;cout<<"缺叶率为："<<float(v.size())/float(a.size())<<endl; }//lru=============================================== QueuePtr ZhiZhen(LinkQueue &Q,int e){QueuePtr p,q;//int a;q=Q.front;for(p=Q.front;p->next!=Q.rear->next;p=p->next){if(q->next->time<p->next->time)q=p;else{};}return q;//返回的是需要调换的上一个页面节点}void DoQueueEarly(LinkQueue &Q,int e,vector<int> &v){ QueuePtr q;int b;b=PanDuan(Q,e);if(b==1){EnQueueTheFist(Q,e);v.push_back(e);//PrintQueue(Q);else{q=ZhiZhen(Q,e);if(Q.front->next==Q.rear){EnQueueRear(Q,e,q,v);v.push_back(e);//PrintQueue(Q);}else{EnQueueMid(Q,e,q,v);v.push_back(e);//PrintQueue(Q); }}}void EnQueueMid(LinkQueue &Q,int e,QueuePtr p,vector<int> &v){ QueuePtr q;QueuePtr newq;int a;q=p;//================//a=PanDuan(Q,e);newq=(QueuePtr)malloc(sizeof(Queue));if(!newq)cout<<" connot malloc newq in the EnQueueMid"<<endl;//if(a==1)//没有次页面存在，进行页面置换//{if(q!=Q.front){QueuePtr q1=q->next;newq->data=e;newq->next=q->next->next;q->next=newq;q->next->time=0;free(q1);}Elseif(q==Q.front){QueuePtr q1=q->next;newq->data=e;newq->next=q->next->next;q->next=newq;Q.front->next=newq;q->next->time=0;free(q1);}//v.push_back(e);//else//{};for(p=Q.front;p->next!=Q.rear->next;p=p->next)p->next->time+=1;}void EnQueueRear(LinkQueue &Q,int e,QueuePtr p,vector<int> &v){ QueuePtr q;QueuePtr newq;int a;q=p;//===================a=PanDuan(Q,e);newq=(QueuePtr)malloc(sizeof(Queue));//if(a==1)//没有次页面存在，进行页面置换//{newq->data=e;Q.rear=newq;q->next=newq;Q.rear->next=NULL;q->next->time=0;//v.push_back(e);//}//else//{};for(p=Q.front;p->next!=Q.rear->next;p=p->next)p->next->time+=1;}void EnQueue(LinkQueue &Q,int e,vector<int> &v){QueuePtr p;int a;a=PanDuan(Q,e);if(a==1){ p=ZhiZhen(Q,e);if(p->next!=Q.rear)EnQueueMid(Q,e,p,v);//PrintQueue(Q);v.push_back(e);}else{ EnQueueRear(Q,e,p,v); //PrintQueue(Q);v.push_back(e);}}else{cout<<"不置换"<<endl;};}void EnQueueTheFist(LinkQueue &Q,int e){QueuePtr p;p=(QueuePtr)malloc(sizeof(Queue));if(!p)cout<<"cannot malloc EnQueue of the p"<<endl;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;p->time=0;for(p=Q.front;p->next!=Q.rear->next;p=p->next)p->next->time+=1;//for(p=Q.front;p->next!=Q.rear->next;p=p->next)//cout<<p->next->time<<" the frist time "<<endl;//cout<<"===================================="<<endl; }void lru(){vector<int> a;vector<int> v;LinkQueue Q;int m,n,b,c;InitQueue(Q);m=n=b=c=0;cout<<"请输入页块数"<<endl;cin>>n;cout<<"请输入序列的个数"<<endl;cin>>m;cout<<"请输入序列"<<endl;for(int i=0;i<m;++i){cin>>c;a.push_back(c);}cout<<"你输入的序列号是： "<<endl;for(i=0;i<m;++i)cout<<a[i]<<" ";cout<<"开始页面置换"<<endl;i=0;b=a[i];EnQueueTheFist(Q,b);v.push_back(a[i]);PrintQueue(Q);for(i=1;i<n;++i){b=a[i];DoQueueEarly(Q,b,v);PrintQueue(Q);/*if(v[v.size()-1]!=a[i])PrintQueue(Q);else{cout<<"不置换"<<endl;}//*/}for(i=n;i<m;++i){ c=YeMianCount(Q);if(c<n){b=a[i];DoQueueEarly(Q,b,v);PrintQueue(Q);}elseb=a[i];EnQueue(Q,b,v);PrintQueue(Q);}}cout<<"页面置换的顺序为："<<endl;for(i=0;i<v.size();++i)cout<<v[i]<<" ";cout<<endl;cout<<"页面置换率为："<<float(v.size())/float(a.size())<<endl;//* }图4-1 先进先出算法图4-2 最近最久算法。
