实验3 页式存储管理的缺页中断及淘汰算法模拟

合肥学院计算机科学与技术系实验报告2011～2012学年第一学期课程操作系统原理课程设计名称模拟分页式存储管理中硬件的地址转换和产学生姓名学号专业班级10计本（2）班指导教师2011年11月1.实验目的：通过实验模拟分页式存储管理中硬件的地址转换和产生缺页中断帮助理解在分页式存储管理中怎样虚拟存储器。

2.实验内容：分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。

作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：绝对地址=块号×块长+单元号计算出欲访问的主存单元地址。

如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。

若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，由操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

3.实验步骤：任务分析：(1)分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。

为此，在为作业建立页表时，应说明哪些页已在主存，其中，标志----用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。

主存块号----用来表示已经装入主存的页所占的块号。

在磁盘上的位置----用来指出作业副本的每一页被存放在磁盘上的位置。

(2)作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：绝对地址=块号×块长+单元号计算出欲访问的主存单元地址。

如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。

一目的与要求(1) 请求页式虚存管理是常用的虚拟存储管理方案之一。

(2) 通过请求页式虚存管理中对页面置换算法的模拟，加深理解虚拟存储技术的特点。

(3) 模拟页式虚拟存储管理中硬件的地址转换和缺页中断,并用先进先出调度算法(FIFO)处理缺页中断.二实验内容或题目(1)本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。

(2)虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。

(3)要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。

(4)程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。

三实验步骤与源程序（1）实验步骤1、理解好相关实验说明。

2、根据实验说明，画出相应的程序流程图。

3、按照程序流程图，用C语言编程并实现。

（2）流程图如下：①虚页和实页结构在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。

pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。

time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。

在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。

pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。

next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。

②程序流程图如下：（3）源程序如下:#include<iostream.h>#define M 40int N;struct Pro{int num,time;};int Input(int m,Pro p[M]){cout<<"请输入实际页数:";do{cin>>m;if(m>M)cout<<"数目太多，请重试"<<endl;else break;}while(1);//cout<<"请输入各页面号:";for(int i=0;i<m;i++){cout<<"第"<<i<<"个页面号为:";cin>>p[i].num;p[i].time=0;}return m;}void print(Pro *page1)//打印当前的页面{Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)cout<<page[i].num<<" ";cout<<endl;}int Search(int e,Pro *page1 ){Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)if(e==page[i].num)return i; return -1;}int Max(Pro *page1){Pro *page=new Pro[N];page=page1;int e=page[0].time,i=0;while(i<N)//找出离现在时间最长的页面{if(e<page[i].time)e=page[i].time;i++;}for( i=0;i<N;i++)if(e==page[i].time)return i;return -1;}int Compfu(Pro *page1,int i,int t,Pro p[M]){Pro *page=new Pro[N];page=page1;int count=0;for(int j=i;j<M;j++){if(page[t].num==p[j].num )break;else count++;}return count;}int main(){cout<<"可用内存页面数:";cin>>N;Pro p[M];Pro *page=new Pro[N];char c;int m=0,t=0;float n=0;m=Input(m,p);do{for(int i=0;i<N;i++)//初试化页面基本情况{page[i].num=0;page[i].time=2-i;}i=0;cout<<"************************"<<endl;cout<<"*****f:FIFO页面置换*****"<<endl;cout<<"*****l:LRU页面置换******"<<endl;cout<<"*****o:OPT页面置换******"<<endl;cout<<"*****按其它键结束*******"<<endl;cout<<"************************"<<endl;cout<<"请选择操作类型(f,l,o):";cin>>c;if(c=='f')//FIFO页面置换{n=0;cout<<"页面置换情况: "<<endl;while(i<m){if(Search(p[i].num,page)>=0)i++;//找到相同的页面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout<<"缺页次数："<<n<<" 缺页率:"<<n/m<<endl; }if(c=='l')//LRU页面置换{ n=0;cout<<"页面置换情况: "<<endl;while(i<m){int k;k=t=Search(p[i].num,page);if(t>=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}if(k==-1) print(page); i++;}cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl;}if(c=='o')//OPT页面置换{n=0;while(i<m){if(Search(p[i].num,page)>=0)i++;else{int temp=0,cn;for(t=0;t<N;t++){if(temp<Compfu(page,i,t,p)){temp=Compfu(page,i,t,p); cn=t;}}page[cn]=p[i];n++;print(page);i++;}}cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl; }}while(c=='f'||c=='l'||c=='o');return 0;});四测试数据与实验结果五结果分析与实验体会通过上机，我了解了许多关于操作系统的专业知识。

一．实验内容模拟请求页式存储管理中硬件的地址转换和缺页中断处理 二．实验原理装入新页置换旧页时，若旧页在执行中没有被修改过，则不必将该页重写磁盘。

因此，页表中增加是否修改过的标志，执行“存”指令和“写”指令时将对应的修改标志置成“1”三．要求及方法：① 设计一个地址转换程序来模拟硬件的地址转换和缺页中断。

当访问的页在主存时则形成绝对地址，但不去模拟指令的执行，可以输出转换后的绝对地址来表示一条指令已执行完成。

当访问的页不在主存中时，则输出“*页号”来表示硬件产生了一次缺页中断。

模拟地址转换流程见图1。

② 编制一个FIFO 页面调度程序；FIFO 页面调度算法总是先调出作业中最先进入主存中的哪一页。

因此可以用一个数组来表示（或构成）页号队列。

数组中每个元素是该作业已在主存中的页面号，假定分配给作业的页架数为m ，且该作业开始的m 页已装入主存，则数组可由m 个元素构成。

