页面置换算法模拟实验报告.doc

精品文档实验编号 名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便：1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区，并使用FIFO和LRU算法计算访问命中率。先用srand()函数和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。#include /Windows版，随机函数需要，GetCurrentProcessId()需要/#include /Linux版，随机函数srand和rand需要#include /printf()需要#define TRUE 1#define FALSE 0#define INVALID -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 pmt32;typedef struct pfc_struct/页面控制结构int pn, pfn;struct pfc_struct *next;pfc_type;pfc_type pfc32;pfc_type *freepf_head,*busypf_head,*busypf_tail;/空闲页头指针，忙页头指针，忙页尾指针int NoPageCount; /缺页次数int atotal_instruction;/指令流数组int pagetotal_instruction, offsettotal_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;itotal_instruction;i+=4)/产生指令队列if(s319)printf(when i=%d,error,s=%dn,i,s);exit(0);ai=s;/任意选一指令访问点m。（将随机数作为指令地址m）ai+1=ai+1;/顺序执行下一条指令ai+2=rand()%(s+2);/在0，m+1的前地址之间随机选取一地址，记为mai+3=ai+2+1;/顺序执行一条指令s = ai+2 + (int)rand()%(320-ai+2);/在m，319的指令地址之间随机选取一起点mif(ai+2318)|(s319) printf(a%d+2,a number which is:%d and s=%dn,i,ai+2,s);for(i=0;itotal_instruction;i+)/将指令序列变成页地址流pagei=ai/10;offseti=ai%10;for(i=4;i=32;i+)/内存块分别为4块、5块、.32块时的命中率printf(%2d page frames,i);FIFO(i);/计算用FIFO置换时，有i个内存块时的命中率LRU(i);/最近最久未使用NRU(i);/最近最不经常使用printf(n);/* initialize() 形参：内存块数 功能：初始化*/void initialize(int total_pf)/初始化相关数据结构，形参total_pf是用户进程的内存页面数int i;NoPageCount=0;/缺页次数，初始化为0for(i=0;itotal_vp;i+)pmti.pn=i;/填逻辑页号pmti.pfn=INVALID;/物理页面号为-1pmti.counter=0;/置页面控制结构中的访问次数为0pmti.time=-1;/置页面控制结构中的时间为-1for(i=0;itotal_pf-1;i+)/建立pfci-1和pfci之间的连接pfci.next=&pfci+1;pfci.pfn=i;pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/页面队列的头指针为pfc0/* FIFO算法 形参：内存块数 输出：命中率*/void FIFO(int total_pf)/形参total_pf是用户进程的内存页面数int i;pfc_type *p;initialize(total_pf);/初始化相关数据结构busypf_head=busypf_tail=NULL;for(i=0;inext;pmtbusypf_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=pagei;pmtpagei.pfn=freepf_head-pfn;if(busypf_tail=NULL) busypf_head=busypf_tail=freepf_head;elsebusypf_tail-next=freepf_head;/free页面减少一个busypf_tail=freepf_head;freepf_head=p;printf( FIFO: %6.4f,1-(float)NoPageCount/320);/* LRU算法（最近最久未使用） 形参：内存块数 输出：命中率*/void LRU(int total_pf)/形参total_pf是给用户进程的内存块数int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i+)if(pmtpagei.pfn=INVALID)/页面失效NoPageCount+;if(freepf_head=NULL)/无空闲页面min=32767;for(j=0;jpmtj.time&pmtj.pfn!=INVALID)min=pmtj.time;minj=j;freepf_head=&pfcpmtminj.pfn;/腾出一个单元pmtminj.pfn=INVALID;pmtminj.time=-1;freepf_head-next=NULL;pmtpagei.pfn=freepf_head-pfn;/有空闲页面，改为有效pmtpagei.time=present_time;freepf_head=freepf_head-next;/减少一个free页面else pmtpagei.time=present_time;/更新该页面的访问时间（并非真的时间，而是循环次数，每执行一条指令，时间加1）present_time+;/当前时间加1printf( LRU: %6.4f,1-(float)NoPageCount/320);/* NRU算法（最近最不经常使用） 形参：内存块数 输出：命中率*/void NRU(int total_pf)int i,j,dp,cont_flag,old_dp;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+)if(pmtpagei.pfn=INVALID)/缺页NoPageCount+;if(freepf_head=NULL) /无空闲页面cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pmtdp.counter=0&pmtdp.pfn!=INVALID)cont_flag=FALSE;elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;jnext=NULL;pmtpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;elsepmtpagei.counter=1;if(i%clear_period=0)for(j=0;jtotal_vp;j+)pmtj.counter=0;printf( NUR: %6.4f,1-(float)NoPageCount/320);实验结果（写出结果，截图也可）总结（收获，未实现的步骤）这次操作系统课程设计，让我们对操作系统有了更深的认识，首先操作系统是一管理电脑硬件与软件资源的程序，同时也是计算机系统内核与基石。操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能：进程与处理机管理、作业管理、存储管理、设备管理、文件管理。我们这次课程设计的题目是页面置换算法，是属于存储器管理。 在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出，需根据一定的算法来确定。通常，把选择换成页面的算法称为页面置换算法。 通过本次课程设计，我们对页面置换算法的了解更加的深刻。主要有以下置换算法： OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用算法）。每种算法都有各自的优缺点，OPT算法是实际中不能实现的，但是可以利用该算法去评价其它算法；FIFO算法与进程实际运行的规律不相适用，因为在进程中，有些页面经常被访问；LRU算法是根据页面调入内存后的使用情况进行决策的。 在这次课程设计中，遇到了一些困难，例如怎么实现各种算法，如何进行函数调用及对数据的限制操作等，在遇到这些困难的时候，我们会去查阅资料，仔细看书，尝试用不同的方法解决，在各种方法中选择一种最好的方法，有的时候会碰到不知道如何实现的函数，我们会查看MSDN，这次是用的+语言做的，每一步都是自己独立完成的，这次课程设计我最大的收获