页面置换算法实验(内含完整代码)

实验编号４名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便：1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区，并使用FIFO和LRU算法计算访问命中率。

<程序设计>先用srand()函数和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。

<程序1>#include <windows.h> //Windows版，随机函数需要，GetCurrentProcessId()需要//#include <stdlib.h>//Linux版，随机函数srand和rand需要#include <stdio.h> //printf()需要#define TRUE 1#define FALSE 0#define INV ALID -1#define NULL 0#define total_instruction 320 //共320条指令#define total_vp 32 //虚存页共32页#define clear_period 50 //访问次数清零周期typedef struct{//定义页表结构类型〔页面映射表PMT〕int pn, pfn, counter, time;//页号、页框号(块号)、一个周期内访问该页面的次数、访问时间}PMT;PMT pmt[32];typedef struct pfc_struct{//页面控制结构int pn, pfn;struct pfc_struct *next;}pfc_type;pfc_type pfc[32];pfc_type *freepf_head,*busypf_head,*busypf_tail;//空闲页头指针，忙页头指针，忙页尾指针int NoPageCount; //缺页次数int a[total_instruction];//指令流数组int page[total_instruction], offset[total_instruction];//每条指令的页和页内偏移void initialize( int );void FIFO( int );//先进先出void LRU( int );//最近最久未使用void NRU( int );//最近最不经常使用/****************************************************************************main()*****************************************************************************/ void main(){int i,s;//srand(10*getpid());//用进程号作为初始化随机数队列的种子//Linux版srand(10*GetCurrentProcessId());//用进程号作为初始化随机数的种子//Windows版s=rand()%320;//在[0，319]的指令地址之间随机选取一起点mfor(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。

实验7页面置换算法的模拟实现三、实验内容与步骤1、定义相关数据#define InitPysiBlocks 4#define MaxPages 16：unsigned int PysicalBlocks[InitPysiBlocks] = { 0 };unsigned int PageSequence[30] = { 1,2,3,6,4,7,3,2,1,4,7,5,6,5,2,1};2、按照教材中FIFO、LRU算法描述进行算法设计unsigned FIFO(unsigned *py,unsigned *pg)unsigned LRU(unsigned *py,unsigned *pg)3、查看运行结果是否与手工计算一致。

