操作系统课程设计报告
院(系): 计算机工程学院 专业: 计算机科学与技术专业 学生姓名: __ ****** 班级:_*******___ 学号: ****** 题目: _页面置换算法 ____
起迄日期: _************_
设计地点: ************ 指 导 教 师: ****
一、 课程设计目的
操作系统是计算机教学中最重要的环节之一,也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏,直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能,充分发挥系统中各种设备的使用效率,提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理,内容比较繁琐,具有很强的实践性。要学好这门课程,必须把理论与实践紧密结合,才能取得较好的学习效果。
课程设计是学生学习完《计算机操作系统》课程后,进行的一次全面的综合训练,通过课程设计,让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强学生的动手能力。
二、 课程设计内容
模拟仿真请求分页调度算法OPT、FIFO、LRU、LFU、CLOCK等模拟页面调度算法,并提
供性能比较分析功能。
三、 系统分析与设计 1、系统分析
由于分区式管理尽管实现方式较为简单,但存在着严重的碎片问题使得内存的利用率不高。再者,分区式管理时,由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放,进程的大小或内存可用空间的限制。而且分区式管理也不利于程序段和数据段的共享。页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分,而把那些不经常执行的程序段和数据存放于外存待执行时调入,以提高内存利用率而提出来的页式管理有动态页式管理和静态页式管理之分,动态页式管理是在静态页式管理的基础上发展起来的。请求页式管理属于动态页式管理中的一种,它的地址变换过程与静态页式管理时的相同,也是通过页表查出相应的页面号,由页面号与页内相对地址相加而得到实际物理地址。有关的地址变换部分是由硬件自动完成的。当硬件变换机构发现所要求的页不在内存时,产生缺页中断信号,由中断处理程序做出相应的处理。中断处理程序是由软件实现的。除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外,还要从外存读入所需要的虚页。这个过程要启动相应的外存和涉及到文件系统。因此,请求页式管理是一个十分复杂的过程,内存利用率的提高是以牺牲系统开销的代价换来的。这里用到了置换算法。它是在内存中没有空闲页面时被调用。目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放所调入的页,则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此,置换算法应该置换那些被访问概率低的页,将它们移出内存。 调页策略
1)何时调入页面
如果进程的许多页是存放在外存的一个连续区域中,则一次调入若干个相邻的页,会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问,则又是低效的。可采用一种以预测为基础的预调页策略,将那些预计在不久之后便会被访问的页面,预先调入内存。如果预测较准确,那么,这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时,由程序员指出应该先调入哪些页。 2)请求调页策略
当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便即提出请求,由OS将其所需页面调入内存。由请示调页策略所确定调入的页,是一定会被访问的,再加之请求调页策略比较易于实现,故在目前的虚拟存储器中,大多采用此策略。但这种策略每次仅调入一页,故须花费较大的系统开销,增加了磁盘I/O的启用频率。 从何处调入页面
在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。通常,由于对换区是采用连续分配方式,而事件是采用离散分配方式,故对换区的磁盘I/O速度比文件区的高。这样,每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况:
(1)系统拥有足够的对换区空间,这时可以全部从对换区调入 所需页面,以提高调页速度。为此,在进程运行前,便须将与该进程有关的文件,从文件区拷贝到对换区。
(2)系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入;而当换出这些页面时,由于它们未被修改而不必再将它们换出时,以后需要时,再从对换区调入。 (3)UNIX方式。
2、系统设计:
在进程运行过程中,若其所要访问的页面不在内存而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区中。但应将哪 个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法,应具有较低的页面更换频率。从理论上讲,应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。 则有以下页面置换方法:
1) 、 先进先出(FIFO)页面置换算法: 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序存入一个时间数组,并将其中时间值最大的页面进行淘汰,并替换入新的页面就可以实现。
2)、 最近最久未使用页面置换算法LRU(least recently used): 算法的基本思想:当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是,如果某页被访问了,则它可能马上还被访问。或者反过来说,如果某页很长时间未被访问,则它在最近一段时间不会被访问。
3)、最佳页面置换置换算法(OPT)
其所选择的被淘汰页面,将是永不使用的,或者是在最长时间内不再被访问的页面。可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法也是无法实现的。但是可利用该算法去评价其它算法。
4)、简单Clock置换算法
该算法是当某页被访问时,其访问位被设置为1,置换算法选择某一页淘汰时,只需检查页的访问位,如果是0,则将该页换出,如果为 1,则重新将它置0,暂不换出,而给该页第二次驻留内存的机会,再按照FIFO算法检查下一个页面。当检查到队列的最后一个页面时,若其访问位仍为1,则再返回到队首的第一个页面。 5)最少使用置换算法(LFU)
该置换算法选择在最近一段时间内使用最少的页面作为淘汰页。LFU算法并不能真正的反映出页面的使用情况。
3、模块设计: 系统功能结构图
运行程序 页面置换算法的主界面 输入页面序列和物理块数 OPT LRU F IFO 简单Clock LFU 性能分析
4、数据结构说明:
程序中用到了struct struct Pagetime
{
//字段
private int num;//页面的序号
private int timer;//不同的算法有不同的含义 private int count;//页面访问次数 //属性
public int Num {
get { return num; } set { num = value; } }
public int Timer {
get { return timer; } set { timer = value; } }
public int Count {
get { return count; } set { count = value; } }
}
程序中用到了字符串和数组
public string page;//用于接收页面序列
public string strsize;//用于接收物理块数
page = page_textBox.Text;
strsize = size_textbox.Text;
//声明struct数组,用于存储内存中页面的信息 Pagetime[] X = new Pagetime[20];
5、算法流程图:
开始 输入页面序列 输入物理块数 调用各种置换算法,OPT,LRU,FIFO,LFU,简单Clock,并输出结果 性能分析 结束
主流程图