P[0]，P[1]，P[2]，…，P[m-1]它们的初值为P[0]：=0，P[1]：=1，P[2]：=2，…，P[m-1]：=m-1用一指针K 指示当要调入新页时应调出的页在数组中的位置，K 的初值为“0”，当产生缺页中断后，操作系统总是选择P[K]所指出的页面调出，然后执行：P[K]：=要装入的新页页号 K ：=(k+1)mod m在实验中不必实际地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT 调出的页号”和“IN 要装入的新页页号”来模拟一次调出和装入过程，模拟程序的流程图见附图1。

按流程控制过程如下：提示：输入指令的页号和页内偏移和是否存指令⎩⎨⎧ 0 1非存指令存指令，若d 为-1则结束，否则进入流程控制过程，得P1和d，查表在主存时，绝对地址=P1×1024+d③假定主存中页架大小为1024个字节，现有一个共7页的作业，其副本已在磁盘上。

系统为该作业分配了4个页架，且该作业的第0页至第3页已装入内存，其余3页未装入主四．主要代码及其说明#include <stdio.h>#include <string.h>#include <stdlib.h>#define M 1024#define R 4typedef struct _PTable{int Number; //页号int Flag; //标志int Fnum; //页架号int Mflag; //修改标志int Position; //该页存放在磁盘上的位置}PTable;//初始化PTable ptable[]={{0, 1, 5, 0, 11},{1, 1, 8, 0, 12},{2, 1, 9, 0, 13},{3, 1, 1, 0, 21},{4, 0, -1, 0, 22},{5, 0, -1, 0, 23},{6, 0, -1, 0, 121},};void menu();int change(char op,int number,int add);void display();int p[]={0,1,2,3},k=0;void main(void){int number,add,n;char op;while(n){display();fflush( stdin );printf("输入:操作页号页内地址(存指令用\"c\"代表)\n");scanf("%c %d %d",&op,&number,&add);change(op,number,add);printf("\"是否继续! (按1 继续按任意键结束)\"\n");scanf("%d",&n);system( "cls ");if(n==1)continue;elsebreak;}}void menu(){printf("操作码\t页号\t页内地址页架标志修改标志出入状态绝对地址(L)\n");}int change(char op,int number,int add){bool flag1=false;bool flag2=false;int i,address,cout,temp;;for(i=0;i<7;i++){if(op=='c'){ptable[number].Mflag=1;}if(ptable[i].Number==number && ptable[i].Flag==1){address=ptable[i].Fnum*M+add;flag1=true;}if(ptable[i].Number==number && ptable[i].Flag==0){cout=i;temp = p[k]; //将要出的页if(ptable[temp].Mflag==1){flag2=true;}//修改页表ptable[number].Flag=1; //修改新页标志ptable[number].Fnum=ptable[temp].Fnum; //修改新页页架address=ptable[number].Fnum*M+add;ptable[temp].Flag=0; //修改旧页ptable[temp].Fnum=-1; //修改页架ptable[temp].Mflag=0; //修改修改标志p[k]=number; //新页k=(k+1)%R;}}menu();if(flag1)printf("%c\t %d\t %d\t %d\t %d\t %d\t 无出入\t%d\n",op,number,add,ptable[number].Fnum,ptable[number].Flag,ptable[number].Mflag,address);else if(flag2)printf("%c\t *%d\t %d\t %d\t %d\t%d OUT:%d,IN:%d %d\n",op,number,add,number,ptable[number].Fnum,ptable[number].Flag,ptable[number].Mflag,temp,number,address);elseprintf("%c\t *%d\t %d\t %d\t %d\t %d\t IN%d\t %d\n",op,number,add,ptable[number].Fnum,ptable[number].Flag,ptable[number].Mflag,number,address);return 0;}void display(){int i;printf("********当前页表中的状态*********\n");printf("页号标志页架修标志\n");for(i=0;i<7;i++){printf("%d\t%d\t%d\t%d\n",ptable[i].Number,ptable[i].Flag,ptable[i].Fnum,ptable[i]. Mflag);}printf("当前主存中的页号为: ");for(i=0;i<4;i++){printf("%d ",p[i]);}printf("\n*********************************\n");}五,实验截图。

课程名称操作系统原理实验名称模拟请求页式存储管理中硬件的地址转换和缺页中断姓名学号专业班级实验日期成绩指导老师(①实验目的②实验原理③主要仪器设备④实验内容与步骤⑤实验数据记录与处理⑥实验结果分析⑦问题建议)一、实验目的模拟请求页式存储管理中硬件的地址转换和缺页中断，并用先进先出调度算法（FIFO）处理缺页中断。

二、实验内容内容：模拟请求页式存储管理中硬件的地址转换和缺页中断处理思想：装入新页置换旧页时，若旧页在执行中没有被修改过，则不必将该页重写磁盘。