四、实验材料的提交与成绩评定1.代码：#include<iostream>usingnamespace std;#define InitPysiBlocks 4#define MaxPages 16unsignedint PysicalBlocks[InitPysiBlocks] = { 0 };unsignedint PageSequence[30] = { 1,2,3,6,4,7,3,2,1,4,7,5,6,5,2,1 };//FIFO算法unsigned FIFO(unsigned *py, unsigned *pg){//初始化填满数据for (int i = 0; i <InitPysiBlocks; i++){py[i] = pg[i];}cout <<"FIFO置换过程如下："<< endl;cout <<py[0] <<" "<<py[1] <<" "<<py[2] <<" "<<py[3] << endl;//判断新获取数据进来的时间int time[4] = { 3,2,1,0 };//开始检测for (int i = 4; i <MaxPages; i++){for (int j = 0; j <InitPysiBlocks; j++){//如果新获取的已存在，直接输出if (py[0] == pg[i] || py[1] == pg[i] || py[2] == pg[i] || py[3] == pg[i]){cout <<py[0] <<" "<<py[1] <<" "<<py[2] <<" "<<py[3] << endl;break;}else{for (int k = 0; k < 4; k++){if (time[k] == 3){time[k] = 0;py[k] = pg[i];}else{time[k]++;}}cout <<py[0] <<" "<<py[1] <<" "<<py[2] <<" "<<py[3] << endl;break;}}}cout <<"置换结束"<< endl;return 0;}//LRU算法//LRU辅助函数:返回除某一排下标后数组中最大元素下标int Max(unsigned *py, int te){int max = 0;int index = -1;for (int i = 0; i <InitPysiBlocks; i++){if (i == te){continue;}else{if (py[i] > max){max = py[i];index = i;}else{continue;}}}return index;}unsigned LRU(unsigned *py, unsigned *pg){//初始化填满数据for (int i = 0; i <InitPysiBlocks; i++){py[i] = pg[i];}cout <<"LRU置换过程如下："<< endl;cout <<py[0] <<" "<<py[1] <<" "<<py[2] <<" "<<py[3] << endl;//判断新获取数据进来的时间unsigned time[4] = { 3,2,1,0 };//统计命中次数int count[4] = { 0 };//开始检测for (int i = InitPysiBlocks; i < 16; i++){for (int j = 0; j <InitPysiBlocks; j++){//如果新获取的已存在，直接输出,并将对应的命中变为1if (py[0] == pg[i] || py[1] == pg[i] || py[2] == pg[i] || py[3] == pg[i]){cout <<py[0] <<" "<<py[1] <<" "<<py[2] <<" "<<py[3] << endl;if (py[0] == pg[i]){count[0] = 1;}elseif (py[1] == pg[i]){count[1] = 1;}elseif (py[2] == pg[i]){count[2] = 1;}elseif (py[3] == pg[i]){count[3] = 1;}else{count[4] = { 0 };}break;}else{if (count[0] == 1){//返回数组中最大值int temp = Max(time, 0);py[temp] = pg[i];for (int k = 0; k <InitPysiBlocks; k++){time[k]++;}time[temp] = 0;count[0] = 0;}elseif (count[1] == 1){//返回数组中最大值int temp = Max(time, 1);py[temp] = pg[i];for (int k = 0; k <InitPysiBlocks; k++){time[k]++;}time[temp] = 0;count[1] = 0;}elseif (count[2] == 1){//返回数组中最大值int temp = Max(time, 2);py[temp] = pg[i];for (int k = 0; k <InitPysiBlocks; k++){time[k]++;}time[temp] = 0;count[2] = 0;}elseif (count[3] == 1){//返回数组中最大值int temp = Max(time, 3);py[temp] = pg[i];for (int k = 0; k <InitPysiBlocks; k++){time[k]++;}time[temp] = 0;count[3] = 0;}else{//返回数组中最大值int temp = Max(time, -1);py[temp] = pg[i];for (int k = 0; k <InitPysiBlocks; k++){time[k]++;}time[temp] = 0;}cout <<py[0] <<" "<<py[1] <<" "<<py[2] <<" "<<py[3] << endl;break;}}}cout <<"置换结束"<< endl;return 0;}int main(){FIFO(PysicalBlocks, PageSequence);LRU(PysicalBlocks, PageSequence);return 0;}2.运行截图：运行结果与手工计算结果一致。

