请求页式存储管理中常用页面置换算法模拟

实验五. 请求页式存储管理的模拟[实验内容]:熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。

[实验要求]：1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。

2、执行2个页面置换模拟程序，分析缺页率的情况。

最好页框数和访问序列长度可调节，在使用同一组访问序列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。

3、在每次产生置换时要求显示分配状态和缺页率。

程序的地址访问序列通过随机数产生，要求具有足够的长度。

最好页框数和访问序列长度可调节。

实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）：程序源代码：#include <libio.h>#include "windows.h"#include <conio.h>#include <stdlib.h>#include <fstream.h>#include <io.h>#include <string.h>#include <stdio.h>void initialize(); //初始化相关数据结构void createps(); //随机生成访问序列void displayinfo(); //显示当前状态及缺页情况void fifo(); //先进先出算法int findpage(); //查找页面是否在内存void lru(); //最近最久未使用算法int invalidcount = 0; // 缺页次数int vpoint; //页面访问指针int pageframe[10]; // 分配的页框int pagehistory[10]; //记录页框中数据的访问历史int rpoint; //页面替换指针int inpflag; //缺页标志，0为不缺页，1为缺页struct PageInfo //页面信息结构{int serial[100]; // 模拟的最大访问页面数，实际控制在20以上int flag; // 标志位，0表示无页面访问数据int diseffect; // 缺页次数int total_pf; // 分配的页框数int total_pn; // 访问页面序列长度} pf_info;//////////////////////////////////////////////////////////////////////// //初始化相关数据结构void initialize(){int i,pf;inpflag=0; //缺页标志，0为不缺页，1为缺页pf_info.diseffect =0; // 缺页次数pf_info.flag =0; // 标志位，0表示无页面访问数据printf("\n请输入要分配的页框数："); // 自定义分配的页框数scanf("%d",&pf);pf_info.total_pf =pf;for(i=0;i<100;i++) // 清空页面序列{pf_info.serial[i]=-1;}///////////////////////////////////////////////////////////////////// 随机生成访问序列void createps(void ){int s,i,pn;initialize(); //初始化相关数据结构printf("\n请输入要随机生成访问序列的长度："); //自定义随机生成访问序列的长度scanf("%d",&pn);srand(rand()); //初始化随机数队列的"种子"s=((float) rand() / 32767) * 50 + pn; // 随机产生页面序列长度pf_info.total_pn = s;for(i=0;i<s;i++) //产生随机访问序列{pf_info.serial[i]=((float) rand() / 32767) * 16 ; //随机数的大小在0-15之间 }}////////////////////////////////////////////////////////////////////////// 显示当前状态及缺页情况void displayinfo(void){int i,n;if(vpoint==0){printf("\n=============页面访问序列=============\n");for(i=0; i<pf_info.total_pn; i++){printf("%4d",pf_info.serial[i]);if ((i+1) % 10 ==0) printf("\n"); //每行显示10个}printf("\n======================================\n");}printf("访问%3d : 内存<",pf_info.serial[vpoint]);for(n=0;n<pf_info.total_pf;n++) // 页框信息{if (pageframe[n] >=0)printf("%3d",pageframe[n]);elseprintf(" ");}printf(" >");if(inpflag==1) //缺页标志，0为不缺页，1为缺页{printf(" ==>缺页 ");printf("缺页率%3.1f",(float)(pf_info.diseffect)*100.00/vpoint);}printf("\n");}//////////////////////////////////////////////////////////////////////// // 查找页面是否在内存，1为在内存，0为不在即缺页int findpage(int page){int n;for(n=0;n<pf_info.total_pf;n++){pagehistory[n] ++; // 访问历史加1}for(n=0;n<pf_info.total_pf;n++){if (pageframe[n]==page ){inpflag=0 ; //inpflag缺页标志，0为不缺页，1为缺页pagehistory[n]=0; //置访问历史为0return 1;}}inpflag=1; //页面不存在，缺页return 0;}//////////////////////////////////////////////////////////////////////// // FIFO页面置换算法void fifo(void){int n,count,pstate;rpoint=0; // 页面替换指针初始化为0invalidcount = 0; // 缺页数初始化为0createps(); // 随机生成访问序列count=0; // 是否装满是所有的页框for(n=0;n<pf_info.total_pf;n++) // 清除页框信息{pageframe[n]=-1;}inpflag=0; //缺页标志，0为不缺页，1为缺页for(vpoint=0;vpoint<pf_info.total_pn;vpoint++) // 执行算法{pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存if(count<pf_info.total_pf) // 开始时不计算缺页{if(pstate==0) // 页不存在则装入页面{pageframe[rpoint]=pf_info.serial[vpoint];rpoint=(rpoint+1) % pf_info.total_pf;count++;}}else // 正常缺页置换{if(pstate==0) // 页不存在则置换页面{pageframe[rpoint]=pf_info.serial[vpoint];rpoint=(rpoint+1) % pf_info.total_pf;pf_info.diseffect++; // 缺页次数加1}}Sleep(10);displayinfo(); // 显示当前状态} // 置换算法循环结束getch();return;}///////////////////////////////////////////////////////////////////// LRU页面置换算法void lru(void){int n,count,pstate,max;rpoint=0; // 页面替换指针invalidcount = 0; // 缺页次数初始化为0createps(); // 随机生成访问序列count=0; // 是否装满所有的页框for(n=0;n<pf_info.total_pf;n++){pageframe[n]=-1; // 清除页框信息pagehistory[n]=0; // 清除页框历史}inpflag=0; //缺页标志，0为不缺页，1为缺页for(vpoint=0;vpoint<pf_info.total_pn;vpoint++) // 执行算法{pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存if(count<pf_info.total_pf) // 开始时不计算缺页{if(pstate==0) // 页不存在则装入页面{pageframe[rpoint]=pf_info.serial[vpoint]; //把要调入的页面放入一个空的页框里rpoint=(rpoint+1) % pf_info.total_pf;count++;}}else // 正常缺页置换{if(pstate==0)// 页不存在则置换页面{max=0;for(n=1;n<pf_info.total_pf;n++){if(pagehistory[n]>pagehistory[max]){max=n;}}rpoint=max;pageframe[rpoint]=pf_info.serial[vpoint];pagehistory[rpoint]=0;pf_info.diseffect++; // 缺页次数加1}}Sleep(10);displayinfo(); // 显示当前状态} // 置换算法循环结束_getch();return;}/////////////////////最佳置换算法自己完成///////////////////////////////////////////////////////////////////// 主函数int main(){char ch;system("cls") ;while ( true ){printf("*******************************************\n");printf(" 若要执行FIFO页面置算法请按1\n");printf(" 若要执行LRU 页面置算法请按2\n");printf(" 若要退出请按3\n") ;printf("*******************************************\n");printf( "Enter your choice (1 or 2 or 3): ");do{ //如果输入信息不正确，继续输入ch = (char)getch() ;}while(ch != '1' && ch != '2'&& ch != '3');printf("\n\n你按的是：%c ,现在为你执行对应操作。

页面替换算法一、实验目的1，通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。

2，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，用三种算法来模拟实现。

3，通过对几种置换算法页面来比较他们的优缺点。

二，实验内容：设计一个虚拟工作区和内存工作区，并使用下列算法来模拟实现页面的置换：1，先进先出算法2，最近最少使用算法3，最佳置换算法三，源程序#include<iostream>#include<stdlib.h>using namespace std;int const InsideCount = 3;//内存中存放的页面数int count = 0;int Inside[InsideCount];int const PageCount =10;//总的页面数int Page[PageCount];int insert = 0;//先到先出置换算法fcfo中表示当内存满的时候，新进入的页号放的位置int suiji = 0; //随机置换算法randchange 当内存满的时候，新进入的页号放的位置int state[InsideCount];//clock置换算法中，内存中的每个页面号对应的状态int state2[InsideCount][2];// 二维数组，第一行第一列为访问位，第一行的第二列为修改位double lost = 0.0;bool isInside(int num)//检测页号是否在内存中{for(int i = 0; i < InsideCount; i++){if(Inside[i] == Page[num]){state[i] = 1;return true;}}return false;}bool change() //判断页面是否已经被修改{if((rand()%2+1) == 1 ){cout<<"该页面被修改"<<endl;return true;}elsereturn false;}void LRU(int num)//最近最久未使用置换算法LRU{int max = 0; // 表示内存中的页号，下一次出现的距离int maxchange; //表示内存中下次出现距离最大的页号在内存中的位置int k;if(isInside(num)){cout<<"命中"<<endl;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}elseif(count == InsideCount){lost++;for(int j=0; j < InsideCount; j++){for( k = num; k >0;k--) //从当前的页号向前看，发现页号与内存中的页号相同，break ；比较内存中三个页号，看哪一个走的远，用max记录{if(Inside[j] == Page[k])break;}if( num - k > max){max = num - k;maxchange =j;//j 表示把内存中第j个Inside中的页面从内存拿出，把新的页面放入}}Inside[maxchange] = Page[num];for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}else{Inside[count] = Page[num];count++;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}}void FIFO(int num)//先进现出置换算法（FIFO）：{if(isInside(num)){cout<<"命中"<<endl;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}elseif(count == InsideCount){lost++;Inside[insert] = Page[num];insert++;insert = insert % 3;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}else{Inside[count] = Page[num];count++;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}}void OPT(int num)//最佳置换算法（OPT）{int max = 0; // 表示内存中的页号，下一次出现的距离int maxchange; //表示内存中下次出现距离最大的页号在内存中的位置int k;if(isInside(num)){cout<<"命中"<<endl;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}elseif(count == InsideCount){lost++;for(int j=0; j < InsideCount; j++){for( k = num; k < PageCount;k++){if(Inside[j] == Page[k])break;}if( k > max){max = k; //k表示在这个地方会再次出现给定页面maxchange =j;//j 表示把内存中第j个Inside中的页面从内存拿出，把新的页面放入}}Inside[maxchange] = Page[num];for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}else{Inside[count] = Page[num];count++;for(int i=0 ; i <InsideCount; i++)cout<<"内存Inside["<<i<<"]中内容为："<<Inside [i]<<endl;}}int main(){char ch ;//选择使用哪种算法while(1){for(int i = 0; i < PageCount; i++){Page[i] =rand()%9 + 1;}cout<<"O 最佳置换算法（OPT）（理想置换算法）"<<"\n"<<endl;cout<<"F 先进现出置换算法（FIFO）"<<"\n"<<endl;cout<<"U 最近最少使用（LRU）算法"<<"\n"<<endl;cin>>ch;switch(ch){case 'O':{lost = 0;count = 0;for(int j = 0; j < InsideCount; j++){Inside[j] = 0;}for(int i = 0; i < PageCount; i++){cout<<"读入Page["<<i<<"]="<<Page[i]<<endl;OPT(i);}cout<<"共" <<PageCount<<"次,"<<"缺失"<<lost<<" 次，缺失率为"<<lost/(PageCount)<<"\n\n"<<endl;}break;case 'F':{lost = 0;count = 0;for(int j = 0; j < InsideCount; j++){Inside[j] = 0;}for(int i = 0; i < PageCount; i++){cout<<"读入Page["<<i<<"]="<<Page[i]<<endl;FIFO(i);}cout<<"共" <<PageCount<<"次,"<<"缺失"<<lost<<" 次，缺失率为"<<lost/(PageCount)<<"\n\n"<<endl;}break;case 'U':{lost = 0;count = 0;for(int j = 0; j < InsideCount; j++){Inside[j] = 0;}for(int i = 0; i < PageCount; i++){cout<<"读入Page["<<i<<"]="<<Page[i]<<endl;LRU(i);}cout<<"共" <<PageCount<<"次,"<<"缺失"<<lost<<" 次，缺失率为"<<lost/(PageCount)<<"\n\n"<<endl;}break;}}return 0;}四、调试结果。

