操作系统页面置换

1、西安文理学院软件学院操作系统课程设计报告设计名称： 操作系统课程设计 设计题目： 页面置换算法 学生学号： 1402120110 专业班级： 信息系统开发1班 学生姓名： 杜倩 学生成绩： 指导教师（职称）： 孙少波 课题工作时间： 2014.10.27 至 2014.12.1 说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩由指导教师实施。4、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另

2、行规定。5、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。软件学院课程设计任务书学生姓名杜倩学号1402120110专业班级信息系统开发1班设计题目页面置换算法内容概要： 系统采用环境为Visual Studio2012 ，采用c语言程序编写，程序包含页面置换算法中 （1）先进先出页面置换算法（FIFO） （2）最近最久未使用页面置换算法（LRU） （3）最佳置换页面置换算法（OPT）文献资料： 1严蔚敏 吴伟民 数据结构 清华大学出版社 2005 2谭浩强. C语言程序设计. 清华大学出版社, 2005 3于帆, 赵妮. 程序设计基础(C语言版). 清华大学出版社

3、, 2006 4汤小丹, 梁红兵, 哲凤屏, 汤子瀛. 计算机操作系统. 西安电子科技大学出版社, 2014设计要求： 编程实现： （1）先进先出页面置换算法（FIFO） （2）最近最久未使用页面置换算法（LRU） （3）最佳置换页面置换算法（OPT）设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。演示页面置换的三种算法。通过随机数产生一个指令序列，将指令序列转换成为页地址流。计算并输出各种算法在不同内存容量下的命中率。工作期限：设计工作自2011年10月27日至2014年12月1日止。指导教师： 院长： 日 期：2013年12月9日软件学院课程设计进度

4、安排表学生姓名： 学号： 专业： 班级： 起止日期内 容备注12月9日下达任务书，制定进度安排计划 12月10日12月12日系统整体设计和详细设计12月13日12月17日系统编码实现12月18日12月19日系统测试 12月20日12月23日撰写课程设计报告 12月25日演示软件和答辩 指导教师签名： 2013年12月11日成绩评定表学生姓名： 学号： 专业： 班级： 类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师

5、提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分 指导教师： （签字） 日期：2013 年12

6、月 25 日摘 要摘要：介绍操作系统内存调度的算法的概念原理和实验方法，页面置换算法有先进先出，最近最久未使用，最佳置换。使用c语言编写程序实现程序的几种算法，并在vs2012的环境中运行实现，要求实现的功能为通过随机数产生指令，转换为页地址流，计算访问的命中率。关键词：页面置换,FIFO,LRU,OPT西安文理学院软件学院 课程设计报告目 录目 录I第一章 课题背景（或绪论、概述）11.1 课程设计背景11.2 课程设计实现功能1第二章 设计简介及设计方案论述22.1 任务目标（三号字 黑体）22.2 开发设计思想32.3 实现功能3第三章 详细设计43.1 模板设计图43.2 函数模块，程

7、序流程53.2.1先进先出页面置换算法（FIFO）53.2.2最近最久未使用页面置换算法（LRU）63.2.3最佳置换页面置换算法（OPT）7第四章 设计结果及分析84.1 运行8总结10参考文献11附录12- 7 - 第一章 课题背景（或绪论、概述）1.1 课程设计背景随着硬件技术的发展，各式各样的大容量存储设备相继出现，一台计算机上可能存在多种外存储设备。不同存储设备有着不同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写速度的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性能会有很大的提高。1.2 课程设计实现功能 （1）先进先出页面置换算法（FI

8、FO） （2）最近最久未使用页面置换算法（LRU） （3）最佳置换页面置换算法（OPT） 第二章 设计简介及设计方案论述2.1 任务目标（三号字 黑体）1.用c语言编写FIFO,LRU,OPT三种页面置换算法2.掌握内存调度算法的概念原理和实现方法3.计算并输出各种算法在不同内存容量下的命中率2.2 开发设计思想2.3 实现功能编写程序实现： （1）先进先出页面置换算法（FIFO） （2）最近最久未使用页面置换算法（LRU） （3）最佳置换页面置换算法（OPT） 第三章 详细设计3.1 模板设计图3.2 函数模块，程序流程3.2.1先进先出页面置换算法（FIFO）是用队列存储内存中的页面，队列