实验三实验报告实验源码：#include "stdio.h"#include <iostream.h>#include <stdlib.h>#define DataMax 100 // 常量DataMax#define BlockNum 10 // 常量BlockNumint 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 Optimal(); // Optimal函数void LRU(); // LRU函数int main(int argc, char* argv[]){DataInput();int menu;while(true){printf("\n* 菜单选择 *\n");printf("*******************************************************\n");printf("* 1-Optimal *\n");printf("* 2-FIFO *\n");printf("* 3-LRU *\n");printf("* 4-返回上一级 *\n");printf("* 0-EXIT *\n");printf("*******************************************************\n");scanf("%d",&menu);switch(menu){case 1:Optimal();break;case 2:FIFO();break;case 3:LRU();break;case 0:exit(0);break;case 4:system("cls");DataInput();break;}if(menu != 1 && menu != 2 && menu != 3 && menu != 0 && menu !=4) { system("cls");printf("\n请输入0 - 4之间的整数！\n");continue;}}return 0;}void DataInput(){int i,choice;printf("请输入最小物理块数：");scanf("%d",&M);// 输入最小物理块数大于数据个数while(M > BlockNum){printf("物理块数超过预定值，请重新输入：");scanf("%d",&M);}printf("请输入页面的个数：");scanf("%d",&N);// 输入页面的个数大于数据个数while(N > DataMax){printf("页面个数超过预定值，请重新输入：");scanf("%d",&N);}printf("请选择产生页面访问序列的方式(1.随机 2.输入)：");scanf("%d",&choice);switch(choice){case 1:// 产生随机访问序列for(i = 0;i < N;i++){Data[i] = (int)(((float) rand() / 32767) * 10); // 随机数大小在0 - 9之间}system("cls");// 显示随机产生的访问序列printf("\n随机产生的访问序列为：");for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");break;case 2:// 输入访问序列printf("请输入页面访问序列：\n");for(i = 0;i < N;i++)scanf("%d",&Data[i]);system("cls");// 显示输入的访问序列printf("\n输入的访问序列为：");for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");break;default:while(choice != 1 && choice != 2){printf("请输入1或2选择相应方式:");scanf("%d",&choice);}break;}}void DataOutput(){int i,j;// 对所有数据操作for(i = 0;i < N;i++){printf("%d ",Data[i]);}printf("\n");for(j = 0;j < M;j++){// 对所有数据操作for(i = 0;i < N;i++){if( DataShowEnable[j][i] )printf("%d ",DataShow[j][i]);elseprintf(" ");}printf("\n");}printf("缺页次数: %d\n",ChangeTimes);printf("缺页率: %d %%\n",ChangeTimes * 100 / N); }// 最佳置换算法void Optimal(){int i,j,k;bool find;int point;int temp; // 临时变量，比较离的最远的时候用int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i=0;i < N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0 ; // 初始化计数器}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////////////////////////////////////////// ////////Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}/////////////////////////////////////////////////////////////////////////// ///////// 对所有数据进行操作for(i=0;i < N;i++){// 表示块中有没有该数据find = false;for(j = 0;j < M;j++){if( Block[j] == Data[i] ){find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据，最优算法ChangeTimes++; // 缺页次数++for(j = 0;j < M;j++)// 找到下一个值的位置find = false;for( k = i;k < N;k++){if( Block[j] == Data[k] ){find = true;count[j] = k;break;}}if( !find ) count[j] = N;}// 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针temp = 0;for(j = 0;j < M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];// 保存要显示的数据for(j = 0;j < M;j++){DataShow[j][i] = Block[j];DataShowEnable[i < M ? (j <= i ? j : i) : j][i] = true; // 设置显示数据}}// 输出信息printf("\nOptimal => \n");DataOutput();// 先进先出置换算法void FIFO(){int i,j;bool find;int point;int temp; // 临时变量int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i = 0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////////////////////////////////////////// ////////Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}/////////////////////////////////////////////////////////////////////////// ///////// 对有所数据操作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] ){find = true;}}// 块中有该数据，判断下一个数据if( find ) continue;// 块中没有该数据ChangeTimes++; // 缺页次数++// 因为i是从0开始记，而M指的是个数，从1开始，所以i+1 if( (i + 1) > M ){//获得要替换的块指针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; // 设置显示数据}}// 输出信息printf("\nFIFO => \n");DataOutput();}// 最近最久未使用置换算法void LRU(){int i,j;bool find;int point;int temp; // 临时变量int m = 1,n;ChangeTimes = 0;for(j = 0;j < M;j++){for(i = 0;i < N;i++){DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据}}for(i = 0;i < M;i++){count[i] = 0 ; // 初始化计数器}// 确定当前页面是否在物理块中，在继续，不在置换/////////////////////////////////////////////////////////////////////////// ////////Block[0] = Data[0];for(i = 1;m < M;i++){int flag = 1;for(n = 0; n < m;n++){if(Data[i] == Block[n]) flag = 0;}if(flag == 0) continue;Block[m] = Data[i];m++;}/////////////////////////////////////////////////////////////////////////// ///////// 对有所数据操作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++;// 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1if( (i + 1) > M ){//获得要替换的块指针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; // 设置显示数据}}// 输出信息printf("\nLRU => \n");DataOutput();}实验结果截图：程序运行：输入相应数据：选择相应算法：最佳置换算法：先进先出算法：最近最久未使用算法：。