实验报告课程：操作系统班级：成绩：指导教师：实验密级：预习程度：仪器组次：必修/选修：姓名：学号：实验日期：实验时间：实验序号：实验名称：访问实验二请求页式管理中的置换算法实验目的与要求：１．采用FIFO〔先进先出〕置换算法，发生缺页中断时，给出相应的字地址及页号，计算缺页中断率。

２．采用LFU〔最不经常使用〕置换算法，发生缺页中断时，给出相应的字地址及页号，计算缺页中断率。

实验仪器：名称型号数量微机1一、实验内容１．假设有一个用户进程P的地址空间为n〔n=60〕页，系统已在内存中给该进程分配有m〔m<n，m=8〕个页面，且该进程的第0、5、6页〔p0、p5、p6〕已经装入内存，页长为1K。

根据进程访问的字地址序列，采用不同的置换算法，分别计算缺页中断率。

２．进程依次要访问的字地址序列〔访问串〕，在0~1024*n-1〔0~61439〕中模拟随机发生，访问序列的随机生成规那么为：50%的字地址前向顺序增长，25%的字地址均匀分布在前地址〔低地址〕局部，25%的字地址均匀分布在后地址〔高地址〕局部，为了减少模拟次数，前向顺序递增产生的字地址如小于1024*n-51360927〕那么自动加512。

模拟访问串长度为100。

以n=60为例，字地址序列〔访问串〕的随机生成方法如下：〔1〕在[0，61439]之间随机产生起始字地址，当前访问的字地址记为k；〔2〕前向顺序递增产生的字地址为 k+1+512；〔3〕前地址〔低地址〕在[0，k-1]内随机产生；〔4〕后地址〔高地址〕在[k+1，61439]内随机产生；〔5〕重复顺序递增、前地址区间随机产生、后地址区间随机产生的过程，概率分别为：50%、25%、25%。

二、实验要求１．采用FIFO〔先进先出〕置换算法，发生缺页中断时，给出相应的字地址及页号，计算缺页中断率。

２．采用LFU〔最不经常使用〕置换算法，发生缺页中断时，给出相应的字地址及页号，计算缺页中断率。

实验四请求分页存储管理模拟实验一：实验目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求分页存储管理系统的原理和实现技术的理解。

二：实验内容假设每个页面可以存放10条指令，分配给进程的存储块数为4。

用C语言或Pascal语言模拟一进程的执行过程。

设该进程共有320条指令，地址空间为32个页面，运行前所有页面均没有调入内存。

模拟运行时，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令；如果所访问的指令还未装入内存，则发生缺页，此时需要记录缺页产生次数，并将相应页面调入内存，如果4个内存块已满，则需要进行页面置换。

最后显示其物理地址，并转下一条指令。

在所有指令执行完毕后，显示进程运行过程中的缺页次数和缺页率。

页面置换算法：分别采用OPT、FIFO、LRU三种算法。

进程中的指令访问次序按如下原则生成：50%的指令是顺序执行的。

25%的指令是均匀分布在低地址部分。

25%的指令是均匀分布在高地址部分。

三：实验类别分页存储管理四：实验类型模拟实验五：主要仪器计算机六：结果OPT:LRU:FIFO:七：程序# include<stdio.h># include<stdlib.h># include<conio.h># define blocknum 4//页面尺寸大小int m; //程序计数器，用来记录按次序执行的指令对应的页号static int num[320]; //用来存储320条指令typedef struct BLOCK //声明一种新类型--物理块类型{int pagenum; //页号int accessed; //访问量，其值表示多久未被访问}BLOCK;BLOCK block[blocknum]; //定义一大小为8的物理块数组void init() //程序初始化函数,对block初始化{for(int i=0;i<blocknum;i++){block[i].pagenum=-1;block[i].accessed=0;m=0;}}int pageExist(int curpage)//查找物理块中页面是否存在,寻找该页面curpage是否在内存块block中，若在，返回块号{for(int i=0; i<blocknum; i++){if(block[i].pagenum == curpage )return i; //在内存块block中，返回块号}return -1;}int findSpace()//查找是否有空闲物理块,寻找空闲块block，返回其块号{for(int i=0;i<blocknum;i++){if(block[i].pagenum==-1)return i; //找到了空闲的block，返回块号}return -1;}int findReplace()//查找应予置换的页面{int pos = 0;for(int i=0;i<blocknum;i++){if(block[i].accessed > block[pos].accessed)pos = i; //找到应该置换页面，返回BLOCK中位置}return pos;void display()//显示物理块中的页面号{for(int i=0; i<blocknum; i++){if(block[i].pagenum != -1){printf(" %02d ",block[i].pagenum);printf("%p |",&block[i].pagenum);}}printf("\n");}void randam()//产生320条随机数,显示并存储到num[320]{int flag=0;printf("请为一进程输入起始执行指令的序号(0~320):\n");scanf("%d",&m);//用户决定的起始执行指令printf("******进程中指令访问次序如下：(由随机数产生)*******\n");for(int i=0;i<320;i++){//进程中的320条指令访问次序的生成num[i]=m;//当前执行的指令数，if(flag%2==0)m=++m%320;//顺序执行下一条指令if(flag==1)m=rand()%(m-1);//通过随机数，跳转到低地址部分[0，m-1]的一条指令处，设其序号为m1if(flag==3)m=m+1+(rand()%(320-(m+1)));//通过随机数，跳转到高地址部分[m1+2，319]的一条指令处，设其序号为m2flag=++flag%4;printf(" %03d",num[i]);//输出格式：3位数if((i+1)%10==0) //控制换行,每个页面可以存放10条指令，共32个页面printf("\n");}}void pagestring() //显示调用的页面序列,求出此进程按次序执行的各指令所在的页面号并显示输出{for(int i=0;i<320;i++){printf(" %02d",num[i]/10);//输出格式：2位数if((i+1)%10==0)//控制换行,每个页面可以存放10条指令，共32个页面printf("\n");}}void OPT() //最佳替换算法{int n=0;//记录缺页次数int exist,space,position;int curpage;//当前指令的页面号for(int i=0;i<320;i++){m=num[i];curpage=m/10;exist=pageExist(curpage);if(exist==-1){ //当前指令的页面号不在物理块中space=findSpace();if(space != -1){ //当前存在空闲的物理块block[space].pagenum = curpage; //将此页面调入内存display();//显示物理块中的页面号n++;//缺页次数+1}else{ //当前不存在空闲的物理块，需要进行页面置换for(int k=0;k<blocknum;k++){for(int j=i;j<320;j++){//找到在最长（未来）时间内不再被访问的页面if(block[k].pagenum!= num[j]/10){block[k].accessed = 1000;} //将来不会被访问，设置为一个很大数else{ //将来会被访问，访问量设为jblock[k].accessed = j;break;}}}position = findReplace();//找到被置换的页面 ,淘汰block[position].pagenum = curpage;// 将新页面调入display();n++; //缺页次数+1}}}printf("缺页次数:%d\n",n);printf("缺页率:%f%%\n",(n/320.0)*100);}void LRU() //最近最久未使用算法{int n=0;//记录缺页次数int exist,space,position ;int curpage;//当前指令的页面号for(int i=0;i<320;i++){m=num[i];curpage=m/10;exist = pageExist(curpage);if(exist==-1){ //当前指令的页面号不在物理块中space = findSpace();if(space != -1){ //当前存在空闲的物理块block[space].pagenum = curpage; //将此页面调入内存display();//显示物理块中的页面号n++;//缺页次数+1}else{ //当前不存在空闲的物理块，需要进行页面置换position = findReplace();block[position].pagenum = curpage;display();n++; //缺页次数+1}}elseblock[exist].accessed = -1;//恢复存在的并刚访问过的BLOCK中页面accessed为-1for(int j=0; j<blocknum; j++){//其余的accessed++block[j].accessed++;}}printf("缺页次数:%d\n",n);printf("缺页率:%f%%\n",(n/320.0)*100);}void FIFO(){int n=0;//记录缺页次数int exist,space,position ;int curpage;//当前指令的页面号int blockpointer=-1;for(int i=0;i<320;i++){m=num[i];curpage=m/10;exist = pageExist(curpage);if(exist==-1){ //当前指令的页面号不在物理块中space = findSpace();if(space != -1){ //当前存在空闲的物理块blockpointer++;block[space].pagenum=curpage; //将此页面调入内存n++;//缺页次数+1display();//显示物理块中的页面号}else{ // 没有空闲物理块，进行置换position = (++blockpointer)%4;block[position].pagenum = curpage; //将此页面调入内存n++;display();}}}printf("缺页次数:%d\n",n);printf("缺页率:%f%%\n",(n/320.0)*100);}void main(){int choice;printf("************请求分页存储管理模拟系统*************\n");randam();printf("************此进程的页面调用序列如下**************\n");pagestring();while(choice != 4){printf("********1:OPT 2:LRU 3:FIFO 4:退出*********\n");printf("请选择一种页面置换算法:");scanf("%d",&choice);init();switch(choice){case 1:printf("最佳置换算法OPT:\n");printf("页面号物理地址页面号物理地址页面号物理地址页面号物理地址\n");OPT();break;case 2:printf("最近最久未使用置换算法LRU:\n");printf("页面号物理地址页面号物理地址页面号物理地址页面号物理地址\n");LRU();break;case 3:printf("先进先出置换算法FIFO:\n");printf("页面号物理地址页面号物理地址页面号物理地址页面号物理地址\n");FIFO();break;}}}。

计算机操作系统实验报告济南大学信息科学与技术学院2013年xx月xx日一、实验概述1. 实验名称请求页式存储管理中常用页面置换算法管理2. 实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。

（5）了解页面大小和内存实际容量对命中率的影响3. 实验内容（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；（2）实现OPT 算法(最优置换算法) 、LRU 算法(Least Recently) 、FIFO 算法(First IN First Out)的模拟；（3）使用某种编程语言模拟页面置换算法。

二、实验环境C语言三、实验过程1. 设计思路和流程图选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换2. 算法实现（1）OPT基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。

数组next[mSIZE]记录物理块中对应页面的最后访问时间。

每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

（2）FIFO基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。

或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。

(3)LRU基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。

数组flag[10]标记页面的访问时间。

每当使用页面时，刷新访问时间。

发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。

