操作系统页面置换算法.docx

哈尔滨理工大学课　程　设　计（操作系统）题　　目：　页式虚拟存储管理FIFO、LRU和OPT页面置换算法班　　级： 计算机科学与技术学院 计13-9班姓　　名：　　　 刘骐郡-1304010910指导教师：　　　　　 孙冬璞系主任： 林克正2016年03月10日目 录1 需求分析 2 1.1 目的和要求 2 1.2 研究内容 2 2 概要设计 2 2．1 FIFO算法 3 2．2 LRU算法 3 2．3 OPT算法 3 2．4 输入新的页面引用串 3 3 详细设计 4 3．1 FIFO（先进先出）页面置换算法： 43．2 LRU（最近最久未使用）置换算法： 4 3．3 OPT（最优页）置换算法 4 4 测试 5 5 运行结果 56 课程设计总结 10页式虚拟存储管理FIFO、LRU和OPT页面置换算法1?需求分析??1.1?目的和要求?在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础?。1.2?研究内容?模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU（最近最久未使用）和OPT（最长时间不使用）），并通过比较性能得出结论。?前提：?（1）页面分配采用固定分配局部置换。?（2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以从文件读入。?（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。2?概要设计?本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、应用OPT算法和页面引用串的插入。2．1??FIFO算法?该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO算法处理之后的结果。??2．2?LRU算法?该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU算法处理之后的结果。?2．3??OPT算法?该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT算法处理之后的结果。?2．4??输入新的页面引用串?该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是0?0?0?0?0?0?0?0?0?0?0?0?0?0?0?0?0?0?0?0，用户可以自定义全新的20个数字页面引用串。3??详细设计?在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。???一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。??3．3?OPT（最优页）置换算法?最优页置换算法是所有算法中产生页错误率最低的，而且绝对没有Belady异常的问题。它会置换最长时间不会使用的页。最优页（OPT）置换算法，是根据最长时间不会使用的页来决策的。这就意味着，需要注意内存中的页面和页面的距离了。因此OPT算法是选择最久未使用的页面进行淘汰的。该算法赋予内存中每个页面一个访问字段，用来记录距离此处的最近页面的距离，这样通过比较，就能把最久未使用的页面淘汰掉。代码：#includeiostream.h?#includestdlib.h?const?int?Nsize=10;?const?int?Psize=20;?typedef?struct?page?{??int?yemian;//页面号??int?biaoji;//被访问标记?}page;?/*?页面逻辑结构，结构为方便算法实现设计*/???page?block[Nsize];//物理块?page?page[Psize];//页面号串??void?Init(int?QString[],int?Nsize)?{//初始化内存单元、缓冲区???for(int?i=0;?iNsize;?i++)???{?????block[i].yemian?=?-1;//找到空闲内存?????block[i].biaoji?=?0;???}????for(i=0;?iPsize;?i++)???{?????page[i].yemian?=?QString[i];?????page[i].biaoji?=?0;???}?}?int?findSpace(int?Nsize)?{//查找是否有空闲内存for(int?i=0;?iNsize;?i++)???{?????if(block[i].yemian?==?-1)?????{????retur