因此，页表中增加是否修改过的标志，执行“存”指令和“写”指令时将对应的修改标志置成模拟算法流程三、程序及截图程序:#include<iostream>#include<iomanip>#include<list>using namespace std;char useSign[12][5]={{'+'},{'-'},{'*'},{"存"},{"取"},{'-'},{"移位"},{'+'},{"存"},{"取"},{'+'},{"存"}};int PageAddress[12]={70,50,15,21,56,40,53,23,37,78,01,84};int PageNum[12]={0,1,2,3,0,6,4,5,1,2,4,6};int S_Station;int pPageNum[7];//页号pPageint pSign[7];int pStool[7];//页架号int pModify[7];//修改标志int pStation[7];//磁盘位置static int z=0;void Store(){for(int i=0;i<7;i++){if(i<4){pSign[i]=1;}elsepSign[i]=0;pPageNum[i]=i;pModify[i]=0;}int p1=1,p2=2,p3=3;for(i=0;i<7;i++){if(i<3){pStation[i]=p1;p1++;}elseif(i<6){pStation[i]=p2;p2++;}elsepStation[i]=p3;}pStool[0]=5;pStool[1]=8;pStool[2]=9;pStool[3]=1;}void CShow(){cout<<"操作";cout<<"页号";cout<<"页内地址";cout<<"标志";cout<<"绝对地址";cout<<"修改页号";cout<<"页架号";cout<<"绝对地址";cout<<endl;}void Find(){int m_Pagenum;int m_Station;int Y_Station;//绝对地址int m_Stool;cout<<"输入页号及页内地址查询操作：";cin>>m_Pagenum>>m_Station;CShow();int i,j=0;//string m_Modify;for(i=0;i<12;i++){if(PageAddress[i]==m_Station){break;}}Y_Station=pStool[m_Pagenum]*1024+m_Station;if(pSign[m_Pagenum]==1){if(strcpy(useSign[i],"存")!=0){pModify[m_Pagenum]=1;}}cout<<useSign[i]<<" ";cout<<m_Pagenum<<" ";cout<<m_Station<<" ";cout<<pSign[m_Pagenum]<<" ";if(Y_Station!=m_Station){cout<<Y_Station<<" ";cout<<" ";cout<<pStool[m_Pagenum]<<" ";cout<<Y_Station<<endl;}else{cout<<"*"<<m_Pagenum<<" ";for(j=z;j<7;j++){if(pSign[j]==1){z++;break;}}cout<<m_Pagenum<<"->"<<j<<" ";pStool[m_Pagenum]=pStool[j];pSign[j]=0;pStool[j]=0;cout<<pStool[m_Pagenum]<<" ";cout<<pStool[m_Pagenum]*1024+m_Station<<endl;}}int main(void){Store();char judge='Y';while(judge=='Y'){Find();cout<<"是否继续输入？Y = 是N=否"<<endl;cin>>judge;}return 0;}截图:五．心得体会在实验过程中，遇到了一些问题但是在调试的过程中，会出现很多错误，有的自己可以解决，也有一些在同学的帮助下，基本都解决了所有问题。

存储器管理(一)一、实验目的模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二、实验目的在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。

用这种办法扩充的主存储器称为虚拟存储器。

通过本实验帮助同学理解在分页式存储管理中怎样实现虚拟存储器。

三、实验题目示例程序给出了模拟分页式存储管理中硬件的地址转换和产生缺页中断；请写出用先进先出（FIFO）页面调度算法处理缺页中断或用最近最少用（LRU）页面调度算法处理缺页中断的程序。

四、示例程序源代码#include "stdio.h"#define blockLength 128typedef enum {NO=0,YES}FLAG;typedef struct pagetable {int pageNumber;FLAG flag;int memoryBlock;int place;}PAGETAB;typedef struct job{int pageNumber;int unitNumber;}JOB;PAGETAB pageTAB[7]={0,YES,5,11,1,YES,8,12,2,YES,9,13,3,YES,1,21,4,NO,-1,22,5,NO,-1,23,6,NO,-1,121};JOB work[12] = {0,70,1,50,2,15,3,21,0,56,6,40,4,53,5,23,1,37,2,78,4,1,6,84};int main(int argc, char* argv[]){//first init page table// and work list// look for the work list and pick one to fix the page tablefor(int i=0; i<12;i++){printf("Instruction sequence :%d\n",i+1);int j = work[i].pageNumber;printf("The page %d is in the memory? %s!\n",j,(pageTAB[j].flag == YES)?"YES":"NO");if(pageTAB[j].flag == YES){int absoluteAddress = pageTAB[j].memoryBlock*blockLength+work[i].unitNumber; printf("Instruction absolute address:%d\n",absoluteAddress);}else{printf("missing page interrupt, page fault interrupt!\n");}}return 0;}存储器管理(二)一、实验目的：掌握分页式存储管理的基本概念和实现方法。

一、实验目的1. 理解缺页中断的概念及其在操作系统中的作用。

2. 掌握常见的页面置换算法，如先进先出（FIFO）、最近最少使用（LRU）等。

3. 通过模拟实验，验证不同页面置换算法对缺页中断次数的影响。

4. 深入了解页式虚拟存储管理中地址转换的过程。

二、实验环境1. 操作系统：Windows 102. 编程语言：C/C++3. 实验工具：Visual Studio三、实验内容1. 模拟缺页中断的产生2. 实现不同的页面置换算法3. 分析页面置换算法对缺页中断次数的影响4. 模拟地址转换过程四、实验步骤1. 模拟缺页中断的产生（1）定义一个模拟指令序列，包含多个页面号。

（2）创建一个模拟的页表，用于记录每个页面是否在内存中。

（3）根据指令序列，遍历页表，判断访问的页面是否在内存中。

（4）如果页面不在内存中，则产生缺页中断。

2. 实现不同的页面置换算法（1）先进先出（FIFO）算法：- 定义一个队列，用于存储内存中的页面号。

- 当发生缺页中断时，将新页面号入队，同时判断队列长度是否超过内存块数。

- 如果队列长度超过内存块数，则将队首元素出队，模拟页面置换过程。

（2）最近最少使用（LRU）算法：- 定义一个链表，用于存储内存中的页面号。

- 当发生缺页中断时，将新页面号插入链表尾部。

- 如果链表长度超过内存块数，则从链表头部删除元素，模拟页面置换过程。

3. 分析页面置换算法对缺页中断次数的影响（1）定义一个变量，用于记录缺页中断次数。

