面置换算法模拟试验报告

1、实验编号 名称 页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便： 1、了解虚拟存储技术的特点 2、掌握请求页式存储管理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区，并使用FIFO 和 LRU算法计算访问命中率。先用 srand() 函数和 rand() 函数定义和产生指令序列， 然后将指令序列变换成相应的页 地址流，并针对不同的算法计算相应的命中率。instruction 320/ 共 320 条指令_vp 32/ 虚存页共 32 页50/ 访问次数清零周期#include /Windows 版，随机函数需要，GetCurrentProcessId()需

2、要/#include /Linux版，随机函数 srand和 rand 需要#include /printf()需要#define TRUE 1#define FALSE 0#define INVALID1#define NULL 0typedef struct/ 定义页表结构类型(页面映射表PMT)int pn, pfn, counter, time;/ 页号、页框号(块号) 、一个周期内访问该页面的次数、访问时间PMT;PMT pmt32;/ 页面控制结构typedef struct pfc_structint pn, pfn; struct pfc_struct *next;pfc_ty

3、pe; 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 );/ 最近最不经

4、常使用/*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

5、) 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;

6、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 和 pfc

7、i 之间的连接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

8、;busypf_head=p;p=freepf_head-next; / 按 FIFO 方式调新页面入内存 freepf head-next=NULL;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(freep

9、f_head=NULL)/ 无空闲页面min=32767;for(j=0;jpmtj.time&pmtj.pfn!=INVALID) min=pmtj.time;minj=j;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; / 更新该页面的访问时间(并非真的时 间，而是循环次

10、数，每执行一条指令，时间加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) / 无空闲页面elsedp+

11、;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+)总结（收获，未实现的步骤）这次操作系统课程设计， 让我们对操作系统有了更深的认识， 首先操作系统是一管理电脑硬 件与软件资源的程序， 同时也是计算机系统内核与基石。 操作系统是一个庞大的管理控制程 序，大致包括 5 个方面的管理功能：进程与处理机管理

12、、作业管理、 存储管理、 设备管理、 文件管理。 我们这次课程设计的题目是页面置换算法， 是属于存储器管理。 在进程运行过程中，若其访问的页面不在内存而需把它们调入内存， 但内存以无空闲空间时， 为了保证该进程能正常的运行， 系统必须从内存中调出一页程序或 数据送磁盘的兑换区中， 但应将哪个页面调出，需根据一定的算法来确定。 通常， 把选择换 成页面的算法称为页面置换算法。 通过本次课程设计， 我们对页面置换算法的了解更加的 深刻。主要有以下置换算法： OPT （最佳置换算法） 、FIFO（先进先出置换算法） 、LRU（最 近最久未使用算法） 。每种算法都有各自的优缺点， OPT 算法是实际中不能实现的，但是可 以利用该算法去评价其它算法； FIFO 算法与进程实际运行的规律不相适用，因为在进程中， 有些页面经常被访问； LRU算法是根据页面调入内存后的使用情况进行决策的。在这次课程设计中， 遇到了一些困难， 例如怎么实现各种算法， 如何进行函数调用及对数据的限制操 作等，在遇到这些困难的时候，我们会去查阅资料，仔细看书，尝试用不同的方法解决，在 各种方法中选择一种最好的方法，有的时候会碰到不知道如何实现的函数，我们会查看 MSDN，这次是用的 +语言做的， 每一步都是自己独立完成的，