理技术
一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
二、实验要求与内容、过程与结果
1.用随机数产生一个指令序列，共320条指令。其地址按下述原则生成：
①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分；
③25%的指令是均匀分布在后地址部分；
具体的实施方法是：
A.在[0，319]的指令地址之间随机选区一起点M;
B.顺序执行一条指令，即执行地址为M+1的指令；
C.在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’；
D.顺序执行一条指令，其地址为M’+1；
E.在后地址[M’+2，319]中随机选取一条指令并执行；
F.重复A—E，直到执行320次指令。
2.指令序列变换成页地址流
设：（1）页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条—第9条指令为第0页（对应虚存地址为[0，9]）；
第10条—第19条指令为第1页（对应虚存地址为[10，19]）；
……………………………………
第310条—第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。
3.计算并输出下述各种算法在不同内存容量下的命中率。
FIFO先进先出的算法
LRU最近最少使用算法
LFU最少访问页面算法
4.运行实例程序，内存块分别为4和5时，记录运行结果。缺页率有何变化？
内存块为4时 FIFO:
内存块为4时 LRU:
内存块为4时 LFU:
内存块为5时 FIFO:
内存块为5时 LRU:
内存块为5时 LFU:
答：随内存块数量的增加，缺页率降低。
5.参照示例程序，实现OPT算法。
提示：
A.缺页率=页面失效次数/页地址流长度=缺页次数/页面访问次数。
B.为了调试方便，可设置页地址流长度（页面访问次数）为100，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
C.关于随机数产生方法，采用函数RAND()和RANDOMIZE()来产生。
D.OPT算法可修改示例程序，先生成页面访问序列，在需要淘汰页面时，从内存块中选择未来最久才被访问的页淘汰之。
程序代码：
#include <iostream> #include<stdio.h> #include <stdlib.h> #include<time.h> using namespace std; #define Options 100 //共100条指令 struct MemBlock { int page; int count; MemBlock* next; }; int main() { time_t t; srand(unsigned(time(&t))); int i,n,j,ii,m,answer,ffalse,count,fangfa,min; double sum; MemBlock *head,*tail,*temp,*table,*first,*ti,*Loadin; cout<<"输入分配的内存块数目【2-6】："<<endl; cin>>m; cout<<endl; cout<<"内存块初始化：\n"; table=new(MemBlock); temp=table; table->page=-1; table->count=0; head=table; for(ii=2; ii<=m; ii++) { table=new(MemBlock); table->page=-1; table->count=0; temp->next=table; temp=table; if (ii==m) table->next=NULL; } for(ti=head; ti!=NULL; ti=ti->next) cout<<ti->page<<"["<<ti->count<<"]"<<"\t\t"; cout<<endl; cout<<"采用页面置换法:\n"<<"1-FIFO\n"<<"2-LRU\n"<<"3-LFU\n"<<"4-OPT"<<endl; cout<<"请选择【1-4】:"; cin>>fangfa; tail=table; temp=head; ffalse=0; answer=0; first=head; count=0; i=0; int index=0; int z; int input[Options]; for(z=0;z<Options;z++) { input[z]=(rand()%Options+1)%Options/10; } for(z=0;z<Options;z++) { if(z%5==0) printf("\n"); printf("%3d",input[z]); } printf("\n"); while(i<Options) //320条指令，指令访问地址为0-319 { table=head; temp=head; answer=0; min=400; //随机生成指令的访问地址n，j为页号 if (count==0) { n=(rand()%Options+1)%Options; j=n/10; } if(count==1) { n=rand()%(n+1); j=n/10; } if(count==2) { j=((n+1)%Options)/10; } if(count==3) { j=((rand()%(Options-n-2))+n+2)/10; } if (fangfa==2||fangfa==3) { while(table!=NULL) { if (table->page==j) //访问的页已装入内存 { answer=1; ++(table->count); break; } table=table->next; } if(answer!=1) //访问的页不在内存 { ++ffalse; //页面缺页次数加1 cout<<j<<"页不在内存，请求装入！\n"; table=head; while (table!=NULL) //查找最少访问的页temp { if(table->page==-1) //如果有空闲页，则不需要置换 { temp=table; break; } if (table->count<min) { temp=table; min=table->count; } table=table->next; } if (temp->page!=-1) //淘汰temp页 cout<<temp->page<<"页被淘汰！\n"; temp->page=j; //装入j页到temp块中 temp->count=1; if(count==3) //每过4次页面访问进行一次计数 { table=head; while(table) { if(table->page!=j && table->count>0) table->count-=1; table=table->next; } } } } if (fangfa==1) //FIFO算法 { int flag=0; Loadin=first; while(table!=NULL) { if (table->page==j) { answer=1; table->count++; break; } if(flag==0&&table->page==-1) //空闲块 { Loadin=table; flag=1; } table=table->next; } if(answer!=1) { ++ffalse; cout<<j<<"页不在内存，请求装入！\n"; if (Loadin->page!=-1) { cout<<Loadin->page<<"页被淘汰！\n"; first=first->next; //下次被淘汰的页 if (first==NULL) first=head; } Loadin->page=j; Loadin->count=1; } } if(fangfa==4) //opt { while(table!=NULL) { if (table->page==input[index]) //访问的页已装入内存 { answer=1; table->count++; break; } table=table->next; } if(answer!=1) //访问的页不在内存 { ++ffalse; //页面缺页次数加1 cout<<input[index]<<"页不在内存，请求装入！\n"; table=head; int h,max=index; while (table!=NULL) //查找未来最久才被访问的页temp { if(table->page==-1) //如果有空闲页，则不需要置换 { temp=table; break; } /*if (table->count<min) //在input中 { //查找最久才被访问的页 temp=table; // min=table->count; // }*/ // //查找table->page在input中将要被访问的地址 for(h=index;h<Options;h++) { if(table->page==input[h]) { if(h>max) { temp=table; max=h; } break; } } if(h>=20) { temp=table; break; } table=table->next; } if (temp->page!=-1) //淘汰temp页 cout<<temp->page<<"页被淘汰！\n"; temp->page=input[index]; //装入j页到temp块中 temp->count=1; } } ++i;index++; count=++count%4; for(ti=head; ti!=NULL; ti=ti->next) cout<<ti->page<<"["<<ti->count<<"]"<<"\t\t"; cout<<endl; } cout<<"\n缺页率为："; sum=ffalse/(Options*1.0); cout<<sum<<endl; }
运行效果：
程序分析：
本程序是一个模拟操作系统页面置换算法的程序，通过模拟程序的运行过程，来分析不同的页面置换算法的效率，从而选择最优的算法，以达到提高程序运行效率的目的。
程序中使用了四种页面置换算法，分别是FIFO（先进先出）、LRU（最近最少使用）、LFU（最不经常使用）和OPT（最优置换算法）。其中，FIFO算法是最简单的算法，即按顺序淘汰最先进入内存的页面；LRU算法是按页面最后一次被访问的时间来淘汰页面；LFU算法是按页面被访问的频率来淘汰页面；OPT算法是预测将来会被使用的页面，将最长时间不被使用的页面淘汰。
在程序开始运行时，需要输入分配的内存块数目，以及选择要使用的页面置换算法。程序首先进行内存块的初始化，将内存块中的页都设置为-1，表示还没有被装入页。然后程序通过随机生成指令的访问地址来模拟程序运行。每访问一次页面，程序会首先检查页面是否已经在内存中，如果在，则将其访问次数加1；如果不在，则需要进行页面置换。
在FIFO算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要将最先进入内存的页面淘汰，将新的页面装入内存。在LRU算法和LFU算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要淘汰最近或最不经常被使用的页面，将新的页面装入内存。在OPT算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要预测将来会被使用的页面，并淘汰最长时间不被使用的页面，将新的页面装入内存。
程序最后输出缺页率，即页面置换的次数除以指令总数。
通过模拟程序运行过程，并比较四种不同的页面置换算法的缺页率，可以得出最优的页面置换算法。当然，不同的程序运行情况下，最优的页面置换算法可能会不同，需要根据实际情况进行选择。