（2）遍历模拟指令序列，根据不同的页面置换算法处理缺页中断。

（3）统计不同算法下的缺页中断次数，并进行比较。

4. 模拟地址转换过程（1）根据指令中的逻辑地址，计算页号和偏移量。

（2）根据页号，查找页表，判断页面是否在内存中。

（3）如果页面在内存中，则根据偏移量计算物理地址。

（4）如果页面不在内存中，则产生缺页中断。

五、实验结果与分析1. 模拟缺页中断的产生通过模拟指令序列，成功产生了缺页中断。

燕山大学课程设计说明书课程设计名称：操作系统OS题目：页式存储管理中页面置换（淘汰）的模拟程序班级：计算机应用二班开发小组名称：CAMPUS课题负责人：课题组成员：姓名学号班级自评成绩课题开发日期：2011-1-10至2011-1-14一．概述1目的通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标——缺页次数和缺页率，来对各种替换算法进行评价比较。

2.主要完成的任务自行输入实际页数、内存可用页面数、存取内存时间、存取快表时间及缺页中断时间，然后由用户随机输入各页面号，模拟系统自动运行出FIFO、LRU、OPT、LFU四种算法的缺页次数、缺页率、命中率、总存取时间、存取平均时间等结果。

3 使用的开发工具（1）使用系统：Windows7（2）使用语言：C++（3）开发工具：Visual C++ 6.04 解决的主要问题设计的结果程序能实现FIFO、OPT、LRU、LFU算法模拟页式存储管理缺页中断，主要能够处理以下的问题：(1) 用户能够输入给作业分配的内存块数；(2) 用户能够输入给定的页面，并计算发生缺页的次数以及缺页率；(3) 程序可由用户输入页面序列；(4)系统自动计算总存取时间及平均存取时间。

二使用的基本概念和原理1.概念FIFO即先进先出页面置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

LRU 即最近最久未使用页面置换算法，该算法选择最近最久未使用的页面予以淘汰。

OPT 即最佳值换算法，其选择淘汰的页面是在最长时间内不再被访问的页面。

LFU 即最近使用最少页面置换算法，其淘汰的页面是最近一段时间内使用最少的页面。

缺页中断存取页面时页面不在内存中需从外存调入的现象。

缺页次数即在存取页面过程中发生缺页中断的次数。

页式虚拟FIFO存储管理缺页中断的模拟算法FIFO一课程设计目的与功能1目的通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标——缺页次数和缺页率，来对各种替换算法进行评价比较。

设计并实现出的结果程序要能够很好地显示页面调入和替换详细信息。

2初始条件（1）预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。

（2）实践准备：掌握一种计算机高级语言的使用3 开发环境（1）使用系统：Windows XP（2）使用语言：C++（3）开发工具：Visual C++ 6.04功能设计的结果程序能实现OPT、FIFO、随机淘汰算法模拟页式存储管理缺页中断，主要能够处理以下的情形：(1) 用户能够输入给作业分配的内存块数；(2) 用户能够输入给定的页面，并计算发生缺页的次数以及缺页率；(3) 程序可随机生成页面序列，替代用户输入；(4) 缺页时，如果发生页面置换，输出淘汰的页号。

二需求分析，整体功能及设计数据结构或模块说明1 需求分析在纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。

即用户程序将受到物理内存大小的限制。

为了解决这个问题，人们提出了能提供虚存的存储管理技术——请求分页存储管理技术和请求分段技术。

本设计实现请求分页管理技术。

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

它允许只装入部分页面的程序和数据，便启动运行。

以后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上。

置换时以页面为单位，为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。

实验报告院（系）：数学与计算机科学学院专业班级：学号：姓名：实验地点：实验日期：年月日一、实验目的及要求通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页面替换算法的具体实现方法。

二、实验环境PC /Windows系统/Visual C++6.0三、实验内容①实现三种算法：先进先出；OPT；LRU②页面序列从指定的文本文件（TXT文件）中取出③输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数/*全局变量*/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 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];}elsefor(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];}elsefor(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}compute();print(count);}四、实验步骤页面置换：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。

课程设计题目请求页式管理缺页中断模拟设计--FIFO、OPT学院计算机科学与技术专业班级姓名指导教师吴利军2013 年 1 月16 日课程设计任务书学生姓名：指导教师：吴利军_ 工作单位：计算机科学与技术学院题目: 请求页式管理缺页中断模拟设计--FIFO、OPT初始条件：1．预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。

2．实践准备：掌握一种计算机高级语言的使用。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．实现指定淘汰算法。

能够处理以下的情形：⑴能够输入给作业分配的内存块数；⑵能够输入给定的页面，并计算发生缺页的次数以及缺页率；⑶缺页时，如果发生页面置换，输出淘汰的页号。

2．设计报告内容应说明：⑴需求分析；⑵功能设计（数据结构及模块说明）；⑶开发平台及源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。

周2、周3：完成程序调试及测试。

周4、周5：验收、撰写课程设计报告。

（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日请求页式管理缺页中断模拟设计——FIFO、OPT1课程设计目的与功能1.1设计目的结合《操作系统》所学内存页式管理章节，掌握虚拟内存设计的重要性，熟悉和掌握请求分页式存储管理的实现原理，通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法（主要通过FIFO和OPT实现），并考察替换算法的评价指标——缺页次数和缺页率，得到淘汰的页面次序。

实验模拟页式虚拟存储管理中硬件的地址转换和用先进先出调度算法处理缺页中断1、实验目的1）理解页式虚拟存储管理中的地址转换。

2）理解用先进先出调度算法如何处理缺页中断。

