/NUMPAGES13《操作系统原理与Linux》课程设计报告专业计算机科学与技术班级计算机09-2学号09034050244姓名赵伯涛指导教师许波完成时间2012年6月5日成绩操作系统课程设计一、设计题目：页面置换算法模拟二、设计目的1、通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2、掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。3、通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。三、设计要求1、实现OPT，LRU，FIFO三种算法并进行对比分析。2、要求界面简单，易懂，关键代码部分要注释。3、编程语言可以采用自己任意精通的语言。四、设计思想说明在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。假设分给一作业的物理块数为3，页面数为20个。页面号为(20个)：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，11、最佳（OPT）置换算法的思路其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。2、最近久未使用(LRU)置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。3、先进先出(FIFO)置换算法的思路该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。五、系统结构说明程序采用C++与Qt库进行开发。代码分为算法部分和界面部分，如上图。1、算法部分由四个头文件及源文件组成，对应的是4个类。Algorithm类是其它三个类的基类，提供了数据结构和页面置换算法，但是选择被置换掉的页的方法是一个虚方法，没有具体的实现。这是由于三种置换算法中只有选择被置换掉的页的方法是不同的，其它地方都是一样的。OPT类，LRU类，FIFO类都是Algorithm类的子类，继承了Algorithm类中的属性和方法。所以只需要实现选择被置换掉的页的算法就可以了。2、界面部分不是实验要研究的内容，不做详细说明。六、数据结构说明具体数据结构在Algorithm类中定义，下面列出了关键的数据结构：classAlgorithm{public:intblockCount;//物理块的大小intindex;//保存系统页面引用到第几步QList<int>pageReferences;//保存了系统页面引用顺序QList<int>block;//保存了物理块中引用的页voidcalc();//置换算法(包含了整个算法的过程)protected:intfindSpace();//查找是否有空闲内存，返回空闲的位置，没有则返回-1intfindExist(intpage);//查找页面是否在内存中，有则返回页面的位置，没有则返回-1virtualintfindReplace();//查找应予置换的页面};上面的数据结构已经解释得很清晰了，这里要说明的是：1、QList这个类。这个是Qt库提供的一个集合类，可以对集合进行添加，移除，查找等操作。2、virtualintfindReplace();加了virtual关键字，表示该方法可以在子类中被重写。不同的置换算法这个方法不同，所以其它三个算法类最重要的就是重写该方法。七、程序清单Algorithm.h#ifndefALGORITHM_H#defineALGORITHM_H#include<QtCore/QList>classAlgorithm{public:Algorithm();virtual~Algorithm();intblockCount;//物理块的大小intindex;//保存系统页面引用到第几步QList<int>pageReferences;//保存了系统页面引用顺序QList<int>block;//保存了物理块中引用的页voidcalc();//置换算法(包含了整个算法的过程)