3.源程序并附上注释#include <stdio.h>#include <stdlib.h>/*全局变量*/int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串个数*/static int memery[10]={0}; /*物理块中的页号*/static int page[100]={0}; /*页面号引用串*/static int temp[100][10]={0}; /*辅助数组*//*置换算法函数*/void FIFO();void LRU();void OPT();/*辅助函数*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函数*/void main(){int i,k,code;system("color 0A");designBy();printf("┃请按任意键进行初始化操作... ┃\n");printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");printf(" >>>");getch();system("cls");system("color 0B");printf("请输入物理块的个数(M<=10)：");scanf("%d",&mSIZE);printf("请输入页面号引用串的个数(P<=100)：");scanf("%d",&pSIZE);puts("请依次输入页面号引用串(连续输入，无需隔开)：");for(i=0;i<pSIZE;i++)scanf("%1d",&page[i]);download();system("cls");system("color 0E");do{puts("输入的页面号引用串为：");for(k=0;k<=(pSIZE-1)/20;k++){for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++){if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))printf("%d\n",page[i]);elseprintf("%d ",page[i]);}}printf("* * * * * * * * * * * * * * * * * * * * * * *\n");printf("* 请选择页面置换算法：\t\t\t *\n");printf("* ----------------------------------------- *\n");printf("* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *\n");printf("* 3.最佳(OPT) 4.退出*\n");printf("* * * * * * * * * * * * * * * * * * * * * * *\n");printf("请选择操作：[ ]\b\b");scanf("%d",&code);switch(code){case 1:FIFO();break;case 2:LRU();break;case 3:OPT();break;case 4:system("cls");system("color 0A");designBy(); /*显示设计者信息后退出*/printf("┃谢谢使用页面置换算法演示器! 正版授权㊣┃\n");printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");exit(0);default:printf("输入错误，请重新输入：");}printf("按任意键重新选择置换算法：>>>");getch();system("cls");}while (code!=4);getch();}/*载入数据*/void download(){int i;system("color 0D");printf("╔════════════╗\n");printf("║正在载入数据，请稍候!!!║\n");printf("╚════════════╝\n");printf("Loading...\n");printf(" O");for(i=0;i<51;i++)printf("\b");for(i=0;i<50;i++){mDelay((pSIZE+mSIZE)/2);printf(">");}printf("\nFinish.\n载入成功，按任意键进入置换算法选择界面：>>>");getch();}/*设置延迟*/void mDelay(unsigned int Delay){unsigned int i;for(;Delay>0;Delay--){for(i=0;i<124;i++){printf(" \b");}}}/*显示设计者信息*/void designBy(){printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("┃课题三：页面置换算法┃\n");printf("┃学号：20111214034 ┃\n");printf("┃姓名：韩瑶┃\n");printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━┫\n"); }void print(unsigned int t){int i,j,k,l;int flag;for(k=0;k<=(pSIZE-1)/20;k++){for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++){if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))printf("%d\n",page[i]);elseprintf("%d ",page[i]);}for(j=0;j<mSIZE;j++){for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++){if(i>=j)printf(" |%d|",temp[i][j]);elseprintf(" | |");}for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++){for(flag=0,l=0;l<mSIZE;l++)if(temp[i][l]==temp[i-1][l])flag++;if(flag==mSIZE)/*页面在物理块中*/printf(" ");elseprintf(" |%d|",temp[i][j]);}/*每行显示20个*/if(i%20==0)continue;printf("\n");}}printf("----------------------------------------\n");printf("缺页次数：%d\t\t",t+mSIZE);printf("缺页率：%d/%d\n",t+mSIZE,pSIZE);printf("置换次数：%d\t\t",t);printf("访问命中率：%d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE);printf("----------------------------------------\n");}/*计算过程延迟*/void compute(){int i;printf("正在进行相关计算，请稍候");for(i=1;i<20;i++){mDelay(15);if(i%4==0)printf("\b\b\b\b\b\b \b\b\b\b\b\b");elseprintf("Θ");}for(i=0;i++<30;printf("\b"));for(i=0;i++<30;printf(" "));for(i=0;i++<30;printf("\b"));}/*先进先出页面置换算法*/void FIFO(){int memery[10]={0};int time[10]={0}; /*记录进入物理块的时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE) /*如果不在物理块中*/{count++;/*计算换出页*/max=time[0]<time[1]?0:1;for(m=2;m<mSIZE;m++)if(time[m]<time[max])max=m;memery[max]=page[i];time[max]=i; /*记录该页进入物理块的时间*/for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}compute();print(count);}/*最近最久未使用置换算法*/void LRU(){int memery[10]={0};int flag[10]={0}; /*记录页面的访问时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;elseflag[j]=i; /*刷新该页的访问时间*/ }if(k==mSIZE) /*如果不在物理块中*/{count++;/*计算换出页*/max=flag[0]<flag[1]?0:1;for(m=2;m<mSIZE;m++)if(flag[m]<flag[max])max=m;memery[max]=page[i];flag[max]=i; /*记录该页的访问时间*/for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}compute();print(count);}/*最佳置换算法*/void OPT(){int memery[10]={0};int next[10]={0}; /*记录下一次访问时间*/int i,j,k,l,m;int max; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE) /*如果不在物理块中*/{count++;/*得到物理快中各页下一次访问时间*/for(m=0;m<mSIZE;m++){for(l=i+1;l<pSIZE;l++)if(memery[m]==page[l])break;next[m]=l;}/*计算换出页*/max=next[0]>=next[1]?0:1;for(m=2;m<mSIZE;m++)if(next[m]>next[max])max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/memery[max]=page[i];for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else {for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}compute();print(count);}6. 程序运行时的初值和运行结果1. 按任意键进行初始化：2. 载入数据：3. 进入置换算法选择界面：4.运算中延迟操作5.三种算法演示结果：四、实验体会掌握了一般的调度算法，了解了页面大小和内存实际容量对命中率的影响（英文版）Two regulations promulgated for implementation is in the party in power for a long time and the rule of law conditions, the implementation of comprehensive strictly strategic plan, implementation in accordance with the rules and discipline to manage the party, strengthen inner-party supervision of major initiatives. The two regulations supporting each other, the < code > adhere to a positive advocate, focusing on morality is of Party members and Party leading cadres can see, enough to get a high standard; < rule > around the party discipline, disciplinary ruler requirements, listed as "negative list, focusing on vertical gauge, draw the party organizations and Party members do not touch the" bottom line ". Here, the main from four square face two party rules of interpretation: the first part introduces two party Revised regulations the necessity and the revision process; the second part is the interpretation of the two fundamental principles of the revision of laws and regulations in the party; the third part introduces two party regulations modified the main changes and needs to grasp several key problems; the fourth part on how to grasp the implementation of the two regulations of the party. < code > and < Regulations > revised the necessity and revisedhistory of the CPC Central Committee the amendment to the Chinese Communist Party members and leading cadres honest politics several guidelines > and < Chinese Communist Party discipline and Punishment Regulations > column 1 by 2015 to strengthen party laws and regulations focus. Two party regulations revision work lasted a Years, pooling the wisdom of the whole party, ideological consensus, draw historical experience, respect for the wisdom of our predecessors, which reflects the unity of inheritance and innovation; follow the correct direction, grasp the limited goals, adhere to the party's leadership, to solve the masses of the people reflect a focus on the problem. The new revision of the < code > and < rule >, reflects the party's 18 and the eighth session of the third, the spirit of the fourth plenary session, reflecting the experience of studying and implementing the General Secretary Xi Jinping series of important speech, reflects the party's eighteen years comprehensive strictly practice. (a) revised two regulations of the party need of < the ICAC guidelines > in < in 1997 Leaders as members of the Communist Party of China clean politics certain criteria (Trial) > based on revised, the promulgation and implementation of January 2010, to strengthen the construction of the contingent of leading cadres play animportant role. But with the party to manage the party strictly administering the deepening, has not been able to fully meet the actual needs. Content is too complicated, "eight prohibition, 52 are not allowed to" hard to remember, and also difficult to put into practice; the second is concisely positive advocated by the lack of prohibited provisions excessive, no autonomy requirements; the third is banned terms and discipline law, both with the party discipline, disciplinary regulations repeat and Criminal law and other laws and regulations repeat; the fourth is to "clean" the theme is not prominent, not for the existing problems, and is narrow, only needle of county-level leading cadres above. < rule > is in 1997 < Chinese Communist Party disciplinary cases (Trial) > based on revision, in December 2003 the promulgation and implementation, to strengthen the construction of the party play very important role. Along with the development of the situation, which many provisions have been unable to fully meet the comprehensive strictly administering the practice needs. One is Ji law, more than half of the provisions and criminal law and other countries laws and regulations Repetition; two is the political discipline regulations is not prominent, not specific, for violation of the party constitution, damage theauthority of Party Constitution of misconduct lack necessary and serious responsibility to pursue; third is the main discipline for the leading cadres, does not cover all Party members. Based on the above situation, need to < the criterion of a clean and honest administration > and < rule > the two is likely to be more relevant regulations first amendment. By revising, really put the authority of Party discipline, the seriousness in the party tree and call up the majority of Party members and cadres of the party constitution of party compasses party consciousness. (II) two party regulations revision process the Central Committee of the Communist Party of China attaches great importance to two regulations revision . Xi Jinping, general books recorded in the Fifth Plenary Session of the eighth session of the Central Commission for Discipline Inspection, on the revised regulations < > made clear instructions. According to the central deployment, the Central Commission for Discipline Inspection from 2014 under six months begin study two regulations revision. The Standing Committee of the Central Commission for Discipline Inspection 4 review revised. Comrade Wang Qishan 14 times held a special meeting to study two regulations revision, amendment clarifies the direction, major issues of principle, path and target,respectively held a forum will listen to part of the province (area) secretary of the Party committee, Secretary of the Discipline Inspection Commission, part of the central ministries and state organs DepartmentThe first party committee is mainly responsible for people, views of experts and scholars and grassroots party organizations and Party members. Approved by the Central Committee of the Communist Party of China, on 7 September 2015, the general office of the Central Committee of the Party issued a notice to solicit the provinces (autonomous regions, municipalities) Party, the central ministries and commissions, state ministries and commissions of the Party (party), the General Political Department of the military, every 3 people organization of Party of two regulations revision opinion. Central Commission for Discipline Inspection of extensive solicitation of opinions, careful study, attracting, formed a revised sent reviewers. In October 8 and October 12, Central Committee Political Bureau Standing Committee and the Political Bureau of the Central Committee After consideration of the two regulations revised draft. On October 18, the Central Committee of the Communist Party of China formally issued two regulations. Can say, two laws amendment concentrated thewisdom of the whole party, embodies the party. Second, < code > and < Regulations > revision of the basic principles of two party regulations revision work and implement the party's eighteen, ten eight plenary, the spirit of the Fourth Plenary Session of the Eleventh Central Committee and General Secretary Xi Jinping important instructions on the revised < low political criterion > and < Regulations >, highlighting the ruling party characteristics, serious discipline, the discipline quite in front of the law, based on the current, a long-term, advance as a whole, with Bu Xiuding independent < rule > and < rule >. Main principle is: first, adhere to the party constitution to follow. The constitution about discipline and self-discipline required specific, awaken the party constitution of party compasses party consciousness, maintaining the authority of the constitution. General Secretary Xi Jinping pointed out that "no rules, no side round. Party constitution is the fundamental law, the party must follow the general rules. In early 2015 held the eighth session of the Central Commission for Discipline Inspection Fifth Plenary Session of the 16th Central Committee, Xi Jinping again pointed out that constitution is the party must follow the general rules, but also the general rules." the revision of the< code > and < rule > is Method in adhere to the regulations established for the purpose of combining rule of virtue is to adhere to the party constitution as a fundamental to follow, the constitution authority set up, wake up the party constitution and party rules the sense of discipline, the party constitution about discipline and self-discipline specific requirements. 4 second is to adhere to in accordance with the regulations governing the party and the party. The Party of rule of virtue "de", mainly refers to the party's ideals and beliefs, excellent traditional style. The revised the < code > closely linked to the "self-discipline", insisting on the positive initiative, for all members, highlight the "vital few", emphasized self-discipline, focusing on the morality, and the majority of Party members and the ideological and moral standards. The revised < > Ji method separately, Ji, Ji Yan to Method, as a "negative list", emphasizing the heteronomy, focusing on vertical gauge. Is this one high and one low, a positive reaction, the strict party discipline and practice results transformation for the integration of the whole party to observe moral and discipline requirements, for the majority of Party members and cadres provides benchmarking and ruler. Third, insist on to. In view of the problems existing in theparty at the present stage, the main problems of Party members and cadres in the aspect of self-discipline and abide by the discipline to make clearly defined, especially the party's eighteen years strict political discipline and political rules, organization and discipline and to implement the central eight provisions of the spirit against the four winds and other requirements into Disciplinary provisions. Not one pace reachs the designated position, focusing on in line with reality, pragmatic and effective. After the revision of major changes, major changes in the < code > and < rule > modified and needs to grasp several key problems (a) < code > < code > adhere to according to regulations governing the party and party with morals in combination, for at the present stage, the leadership of the party members and cadres and Party members in existing main problems of self-discipline, put forward principles, requirements and specifications, showing Communists noble moral pursuit, reflected at all times and in all over the world ethics from high from low 5 common requirements. One is closely linked to the "self-discipline", removal and no direct relation to the provisions of . the second is adhere to a positive advocate, "eight prohibition" 52 are not allowed to "about the content of the" negative list moved into synchronizationamendment < cases >. Three is for all the party members, will apply object from the leadership of the party members and cadres to expand to all Party members, fully embodies the comprehensive strictly required. The fourth is prominent key minority, seize the leadership of the party members and cadres is the key, and put forward higher requirements than the ordinary Party members. Five is to simplify, and strive to achieve concise, easy to understand, easy to remember. The revised < code > is the ruling Party since the first insists on a positive advocate forAll Party members and the self-discipline norms, moral declaration issued to all members of the party and the National People's solemn commitment. > < criterion of a clean and honest administration consists of 4 parts, 18, more than 3600 words. After the revision of the < code >, a total of eight, 281 words, including lead, specification and Party member cadre clean fingered self-discipline norms, etc. Part 3 members low-cost clean and self-discipline, the main contents can be summarized as "four must" "eight code". Lead part, reiterated on ideal and faith, fundamental purpose, the fine traditions and work style, noble sentiments, such as "four must" the principle of requirements, strong tone of self-discipline, The higher request for 6 andsupervised tenet, the foothold in permanent Bao the party's advanced nature and purity, to reflect the revised standards requirements. Members of self-discipline norms around the party members how to correctly treat and deal with the "public and private", "cheap and rot" thrifty and extravagance "bitter music", put forward the "four norms". Party leader cadre clean fingered self-discipline norms for the leadership of the party members and cadres of the "vital few", around the "clean politics", from civil servant of the color, the exercise of power, moral integrity, a good family tradition and other aspects of the leadership of the party members and cadres of the "four norms" < > < norm norm. "The Party member's self-discipline norms" and "party members and leading cadre clean fingered self-discipline norms," a total of eight, collectively referred to as the "eight". "Four must" and "eight" of the content from the party constitution and Party's several generation of leaders, especially Xi Jinping, general secretary of the important discussion, refer to the "three discipline and eight points for attention" statements, and reference some embody the Chinese nation excellent traditional culture essence of epigrams. (2) the revised regulations, the main changes in the revised Regulations > to fully adapt to thestrictly requirements, reflects the according to the regulations governing the law of recognition of deepening, the realization of the discipline construction and Jin Ju. < rule > is party a ruler, members of the basic line and follow. And the majority of Party members and cadres of Party organizations at all levels should adhere to the bottom line of thinking, fear discipline, hold the bottom line, as a preventive measure, to keep the party's advanced nature and purity. 1, respect for the constitution, refinement and discipline. Revised < rule > from comprehensive comb physical constitution began, the party constitution and other regulations of the Party of Party organizations and Party discipline requirements refinement, clearly defined in violation of the party constitution will be in accordance with regulations to give the corresponding disciplinary action. The original 10 categories of misconduct, integration specification for political discipline, discipline, honesty and discipline masses Ji Law and discipline and discipline and other six categories, the content of < rule > real return to Party discipline, for the majority of Party members and listed a "negative list. 7 2, highlighting the political discipline and political rules. > < Regulations according to the stage of the discipline of outstandingperformance, emphasizing political discipline and political rules, organization and discipline, in opposition to the party's leadership and the party's basic theory, basic line, basic program and basic experience, the basic requirement of behavior made prescribed punishment, increase the cliques, against the organization such as violation of the provisions, to ensure that the central government decrees and the Party of centralized and unified. 3, adhere to strict discipline in the law and discipline In front, Ji separated. Revised < Regulations > adhere to the problem oriented, do Ji separated. Any national law existing content, will not repeat the provisions, the total removal of 79 and criminal law, repeat the content of the public security management punishment law, and other laws and regulations. In the general reiterated that party organizations and Party members must conscientiously accept the party's discipline, die van comply with national laws and regulations; at the same time, to investigate violations of Party members and even criminal behavior of Party discipline and responsibility, > < Regulations distinguish five different conditions, with special provisions were made provisions, so as to realize the connection of Party discipline and state law. 4, reflect Wind building and anti-corruptionstruggle of the latest achievements. < rule > the party's eighteen years implement the spirit of the central provisions of the eight, against the requirements of the "four winds" and transformation for disciplinary provisions, reflecting the style construction is always on the road, not a gust of wind. In the fight against corruption out of new problems, increase the trading rights, the use of authority relatives profit and other disciplinary terms. Prominent discipline of the masses, the new against the interests of the masses and ignore the demands of the masses and other disciplinary terms and make provisions of the disposition and the destruction of the party's close ties with the masses.Discipline to protect the party's purpose. 8 of these regulations, a total of three series, Chapter 15, 178, more than 24000 words, after the revision of the regulations a total of 3 series, Chapter 11, 133, 17000 words, divided into "general" and "special provisions" and "Supplementary Provisions" Part 3. Among them, add, delete, modify the provisions of the proportion of up to nearly 90%. 1, the general general is divided into five chapters. The first chapter to the regulations of the guiding ideology, principles and scope of application of the provisions, highlight the strengthening ofthe party constitution consciousness, maintenance the authority of Party Constitution, increase the party organizations and Party members must abide by the party constitution, Yan Centralized centralized, would examine at all levels of the amended provisions implementing and maintaining Party discipline, and consciously accept the party discipline, exemplary compliance with national laws and regulations. The second chapter of discipline concept, disciplinary action types and effects of the regulations, will be a serious warning from the original a year for a year and a half; increase the Party Congress representative, by leaving the party above (including leave probation) punishment, the party organization should be terminated its representative qualification provisions. The third chapter of the disciplinary rules of use prescribed in the discipline rectifying process, non convergence, not close hand classified as severely or heavier punishment. "Discipline straighten "At least eighteen years of five years, these five years is to pay close attention to the provisions of the central eight implementation and anti -" four winds ". The fourth chapter on suspicion of illegal party disciplinary distinguish five different conditions, with special provisions were madeprovisions, to achieve effective convergence of Party and country 9 method. < rule > the provisions of Article 27, Party organizations in the disciplinary review found that party members have committed embezzlement, bribery, dereliction of duty dereliction of duty and other criminal law act is suspected of committing a crime shall give cancel party posts, probation or expelled from the party. The second is < Regulations > Article 28 the provisions of Party organizations in the disciplinary review But found that party members are stipulated in the criminal law, although not involved in a crime shall be investigated for Party discipline and responsibility should be depending on the specific circumstances shall be given a warning until expelled punishment. This situation and a difference is that the former regulation behavior has been suspected of a crime, the feeling is quite strict, and the latter for the behavior not involving crime, only the objective performance of the provisions of the criminal code of behavior, but the plot is a crime to slightly. < Regulations > the 29 provisions, Party organizations in the discipline review found that party members and other illegal behavior, affect the party's image, the damage to the party, the state and the people's interests, we should depend on the situation。