2、实验原理在页式虚拟存储管理中，如果访问的页面在内存，计算出相应的物理地址，如果访问的页面不在内存，产生缺页中断，将所缺页从外存调入，如果内存没有空间需要将内存的一页淘汰，再将所缺页调入，然后计算出相应的物理地址。

3、实验仪器设备微型计算机、C或Visual C++开发软件4、实验内容与步骤编写程序，模拟页式虚拟存储管理中硬件的地址转换和用先进先出调度算法处理缺页中断。

假定主存的每块长度为1024个字节，现有一个共7页的作业，其副本已在磁盘上。

系统为该作业分配了4个主存块，且该作业的第0页至第3页已经装入主存，其余3页尚未装入主存，该作业的页表见下表。

实验步骤1）输入程序2）如果该作业执行的指令序列如下表所示：执行上述的指令序列来调试你所设计的程序（仅模拟指令的执行，不必考虑指令序列中具体操作的执行）5、预习及实验报告要求预习页式虚拟存储管理中地址转换和页面置换算法的有关内容。

实验报告要求写出程序的源代码及运行结果。

分析：主存块有4个，物理地址=块号*块长（这里是1024）+块内地址（块内地址=页内地址），若页号不在主存中，则产生缺页中断，根据先进先出原则，今要执行的页号置换最先进入主存的页号，计算得到如下值：5192，8242，9231，1050，5176，5160，8248，9239，1061，5198，8193，8278 012306451246000006666222111111444446222222255555333333331111英文版#define size 1024//定义块的大小，本次模拟设为1024个字节。

#include "stdio.h"#include "string.h"#include <conio.h>struct plist{int number; //页号int flag; //标志，如为1表示该页已调入主存，如为0则还没调入。

操作系统实验二〔第一题〕一．实验内容模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二．实验目的在电脑系统总，为了提高主存利用率，往往把辅助存储器作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间综合可以超出主存的绝对地址空间。

用这种方法扩充的主存储区成为虚拟存储器。

三．实验题目模拟分页式存储管理中硬件的地址转换和产生缺页中断。

四．程序清单//// 操作实验二.cpp : 定义控制台应用程序的入口点。

//#include "stdafx.h"#include<iostream>#include<string>#include<fstream>using namespace std;class ins{private:string ope;long int page;long int unit;public:ins(){ }ins(string o,long int p,long int u):ope(o),page(p),unit(u){}void setope(string o){ ope=o;}void setpage(long int p){ page=p;}void setunit(long int u){ unit=u;}string getope(){return ope;}long int getpage(){return page;}long int getunit(){return unit;}};class work{private:long int Page;int sym;long int inum;long int onum;public:work(){}work(long int P, int s,long int i,long int o):Page(P),sym(s),inum(i),onum(o){} void setPage(long int P){ Page=P;}void setsym( int s){ sym=s;}void setinum(long int i){ inum=i;}void setonum(long int o){ onum=o;}long int getPage(){return Page;}int getsym(){return sym;}long int getinum(){return inum;}long int getonum(){return onum;}};void diaodu(work *w,ins * i,int numofins){ for(int j=0;j<numofins;j++){long int tempofk;long int a =i[j].getpage();for(int k=0;k<7;k++) //7是页表的页数if(w[k].getPage()!=a)continue;else{tempofk=k;break;}if(w[tempofk].getsym()==1)cout<<"绝对地址："<<w[tempofk].getinum()*128+i[j].getunit()<<" "<<"磁盘地址为："<<w[tempofk].getonum()<<" "<<"操作为："<<i[j].getope()<<endl;else cout<<"*"<<"发生缺页中断"<<endl;}}int main(){ins*INS=new ins[12];INS[0].setope ("+");INS[0].setpage(0);INS[0].setunit(70);INS[1].setope ("+");INS[1].setpage(1);INS[1].setunit(50);INS[2].setope ("×");INS[2].setpage(2);INS[2].setunit(15);INS[3].setope ("存"); INS[3].setpage(3);INS[3].setunit(21);INS[4].setope ("取"); INS[4].setpage(0);INS[4].setunit(56);INS[5].setope ("-");INS[5].setpage(6);INS[5].setunit(40);INS[6].setope ("移位"); INS[6].setpage(4);INS[6].setunit(53);INS[7].setope ("+");INS[7].setpage(5);INS[7].setunit(23);INS[8].setope ("存"); INS[8].setpage(1);INS[8].setunit(37);INS[9].setope ("取"); INS[9].setpage(2);INS[9].setunit(78);INS[10].setope ("+"); INS[10].setpage(4);INS[10].setunit(1);INS[11].setope ("存"); INS[11].setpage(6);INS[11].setunit(84);work*W =new work[7]; ifstream in("g://operate1.txt");long int p;int s;long int i;long int o;for(int jj=0;jj<7 ;jj++){in>>p;in>>s;in>>i;in>>o ;W[jj].setPage(p);W[jj].setsym(s);W[jj].setinum(i);W[jj].setonum(o);}diaodu(W,INS,12);}五．结果显示操作系统实验二〔第二题〕一．用先进先出〔FIFO〕九．程序清单/ 操作系统实验二.cpp : 定义控制台应用程序的入口点。

实验三内存页面置换算法的设计一、实习内容实现最近最久未使用（LRU）置换算法二、实习目的LINUX 中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行，还支持请求调页的存储管理方式。

当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU 发出缺中断），由系统将其所需页面调入内存。

这种页面调入方式叫请求调页。

当CPU 接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。

该程序通过查找页表，得到该页所在外存的物理块号。

如果此时内存未满，能容纳新页，则启动磁盘I/O 将所缺之页调入内存，然后修改页表。

