课程设计：采用近期最久未使用（lru）算法仿真请求分页系统

《课程设计：采用近期最久未使用（lru）算法仿真请求分页系统》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储功能而增加的调页和页而置换功能。每次调入和换出的基本单位都是长度固定的页而。请求分页是目前最常用的一种实现虚拟存储器的方式。对于虚拟页式存储，内外存信息的替换是以页面为单位进行的一一当需要一个放在外存的贞面吋，把它调入内存，同吋为了保持原有空间的大小，还要把-个内种调动越少，进程执行的效率也就越高。时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结朿前阻塞或结束，则CPU

2、当即进行切换。调度程序所要做的就是维护•一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。目录1.醒32.课程设计任务及要求42.1设计任务42.2设计要求43.算法及数据结构53.1算法的总体思想53.2数据结构模块103.2.1功能103.2.2数据结构103.3LRU模块103.3.1功能93.3.2数据结构103.3.3算法10错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。3.4保存模块.....3.4.1功能....3.4.2数据结构3.4.3算法.3.5主函数模块3.5.1功能103.5.2数据结构103.5.3算法104.1程序流程4.程

3、序设计与实现1414144.2程序代码4.3实验结果164.4吋间安排195.雖206.收获、体会和建议207.参考文献211.概述关于操作系统的a存管理，如何节省利用容:y:不人的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式一一在内存有限的情况丁，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟贞式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却

4、也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中己有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情。对于虚拟页式存储，内外存信息的替换是以页面为单位进行的一一当需要一个放在外存的页而时，把它调入内存，同时为了保持原有空间的大小，还要把一个内存中页而调出至外存。自然，这种调动越少，进程执行的效率也就越高。那么，把哪个页面调出去可以达到调动尽量少的目的？我们需要一个算法。自然，达到这样一种情形的算法是最理想的了一一每次调换出的页面是所有内存页面中最迟将被使用的一一这可以最人限度

5、的推迟页而调挽，这种算法，被称为理想页而賈挽算法。可惜的是，这种算法是无法实现的。为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较氏的一段时间内不会被用到。这个，就是著名的局部性原理一一比内存速度还要快的cache,也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。LRU在电子系统屮的解释：LineReplaceableUnit-LR

6、U,电子系统屮常采用模块化设计，这种可更换的模块单元则被叫做LRU，中文名称是“线性可更换单元”2.课程设计任务及要求2.1设计任务用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。分工：钟志亮：查找资料，编写主函数的算法，遇到问题上网查或者发问，或请教其•他同学,和王晓宇进一步修改内容、编写文档。王晓宇：查找资料，编写LRU算法和时间R轮转调度算法，遇到问题和组员讨论，请教同学，上网查询，实现后和钟志亮的合并。实现后和钟志亮进一步修改内容，完善内容。2.2设计要求1）实现请求分页存储管理方式的页面賈换算法：近期最久未使用算法（LKU）2）内存物理块数固定为15个，对多个作业

7、采用可变分配全局置换的策略分配物理块3）作业数量与作业大小（10-20页）可在界面进行设置4）所有作业按RR算法进行调度，时间片长度为1秒5）可为每个作业随机产生引用的页面串，也可以人工输入引用的页而串，页而串长度50—100,要求必须包括作业所有的页面，可作为样例数据保存6）可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、页面串长度的初始化7）要求采用可视化界面，模拟内存分配和使用情况图，川‘在运行过程中