《计算机操作系统》课外实践报告题目：页面置换算法模拟班级： 13级物联网工程一班姓名：王铎学号： 130911044指导老师: 王蕾设计时间: 2014.6一、实验目标：通过设计请求页面存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页面存储管理的页面置换算法。

二、实验要求1通过随机数产生一个指令序列 共320条指令。

指令的地址按下述原则生成50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在地址部分。

2将指令序列换成为页地址流。

3计算并输出下述各种算法在不同内存容量下的命中率。

（1）先进先出的算法 FIFO（2）最近最少使用算法 LRU（3）最近最不经常使用算法 NUR三．实践内容简要描述1、实践环境windows XP/7，visual C++ 6.02、算法思路与算法原理2.1、先进先出算法（FIFO）：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单，只需要把一个进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，成为替换指针，使它总是指向最老的页面。

2.2、最近最久未使用页面置换算法（LRU）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近一段时间内最久没有使用过的页先淘汰。

该算法的出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页长时间未被访问，则它在最近一段时间不会被访问。

3概要设计3.1 总体设计框图4系统流程图图4.1详细设计框图图4.2为置换方法的流程图5代码分析结果5.1 数据结构int m, int need[],int n, result[10][20],int state[],int count1[];5.2 FIFO具体函数及设计实现FIFO流程图FIFO函数实现void FIFO(int m, int need[],int n) //m分配物理页面大小，n需要页面数组的最大值{int p=0; //当前请求的页面int del=0; //步数int count1[20];double count=0; //缺页数double que=0; //缺页率int result[10][20]; //结果表for(int i =0;i<=m;i++)for(int j=0;j<=n;j++){result[i][j]=-1;count1[j]=-1;}while(n>=p){int k=need[p];if(p>0){for(int i=0;i<=m;i++){result[i][p]=result[i][p-1];}}int f1=0;//首先看是否有空位置或者已经存在请求的页面for(int i =0;i<=m;i++){if(result[i][p]==-1){result[i][p]=k;f1=1;i=m+1;count1[p]=k;count=count+1;p=p+1;}else if(result[i][p]==k){f1=1;p=p+1;i=m+1;}}if(f1==1) continue;//这里发生替换result[del][p]=k;count1[p]=k;count=count+1;p=p+1;del=(del+1)%(m+1);}cout<<"*******************FIFO过程如下表************************"<<endl; for(int t3=0;t3<=n;t3++)//输出原来的页面cout<<need[t3]<<" ";cout<<endl;for(int t0 =0;t0<=m;t0++)//判断页表是否填满{for(int t1=0;t1<=n;t1++){if(result[t0][t1]!=-1)cout<<result[t0][t1]<<" ";else cout<<" "<<" ";}cout<<endl;}for(int j1=0;j1<=n;j1++)//对于缺页的打×，否则打√{if(count1[j1]!=-1)cout<<"×";else cout<<"√";}cout<<endl;que=count/(n+1);//统计缺页次数和缺页率cout<<"缺页次数为:"<<count<<endl;cout<<"缺页率"<<count<<"/"<<n+1<<"="<<que<<endl;cout<<"**************************************************"<<endl;}5.3LRU具体函数及设计实现LRU流程图LRU函数实现void LRU(int m, int need[],int n){m++;n++;int i, j, min, num = 1, k, flag;int state[10], count[20], hsive[10];int result[10][20];memset(state, 0, sizeof(state));//初始化内存空间，给三个数组分配内存memset(count, -1, sizeof(count));memset(hsive, -1, sizeof(hsive));memset(result, -1, sizeof(result));for(i = 0; i < n; i++)//将need数组值赋给resultresult[0][i] = need[i];cout<<"*****************LRU过程如下表*********************"<<endl;for(i = 0; i < n; i++){flag = 0;//标志位，如果页面和页表内的熄灯则赋值for(j = 1; j < num; j++){if(result[0][i] == hsive[j]){flag = 1;state[j] = -1;break;}}if(flag == 0)//替换{if(num <= m)hsive[num] = result[0][i];else{min = -1;for(j = 1; j <= m; j++){if(state[j] > min){k = j;min = state[j];}}hsive[k] = result[0][i];state[k] = -1;}count[i] = 1;num++;}for(j = 1; j <= m; j++){result[j][i] = hsive[j];state[j]++;}}for(j = 0; j <= m; j++)//输入个页面替换情况{for(i = 0; i < n; i++){if(result[j][i] == -1)cout << " ";elsecout << result[j][i] << " ";}cout << endl;}for(i = 0; i < n; i++){if(count[i] != -1)cout<<"×";elsecout<<"√";}cout << endl;//统计各页面缺页次数和缺页率cout << "缺页次数为:" << num - 1 << endl;cout << "缺页率" << num - 1 << "/"<<n << "=" << double(num - 1) / n <<endl;cout<<"**************************************************"<<endl; }主方法int main(){cout<<" *********************************************"<<endl;cout<<" * 页式存储管理*"<<endl;cout<<" ********************************************* "<<endl;int m;int n=0;int choose=2;int need[20];char flag;while(1){cout<<"指定内存分配页面数:";while (flag<'0'||flag>'9'){cin>>flag;}m=flag-'0'-1;flag=' ';cout<<"请选择页面序列产生方式:"<<endl;cout<<" (0)手动输入"<<endl;cout<<" (1)随机产生"<<endl;while (flag<'0'||flag>'1'){cin>>flag;}choose =flag-'0';flag=' ';if(choose==0){cout<<"输入页面走向！以s结尾"<<endl;while(1){while ((flag<'0'||flag>'9')&&flag!='s'){cin>>flag;}if(flag=='s') break;need[n]=flag-'0';flag=' ';n=n+1;}flag=' ';n=n-1;}else {cout<<"随机产生的页面个数:";cin>>n;n=n-1;for(int i=0;i<=n;i++){need[i]=rand()%10;}}system("cls");cout<<"选择页面置换算法:"<<endl;cout<<"0-FIFO 1-LRU"<<endl;while (flag<'0'||flag>'1'){cin>>flag;}choose =flag-'0';flag=' ';if(choose==0){FIFO(m, need,n);}else {LRU(m, need,n);}cout<<"输入Y/y可以看另外一种置换算法的执行过程"<<endl;cin>>flag;if(flag=='Y'||flag=='y'){system("cls");if(choose==0) LRU(m, need,n);else FIFO(m, need,n);}else flag=' ';cout<<"输入N/n退出否则输入任意键继续"<<endl;cin>>flag;if(flag=='N'||flag=='n') break;else{system("cls");flag=' ';}}return 0;}5.4调用关系图6测试6.1进入界面及产生页面走向运行结果如下图6.1 进入管理界面图6.2产生页面走向6.2FIFO算法及查看结果图6.3选择FIFO算法结果6.3LRU算法及查看结果图6.4选择LRU结果6.4继续进入主界面及产生页面走向图6.5按y继续回到主界面设置页面为46.5调度算法及结果图6.6选择LRU算法结果图6.7选择FIFO算法结果7 总结与体会通过这次实验，我基本了解了页面置换算法的基本设置与要求，懂得了先进先出算法（FIFO）、最近最久未使用页面置换算法（LRU）的基本编程及算法原理。

