操作系统课程设计-页面置换算法模拟程序报告.doc

1 引 言 1 1.1 问题的提出 1 1.2国内外研究的现状 1 1.3任务与分析 2 2 需求分析 2 2.1页面置换算法概念 2 2.2关于页面置换算法的一些基本思想 3 2.2.1先进先出（FIFO）页面置换算法 3 2.2.2最近最久未使用（LRU）置换算法 3 2.2.3最佳（Optimal）置换算法 4 2.3需求分析 5 3 程序运行平台 5 4总体设计 5 5详细设计 6 5.1界面设计 6 5.2随机产生长度为20的页面走向 6 5.3 FIFO算法设计 8 5.4 LRU算法设计 11 6 系统测试 15 6.1测试的数据 17 6.2测试小结 21 总 结 23 致 谢 24 参考文献 24  摘 要 随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学号这门课程，必须把理论和实践紧密结合，才能取得教好的学习效果。 本次课程设计是在学习完《操作系统教程》后，进行的一次全面的综合训练，通过课程设计，让学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。 熟悉页面置换算法及其实现，引入计算机操作性能评价方法的概念。 关键词：页面置换算法，LRU算法，OPT算法，FIFO算法 1 引 言 1.1 问题的提出 在存储器管理方式中，有一个特点，就是当要求作业全部装入内存才能运行。但是这样就存在两种情况： （1）有的作业很大，不能全部装入内存，致使作业无法进行。 （2）有大量作业要求运行时，内存容量不足容纳所有作业，而虚拟内存技术正是下哦那个逻辑上扩充内存容量，将会解决以上两个问题。 所以，可以当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其它进程使用 通常，把选择换出页面的页面的算法称为页面置换算法，模拟页面置换算法用以客观解决内存不足的矛盾。 1.2国内外研究的现状 1961年英国曼彻斯特大学推出了“虚拟存储”管理技术，并在ATRAS计算机上实现这一技术，70年代以后，这一技术才真正广泛使用，目前许多大型计算机均采用此技术。虚拟存储管理技术的关键在于页面置换算法的选择。1966年Belady在理论上提出最优页面置换算法(Optimal Replacement Algorithm, OPT)，此外还有先进先出置换算法(first input first output, FIFO) ，最近最少使用页面置换算法(least recently used, LRU)，最少使用页面置换算法(least frequent used, LFU，或最不常用算法），时钟置换算法（clock，或称最近未使用页面置换算法(not used recently, NUR)），页面缓冲（page buffering）置换算法等。 1.3任务与分析 本课程设计完成一个简单页面置换算法的模拟，加深理解页面置换算个算法对于存储器内存扩展使用的原理以及对于不同置换算法的使用的优缺点。在此次课程设计中完成的只是一个小小的模拟算法，对于操作系统中对于置换算法的选择远远不止这些。 用随机数方法产生页面走向，页面走向长度为L。 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。 假定可用内存块和页表长度 (作业的页面数)分别为m和k，初始时，作业页面都不在内存。 随机数产生程序： function random: real: begin Seed: =125.0(seed+1.0) Seed: =Seed8192.0trunc (seed/8192) random: = (Seed+0.5)/8192 end; 上述随机数发生函数产生的随机数为0.0～1.0，稍另变化就可得到0～n1之间的随机数。 程序开始时，应对变量Seed (实型)赋初值。 2 需求分析 2.1页面置换算法概念 所