9、的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组timemSIZE记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。3.2.2最近最久未使用页面置换算法（LRU） 是用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组flag10标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。3.2.3最佳置换页面置换算法（OPT） 是用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块

10、中的页面。数组nextmSIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。第四章 设计结果及分析4.1 运行 总结 通过这次页面置换模拟实验，我对操作系统这门课程有了更加深刻的了解，自己的编程能力有了一定的提高。把书中的理论知识和实践相结合，使我的知识水平在原有的基础上有了一定的进步，能够熟练的掌握一些关于内存分配管理的一些算法。而在实现FIFO算法后，由于没能掌握LRU算法的过程导致实现时花了很多时间。在调试的过程中也出现的大多是关于内存分配和数组地址越界的问题，比如关于循环时各个数的递增，还有就是显示给个数组的内容

11、等问题。就因为这些问题，多次造成了淘汰序列出错。 理论上，三种替换算法的命中率由高到底排列应该是OPT>LRU>FIFO。实际上，从实验数据观测得到，存在这种由高到低的趋势，由page=4时可以观测到，但是效果不是很明显。一开始做这个实验时，首先是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺点和相互之间衍生互补关系。这三个算法中，难以实现的是LRU算法，因为它涉及到访问时间的计算，而且它的开销也比较大。OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。而FIFO实现起来比较容易，FIFO算法保持先进先出，因此需要一个先进先出队列。 这次实验大大提高了

12、我的分析能力、编程能力和综合能力，找出并改正了自己的许多错误与不足之处，为在毕业后在就业市场上提高自己的竞争力打下了坚实的基础。 参考文献1严蔚敏 吴伟民 数据结构 清华大学出版社 20052谭浩强. C语言程序设计. 清华大学出版社, 20053于帆, 赵妮. 程序设计基础(C语言版). 清华大学出版社, 2006 4汤小丹, 梁红兵, 哲凤屏, 汤子瀛. 计算机操作系统. 西安电子科技大学出版社, 2014 附录#include <stdio.h>#include <stdlib.h>#include <string.h>#ifndef _UNISTD_

13、H#define _UNISTD_H#include <IO.H>#include <PROCESS.H>#endif#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流长#define total_vp 32 /虚页长#define clear_period 50 /清周期typedef struct /页面结构 int pn,/页面序号pfn,/页面所在内存区的帧号counter,/单位时间内访问次数time;/上次访问的时间pl_type;pl_type

14、pltotal_vp; /页面结构数组struct pfc_struct /页面控制结构 int pn,/页面号 pfn;/内存区页面的帧号 struct pfc_struct *next;/页面指针，用于维护内存缓冲区的链式结构;typedef struct pfc_struct pfc_type; /主存区页面控制结构别名pfc_type pfctotal_vp, /主存区页面控制结构数组*freepf_head, /主存区页面控制结构的空闲页面头指针*busypf_head, /主存区页面控制结构的忙页面头指针*busypf_tail; /主存区页面控制结构的忙页面尾指针int dise

15、ffect; /页错误计数器，初次把页面载入主存时也当做页错误int atotal_instruction; /随即指令流数组int pagetotal_instruction; /指令对应的页面号int offsettotal_instruction; /指令所在页面中的偏移量int initialize(int);/初始化页面结构数组和页面控制结构数组int FIFO(int);/先进先出算法int LRU(int);/最近最久未使用算法int OPT(int);/最佳置换算法/*int CLOCK(int);/简单时钟(钟表)算法*/int main( ) int s;/随机数inti;

16、 srand(10*getpid(); /*每次运行时进程号不同，用来作为初始化随机数队列的"种子"*/ s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf("n-随机产生指令流-n"); for (i=0; i<total_instruction; i+=4) /产生指令队列 ai=s; /任选一指令访问点m ai+1=ai+1; /顺序执行一条指令 ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0); /执行前地址指令m'

