《操作系统》实验五：页面置换算法模拟(6页).doc

-操作系统实验五：页面置换算法模拟-第 6 页 实验五. 请求页式存储管理的模拟实验内容:熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法-最近最久未使用算法（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 pageframe10; / 分配的页框int pagehistory10; /记录页框中数据的访问历史int rpoint; /页面替换指针int inpflag; /缺页标志，0为不缺页，1为缺页struct PageInfo /页面信息结构 int serial100; / 模拟的最大访问页面数，实际控制在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.seriali=-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.seriali=(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.seriali); if (i+1) % 10 =0) printf("n"); /每行显示10个 printf("n=n"); printf("访问%3d : 内存<",pf_info.serialvpoint); for(n=0;n<pf_info.total_pf;n+) / 页框信息 if (pageframen >=0) printf("%3d",pageframen); else printf(" "); printf(" >"); if(inpflag=1) /缺页标志，0为不缺页，1为缺页 printf(" =>缺页 "); printf("缺页率%",(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+) pagehistoryn +; / 访问历史加1for(n=0;n<pf_info.total_pf;n+) if (pageframen=page ) inpflag=0 ; /inpflag缺页标志，0为不缺页，1为缺页 pagehistoryn=0; /置访问历史为0 return 1;inpflag=1; /页面不存在，缺页 return 0; / FIFO页面置换算法void fifo(void) int n,count,pstate; rpoint=0; / 页面替换指针初始化为0 invalidcount = 0; / 缺页数初始化为0 createps(); / 随机生成访问序列 count=0; / 是否装满是所有的页框 for(n=0;n<pf_info.total_pf;n+) / 清除页框信息 pageframen=-1; inpflag=0; /缺页标志，0为不缺页，1为缺页 for(vpoint=0;vpoint<pf_info.total_pn;vpoint+) / 执行算法 pstate=findpage(pf_info.serialvpoint); /查找页面是否在内存 if(count<pf_info.total_pf) / 开始时不计算缺页if(pstate=0) / 页不存在则装入页面pageframerpoint=pf_info.serialvpoint;rpoint=(rpoint+1) % pf_info.total_pf;count+; else / 正常缺页置换 if(pstate=0) / 页不存在则置换页面 pageframerpoint=pf_info.serialvpoint;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; / 缺页次数初始化为0 createps(); / 随机生成访问序列 count=0; / 是否装满所有的页框 for(n=0;n<pf_info.total_pf;n+) pageframen=-1; / 清除页框信息 pagehistoryn=0; / 清除页框历史 inpflag=0; /缺页标志，0为不缺页，1为缺页 for(vpoint=0;vpoint<pf_info.total_pn;vpoint+) / 执行算法 pstate=findpage(pf_info.serialvpoint); /查找页面是否在内存 if(count<pf_info.total_pf) / 开始时不计算缺页 if(pstate=0) / 页不存在则装入页面pageframerpoint=pf_info.serialvpoint; /把要调入的页面放入一个空的页框里rpoint=(rpoint+1) % pf_info.total_pf;count+; else / 正常缺页置换 if(pstate=0)/ 页不存在则置换页面 max=0; for(n=1;n<pf_info.total_pf;n+) if(pagehistoryn>pagehistorymax) max=n; rpoint=max; pageframerpoint=pf_info.serialvpoint; pagehistoryrpoint=0; pf_info.diseffect+; / 缺页次数加1 Sleep(10); displayinfo(); / 显示当前状态 / 置换算法循环结束 _getch(); return;/最佳置换算法 自己完成/ 主函数int main() char ch; system("cls") ; while ( true ) printf("*n"); printf(" 若要执行FIFO页面置算法请按1n");printf(" 若要执行LRU 页面置算法请按2n"); printf(" 若要退出请按3n") ; printf("*n"); printf( "Enter your choice (1 or 2 or 3): "); do /如果输入信息不正确，继续输入 ch = (char)getch() ;while(ch != '1' && ch != '2'&& ch != '3'); printf("nn你按的是：%c ,现在为你执行对应操作。",ch); if(ch = '3') /选择3，退出 return 0;else if(ch = '1') /选择1，FIFO printf("nn-*执行FIFO算法*-n"); fifo(); else printf("nn-*执行LRU算法*-n"); /lru();system("cls") ; printf("nnPress Any Key To Continue:"); getch() ; return 0;