如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。

利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。

整个页面的调入过程对用户是透明的。

本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。

三、实习题目实现最近最久未使用（LRU）置换算法[提示]：(1) 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

例如:分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，则缺页次数和缺页率按表3-1 给出:缺页次数: 15缺页率: 15/20=0.75(2) 假定分配给该进程的页块数为3，页面访问序列长度为20。

本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。

模拟程序的算法如图3-2。

四、源程序及程序中使用的数据结构、符号说明#include<iostream>#include<cstring>#include<vector>#include<cmath>#include<ctime>#include<cstdlib>#include<iomanip>using namespace std;void showState(int page[][20],int visit[][2],int t);int pick(int page[][20],int visit[][2],int time,int useTime[]); int min(int a,int b,int c);int main(){srand(time(NULL));int visit[20][2];memset(visit,-1,sizeof(visit));for(int i=0;i<20;i++)visit[i][0]=rand()%8;cout<<"20位长的随机访问序列为:"<<endl;for(int i=0;i<20;i++)cout<<setw(2)<<visit[i][0]<<" ";cout<<endl;int page[3][20];memset(page,-1,sizeof(page));int useTime[3];memset(useTime,0,sizeof(useTime));for(int t=0;t<20;t++){int p=pick(page,visit,t,useTime);//选中的页if(p<0){//命中第p+3页，设置此页命中，帧内容不变visit[t][1]=1;for(int x=0;x<3;x++)page[x][t]=page[x][t-1];useTime[p+3]=t;}else{// 此页不命中，帧内容替换visit[t][1]=0;if(t==0){page[p][t]=visit[t][0];}else{for(int y=0;y<3;y++)page[y][t]=page[y][t-1];page[p][t]=visit[t][0];}useTime[p]=t;}showState(page,visit,t);}int miss=0;for(int i=0;i<20;i++){if (visit[i][1]==0) miss++;}double per=1-(double)miss/20;int peri=per*100;cout<<"共miss"<<miss<<"/20次,"<<"命中率为" <<peri<<"%";return 0;}int pick(int page[][20],int visit[][2],int time,int useTime[]){//如果命中了，就返回下标-3，比如如果0帧命中，返回-3//如果不命中，选择一个最久没有访问到的帧，返回帧下标cout<<"输出usetime: ";cout<<useTime[0]<<" " <<useTime[1]<<" " <<useTime[2]<<" "<<endl;for(int i=0;i<3;i++){ //先遍历一遍，看有没有命中的if(page[i][time-1]==visit[time][0]){cout<<"time"<<time<<"此次要调度的页号"<<visit[time][0]<<"命中当前第"<<i<<"帧"<<endl;return i-3;}}for(int i=0;i<3;i++){//不存在命中，则从头开始选，先选帧空的情况if(page[i][time-1]==-1){cout<<"time"<<time<<"选中第"<<i<<"个空页" <<endl;return i;}}//都没有，就选最久没用过的int m=min(useTime[0],useTime[1],useTime[2]);cout<<"time"<<time<<"此次要调度的页号"<<visit[time][0]<<"选中第"<<m<<"个最久没有使用的页" <<endl;return m;}void showState(int page[][20],int visit[][2],int t){cout<<t<<"时刻访问状态"<<endl;cout<<"时间";for(int i=0;i<20;i++)cout<<setw(3)<<i<<" ";cout<<endl;cout<<"序列";for(int i=0;i<20;i++){cout<<setw(3)<<visit[i][0]<<" ";}cout<<endl;cout<<"零帧";for(int i=0;i<=t;i++){cout<<setw(3)<<page[0][i]<<" ";}cout<<endl;cout<<"一帧";for(int i=0;i<=t;i++){cout<<setw(3)<<page[1][i]<<" ";}cout<<endl;cout<<"二帧";for(int i=0;i<=t;i++){cout<<setw(3)<<page[2][i]<<" ";}cout<<endl;cout<<"命中";string str1="√";string str2="×";for(int i=0;i<=t;i++){string x=(visit[i][1]==1)? str1:str2;cout<<setw(3)<<x<<" ";}cout<<endl<<endl;}int min(int a,int b,int c){if(a<=b&a<=c) return 0;if(b<a&b<=c) return 1;if(c<a&c<b) return 2;}代码详细说明：在本例中，我设定了页面调度页块数为3，要访问的页面序列长度为20.从随机数获取20个访问的页面后进行页面调度算法，并将每次调度完的结果打印到控制台面板上，页面调度的具体算法为：维护一个useTime数组，其中存储着三个页块的上次使用时间，在每次向页块中调度内容/页块或页面访问命中页块时，更新被访问的页块的使用时间，如果页面访问不命中页块时，则选择useTime数组中最小的那一块，即最久没使用的页块，置换其中的内容。

实验项
目
名称
页式虚拟存储管理中地址转换和缺页中断
实验目的及要求1、深入了解页式存储管理如何实现地址转换。

2、进一步认识页式虚拟存储管理中如何处理缺页中断。

实验内容
编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。

实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所做工作进行测试。

假定内存64KB，每个内存块1024字节；作业最大支持到64KB，系统中每个作业分得内存块4块。

实验步骤
注：可根据实际情况加页。

请求页式管理缺页中断模拟设计--FIFO、OPT1.程设计目的与功能2.1 目的实现请求页式管理缺页中断FIFO、OPT算法，掌握页式存储管理系统的相关理论知识。

2.2 功能实现指定淘汰算法。

能够处理一下情形：2.2.1能够输入给作业分配的内存块数；2.2.2 能够输入给定的页面，并计算发生缺页的次数以及缺页率；2.2.3 缺页时，如果发生页面置换，输出淘汰的页号。

