上海电力学院计算机操作系统原理课程设计报告题目名称：编写程序模拟虚拟存储器管理姓名：杜志豪.学号：班级： 2012053班 .同组姓名：孙嘉轶课程设计时间：——评语：成绩：目录一、设计内容及要求 (4)1. 1 设计题目 (4)1．2 使用算法分析： (4)1． FIFO算法（先进先出淘汰算法） (4)1． LRU算法（最久未使用淘汰算法） (5)1. OPT算法（最佳淘汰算法） (5)分工情况 (5)二、详细设计 (6)原理概述 (6)主要数据结构(主要代码) (6)算法流程图 (9)主流程图 (9)Optimal算法流程图 (10)FIFO算法流程图 (10)LRU算法流程图 (11)．1源程序文件名 (11). 2执行文件名 (11)三、实验结果与分析 (11)Optimal页面置换算法结果与分析 (11)FIFO页面置换算法结果与分析 (16)LRU页面置换算法结果与分析 (20)四、设计创新点 (24)五、设计与总结 (27)六、代码附录 (27)课程设计题目一、设计内容及要求编写程序模拟虚拟存储器管理。
假设以M页的进程分配了N块内存（N<M）。
输入：设定系统分配的块数，以及进程页面引用序列（也可随即产生）。
输出：显示每一次页面引用内存状态，最终显示产生缺页中断的次数及页面置换的次数（假设初始状态内存没有装入任何页面）。
必须分别使用以下置换算法完成模拟：(1)FIFO页面置换算法;(2)LRU页面置换算法;(3)最佳（Optimal）页面置换算法。
使用算法分析：FIFO页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面以淘汰。
该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但该算法并不是都适合实际情况，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数，例程等得页面，FIFO算法并不能保证这些页面不被淘汰。
1.2.2LRU页面置换算法：最近最久未使用（LRU）的页面置换算法是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择有页面中t值最大的，即最近最久为使用的页面以淘汰。
1.2.3最佳（Optimal）页面置换算法：Optimal算法是一种理论的算法，其所选择的被淘汰页面将是以后永久不使用的，或许是在最长（未来）时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其他算法。
分工情况：共同讨论并构思，杜志豪负责FIFO和LRU算法的编程，孙嘉轶负责窗体界面和OPT算法的编写。
编程中遇到困难共同讨论并解决。
二、详细设计2.1原理概述定义一个整型变量int buffer=0来记录内存分块数，定义一个string 类型的算法 string suanfa来选择具体的算法；用一个数组int[]xulie来存储页面序列，长度为20；用一个数组int[]kuai来存储内存分配的物理块个数，长度为5；用int s来记录具体的步骤数，用int num来记录页面中断次数。
空白表示物理块没有被使用。
2.2主要数据结构（代码）结构体：输入的页面序列号：2.3 public Form1() pp执行文件名：虚拟存储器管理.exe三、实验结果与分析（要有结果截图）Optimal页面置换算法结果与分析最佳页面置换算法是指：其选择的被淘汰的页面将是以后永不使用，或许是在最长时间内不被访问的页面。
假设系统分配了3块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面三个直接进入内存即：7 0 1。
由于7是未来最长时间不被使用，因此把7置换成2即为：2 0 1。
由于0已经在内存里面，不需置换。
1是未来最长时间不被使用的，所以把1置换成3得到：2 0 3。
由于0在已经在内存里面，不需置换。
0是未来最长时间不被使用的，所以把0换成4得到：2 4 3。
由于2、3已经在内存里面，所以不用置换。
由于4以后不被使用，所以把4置换成0得到：2 0 3。
又由于3、2已在里面无需置换。
由于3以后不被使用，把3置换成1得到：2 0 1。
又因为2、0、1已在内存里面，所以无需置换。
又由于2以后不被使用，所以把2置换成7得到：7 0 1。
又因为0、1已经在内存里面，所以不用置换。
分配完成。
页面中断次数为6。
实验结果与猜想一致，成功。
假设系统分配了4块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前4个直接进入内存即为：7 0 1 2。
由于2已经在内存中，所以不需置换。
由于7是未来最长时间不被使用的，所以把7置换成3得到：3 0 1 2。
由于0已在内存里面，无需置换。
由于1是未来最长时间不被使用，所以把1置换成4得到：3 0 4 2。
由于2、3、0、3、2已经在内存里面，所以无需置换。
由于3是未来不被使用，所以把3置换成1得到：1 0 4 2。
又因为2、0、1已在内存里面，无需置换。
由于4是未来时间不被使用，所以把4置换成7得到：1 0 7 2。
因为0、1已在内存里面，所以无需置换。
分配完成。
页面中断次数为4。
实验结果与猜想一致，成功。
假设系统分配了5块物理块，读取一个页面顺序：7 0 1 2 3 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面5个数直接填满即为：7 0 1 2 3。
由于3、0已经在内存里面，所以无需置换。
由于7是在未来最长时间不被使用，所以把7置换成4得到：4 0 1 2 3。
由于2、3、0、3、2、1、2、0、1已经在内存中，无需置换。
由于4是未来不被使用的，所以把4置换成7得到：7 0 1 2 3。
由于0、1已在内存里面，不需置换。
分配完成。
页面中断次数为2。
实验结果与猜想一致，成功。
FIFO页面置换算法结果与分析:先进先出页面置换算法，就是总淘汰最先进入内存的页面。
假设系统分配了3块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前三个没有重复的，直接填满即：7 0 1，下一个数为2，不在内存中，则根据FIFO算法原则，将7换成2即：2 0 1。
接下来进来的是一个0，在内存中，则不用置换。
3要进来了，由于0是最先进来的，所以将0替换成3得到：2 3 1。
1变成最先进来的了，则把1换成0，得到：2 3 0。
这时2成了最先进来的，则把2换成4即：4 3 0。
由于3最先进来，则把3换成2变成：4 2 0。
由于0是最先进来的，把0换成3即：4 2 3。
此时4变成最先进来的，把4换成0即：0 2 3。
接下来进来的是2，在内存里面，不需置换，3同理可得不用置换即为：0 2 3。
由于2是最先进来的，则把2置换成1得到：0 1 3。
此时3为最先进来的，则把3置换成2即为：0 1 2。
由于0，1已在里面，不需置换。
由于0最先进入内存，则把0置换成7得到：7 1 2。
由于1最先进入，则把1置换成0得到：7 0 2。
由于2最先进入内存，则把2置换成1得到：7 0 1。
分配完成。
此时显示页面中断次数为12次。
得到的实验结果与猜想的一样，猜想成功。
假设系统分配了4块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面4个数没有出现重复，直接填满即：7 0 1 2。
0在里面无需置换。
由于7最先进入，则把7置换成3得到：3 0 1 2。
由于0在里面，无需置换。
此时0为最先进入，则把0置换成4得到：3 4 1 2。
由于接下来进来的页面数2，3都在里面，则无需置换。
此时1为最先进入，则把1置换成0即为：3 4 0 2。
由于接下来进来的页面数3，2都在里面，则无需置换。
此时2为最先进入，则把2置换成1得到：3 4 0 1。
3为最先进入，则把3置换成2得到：2 4 0 1。
由于接下来进来的页面数0,1都在里面，则无需置换。
此时最先进入的为4，则把4置换成7得到：2 7 0 1。
由于接下来进来的页面数0,1都在里面，则无需置换。
分配完成，此时显示页面中断次数为6次。
得到的实验结果与猜想的一致，成功。
假设系统分配了5块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前面四个直接进入内存即为：7 0 1 2。
因为0已在内存中，不需置换。
由于不在里面3直接进入得到：7 0 1 2 3。
由于0在内存中，不需置换。
由于7最先进入，则把7置换成4得到：4 0 1 2 3。
由于2、3、0、3、2、1、2、0、1都在内存里面，不需置换。
由于0最先进入，则把0置换成7得到：4 7 1 2 3。
由于1为最先进入，则把1置换成0得到：4 7 0 2 3。
由于2最先进入，则把2置换成1得到：4 7 0 1 3。
分配完成。
页面中断次数为：3。
实验结果与猜想一样，成功。
LRU页面置换算法结果与分析LRU是选择最近最久未使用的页面予以淘汰。
该算法富裕每个页面一个访问字段。
用来记录一个页面自上次被访问以来所经历的时间a，当淘汰一个页面时，选择现有页面中其a值最大的，即最近最久未使用的页面予以淘汰。
假设系统分配了3块物理块，读取一个页面顺序：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1前三个直接进入内存即为：7 0 1。
由于7最近最久未使用，则把7置换成2得到：2 0 1。
由于0在内存里面，不需置换。
由于1最近最久未使用，则把1置换成3得到：2 0 3。
由于0 在内存中，不需置换。
由于2最近最久未使用，则把2置换成4得到：4 0 3。
由于3最近最久未使用，则把3置换成2得到：4 0 2。
由于0最近最久未使用，则把0置换成3得到：4 3 2。
由于4最近最久未使用，则把4置换成0得到：0 3 2。
由于3、2已在内存中，不需置换。
由于0最近最久未使用，则把0置换成1得到：1 3 2。
由于2在内存中，不需置换。
由于3最近最久未使用，则把3置换成0得到：1 0 2。
由于1已在内存中，不需置换。
由于2最近最近未使用，则把2置换成7得到：1 0 7。
由于0、1已在内存中不需置换。
分配完成。
页面中断次数为9.实验结果与猜想一致，成功。