请求页式管理中的置换算法页式管理是计算机内存管理的一种方式，它利用虚拟内存和分页技术使得操作系统可以在有限的物理内存下运行更多的进程。

在页式存储管理中，操作系统将物理内存分成若干个固定的大小的块，称为物理块，同时将进程分成若干个大小相等的块，称为页面。

当一个进程需要访问某个页面时，操作系统就将页面调入物理块中，若所有物理块都被占满，则需要选择一个物理块将其替换成即将调入的页面，这就需要使用到置换算法。

常见的置换算法有如下几种：1. 先进先出算法（FIFO）该算法是最简单的、最易实现的一种页面置换算法。

其原理是将先进入内存的页面优先替换出去。

使用一个先进先出的队列来维护物理块的使用情况，每次选择队列头的页面进行置换。

因此该算法的缺点就是无法考虑页面替换的实际使用情况。

2. 最近最少使用算法（LRU）该算法会将最近未被使用的页面优先置换出去，即在内存中驻留时间最长的页面最不容易被替换出去。

其难点在于如何确定何时页面被使用过。

可以使用栈或者链表来实现。

3. 最不常用算法（LFU）该算法会将内存中使用次数最少的页面优先置换出去，即在内存中使用次数最少的页面最容易被替换出去。

为实现该算法，需要维护每个页面的使用次数。

4. 时钟算法（Clock）该算法是一种Clock页面置换算法，在物理块使用情况时采用了一个环形链表的结构。

每个页面都有一个标志位，若该位为1，则说明该页面在当前的一轮中被使用过，同时将该位变为0；若该位为0，则说明该页面未被使用过，这时候会考虑是否将该页面替换出去。

5. 二次机会算法（Second chance）该算法对时钟算法进行了改进，增加了一个修改位，表明是否被修改过。

每次选择的是位0(未被使用/未被修改)或者1(未被使用/被修改)的页面，如果选择到的是1则把修改位清零，并转化为0重新加入内存块队列。

以上是常见的五种页面置换算法，不同的算法有各自的优缺点，需要根据内存管理的需要、机器性能和系统配置来选择合适的算法来实现。