实验五虚拟内存页⾯置换算法实验五虚拟内存页⾯置换算法⼀：实验⽬的通过这次实验，加深对虚拟内存页⾯置换概念的理解，进⼀步掌握先进先出FIFO、最佳置换OPI和最近最久未使⽤LRU页⾯置换算法的实现⽅法。

⼆：实验内容问题描述：设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使⽤LRU页⾯置换算法的⼯作过程。

假设内存中分配给每个进程的最⼩物理块数为m，在进程运⾏过程中要访问的页⾯个数为n，页⾯访问序列为P1, … ,P n，分别利⽤不同的页⾯置换算法调度进程的页⾯访问序列，给出页⾯访问序列的置换过程，计算每种算法缺页次数和缺页率。

程序要求：1）利⽤先进先出FIFO、最佳置换OPI和最近最久未使⽤LRU三种页⾯置换算法模拟页⾯访问过程。

2）模拟三种算法的页⾯置换过程，给出每个页⾯访问时的内存分配情况。

3）输⼊：最⼩物理块数m，页⾯个数n，页⾯访问序列P1, … ,P n，算法选择1-FIFO，2-OPI，3-LRU。

4）输出：每种算法的缺页次数和缺页率。

实现提⽰：⽤C++语⾔实现提⽰：1）程序中变量定义参考如下：int PageOrder[MaxNumber];int Time[MaxNumber];int Simulate[MaxNumber][MaxNumber];int PageCount[MaxNumber];int PageNum,LackNum,PageMin;double LackPageRate;bool found;2）页⾯置换的实现过程如下：变量初始化；接收⽤户输⼊最⼩物理块数m，页⾯个数n，页⾯序列P1, … ,P n，选择算法1-FIFO，2-OPI，3-LRU；根据⽤户选择的算法进⾏页⾯的分配和置换，输出页⾯置换算法的模拟过程；计算选择算法的缺页次数和缺页率；输出选择算法的缺页次数和缺页率。

三：概要设计输⼊函数void input()初始化函数void Initial()最佳置换算法的函数void OPI()最近最久未使⽤置换算法void LRU()主函数void main(){input();int s=0;while(s!=4){cout<<"请选择算法："<cout<<"1：先进先出；2：最佳值换算法；3：最近最久未使⽤置换算法；4：退出"< cin>>s;switch(s){case 1:FIFO();show();break;case 2:OPI();show();break;case 3:LRU();show();break;case 4:return;default:cout<<"输⼊数字不对，请重新输⼊：";break;}}}页⾯数列7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1系统为进程分配的物理块：3输出结果如截图所⽰：先进先出算法：2.最佳置换算法3.LRU算法说明：—1表⽰的是物理块中没有页⾯。

操作系统实验报告计算机0703班200729实验5 页面置换算法一、实验题目：页面置换算法（请求分页）二、实验目的：进一步理解父子进程之间的关系。

1）理解内存页面调度的机理。

2）掌握页面置换算法的实现方法。

3）通过实验比较不同调度算法的优劣。

4）培养综合运用所学知识的能力。

页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。

将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。

三、实验内容及要求这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。

程序涉及一个父进程和两个子进程。

父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。

两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。

要求：1）每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。

设缺页的次数为diseffect。

总的页面访问次数为total_instruction。

缺页率= disaffect/total_instruction命中率= 1- disaffect/total_instruction2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。