17、; ai+3=ai+2+1; /顺序执行一条指令 printf("%6d%6d%6d%6dn", ai,ai+1,ai+2,ai+3); s = (int)(float)(total_instruction-1)-ai+2)*(rand()/(RAND_MAX+1.0) + ai+2; printf("-n");for (i=0;i<total_instruction;i+) /将指令序列变换成页地址流 pagei=ai/10; offseti=ai%10; printf("n-不同页面工作区各种替换策略的命中率表-n"); p

18、rintf("Paget FIFOt LRUt OPTn"); for(i=4;i<=32;i+) /用户内存工作区从个页面到个页面 printf(" %2d t",i); FIFO(i); LRU(i); OPT(i); printf("n"); return 0;/初始化页面结构数组和页面控制结构数组/total_pf; 用户进程的内存页面数int initialize(int total_pf) int i; diseffect=0; for(i=0;i<total_vp;i+)pli.pn=i;pli.pfn=IN

19、VALID; /置页面所在主存区的帧号为-1.表示该页不在主存中pli.counter=0;/置页面结构中的访问次数为pli.time=-1;/置页面结构中的上次访问的时间为-1for(i=0;i<total_pf-1;i+)pfci.next=&pfci+1; /建立pfci-1和pfci之间的链接pfci.pfn=i; /初始化主存区页面的帧号pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/主存区页面控制结构的空闲页面头指针指向pfc0return 0;/最近最久未使用算法

20、/int total_pf; 用户进程的内存页面数int LRU (int total_pf) int MinT;/最小的访问时间，即很久没被访问过int MinPn;/拥有最小的访问时间的页的页号int i,j;int CurrentTime;/系统当前时间 initialize(total_pf);/初始化页面结构数组和页面控制结构数组 CurrentTime=0;diseffect=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /页面失效diseffect+;/页错误次数加 if(freepf_head=NULL)

21、 /无空闲页面 MinT=100000; for(j=0;j<total_vp;j+) /找出time的最小值，表明该页很久没被访问过 if(MinT>plj.time&&plj.pfn!=INVALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn; /最久没被访问过的页被释放 plMinPn.pfn=INVALID; /最久没被访问过的页被换出主存 plMinPn.time=-1;/最久没被访问过的页的访问时间置为无效 freepf_head->next=NULL; plpagei.pfn

22、=freepf_head->pfn; /有空闲页面,把相应的页面换入主存，并把pfn改为相应的帧号 plpagei.time=CurrentTime;/令访问时间为当前系统时间 freepf_head=freepf_head->next; /减少一个空闲页面elseplpagei.time=CurrentTime; /命中则刷新该单元的访问时间CurrentTime+; /系统当前时间加 printf("%6.3ft",1-(float)diseffect/320);return 0;/最佳置换算法/int total_pf; 用户进程的内存页面数int OPT

23、(int total_pf)int i,j;int MaxD;/将来最近一次访问的距离的最大值（以时间单元度量）int MaxPn;/将来最近一次访问的距离的最大值的页号int dis;/距离计数器int disttotal_vp;/距离数组，保存距离上一次访问的时间差距个数initialize(total_pf);/初始化页面结构数组和页面控制结构数组diseffect=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)/页面失效diseffect+;/页错误次数加if(freepf_head=NULL)/无空闲页面for(

24、j=0;j<total_vp;j+)if(plj.pfn!=INVALID)/如果该页在主存中distj=100000;/ 该页关联的距离值改为最大值elsedistj=0;/如果不在该页主存中，该页关联的距离值改为dis=1;/初始距离值为for(j=i+1;j<total_instruction;j+) /从要替换的指令的下一条算起，if(plpagej.pfn!=INVALID &&plpagej.counter=0)/如果该页在主存中,并且是将要最近访问的页/if(plpagej.pfn!=INVALID && distpagej=10000

25、0) /此条语句原理与上相同distpagej=dis;/距离值改为displpagej.counter=1;/使访问次数标志加，区别第一次访问和第二次访问dis+;MaxD=-1;for(j=0;j<total_vp;j+)plj.counter=0;/重置访问次数为if(MaxD<distj)/查找将来最近一次访问的距离的最大值及其序号MaxD=distj;MaxPn=j;freepf_head=&pfcplMaxPn.pfn; /替换将来一段时间最久访问的页freepf_head->next=NULL;plMaxPn.pfn=INVALID;plpagei.pfn=freepf_head->pfn; /把当前页换入主存中，并且把当前页的pfn改为换入页的帧号，freepf_head=freepf_head->next; /减少一个空闲页面/if/forprintf(&qu