2.需求分析，数据结构或模块说明(功能与框图)2.1算法的原理描述:2.1.1先进先出页面置换（FIFO）FIFO法基本思想：选择在内存驻留时间最长的页将其淘汰。

FIFO 算法认为先调入内存的页不再被访问的可能性要比其他页大，因而选择最先调入内存的页换出。

2.1.2理想型淘汰页面置换算法（OPT）OPT法基本思想：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。

这样，淘汰掉该页将不会造成因需要访问该页而又立即把它调入的现象。

该算法无法实现，因为，它要求必须预先知道每一个进程的访问串。

2.2 本次课程设计中的算法流程图2.2.1 FIFO算法的流程图如下图所示：2.2.2 OPT算法的流程图如下图所示：3.源程序的主要部分3.1 程序中要到的全局变量说明#define M 40//最大的访问页面序列数目int N;//内存页面块数3.2 结构体说明struct Pro{int num;//num 记录页面序列号};3.3主函数说明及注释void main(){ cin>>N;// 请输入可用内存物理块数:";Pro p[M];//最大的访问页面序列数目Pro *page=new Pro[N];char c;int m=0,t=0;float n=0;int fifoout[M];//记录FIFO算法淘汰的页面int optout[M];//记录OPT算法淘汰的页面int f=0,o=0;m=Input(m,p);//m返回输入的访问页面总书目do{for(int i=0;i<N;i++){page[i].num=0;//初试化内存页面}i=0;cout<<"****请选择页面置换的(f代表FIFO,o代表OPT)****策略"<<endl;cout<<"f:FIFO页面置换"<<endl;cout<<"o:OPT页面置换"<<endl;cout<<"其他键退出"<<endl;cin>>c;if(c=='f')//FIFO页面置换{n=0;cout<<"******FIFO页面置换算法运行结果如下:******"<<endl;cout<<"FIFO页面置换情况为: "<<endl;while(i<m)//i为当前页面在输入序列中的位置{if(Search(p[i].num,page)>=0)//判断当前输入页面p[i].num 是否已经在内存中,若在则返回其在内存页面块中的位置{i++;//找到相同的页面}else{if(t==N)//N为内存页面数目，t记录是那个页面最先进入内存页面，用来判断内存页面块是否已满t=0;else{n++;//记录缺页次数fifoout[f]=page[t].num;//记录淘汰页面f++;page[t].num=p[i].num;//换入print(page);//输出当前内存页面分配情况t++;}}}cout<<"采用FIFO算法时依次淘汰的页面为：";for(i=0;i<f;i++)//输出淘汰页面号{if(fifoout[i]==0)continue;elsecout<<fifoout[i]<<" ";}cout<<"采用FIFO算法时的缺页次数为："<<n<<endl;cout<<"采用FIFO算法时的缺页率为: "<<(double)n/m<<endl;}if(c=='o')//OPT算法页面置换情况{n=0;cout<<"******OPT页面置换算法运行结果如下:******"<<endl;cout<<"OPT页面置换情况为: "<<endl;int count=0;while(i<m)//i为当前页面在输入序列中的位置{if(Search(p[i].num,page)>=0)//判断当前输入页面p[i].num 是否已经在内存中,若在则返回其在内存页面块中的位置{i++;}else{count++;if(count<=N)//判断内存页面是否有空空闲页面{page[count-1].num=p[i].num;//进入空闲内存n++;print(page);continue;}int temp=0,cn;for(t=0;t<N;t++)//t记录是那个页面最先进入内存页面{if(temp<Compfu(page,i,t,p))//在以后不回访问内存{temp=Compfu(page,i,t,p);cn=t;}}optout[o]=page[cn].num;//输出淘汰页面o++;page[cn].num=p[i].num;//页面置换n++;print(page);i++;}}cout<<"采用OPT算法时依次淘汰的页面为：";for(i=0;i<o;i++){if(optout[i]==0)continue;elsecout<<optout[i]<<" ";}cout<<"采用OPT算法时的缺页次数为："<<n<<endl;cout<<"采用OPT算法时的缺页率："<<(double)n/m<<endl;}else{exit;}}while(c=='f'||c=='o');}3.4输入函数Input(int m,Pro p[M])int Input(int m,Pro p[M]){ cout<<"请输入访问页面目数：";do{cin>>m;//访问页面数目if(m>M)cout<<"数目太多，请重试"<<endl;elsebreak;}while(1);cout<<"请输入访问页面号序列:";for(int i=0;i<m;i++){cin>>p[i].num;//依次输入页面访问顺序}return m;//返回输入的访问页面总数目}3.5输出函数print(Pro *page1)void print(Pro *page1)//输出当前内存块中的访问页面{Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)cout<<page[i].num<<" ";cout<<endl;}3.6 Search(int e,Pro *page1 ) 函数int Search(int e,Pro *page1 )// 用于查找当前页面是否已在内存块中{Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)if(e==page[i].num)return i;//返回页面号为e的页面在那个内存页面中return -1;//若不在则返回-1}3.7 Compfu(Pro *page1,int i,int t,Pro p[M]) 函数int Compfu(Pro *page1,int i,int t,Pro p[M])//i为当前页面在输入序列中的位置，t记录页面进入内存的顺序,此函数判断内存快中的页面page[t]在后续访问序列中出现的次数{Pro *page=new Pro[N];page=page1;int count=0;//记录当前页面的未来访问的次数for(int j=i;j<M;j++)//{if(page[t].num==p[j].num )break;//页面已经在内存中else count++;}return count;//返回当前页面在未来还要出现的次数}4、测试用例，运行结果与运行情况分析4.1测试用例设计4.1.1用例1设计：内存物理块数：N=3页面引用序列中总页面个数为：m=12页面引用序列为：4、3、2、1、4、3、5、4、3、2、1、54.1.2用例2设计：内存物理块数：N=4页面引用序列中总页面个数为：m=15页面引用序列为：3、7、4、8、3、1、6、7、8、3、1、2、9、3、5 4.2运行结果及运行情况分析4.2.1测试用例1运行结果如下：4.2.1.1 FIFO算法的运行结果：缺页率＝缺页次数/ 总访问次数＝9 / 12＝75%依次淘汰的页面号为：4、3、2、1、4、34.2.1.2 OPT算法的运行结果为：缺页率＝缺页次数/ 总访问次数＝7 / 12＝58.33%依次淘汰的页面号为：2、1、4、24.2.2测试用例2运行结果如下：4.2.2.1 FIFO算法运行结果如下：缺页率＝缺页次数/ 总访问次数＝12/ 15＝80%依次淘汰的页面号为：3、7、4、8、1、6、7、3 4.2.2.2 OPT算法运行结果缺页率＝缺页次数/ 总访问次数＝10/ 15＝66.67%以此淘汰的页面号为：4、1、7、4、2、35、自我评价与总结本周我们进行了《操作系统》的课程设计，在拿到题目以后便着手准备，通过查阅课本和相关的资料，对本次课程设计要实现的功能有了深刻的了解，在此基础上写起实验代码变得心应手。