四、程序流程图开始创建子进程1创建子进程2结束读逻辑页面否是否已调入物理页面是当前物理页面表是否已满淘汰最先进入页是失效次数加1将读的页调入物理页面表是否已读完逻辑页面退出是否读逻辑页面否是否已调入物理页面当前物理页面表是否已满淘汰最先进入页是失效次数加1将读的页调入物理页面表是否已读完逻辑页面退出是否调整物理页面表中页的顺序是五、程序源代码、文档注释及文字说明#include<stdio.h> #include<sys/types.h> #include<stdlib.h> #include<sys/stat.h> #include<fcntl.h> #include<error.h>#include<wait.h>#include<unistd.h>main(){int p1,p2;int i,j,k,t,m,kk,r1,r2;int temp1,temp2,temp3;int diseffect1=0;int diseffect2=0;int k1=0;int k2=0; int f1=0;int f2=0;float f;int Access_series[8];struct one_frame{int page_no;char flag;};int mframe=5;struct one_frame M_Frame[5];for(i=0;i<mframe;i++) M_Frame[i].page_no=-1;printf("yemian: ");for(i=0;i<8;i++) //产生随机数{Access_series[i]=rand()%8+1;printf("%d ",Access_series[i]);}printf("\n");}while((p1=fork())==-1);if(p1==0){for(j=0;j<8;j++){r1=Access_series[j]; //读入一个逻辑页面for(k=0;k<k1;k++) //查找页面是否已存在于物理页面{if(r1!=M_Frame[k].page_no) continue;else{ printf("have found!\n");for(i=0;i<k1;i++) //存在则显示，并标记，返回读入逻辑页面printf("%d ",M_Frame[i]);printf("\n");f1=1;break;}}if(f1==0){diseffect1++; //若不存在，发生缺页，则失效率加1if(k1<mframe) //物理页面没有分配满{M_Frame[k1].page_no=r1; //分配一个空的物理页面M_Frame[k1].flag='Y';k1++;for(i=0;i<8;i++)printf("%d",Access_series[i]);printf("\n");printf("diseffect!");printf(" %d\n",diseffect1);for(i=0;i<k1;i++)printf("%d ",M_Frame[i]);printf("\n");}else{ temp1=M_Frame[0].page_no; //物理页面表已满for(i=1;i<5;i++)M_Frame[i-1]=M_Frame[i];M_Frame[4].page_no=r1; //淘汰最早进入的M_Frame[0]//并将所读的逻辑页面调入for(i=0;i<8;i++)printf("%d",Access_series[i]);printf("\n");printf("diseffect! %d\n",diseffect1);printf("lose %d\n",temp1);for(i=0;i<k1;i++)printf("%d ",M_Frame[i]);printf("\n");}}f1=0;}f=diseffect1/8.0; //统计缺页率printf("diseffect rate of FIFO %f\n",f);exit(0);}wait(0);for(i=0;i<mframe;i++) M_Frame[i].page_no=-1;while((p2=fork())==-1) ; //创建子进程2if(p2==0){for(m=0;m<8;m++){r2=Access_series[m]; //读入逻辑页for(kk=0;kk<k2;kk++){if(r2!=M_Frame[kk].page_no) //首先在物理页面中查找continue;else{printf("have found!\n"); //找到for(t=kk+1;t<k2;t++) //调整数组顺序，使刚被访问的页面在最后的位置M_Frame[t-1].page_no=M_Frame[t].page_no;M_Frame[t-1].page_no=r2;for(i=0;i<k2;i++)printf("%d ",M_Frame[i].page_no);printf("\n");f2=1;break;}}if(f2==0) //没有找到，发生缺页{diseffect2++; //缺页率加1if(k2<mframe) //物理页面还没有分配完{M_Frame[k2].page_no=r2; //选择空页面分配M_Frame[k2].flag='Y';k2++;for(i=0;i<8;i++)printf("%d ",Access_series[i]);printf("\n");printf("diseffect! %d\n",diseffect2);for(i=0;i<k2;i++)printf("%d ",M_Frame[i]);printf("\n");}else{ //淘汰最近最久未访问的M_Frame[0]temp3=M_Frame[0].page_no;for(i=1;i<mframe;i++)M_Frame[i-1].page_no=M_Frame[i].page_no;M_Frame[mframe-1].page_no=r2; //将当前页调入for(i=0;i<8;i++)printf("%d ",Access_series[i]);printf("\n");printf("diseffect %d\n",diseffect2);;printf("lose %d\n",temp3);for(i=0;i<k2;i++)printf("%d ",M_Frame[i]);printf("\n");}}f2=0;}f=diseffect2/8.0; //统计失效率printf("diseffect rate of LRU %f\n",f);exit(0);}}六、运行结果及其说明FIFO：8，7，2，4缺页调入，2，8命中，3缺页调入，5缺页淘汰8，调入5；LRU：8，7，2，4缺页调入，访问2，把2移到数组尾，访问8，把8移到数组尾，3缺页调入，5缺页，淘汰7，调入5。