实验目地通过模拟实现请求页式存储管理地几种基本页面置换算法，了解虚拟存储技术地特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法地基本思想和实现过程，并比较它们地效率.文档收集自网络，仅用于个人学习实验内容设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率.1、最佳淘汰算法（OPT）2、先进先出地算法（FIFO ）3、最近最久未使用算法（LRU ）4、最不经常使用算法（LFU ）5、最近未使用算法（NUR ）命中率＝１－页面失效次数／页地址流长度实验准备本实验地程序设计基本上按照实验内容进行.即首先用srand（）和rand（）函数定义和产生指令序列，然后将指令序列变换成相应地页地址流，并针对不同地算法计算出相应地命中率.文档收集自网络，仅用于个人学习（1）通过随机数产生一个指令序列，共320 条指令.指令地地址按下述原则生成：A：50%地指令是顺序执行地B：25%地指令是均匀分布在前地址部分C：25%地指令是均匀分布在后地址部分具体地实施方法是：A：在[0，319]地指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1 地指令C：在前地址[0,m+1] 中随机选取一条指令并执行，该指令地地址为m'D：顺序执行一条指令，其地址为m'+1E：在后地址[m'+2，319]中随机选取一条指令并执行F：重复步骤A-E ，直到320 次指令（2）将指令序列变换为页地址流设：页面大小为1K ；用户内存容量 4 页到32 页；用户虚存容量为32K.在用户虚存中，按每K 存放10 条指令排列虚存地址，即320 条指令在虚存中地存放方式为：第0 条-第9 条指令为第0 页（对应虚存地址为[0，9]）第10 条-第19 条指令为第1页（对应虚存地址为[10，19]）第310 条-第319条指令为第31 页（对应虚存地址为[310，319]）按以上方式，用户指令可组成32 页.实验指导一、虚拟存储系统UNIX 中，为了提高内存利用率，提供了内外存进程对换机制；内存空间地分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页地存储管理方式.文档收集自网络，仅用于个人学习当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU 发出缺中断），由系统将其所需页面调入内存.这种页面调入方式叫请求调页.文档收集自网络，仅用于个人学习为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保 护位等 .二、页面置换算法当 CPU 接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处 理程序 .该程序通过查找页表，得到该页所在外存地物理块号 .如果此时内存未满，能容纳新 页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表 .如果内存已满，则须按某种置换 算法从内存中选出一页准备换出， 是否重新写盘由页表地修改位决定， 然后将缺页调入， 修 改页表 .利用修改后地页表，去形成所要访问数据地物理地址，再去访问内存数据 .整个页面地调入过程对用户是透明地 .文档收集自网络，仅用于个人学习 常用地页面置换算法有1、最佳置换算法( Optimal )2、先进先出法( Fisrt In First Out )3、最近最久未使用( Least Recently Used )4、最不经常使用法( Least Frequently Used )5、最近未使用法( No Used Recently )三、参考程序：view plaincopy to clipboardprint?50 ··60·· ··70·····80· ··90 ·100····110 ·· ·120·130 ···140 ····150 文档收集自网络，仅用于个人学习#define TRUE 1 #define FALSE 0 #define INV ALID -1#define NULL 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]; 文档收集自网络，仅用于个人学习int initialize(int);int FIFO(int); int LRU(int); int LFU(int);10· ····20·· ·30··· ·40/* 指令流长 */ /* 虚页长 */ /*清 0周期*/ /* 页面结构 *//* 页面结构数组 */ /* 页面控制结构 */文档收集自网络，仅用于个人学习int NUR(int);int OPT(int);int main( ){int s,i,j;srand(10*getpid()); /* 由于每次运行时进程号不同，故可用来作为初始化随机数队列地“种子” */ 文档收集自网络，仅用于个人学习s=(float)319*rand( )/32767/32767/2+1; // for(i=0;i<total_instruction;i+=4) /* 产生指令队列*/ { if(s<0||s>319){ printf("When i==%d,Error,s==%d\n",i,s); exit(0);}a[i]=s; /* 任选一指令访问点m*/a[i+1]=a[i]+1; /* 顺序执行一条指令*/ a[i+2]=(float)a[i]*rand( )/32767/32767/2; /* 执行前地址指令m' */ 文档收集自网络，仅用于个人学习a[i+3]=a[i+2]+1; /* 顺序执行一条指令*/s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; 文档收集自网络，仅用于个人学习if((a[i+2]>318)||(s>319)) printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s); 文档收集自网络，仅用于个人学习}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---\n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);} return 0;}int initialize(total_pf) int total_pf;人学习/* 初始化相关数据结构*/ 文档收集自网络，仅用于个人学习/* 用户进程地内存页面数*/ 文档收集自网络，仅用于个for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INV ALID){diseffect+=1; if(freepf_head==NULL){p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID;freepf_head=busypf_head; /* 释放忙页面队列地第一个页面 */ freepf_head->next=NULL; busypf_head=p;}p=freepf_head->next;/* 按 FIFO 方式调新页面入内存页面 */freepf_head->next=NULL; freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL){int i; diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INV ALID; pl[i].counter=0; pl[i].time=-1;}/* 置页面控制结构中地页号，页面为空 */ /* 页面控制结构中地访问次数为 0，时间为 -1*/for(i=0;i<total_pf-1;i++){pfc[i].next=&pfc[i+1]; pfc[i].pfn=i; } /* 建立 pfc[i-1] 和 pfc[i] 之间地链接 */pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; return 0;}int FIFO(total_pf) int total_pf;{int i,j; pfc_type *p; initialize(total_pf);/* 空页面队列地头指针为 pfc[0]*//* 先进先出算法 *//* 用户进程地内存页面数 *//* 初始化相关页面控制用数据结构 */busypf_head=busypf_tail=NULL; /* 忙页面队列头，队列尾链接 */ /* 页面失效 *//* 失效次数 */ /* 无空闲页面*/busypf_head=busypf_tail=freepf_head; else {busypf_tail->next=freepf_head; busypf_tail=freepf_head;}freepf_head=p;}elsepl[page[i]].time=present_time;收集自网络，仅用于个人学习}}printf("FIFO:%6.4f\n",1-(float)diseffect/320); return 0;}int 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==INV ALID){diseffect++;if(freepf_head==NULL){/*最近最久未使用算法*//* 页面失效 *//* 无空闲页面 */min=32767;for(j=0;j<total_vp;j++) if(min>pl[j].time&&pl[j].pfn!=INV {/* 找出 time 地最小值 */ALID) min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INV ALID; pl[minj].time=-1;freepf_head->next=NULL;//腾出一个单元}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time; freepf_head=freepf_head->next;//有空闲页面 ,改为有效//减少一个 free 页面/*free 页面减少一个 *///命中则增加该单元地访问次数文档present_time++;}printf("LRU:%6.4f\n",1-(float)diseffect/320); return 0;}int NUR(total_pf) int total_pf;{ int i,j,dp,cont_flag,old_dp; pfc_type *t;initialize(total_pf); dp=0;for(i=0;i<total_instruction;i++) { if (pl[page[i]].pfn==INV ALID) {diseffect++;if(freepf_head==NULL) { cont_flag=TRUE; old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INV cont_flag=FALSE; else{dp++;if(dp==total_vp)dp=0; if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn]; pl[dp].pfn=INV ALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next;}else pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;j<total_vp;j++) pl[j].counter=0;}printf("NUR:%6.4f\n",1-(float)diseffect/320); return 0;/* 最近未使用算法 *//* 页面失效 */ /* 无空闲页面 */ALID)}int OPT(total_pf) /* 最佳置换算法*/ 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++){ //printf("In OPT for//i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278; 学习if(pl[page[i]].pfn==INV ALID) /* 页面失效*/{diseffect++;if(freepf_head==NULL) /* 无空闲页面*/{for(j=0;j<total_vp;j++)if(pl[j].pfn!=INV ALID) dist[j]=32767; /* 最大"距离" */ 习else dist[j]=0;d=1;for(j=i+1;j<total_instruction;j++){if(pl[page[j]].pfn!=INV ALID)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=NULL;pl[maxpage].pfn=INV ALID;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}}printf("OPT:%6.4f\n",1-(float)diseffect/320);return 0;}int LFU(total_pf) /* 最不经常使用置换法*/1,i=%d\n",i);文档收集自网络，仅用于个人文档收集自网络，仅用于个人学int total_pf;{int i,j,min,minpage; pfc_type *t;initialize(total_pf); for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INV ALID)/* 页面失效 */{ diseffect++; if(freepf_head==NULL) /* 无空闲页面 */ { min=32767; for(j=0;j<total_vp;j++) {if(min>pl[j].counter&&pl[j].pfn!=INV ALID){min=pl[j].counter; minpage=j; }pl[j].counter=0;}freepf_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INV ALID; freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn; //有空闲页面 , 改为有效 pl[page[i]].counter++;freepf_head=freepf_head->next;// 减少一个 free 页面}else pl[page[i]].counter++;}printf("LFU:%6.4f\n",1-(float)diseffect/320); return 0;}#define TRUE 1#define FALSE 0 #define INV ALID -1#define NULL 0 #define total_instruction 320 #define total_vp 32 #define clear_period 50typedef 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]; 文档收集自网络，仅用于个人学习int initialize(int); int FIFO(int); int LRU(int);/* 指令流长 */ /* 虚页长 */ /*清0周期*/ /* 页面结构 *//* 页面结构数组 */int LFU(int);int NUR(int);int OPT(int);int main( ){int s,i,j;srand(10*getpid()); /* 由于每次运行时进程号不同，故可用来作为初始化随机数队列地“种子” */ 文档收集自网络，仅用于个人学习s=(float)319*rand( )/32767/32767/2+1; // for(i=0;i<total_instruction;i+=4) /* 产生指令队列*/ {if(s<0||s>319){ printf("When i==%d,Error,s==%d\n",i,s); exit(0);}a[i]=s; /* 任选一指令访问点m*/a[i+1]=a[i]+1; /* 顺序执行一条指令*/ a[i+2]=(float)a[i]*rand( )/32767/32767/2; /* 执行前地址指令m' */ 文档收集自网络，仅用于个人学习a[i+3]=a[i+2]+1; /* 顺序执行一条指令*/s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; 文档收集自网络，仅用于个人学习if((a[i+2]>318)||(s>319))printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s); 文档收集自网络，仅用于个人学习}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---\n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);}return 0;int initialize(total_pf) int total_pf; /*初始化相关数据结构*/ 文档收集自网络，仅用于个人学习/*用户进程地内存页面数*/ 文档收集自网络，仅用于个人学}习{int i;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INV ALID; /* 置页面控制结构中地页号，页面为空*/ pl[i].counter=0;pl[i].time=-1; /* 页面控制结构中地访问次数为0，时间为-1*/ }for(i=0;i<total_pf-1;i++){pfc[i].next=&pfc[i+1];pfc[i].pfn=i;} /* 建立pfc[i-1] 和pfc[i] 之间地链接*/pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0]; return 0;}int FIFO(total_pf)int total_pf;{int i,j;pfc_type *p;initialize(total_pf); /* 空页面队列地头指针为pfc[0]*//* 先进先出算法*//* 用户进程地内存页面数*//* 初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NULL; /* 忙页面队列头，队列尾链接*/ for(i=0;i<total_instruction;i++){/* 页面失效*/if(pl[page[i]].pfn==INV ALID){diseffect+=1; /* 失效次数*/if(freepf_head==NULL) /* 无空闲页面*/{p=busypf_head->next;pl[busypf_head->pn].pfn=INV ALID;freepf_head=busypf_head; /* 释放忙页面队列地第一个页面*/freepf_head->next=NULL;busypf_head=p;}p=freepf_head->next; /* 按FIFO 方式调新页面入内存页面*/freepf_head->next=NULL;freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NULL)busypf_head=busypf_tail=freepf_head;else{ busypf_tail->next=freepf_head; /*free 页面减少一个*/ busypf_tail=freepf_head;} freepf_head=p;}} printf("FIFO:%6.4f\n",1-(float)diseffect/320);return 0;}int 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==INV ALID) {diseffect++;min=32767;/* 页面失效*/if(freepf_head==NULL){/* 无空闲页面*/for(j=0;j<total_vp;j++) /* 找出time 地最小值*/ if(min>pl[j].time&&pl[j].pfn!=INV ALID){min=pl[j].time;minj=j;} freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元pl[minj].pfn=INV ALID;pl[minj].time=-1;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next; }else //有空闲页面,改为有效//减少一个free 页面pl[page[i]].time=present_time; 自网络，仅用于个人学习//命中则增加该单元地访问次数文档收集present_time++;}printf("LRU:%6.4f\n",1-(float)diseffect/320);return 0;}int NUR(total_pf)int total_pf;{ int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i++){ if (pl[page[i]].pfn==INV ALID) {diseffect++;if(freepf_head==NULL){ cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INV cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0; /* 最近未使用算法*//* 页面失效*//* 无空闲页面*/ ALID)if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INV ALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;j<total_vp;j++)pl[j].counter=0;}printf("NUR:%6.4f\n",1-(float)diseffect/320);return 0;}int OPT(total_pf) /* 最佳置换算法*/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++){ //printf("In OPT for 1,i=%d\n",i);//i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278; 文档收集自网络，仅用于个人学习if(pl[page[i]].pfn==INV ALID) /* 页面失效*/{diseffect++;if(freepf_head==NULL) /* 无空闲页面*/{for(j=0;j<total_vp;j++)if(pl[j].pfn!=INV ALID) dist[j]=32767; /* 最大"距离" */ 文档收集自网络，仅用于个人学习elsedist[j]=0;d=1;for(j=i+1;j<total_instruction;j++){if(pl[page[j]].pfn!=INV ALID)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=NULL; pl[maxpage].pfn=INVALID;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}}printf("OPT:%6.4f\n",1-(float)diseffect/320);return 0;}int LFU(total_pf) /* 最不经常使用置换法 */int total_pf;{int i,j,min,minpage;pfc_type *t;initialize(total_pf); for(i=0;i<total_instruction;i++){ if(pl[page[i]].pfn==INV ALID) /* 页面失效 */{ diseffect++;if(freepf_head==NULL) /* 无空闲页面 */{ min=32767; for(j=0;j<total_vp;j++){if(min>pl[j].counter&&pl[j].pfn!=INVALID){min=pl[j].counter;minpage=j;}pl[j].counter=0;}freepf_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INV ALID;freepf_head->next=NULL;}pl[page[i]].pfn=freepf_head->pfn; pl[page[i]].counter++; freepf_head=freepf_head->next;}else pl[page[i]].counter++;} printf("LFU:%6.4f\n",1-(float)diseffect/320);return 0;}五、分析1、从几种算法地命中率看， OPT 最高，其次为 NUR 相对较高，而 FIFO 与LRU 相差无几， 最低地是 LFU. 但每个页面执行结果会有所不同 .文档收集自网络，仅用于个人学习//有空闲页面 , 改为有效// 减少一个 free 页面2、OPT 算法在执行过程中可能会发生错误五、思考1、为什么OPT 在执行时会有错误产生？本文来自CSDN 博客，转载请标明出处：/followingturing/archive/2010/12/22/6091196.aspx 文档收集自网络，仅用于个人学习版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理。

操作系统课程设计报告题目：页面置换算法院系：班级：姓名学号：指导教师页面置换算法设计报告一、概述通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

二、设计的基本概念和原理基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。

1、基本概念1、先进先出的算法（FIFO）2、最近最久未使用算法（L R U）3、缺页次数：置换页面的次数4、缺页率=置换页面的次数/总页面2、基本原理1、先进先出的算法（FIFO）：优先淘汰最早进入的页面，亦即在内存中驻留时间最久的页面。

2、最近最久未使用算法（L R U）：选择最近最长时间未访问过的页面予以淘汰。

三、总体设计数据结构：const int DataMax=100;const int BlockNum = 10;int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示int Data[DataMax]; // 保存数据int Block[BlockNum]; // 物理块int count[BlockNum]; // 计数器int N ; // 页面个数int M;//最小物理块数int ChangeTimes;void DataInput(); // 输入数据的函数void DataOutput();void FIFO(); // FIFO 函数void LRU(); // LRU函数算法流程：(1)请输入最小物理块数(2)请输入页面的个数(3)请输入页面访问序列：(4)菜单选择算法流程图：开始输入N、M、data[n]选择算法输出结果结束四、详细设计#include <iostream>#include <fstream>using namespace std;const int DataMax=100;const int BlockNum = 10;int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示int Data[DataMax]; // 保存数据int Block[BlockNum]; // 物理块int count[BlockNum]; // 计数器int N ; // 页面个数int M;//最小物理块数int ChangeTimes;void DataInput(); // 输入数据的函数void DataOutput();void FIFO(); // FIFO 函数void LRU(); // LRU函数///*int main(){DataInput();int menu;while(true){cout<<"* 菜单选择*"<<endl;cout<<"*******************************************************"<<endl ;cout<<"* 1-FIFO *"<<endl;cout<<"* 2-LRU *"<<endl;cout<<"* 0-EXIT *"<<endl;cout<<"*******************************************************"<<endl ;cin>>menu;switch(menu){case 1:FIFO();break;case 2:LRU();break;default:break;}if(menu!=1&&menu!=2&&menu!=3) break;}}//*/void DataInput(){ifstream myfile ("a.txt");if(!myfile){cout << "Unable to open myfile";}cout<<"请输入最小物理块数：";myfile>>M;cout<<"请输入页面的个数：";myfile>>N;cout<<"请输入页面访问序列："<<endl;for(int i=0; i<N; i++)myfile>>Data[i];}void DataOutput(){int i,j;for(i=0; i<N; i++) // 对所有数据操作{cout<<Data[i]<<" ";}cout<<endl;for(j=0; j<M; j++){cout<<" ";for(i=0; i<N; i++) // 对所有数据操作{if( DataShowEnable[j][i] )cout<<DataShow[j][i]<<" ";elsecout<<" ";}cout<<endl;}cout<<"缺页次数: "<<ChangeTimes<<endl;cout<<"缺页率: "<<ChangeTimes*100/N<<"%"<<endl;}void FIFO(){int i,j;bool find;int point;int temp; // 临时变量ChangeTimes = 0;for(j=0; j<M; j++){for(i=0; i<N; i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据DataShow[j][i]=-1;}Block[j]=-1;}for(i=0; i<M; i++){count[i] = 0;}for(i=0; i<N; i++) // 对有所数据操作{// 增加countfor(j=0; j<M; j++){count[j]++;cout<<count[j]<<" ";}cout<<endl;find = false; // 表示块中有没有该数据for(j=0; j<M; j++){if( Block[j] == Data[i] ){find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据ChangeTimes++; // 缺页次数++if( (i+1) > M ) // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1{//获得要替换的块指针temp = 0;for(j=0; j<M; j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0; // 更新计数值// 保存要显示的数据for(j=0; j<M; j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"FIFO => "<< endl;DataOutput();}void LRU(){int i,j;bool find;int point;int temp; // 临时变量ChangeTimes = 0;for(j=0; j<M; j++){for(i=0; i<N; i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据DataShow[j][i]=-1;}Block[j]=-1;} // 初始化为false，表示没有要显示的数据for(i=0; i<M; i++){count[i] = 0 ;}for(i=0; i<N; i++) // 对有所数据操作{// 增加countfor(j=0; j<M; j++)count[j]++;find = false; // 表示块中有没有该数据for(j=0; j<M; j++){if( Block[j] == Data[i] ){count[j] = 0;find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据ChangeTimes++; // 缺页次数++if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1{//获得要替换的块指针temp = 0;for(j=0; j<M; j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0;// 保存要显示的数据for(j=0; j<M; j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"LRU => "<< endl;DataOutput();}五、测试与数据分析测试数据：3207 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1六、完成的情况、简要的使用说明完成情况：编写了先进先出的算法（FIFO）、最近最久未使用算法（L R U），得到了正确的结果使用说明：根据提示输入数据，可以得到书上的结果。

页面置换算法一、实验目的1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。

2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。

3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。

二、实验内容：设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）三、实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。

但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。

一个好的页面置换算法，应该有较低的页面更换频率。

假设分给一作业的物理块数为3 ，页面数为20个。

页面号为(20个)：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，11．先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。

2．最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。

3.最佳（OPT）置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。

4．数据结构structpageInfor{int content;//页面号int timer;//被访问标记};class PRA{public:PRA(void);intfindSpace(void); //查找是否有空闲内存intfindExist(intcurpage); //查找内存中是否有该页面intfindReplace(void); //查找应予置换的页面void display(void); //显示void FIFO(void); //FIFO算法void LRU(void); //LRU算法void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示pageInfor * block; //物理块pageInfor * page; //页面号串private:};四、源程序结构分析1．源程序代码#include <iostream.h>#define Bsize 3#define Psize 20structpageInfor{int content;//页面号int timer;//被访问标记};class PRA{public:PRA(void);intfindSpace(void);//查找是否有空闲内存intfindExist(intcurpage);//查找内存中是否有该页面intfindReplace(void);//查找应予置换的页面void display(void);//显示void FIFO(void);//FIFO算法void LRU(void);//LRU算法void Optimal(void);//OPTIMAL算法void BlockClear(void);//BLOCK恢复pageInfor * block;//物理块pageInfor * page;//页面号串private:};PRA::PRA(void){intQString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};block = new pageInfor[Bsize];for(int i=0; i<Bsize; i++){block[i].content = -1;block[i].timer = 0;}page = new pageInfor[Psize];for(i=0; i<Psize; i++){page[i].content = QString[i];page[i].timer = 0;}}int PRA::findSpace(void){for(int i=0; i<Bsize; i++)if(block[i].content == -1)return i;//找到空闲内存，返回BLOCK中位置return -1;}int PRA::findExist(intcurpage){for(int i=0; i<Bsize; i++)if(block[i].content == page[curpage].content)return i;//找到内存中有该页面，返回BLOCK中位置return -1;}int PRA::findReplace(void){intpos = 0;for(int i=0; i<Bsize; i++)if(block[i].timer >= block[pos].timer)pos = i;//找到应予置换页面，返回BLOCK中位置returnpos;}void PRA::display(void){for(int i=0; i<Bsize; i++)if(block[i].content != -1)cout<<block[i].content<<" ";cout<<endl;}void PRA::Optimal(void){intexist,space,position ;for(int i=0; i<Psize; i++){exist = findExist(i);if(exist != -1){ cout<<"不缺页"<<endl; }else{space = findSpace();if(space != -1){block[space] = page[i];display();}else{for(int k=0; k<Bsize; k++)for(int j=i; j<Psize; j++){if(block[k].content != page[j].content){ block[k].timer = 1000; }//将来不会用，设置TIMER为一个很大数else{block[k].timer = j;break;}}position = findReplace();block[position] = page[i];display();}}}}void PRA::LRU(void){intexist,space,position ;for(int i=0; i<Psize; i++){exist = findExist(i);if(exist != -1){cout<<"不缺页"<<endl;block[exist].timer = -1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1 }else{space = findSpace();if(space != -1){block[space] = page[i];display();}else{position = findReplace();block[position] = page[i];display();}}for(int j=0; j<Bsize; j++)block[j].timer++;}}void PRA::FIFO(void){intexist,space,position ;for(int i=0; i<Psize; i++){exist = findExist(i);if(exist != -1){cout<<"不缺页"<<endl;}else{space = findSpace();if(space != -1){block[space] = page[i];display();}else{position = findReplace();block[position] = page[i];display();}}for(int j=0; j<Bsize; j++)block[j].timer++;//BLOCK中所有页面TIMER++ }}void PRA::BlockClear(void){for(int i=0; i<Bsize; i++){block[i].content = -1;block[i].timer = 0;}}void main(void){cout<<"|----------页面置换算法----------|"<<endl;cout<<"|---power by wangxinchuang(080501228)---|"<<endl;cout<<"|-------------------------------------|"<<endl;cout<<"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"<<endl; cout<<"----------------------------------------------------"<<endl;cout<<"选择<1>应用Optimal算法"<<endl;cout<<"选择<2>应用FIFO算法"<<endl;cout<<"选择<3>应用LRU算法"<<endl;cout<<"选择<0>退出"<<endl;int select;PRA test;while(select){cin>>select;switch(select){case 0:break;case 1:cout<<"Optimal算法结果如下:"<<endl;test.Optimal();test.BlockClear();cout<<"----------------------"<<endl;break;case 2:cout<<"FIFO算法结果如下:"<<endl;test.FIFO();test.BlockClear();cout<<"----------------------"<<endl;break;case 3:cout<<"LRU算法结果如下:"<<endl;test.LRU();test.BlockClear();cout<<"----------------------"<<endl;break;default:cout<<"请输入正确功能号"<<endl; break;}}}五、实验结果1运行后的初始界面2 opt3.FIFO算法4LRU算法。

课程设计名称：操作系统题目：页式存储管理中页面置换（淘汰）的模拟程序目录一、概述 (3)1.1目的 (3)1.2主要完成的任务 (3)1.3使用的开发工具 (3)1.4解决的主要问题 (4)二、基本概念和原理 (4)2.1概念 (4)2.2原理 (4)三、总体设计 (5)四、详细设计 (6)4.1 要利用的线程操作的函数 (6)4.2使用的函数变量及解释 (7)4.3 各个页面置换算法 (8)五、编码设计 (9)5.1 开发环境的设置和建立 (9)5.2程序设计时需要注意的问题 (9)5.3 主要程序的代码设计及注释 (10)5.4 解决的技术难点、经常犯的错误 (22)六、测试时出现的问题及解决方法 (22)七、软件使用说明 (22)7.1 基本功能 (22)7.2 需要运行的环境 (23)7.3 安装 (23)7.4 运行 (23)7.5 操作 (24)八、总结 (25)8.1完成的功能 (25)8.2 自我评定 (25)8.3 收获、经验、教训和感受 (25)九、参考文献 (26)页式存储管理中页面置换（淘汰）的模拟程序一．概述1.1目的（1）通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点。

（2）通过创建线程以及初始化线程来掌握实现几个线程同时进行某种操作的方法。

（3）重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法（如FIFO算法、LRU算法、LFU算法、OPT算法）的原理和实现过程。

（4）掌握页面置换时缺页中断与不缺页中断时每个页面进行存取时的时间的计算方法，包括一个页面序列进行存取的总时间与存取每个页面的平均时间。

（5）熟悉使用VC++ 6.0进行有界面的编程的方法。

1.2.主要完成的任务通过使用程序设计语言设计一个程序，模拟页式存储管理中FIFO、LRU、LFU、OPT四页面置换算法运行的过程。

基本要求如下：（1）采用四个线程同时完成每个算法；（2）能够设定驻留内存页面的个数、内存的存取时间、缺页中断的时间、快表的时间，并提供省缺值；（3）能够随机输入存取的逻辑页面的页号序列；（4）能够随机产生存取的逻辑页面的页号序列；（5）能够设定页号序列中页面个数和范围；（6）提供良好图形界面，同时能够展示四个算法运行的结果。

湖南科技学院计算机与信息科学系实验报告实验名称请求页式存储管理中常用页面置换算法模拟课程名称计算机操作系统所属系部班级计科0902时间2011年12地E305月8日第3,4节点姓名姜泽政学号200908001217成绩本组成员（一人一组）一、实验要求1、熟练掌握页面请求算法的原理；2、熟练掌握页面置换算法的思路；3、上机前编写程序源码；4、上机后，写好实验报告和实验结果，实验报告交任课教师。

二、实验目的页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。

本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解三、实验环境每人一台电脑，在下实现。

四、实验内容及过程（1）设计程序实现以上三种页面调度算法，要求：①.可以选择页面调度算法类型；②.可以为进程设置分到物理页的数目，设置进程的页面引用情况，可以从键盘输入页面序列，也可从文件中读取；③.随时计算当前的页面调度次数的缺页中断率；④.使用敲键盘或响应WM-TIMER的形式模仿时间的流逝；⑤.以直观的的形式将程序的执行情况显示在计算机屏幕上；⑥.存盘及读盘功能，可以随时将数据存入磁盘文件，供以后重复实验时使用。

（2）假定进程分配到3个物理块，对于下面的页面引用序列：7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1请分别用先进和先出调度算法，最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。

再假定进程分配到4、5个物理块，重复本实验。

（3）假定进程分配到3个物理块，对于下面的页面引用序列：4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9请分别用先进先出调度算法、最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。

操作系统实验(四)实验报告--虚拟内存操作系统实验（四）虚拟内存1、实验题目页面置换算法模拟——OPT、FIFO和LRU算法2、实验目的了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法，如最佳（Optimal）置换算法、先进先出（Fisrt In First Out）置换算法和最近最久未使用（Least Recently Used）置换算法3、实验内容1）OPT算法：需要发生页面置换时，算法总是选择在将来最不可能访问的页面进行置换。

2）FIFO算法：算法总是选择在队列中等待时间最长的页面进行置换。

3）LRU算法：如果某一个页面被访问了，它很可能还要被访问；相反，如果它长时间不被访问，那么，在最近未来是不大可能被访问的。

4、程序代码#include<iostream>#include <cstdlib>#include <time.h>#include <cstdio>#define L 30///页面走向长度最大为30using namespace std;int M=4; ///内存块struct P///定义一个结构体{int num,time;}p[30];int Input(int m,P p[L])///打印页面走向状态{m=30;int i,j;j=time(NULL);///取时钟时间srand(j);///以时钟时间x为种子，初始化随机数发生器cout<<"页面走向: ";for(i=0; i<m; i++){p[i].num=rand( )%10;///产生1到10之间的随即数放到数组p中p[i].time=0;cout<<p[i].num<<" ";}cout<<endl;return m;}void print(P *page1)///打印当前的页面{P *page=new P[M];page=page1;for(int i=0; i<M; i++)cout<<page[i].num<<" ";cout<<endl;}int Search(int e,P *page1 )///寻找内存块中与e相同的块号{P *page=new P[M];page=page1;for(int i=0; i<M; i++)if(e==page[i].num)return i; ///返回i值return -1;}int Max(P *page1)///寻找最近最长未使用的页面用于OPT算法{P *page=new P[M];page=page1;int e=page[0].time,i=0;while(i<M) ///找出离现在时间最长的页面{if(e<page[i].time) e=page[i].time;i++;}for( i=0; i<M; i++)if(e==page[i].time)return i; ///找到离现在时间最长的页面返回其块号return -1;}int Count(P *page1,int i,int t,P p[L])///记录当前内存块中页面离下次使用间隔长度用于OPT算法{P *page=new P[M];page=page1;int count=0;for(int j=i; j<L; j++){if(page[t].num==p[j].num )break;///当前页面再次被访问时循环结束else count++;///否则count+1}return count;///返回count的值}int main(){int c=1;int m=0,t=0;float n=0;///缺页次数m=Input(m,p);///调用input函数，返回m值M=4;P *page=new P[M];///dowhile(c==1||c==2||c==3){int i=0;for(i=0; i<M; i++) ///初试化页面基本情况{page[i].num=0;page[i].time=m-1-i;}cout<<"1:FIFO页面置换"<<endl;cout<<"2:LRU页面置换"<<endl;cout<<"3:OPT页面置换"<<endl;cout<<"按其它键结束程序；"<<endl;cin>>c;if(c==1)///FIFO页面置换///FIFO();{n=0;cout<<" FIFO算法页面置换情况如下: "<<endl;cout<<endl;while(i<m){if(Search(p[i].num,page)>=0) ///当前页面在内存中{cout<<p[i].num<<" "; ///输出当前页p[i].numcout<<" "<<endl;i++; ///i加1}else ///当前页不在内存中{if(t==M)t=0;else{n++; ///缺页次数加1page[t].num=p[i].num; ///把当前页面放入内存中cout<<p[i].num<<" ";print(page); ///打印当前页面t++; //下一个内存块i++; ///指向下一个页面}}}cout<<"缺页次数："<<n<<" 缺页率："<<n<<"/"<<m<<" ="<<n/m<<endl;}if(c==2)///LRU页面置换,最近最久未使用{n=0;cout<<" LRU算法页面置换情况如下: "<<endl;cout<<endl;while(i<m){int a;t=Search(p[i].num,page);if(t>=0)///如果已在内存块中{page[t].time=0;///把与它相同的内存块的时间置0for(a=0; a<M; a++)if(a!=t)page[a].time++;///其它的时间加1cout<<p[i].num<<" ";cout<<"不缺页"<<endl;}else ///如果不在内存块中{n++; ///缺页次数加1t=Max(page); ///返回最近最久未使用的块号赋值给tpage[t].num=p[i].num; ///进行替换page[t].time=0; ///替换后时间置为0cout<<p[i].num<<" ";print(page);for(a=0; a<M; a++)if(a!=t)page[a].time++; ///其它的时间加1}i++;}cout<<"缺页次数："<<n<<" 缺页率："<<n<<"/"<<m<<" = "<<n/m<<endl;}if(c==3)///OPT页面置换{n=0;cout<<" OPT算法置换情况如下:"<<endl;cout<<endl;while(i<m){if(Search(p[i].num,page)>=0)///如果已在内存块中{cout<<p[i].num<<" ";cout<<" "<<endl;i++;}else///如果不在内存块中{int a=0;for(t=0; t<M; t++)if(page[t].num==0)a++;///记录空的内存块数if(a!=0) ///有空内存块{int q=M;for(t=0; t<M; t++)if(page[t].num==0&&q>t)q=t;///把空内存块中块号最小的找出来page[q].num=p[i].num;///把缺页换过来n++; ///缺页次数加一cout<<p[i].num<<" ";print(page);i++;}else{int temp=0,s;for(t=0; t<M; t++) ///寻找内存块中下次使用离现在最久的页面if(temp<Count(page,i,t,p)){temp=Count(page,i,t,p);s=t;}///把找到的块号赋给spage[s].num=p[i].num;n++;cout<<p[i].num<<" ";print(page);i++;}}}cout<<"缺页次数："<<n<<" 缺页率："<<n<<"/"<<m<<" = "<<n/m<<endl;}}///while(c==1||c==2||c==3);return 0;}5、心得体会通过该实验，是我对虚拟内存更加了解，对最佳置换算法、先进先出算法、最近最久算法更加了解。

实验七请求页式存储管理中常用页面置换算法模拟实验学时：4实验类型：设计实验要求：必修一、实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。

（5）了解页面大小和内存实际容量对命中率的影响。

二、实验内容（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；（2）实现OPT 算法(最优置换算法) 、LRU 算法(Least Recently) 、FIFO 算法(First IN First Out)的模拟；（3）会使用某种编程语言。

三、实验原理分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。

但应将哪个页面调出，须根据一定的算法来确定。

通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。

一个好的页面置换算法，应具有较低的页面更换频率。

从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。

1、最佳置换算法OPT(Optimal)它是由Belady于1966年提出的一种理论上的算法。

其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。

采用最佳置换算法，通常可保证获得最低的缺页率。

但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。

2、先进先出(FIFO)页面置换算法这是最早出现的置换算法。

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

实验3请求调页存储管理方式的模拟1实验目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。

2实验内容（1）假设每个页面中可存放10条指令，分配给一作业的内存块数为4。

（2）模拟一作业的执行过程。

该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。

在模拟过程中，如果所访问的指令已经在内存中，则显示其物理地址，并转下一条指令。

如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。

如果4个内存块中均已装入该作业，则需进行页面置换。

最后显示其物理地址，并转下一条指令。

在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。

（3）置换算法：请分别考虑OPT、FIFO和LRU算法。

（4）作业中指令的访问次序按下述原则生成：•50%的指令是顺序执行的。

•25%的指令是均匀分布在前地址部分。

•25%的指令时均匀分布在后地址部分。

代码：package mainDart;import java.util.ArrayList;import java.util.List;import java.util.Random;public class FIFO {private static int times=0;//记录置换内存页面的次数/*** 随机产生0~319之间的数* 产生320条指令** @return 包含320条指令的数组*/public static int[] productNumber(){int order[] = new int[320];//数组存储的数字表示指令Random rand = new Random();for(int i=0;i<320;i++){if(i%4==0){order[i]=rand.nextInt(319); //0<=order<319}else if(i%4==1){order[i]=order[i-1]+1;//1<=order<320}else if(i%4==2){order[i]= rand.nextInt(order[i-1]);}else if(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}return order;}/*** 打印链表* @param list*/public static void printList(List<Integer> list){for(int temt:list){System.out.print(temt+"\t");}System.out.println();}/*** 先进先出算法* 总是淘汰最先进入内存的页面* 在实现的时候，记录上一次所替换的页面在内存的下标，则本次要替换的位置就是上次下标+1的位置，并且下标是0~3循环的* @param memoryNum* @param page*/public static void FIFOChangePage(List<Integer> memoryNum,int page){int index = FIFOChangePage(memoryNum,page,++times);memoryNum.remove(index);memoryNum.add(index, page);}/*** 返回本次替换的页面在内存中的位置* @param memoryNum* @param page* @param times记录替换页面的次数，第一次替换的是内存第0个单元* @return*/public static int FIFOChangePage(List<Integer> memoryNum,int page,int times) {if(times==1){return 0;}int index = (FIFOChangePage(memoryNum,page,times-1)+1)%4;return index;}public static void main(String[] args) {int[] order = productNumber();System.out.println("320条随机指令数：");for(int i =0;i<order.length;i++){System.out.print(order[i]+"\t");if((i+1)%10==0){System.out.println();}}List<Integer> memoryNum= new ArrayList<Integer>(4);//内存块存储的页面int count=0;//记录缺页次数for(int i=0;i<320;i++){int page = order[i]/10;if(memoryNum.contains(page)) //若该指令所在页面已经在内存，输出该页面所在内存块的号{}else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()<4) //内存没满，直接将所需页面调入内存{memoryNum.add(page);}else//内存存满，需要调用页面置换算法，进行页面置换{FIFOChangePage(memoryNum,page);//先进先出算法}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println("缺页率："+(double)count/320);}}package mainDart;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Random;public class LRU {/*** 随机产生0~319之间的数* 产生320条指令** @return 包含320条指令的数组*/public static int[] productNumber(){int order[] = new int[320];//数组存储的数字表示指令Random rand = new Random();for(int i=0;i<320;i++){if(i%4==0){order[i]=rand.nextInt(319); //0<=order<319}else if(i%4==1){order[i]=order[i-1]+1;//1<=order<320}else if(i%4==2){order[i]= rand.nextInt(order[i-1]);}else if(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}return order;}/*** 打印链表* @param list*/public static void printList(List<Integer> list){for(int temt:list){System.out.print(temt+"\t");}System.out.println();}/*** 最近最久未使用算法* @param order*/public static void LRUChangePage(int [] order){List<Integer> memoryNum = new ArrayList<Integer>(4);//内存块int[] timeFlag =new int[]{-1,-1,-1,-1}; //用来记录内存当中各单元未被访问的时间值int count=0;//记录缺页次数for(int i=0;i<320;i++){int page = order[i]/10;if(memoryNum.contains(page)) //若该指令所在页面已经在内存{int index = memoryNum.indexOf(page);timeFlag[index]=0;//将时间变为0 }else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()<4) //内存没满，直接将所需页面调入内存{//将没有命中的所有页面的时间加一for(int in=0;in<4;in++){if(timeFlag[in]!=-1){timeFlag[in]+=1;}}//将page加入内存并将时间置为0memoryNum.add(page);timeFlag[memoryNum.indexOf(page)]=0;}else//内存存满，需要调用页面置换算法，进行页面置换{int maxIn=-1;//记录拥有最大时间值的标记的下标int maxT=-1;//记录最大的时间值for(int in=0;in<4;in++)//找出内存中时间值最大的进行替换{if(timeFlag[in]>maxT){maxT=timeFlag[in];maxIn=in;}}memoryNum.remove(maxIn);memoryNum.add(maxIn,page);timeFlag[maxIn]=0;//将没有命中的所有页面的时间加一for(int in=0;in<4;in++){if(in!=maxIn){timeFlag[in]+=1;}}}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println("缺页率："+(double)count/320);}public static void main(String[] args) {int[] order = productNumber();System.out.println("320条随机指令数：");for(int i =0;i<order.length;i++){System.out.print(order[i]+"\t");if((i+1)%10==0){System.out.println();}}LRUChangePage(order);}}package mainDart;import java.util.ArrayList;import java.util.List;import java.util.Random;public class Optimal {/*** 随机产生0~319之间的数* 产生320条指令** @return 包含320条指令的数组*/public static int[] productNumber(){int order[] = new int[320];//数组存储的数字表示指令Random rand = new Random();for(int i=0;i<320;i++){if(i%4==0){order[i]=rand.nextInt(319); //0<=order<319}else if(i%4==1){order[i]=order[i-1]+1;//1<=order<320}else if(i%4==2){order[i]= rand.nextInt(order[i-1]);}else if(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}return order;}/**** @param order320条指令数组* @return 返回一个链表，依次保存着320条指令每条指令所在的页面*/public static List<Integer> pageSeq(int[] order){List<Integer> pageSeq = new ArrayList<Integer>();for(int temp:order){pageSeq.add(temp/10);}return pageSeq;}/*** 打印链表* @param list*/public static void printList(List<Integer> list){for(int temt:list){System.out.print(temt+"\t");}System.out.println();}/*** 最佳置换算法* 根据当前已经在内存中的页面在之后被需要的先后进行置换** @param pageSeq 整个320条指令，从头到尾所需要的页面* @param memoryNum 已满的内存空间* @param page等待被调入内存的页面*/public static void OptimalChangePage(List<Integer> pageSeq,int start,List<Integer> memoryNum,int page){int maxSeq=-1,index=0;for(int pageNum:memoryNum) //遍历内存{for(int i=start;i<pageSeq.size();i++){if(pageNum==pageSeq.get(i)){if(i>maxSeq){maxSeq=i;}break;}}}if(maxSeq>-1)//maxSeq==-1说明内存当中的四个页面在将来都不会再被使用，这时默认将内存块中的第一个页面置换出{index = memoryNum.indexOf(pageSeq.get(maxSeq));//记录将要被置换的那个页面所在内存位置}memoryNum.remove(index);//将内存中将来最久被使用的页面删除memoryNum.add(index, page);//将需要调入的页面加入内存}public static void main(String[] args) {int[] order = productNumber();System.out.println("320条随机指令数：");for(int i =0;i<order.length;i++){System.out.print(order[i]+"\t");if((i+1)%10==0){System.out.println();}}List<Integer> pageSeq = pageSeq(order); //依次存放着指令所在的页面号List<Integer> memoryNum= new ArrayList<Integer>(4);//内存块存储的页面int count=0;//记录缺页次数for(int i=0;i<320;i++){int page = order[i]/10;if(memoryNum.contains(page)) //若该指令所在页面已经在内存，输出该页面所在内存块的号{}else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()<4) //内存没满，直接将所需页面调入内存{memoryNum.add(page);}else//内存存满，需要调用页面置换算法，进行页面置换{OptimalChangePage(pageSeq,i+1,memoryNum,page);//最佳置换算法}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println("缺页率："+(double)count/320);}}package mainDart;import java.util.ArrayList;import java.util.List;public class TestAPP {public static void main(String[] args) {List<Integer> list = new ArrayList<Integer>();list.add(1);list.add(3);list.add(45);System.out.println(list);list.remove(1);list.add(1, -1);System.out.println(list);}}。