课程设计名称：操作系统题目：页式存储管理中页面置换（淘汰）的模拟程序目录一、概述 (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）提供良好图形界面，同时能够展示四个算法运行的结果。

实验报告院（系）：专业班级：学号:姓名:实验地点:实验日期:课程名称实验项目名称实验学时实验类型计算机操作系统页面调度算法 2 验证型一、实验目的及要求通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页面替换算法的具体实现方法。

二、实验环境PC /Windows系统/Visual C++6.0三、实验内容①实现三种算法：先进先出；OPT；LRU②页面序列从指定的文本文件（TXT文件）中取出③输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数四、实验步骤1．先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

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

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

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

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

4、流程图如下图所示：五、调试过程 程序结构分析：程序共有以下九个部分：int findSpace(void);//查找是否有空闲内存int findExist(int curpage);//查找内存中是否有该页面开始 取一条指令取指令中访问的页号=>L查 页 表页标记=1？形成绝对地址是“存”指令？置L 页修改标记“1”输出绝对地址输出“*页号”有后继指令？取一条指令结 束J:=P[k]J 页的修改标记输出“OUTj ”输出“INL ”P[k]:=L k:=(k+1) mod m修改页面是否是 否否（产生缺页中断）是否int findReplace(void);//查找应予置换的页面void display(void);//显示void FIFO(void);//FIFO算法void LRU(void);//LRU算法void OPT(void);//OPT算法；void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示int main() //主程序六、实验结果及分析程序源代码：#include <iostream.h>#define Bsize 3#define Psize 20struct pageInfor{int content;//页面号int timer;//被访问标记};class PRA{public:PRA(void);int findSpace(void);//查找是否有空闲内存int findExist(int curpage);//查找内存中是否有该页面int findReplace(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){int QString[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(int curpage){for(int i=0; i<Bsize; i++)if(block[i].content == page[curpage].content)return i;//找到内存中有该页面，返回BLOCK中位置return -1;}int PRA::findReplace(void){int pos = 0;for(int i=0; i<Bsize; i++)if(block[i].timer >= block[pos].timer)pos = i;//找到应予置换页面，返回BLOCK中位置return pos;}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){int exist,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){int exist,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){int exist,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 kangyan(1318064008)---|"<<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选择运行LRU算法的置换<—初始化信息：3个页块，20个页面号引用串<—存入前三个页，有空闲内存，无需置换<—3，4页已经在内存中无需再写入<—因为3是最久的页面所以将其置换下面原理相同<—所有命中的页面数<—命中率0.5七、总结页面置换算法的思想可以说比较简单，易懂，但是在实现的时候，也遇到了很多的问题，比如说在找空闲物理块的时候，起初我是比较物理块是否等于0，若为0，则直接把页面放入，后来发现不论什么时候都是把0替换出去，才恍然大悟，既然页面标号有0，就不能用0来表示空闲物理块，后来就换成用-1来表示物理块空闲了。

实验内容：
此实验模拟页式虚拟存储管理中硬件的地址转换和采用先进先出算法（FIFO）的缺页中断处理。

地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图1所示(模拟实验中假定主存64KB，每个主存块1024字节，即n=10,m=16，物理地址中块号6位，块内地址10位；作业最大64KB，即m=16，逻辑地址中页号6位，页内地址10位)。

在模拟实验中页表格式如图2所示。

模拟实验执行一条指令时，不模拟指令的执行，只是考虑执行是否修改页面，若修该页面，则将页面的页表中修改标志置为“1”，然后输出转换后的物理地址，并输出物理地址来表示一条指令的完成；如果访问的页不存在时，则产生缺页中断，往后直接转去缺页中断处理，最后模拟中断返回，就是返回重新进行地址转换。

一条指令执行的模拟流程图如图4所示。

模拟程序中首先手工输入页表信息，创建该作业的页表；然后循环执行假定的指令，观察地址转换情况。

模拟程序的完整流程图如图5所示。

THANKS !!!
致力为企业和个人提供合同协议，策划案计划书，学习课件等等
打造全网一站式需求
欢迎您的下载，资料仅供参考
-可编辑修改-。