目录1．问题的提出 (2)1.1关于页面置换算法模拟程序问题的产生 (2)1.2任务分析 (2)2．需求分析 (2)3．方案设计 (3)4．总体设计 (4)4.1程序N-S图 (4)4.2主要的函数 (4)4.3主要流程图及代码 (5)4.3.1 FIFO（先进先出） (5)4.3.2 LRU（最近最久未使用） (6)4.3.3 OPT（最佳置换算法） (8)4.4实现结果 (11)5．程序测试 (14)5.1设计测试数据 (14)5.2测试结果及分析 (15)摘要随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要提高，所以越来越多的人进行着各种各样的学习。

操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。

操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。

一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。

由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。

要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果.本课程设计是学生学习完《操作系统教程》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。

熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。

关键词：编制页面置换算法模拟程序、打印页面、FIFO页面算法、LRU页面置换算法、OPT页面置换算法。

引言1．问题的提出1.1关于页面置换算法模拟程序问题的产生在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：（1）有的作业很大，不能全部装入内存，致使作业无法运行；（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。

实验六页面置换算法模拟实验一、实验目的1. 掌握虚拟存储器的实现方法。

2. 掌握各种页面置换算法。

3. 比较各种页面置换算法的优缺点。

二、实验内容模拟实现各种页面置换算法。

具体步骤为：1. 使用产生随机数函数得到一个随机的数列，作为将要载入的页面序列。

2. 可以选择使用先进先出（FIFO）算法、最近最久未使用（LRU）置换算法和最佳（OPT）置换算法，给出所需淘汰的页面号序列。

3. 列出缺页中断次数。

三、实验源程序/* 程序说明：本程序假设内存为程序分配的内存块数为4。

*//* 进入程序后可以根据菜单项进入不同的模块 *//* 1.使用首次适应算法分配空间 *//* 2.最近最久未使用的页面 *//* 3.使用最佳适应算法分配空间 *//* 4.显示有多少个缺页中断 *//* 5.推出系统 */#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 39 /* 随机数序列的长度*/#define B 4 /* 内存的页面数 *//函数名：IsInBuf//功能：返回某个数x有没有在缓冲Buf[]中，若在，返回其位置；若不在，则返回-1/ int IsInBuf(int buf[],int x){ int i,j=-1;for(i=0;i<B;i++){ if(buf[i]==x) {j=i;break;}else if(buf[i]==-1){buf[i]=x;j=i;break;}}return j;}/函数名：oldest()//功能：返回最近最久未使用的页面的位置/int oldest(int f[]){ int i,j=0,max=-1;for(i=0;i<B;i++){ if(f[i]>max) {max=f[i];j=i;}f[i]++;}return j;}/函数名：oldest2()//功能：返回未来最长时间不使用的页面的位置/int oldest2(int list[],int buf[],int f[],int start) { int i,j;for(i=0;i<B;i++){ for(j=start;j<N;j++){ if(buf[i]==list[j]) break;}f[i]=j;}return oldest(f);}/函数名：main（）/main(){ int list[N];int buf[B],f[B],i,j,k,max,min;int old=0;int change=0;/生成一系列随机数并初始化环境/srand((int)time(NULL));for(i=0;i<B;i++) buf[i]=f[i]=-1;printf(“\nThe Random List:\n”);for(i=0;i<N;i++){ list[i]=(int) rand()%10;printf(“%2d”,list[i]);}/显示FIFO淘汰页面的序列/printf(“\nFIFO:\n”);change=0;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){ printf(“%2d”,buf[old]);buf[old]=list[i];old=(old+1)%(int)B;change++;}elseprintf(“”);}/显示有多少个缺页中断/printf(“\nchanges:%d\n”,change);/显示LRU淘汰页面的序列/printf(“LRU :\n”);change=0;for(i=0;i<B;i++) buf[i]=f[i]=-1;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);old=oldest(f);if(j==-1){ printf(“%2d”,buf[old]);buf[old]=list[i];f[old]=0;change++;}else{ f[j]=0;printf(“”);}}/显示有多少个缺页中断/printf(“\nchanges:%d\n”,change);/显示OPT淘汰页面的序列/printf(“OPT :\n”);change=0;for(i=0;i<B;i++) buf[i]=f[i]=-1;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){ old=oldest2(list,buf,f,i);printf(“%2d”,buf[old]);buf[old]=list[i];f[old]=0;change++;}else{ printf(“”);}}/显示有多少个缺页中断/printf(“\nchanges:%d\n”,change);}说明：多次运行结果并不相同，分析一下原因。

