页面置换算法模拟实验

1、“计算机操作系统”课程设计大作业页面置换算法模拟实验(含完整资料，可直接提交)一、题目：页面置换算法模拟实验二、目的分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算 法和最近最少使用(LRU)置换算法对用户输入的页面号请求序列进行 淘汰和置换，从而加深对页面置换算法的理解。三、内容和要求请用C/C+语言编一个页面置换算法模拟程序。用户通过键盘输 入分配的物理内存总块数，再输入用户逻辑页面号请求序列，然后分 别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最 近最少使用(LRU)置换算法三种算法对页面请求序列进行转换，最后 按照课本P150页图4-2

2、6的置换图格式输出每次页面请求后各物理块 内存放的虚页号，并算出总的缺页率(缺页次数/总的请求次数)。最 后三种页面置换算法的优缺点。三种页面置换算法的思想可参考教材P149-P152页。假设页面号请求序列为4、3、2、1、4、3、5、4、3、2、1、5, 当分配给某进程的物理块数分别为3块和4块时，试用自己编写的模 拟程序进行页面转换并输出置换图和缺页次数、缺页率。四、提交内容本大作业每个人必须单独完成。最后需提交的内容包括：源程序（关键代码需要注释说明）、可运行程序、运行结果、算法思路及流 程图、心得体会。大作业严禁抄袭。发现抄袭一律以不及格论。请大家严格按照大作业题目来编写程序，不要上交

3、以前布置的大 作业。如果提交的大作业题目与本文档要求不符，成绩一律为及格。目录%正文21、设计思路32、各模块的伪码算法63、函数的调用关系图144、测试20设计总结21参考文献22致谢23附录：部分源程序代码24UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的 分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便 可运行；还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序 和数据时，发现其所在页面不在內存，就立即提出请求（向CPU发岀缺页中断）, 由系统将其所需页面调入内存。这种页面调入方式叫请求调页，为实现请求调页， 核心配置了四种数据结构

4、：页表、页框号、访问位、修改位、有效位、保护位等。 此设计为了 了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练 习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试 C程序，学会如何把学到的知识用于解决实际问题，培养学生的能力。关键字 UNIX 请求调页数据结构存储管理 编辑器调试 C程序一、设计思路页面置换算法：当CPU接收到缺页中断信号，中断处理程序先保存现场， 分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外 存的物理块号o如果此时內存未满，能容纳新页，则启动磁盘I/O将所缺之页调 入内存，然后修改页表。如果内存已

5、满，则须按某种置换算法从内存中选出一页 准备换岀，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利 用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页 面的调入过程对用户是透明的。此设计为了了解UNIX的命令及使用格式，熟悉 UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序， 学会利用gcc、gdb编译、调试C程序，学会如何把学到的知识用于解决实际问 題，培养学生的动手能力。二、设计目的1、用C语言实现页面置换算法。2、了解内存分页管理策略3、掌握调页策略4、掌握一般常用的调度算法5、选取调度算法中的典型算法，模拟实现。三、设计

6、任务在Window98/2000系统的环境下运行程序；通过从一般常用的调页算法中 选取典型算法程序，了解页面管理的相关细节，并用程序设计实现该算法实验。四、设计内容与步骤分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页 面或页。五、调页策略1）何时调入页面如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相 邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多 数都未被访问，则又是低效的。可釆用一种以预测为基础的预调页策略，将那些 预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这 种策略显然是很有吸引力的。但目前预调页的成功率

7、仅为50%o且这种策略主要 用于进程的首次调入时，由程序员指出应该先调入哪些页。2) 请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在 内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调 入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚 拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系 统开销，增加了磁盘I/O的启用频率。3) 从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存 放对换页面的对换区。通常，由于对换区是釆用连续分配方式，而事件是采用离 散分配方式，故对换区的磁盘1

8、/()速度比文件区的高。这样，每当发生缺页请求 时，系统应从何处将缺页调入内存，可分成如下三种情况：(1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面， 以提髙调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区 拷贝到对换区。(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文 件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以 后需要时，再从对换区调入。(3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的 页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换 区，因此在下次时，应从对换区

9、调入。由于UNIX系统允许页面共享，因此，某 进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调 入。3页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处 理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通 过查找页表，得到该页在外在原物理块后，如果此时内存能容纳新页，则启动 磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种 置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回 磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存, 并修改页表中的相应表项，置其存在位

10、“1”,并将此页表项写入快表中。在缺 页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问 内存数据。整个页面的调入过程对用户是透明的。六、页面置换算法在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存, 但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一 页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法 来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将 那些以后不再会访问的页面换出，或将那些在较长时

11、间内不会再访问的页面调 出。常见置换算法 最佳置换算法(Optimal):它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页 面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最 佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程 在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算 法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择 在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入 内存的页面，

12、按先后次序链接成一个队列，并设置一个指针，称为替换指针，使 它总是指向最老的页面。 LRU置换算法：LRU (Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内 存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU) 置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面 将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此， LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个 访问字段，用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一

13、个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。七、各模块的伪码算法(1)先进先出算法伪码算法void fifo()本设计含源文件等全套完整设计资料 联系Q： 1415736481获取代做其它设计题目r本设计含源文件等全套完整设计资料联系Q： 1415736481获取代做其它设计题目c：; F: 新建文件夹DebugCppl. exe*2 1201 70 1U U U(J ?7 72 1111 10 03 3 222 22 123300U44300001 缺.0 勺5 lfrH 7 率 页 TL丸最佳首换OPT萍法:7012030400000000011133333333

14、111111最崖章狭具袪的缺页率为缺页率:45.0%3020 17 0 11 2 U 1 ?2 0 17 00 17 0 17 7 7U1223M422U33 80120304230321 12A3B423A3212 最近曇久未使用算法的缺页率为, 缺页率：60.0/.Press any key to continue本设计含源文件等全套完整设计资料联系Q： 1415736481获取代做其它设计题目汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出版社.2. 王清，李光明，计算机操作系统.冶金工业出版社.3. 孙钟秀等，操作系统教程.高等教育出版社4. 曾明，Linux操作系统应用教程.陕西

15、科学技术出版社.5. 张丽芬，刘利雄.操作系统实验教程.清华大学出版社.6. 孟静，操作系统教程一一原理和实例分析.高等教育出版社7. 周长林，计算机操作系统教程.高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社9. 任满杰，操作系统原理实用教程，电子工业出版社这次课程设计，我从“纸上谈兵”到可以自己动脑动手分析调试程序，收获 不少。首先要感谢有了这次实践的机会，给了自己一个舞台，同时也是对自身的检 验。还有多亏了老师们从理论到上机亲自指导的辛苦教授，给予了我们最大帮助 和全面指导，在这里，尤其感谢我的指导老师*老师、以及我的操作系统 的授课老师*林老师，你们不辞辛苦，在给很多学生指导的情况下还不厌其烦的 给我们心指导，在这里，我衷心向你们致谢！最后还要感谢热心的同学们，在我 陷入误区的时候，是他们热心的帮助使我摆脱困境。最后衷心感谢所有给予我帮助和指导的老师和同学，没有他们的帮助我的程 序也不会完成得这么顺利。附录：部分源程序代码includechar find(int j)；int findo(int j)；int 1 (int j)；int queye；double queyelu；ch