实验二页面置换算法实现一、实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。

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

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

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

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

2.1 先进先出（FIFO ）页面置换算法当需要访问一个新的页面时，首先查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则替换页面。

并将物理块中所有页面 timer++。

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

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

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

三、实验流程3.1 系统功能图图3-1 系统功能图3.2 算法流程图1）先进先出（FIFO ）页面置换算法流程图图3-2 先进先出页面置换算法流程图2）最近久未使用 (LRU) 置换算法图3-3 最近久未使用置换算法流程图3）最佳（ OPT ）置换算法图3-4 最佳置换算法流程图四、源程序#include<iostream.h>#include <stdlib.h>#include <time.h>#include <stdio.h>#define L 20 //页面长度最大为20int M; //内存块struct Pro//定义一个结构体{int num,time;};Input(int m,Pro p[L])//打印页面走向状态{cout<<"请输入页面长度(10～20)：";do{cin>>m;if(m>20||m<10){ cout<<endl;cout<<"页面长度必须在10～20之间"<<endl<<endl;cout<<"请重新输入L：";}else break;}while(1);int i,j;j=time(NULL);//取时钟时间srand(j);//以时钟时间j为种子，初始化随机数发生器cout<<endl;cout<<"输出随机数: "<<endl;cout<<endl;for(i=0;i<m;i++){p[i].num=rand( )%10;//产生0到9之间的随机数放到数组p中p[i].time=0;cout<<p[i].num<<" ";}cout<<endl<<endl;return m;}void print(Pro *page1)//打印当前的页面{Pro *page=new Pro[M];page=page1;for(int i=0;i<M;i++)cout<<page[i].num<<" ";cout<<endl;}int Search(int e,Pro *page1 )//寻找内存块中与e相同的块号{Pro *page=new Pro[M];page=page1;for(int i=0;i<M;i++)if(e==page[i].num)return i;//返回i值return -1;}int Max(Pro *page1)//寻找最近最长未使用的页面{Pro *page=new Pro[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(Pro *page1,int i,int t,Pro p[L])//记录当前内存块中页面离下次使用间隔长度{Pro *page=new Pro[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;int m=0,t=0;float n=0;Pro p[L];m=Input(m,p);//调用input函数，返回m值cout<<"请输入分配的物理块m(2～6): ";cout<<endl<<endl;do{cin>>M;if(M>6||M<2){ cout<<endl;cout<<"物理块m必须在2～6之间"<<endl<<endl;cout<<"请重新输入m： ";}else break;}while(1);Pro *page=new Pro[M];do{for(int i=0;i<M;i++)//初始化页面基本情况{ page[i].num=0;page[i].time=m-1-i;}i=0;cout<<endl;cout<<"1:FIFO页面置换2:LRU页面置换"<<endl;cout<<"3:OPT页面置换4:退出"<<endl;cout<<"请选择页面置换算法："<<endl;cin>>c;if(c==1)//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<<endl;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl<<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;//把与它相同的内存块的时间置0 for(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<<endl;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl<<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<<endl;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl<<endl;}if(c == 4) break;}while(c==1||c==2||c==3);return 0;}五、实验结果5.1 程序主界面运行程序后，将会提示用户输入页面长度，长度在10到20之间。

实验报告：页面置换算法10信息姓名：赵恩林学号：1007433020一、实验内容对于给定数量的物理块和指定的页面引用次序，求OPT、FIFO、LRU三种算法的缺页次数和置换次数，给出缺页次数和置换次数。

二、实验设计序列的个数，物理块个数，序列串的长度及所有序列串由yemian.txt读入OS：Win7；编译器：Microsoft Visual C++6.0；以书上的为例，在文档yemian.txt中，保存着试验的数据，里面包含的数据为：序列个数为2 ，物理块个数为3，每个序列的长度为20，具体序列为：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1和7 0 2 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1页面置换.c实现相应操作，各子函数实现具体操作：void opt()实现最佳置换算法：如果引用页面不在内存如果当前指针所在位置的页面为空放入当前页面，指针后移否则找到最近将不会被访问的页面的位置放入，置换加1缺页加1否则void fito()实现先进先出算法:如果引用页面不在内存如果当前指针所在位置的页面为空放入当前页面否则替换当前页面，置换加1缺页加1，指针后移否则void lru()实现最近最久未使用算法:如果引用页面不在内存如果当前指针所在位置的页面为空放入当前页面否则物理块数据均前移一块，置换物理块最后一块，置换加1缺页加1，指针后移否则当前物理块移动到物理块最后，在当前物理块之后的物理块均前移一个三、实验结果和分析结果：请选择要处理的数据集序号 2输入的串序列为 7 0 2 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 最佳置换算法（OPT）：发生置换的情况如下图所示：7 0 2 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 7 7 3 3 3 1 10 0 0 4 0 0 02 2 2 2 2 7缺页次数为8，置换次数为5先进先出算法（FIFO）发生置换的情况如下图所示：7 0 2 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 7 7 3 3 3 2 2 2 00 0 0 4 4 4 1 1 12 2 2 0 0 0 7 7缺页次数为10，置换次数为7最近最久未使用（LRU）发生置换的情况如下图所示：7 0 2 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17 7 7 3 3 2 2 2 2 2 70 0 0 0 0 3 3 3 0 02 2 4 4 4 0 1 1 1缺页次数为11，置换次数为8分析：每种算法的缺页次数比置换次数都多物理块的个数。

实验四页面置换算法模拟（2）一.题目要求：设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率：要求设计主界面以灵活选择某算法，且以下算法都要实现1）最佳置换算法（OPT）:将以后永不使用的或许是在最长（未来）时间内不再被访问的页面换出。

2）先进先出算法（FIFO）:淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

3）最近最久未使用算法（LRU）:淘汰最近最久未被使用的页面。

4）最不经常使用算法（LFU）.实验目的：1、用C语言编写OPT、FIFO、LRU,LFU四种置换算法2、熟悉内存分页管理策略。

3、了解页面置换的算法。

4、掌握一般常用的调度算法。

5、根据方案使算法得以模拟实现。

6、锻炼知识的运用能力和实践能力。

三.相关知识：1 .虚拟存储器的引入：局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。

2 .虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

3 .虚拟存储器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。

请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。

4 .页面分配：平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。

按比例分配算法，根据进程的大小按比例分配物理块。

考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。

5 .页面置换算法：常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。

四.设计思想：选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。