课程设计题目请求页式管理缺页中断模拟设计--FIFO、OPT学院计算机科学与技术专业班级姓名指导教师吴利军2013 年 1 月16 日课程设计任务书学生姓名：指导教师：吴利军_ 工作单位：计算机科学与技术学院题目: 请求页式管理缺页中断模拟设计--FIFO、OPT初始条件：1．预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。
2．实践准备：掌握一种计算机高级语言的使用。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．实现指定淘汰算法。
能够处理以下的情形：⑴能够输入给作业分配的内存块数；⑵能够输入给定的页面，并计算发生缺页的次数以及缺页率；⑶缺页时，如果发生页面置换，输出淘汰的页号。
2．设计报告内容应说明：⑴需求分析；⑵功能设计（数据结构及模块说明）；⑶开发平台及源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。
周2、周3：完成程序调试及测试。
周4、周5：验收、撰写课程设计报告。
（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日请求页式管理缺页中断模拟设计——FIFO、OPT1课程设计目的与功能1.1设计目的结合《操作系统》所学内存页式管理章节，掌握虚拟内存设计的重要性，熟悉和掌握请求分页式存储管理的实现原理，通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法（主要通过FIFO和OPT实现），并考察替换算法的评价指标——缺页次数和缺页率，得到淘汰的页面次序。
高级语言设计并实现出的结果程序要能够很好地显示页面调入和替换详细信息。
1.2初始条件及可发环境1.2.1初始条件1．预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。
2．实践准备：掌握一种计算机高级语言的使用。
1.2.2开发环境（1）使用系统：Windows XP（2）使用语言：C++（3）开发工具：Visual C++ 6.01.3功能实现设计的结果程序能实现FIFO、OPT算法模拟页式存储管理缺页中断，主要能够处理以下的情形：(1) 用户能够输入给定分配的内存块数；(2) 用户输入给定的页面，并计算发生缺页的次数、缺页率及淘汰页面次序；(3) 程序可随机生成页面序列，或用户输入；2需求分析及设计说明2.1需求分析由于纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，并且会产生磁盘碎片问题。
用户程序将受到物理内存大小的限制。
而虚存的存储管理技术——请求分页存储管理技术和请求分段技术，则很好的解决了这个问题。
该设计虚拟实现请求分页管理（只实现FIFO和OPT）。
请求分页系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。
它允许只装入部分页面的程序和数据，便启动运行。
以后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上，置换时以页面为单位。
实现将程序正在运行时所需的但尚未在内存的页面调入内存，再将内存中暂时不用的页面从内存置换到外存磁盘上。
为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，和在内存的时间的长短。
请求分页中的页表如表1：表1各字段说明如下：状态位：指示该页是否已调入内存。
访问字段：记录本页在被访问的次数，或记录最近已有多长时间未被访问。
修改位：表示该页面在调入内存后是否被修改过。
若未被修改，在替换该页时就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
外存地址：指出该页在外存上的地址，通常是物理块号。
在本设计中模拟FIFO、OPT系统的实现中，只需要用到虚拟页号，物理块号和中断位。
页表可用一个结构体的数组实现。
请求分页的具体实现过程如图1图1请求分页流程图2.2设计说明2.2.1算法分析在进程运行过程中，若其所要访问的页面不在内存，需要把它们调入内存，但内存已无空闲已空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区。
但应将哪个页面调出，必须根据替换算法来确定。
该设计采用的是常见置换算法中的先进先出(FIFO)、理想型淘汰算法OPT(Optimal Replacement Algorithm）。
详细算法原理如下：FIFO(先进先出算法)基本思想：总是选择在内存驻留时间最长的一页将其淘汰，因为最早调入内存的页，不再被使用的可能性比近期调入内存的大。
该算法实现简单，只需要把一个进程调入内存的页面，按先后次序连结成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如有全局变量、常用函数，例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
使用FIFO替换算法效率比较低，可能会比理想型算法要多出一倍。
低的原因是：基于处理器按线性顺序访问地址空间这一假设。
事实上，许多时候，处理器不是按线性顺序访问地址空间的。
例如，执行循环结构的程序段。
使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象（Belady现象）。
例如针对请求序列：1 2 3 4 1 2 5 1 2 3 4 5，若分配3个可用内存块，使用FIFO算法，一共会缺页9次，缺页率：75%；而如果分配4个可用内存块，则一共会缺页10次，缺页率：83.3%。
OPT(理想型淘汰算法)基本思想：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。
采用理想型替换算法，通常可保证获得最低的缺页率。
但是由于人们目前无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是在模拟设计中，由于是事先给定一个页面序列，即知道各个时刻以前和以后的页面出现情况，所以可实现该算法。
在实际系统中，虽无法实现理想型淘汰算法，但是可用它来评价其他替换算法。
2.2.2数据结构模拟设计时，页表没项记录的数据类型用结构体定义。
整该页表用数组模拟。
结构体有三个成员：int page_num 表示页面号；int memory_num表示页面所对应的内存块号；int is_in_memory是存在状态位标志，表示页面是否在内存，0表示不在内存，1表示在内存。
在每一个算法函数中都要初始化页表，否则，后面的算法会受前面算法结果的影响。
struct page{int page_num; //表示页面号int memory_num; //表示页面所对应的内存块号int is_in_memory;//是存在状态位标志，表示页面是否在内存，0 表示不在内存，1表示在内存};page page_table[初始值];for(int i=0;i<10;i++) //初始化页表：{page-table[i].page_num=i;page_table[i].memory_num=-1; //初始化，内存块号为-1，即没在内存块中。
page_table[i].is_in_memory =0; //初始化时，各页面均不在内存}页面请求序列：int *page_array= new int[inputSize]。
内存在程序中模拟内存存放页面号：int *memory=new int[memorySize]2.2.3函数实现Control()函数是class control的构造函数，用来初始化页表、内存(调用initial()函数)。
提示并接受用户输入等待调入页面数page_size，可用物理块数memory_size，并随机生成请求页面，或用户自己输入。
然后调用FIFO()、OPT()函数实现按不同替换算法调入页面进内存。
void FIFO()函数实现先进先出的替换算法调入页面。
void OPT()函数实现理想型替换算法。
3程序的主要模块说明3.1 control类封装内存管理3.1.1 FIFO替换算法实现伪函数void control::FIFO(){control::init(); 初始化页表等do{if(当前页在内存)else（当前页不在内存，直接加载进入物理块）{缺页累积；加载当前页进入内存；修改页表置当前页在页表的是否在内存标志为1。
将该页在内存的位置对应。
}}while(内存物理块没有加载满);//内存物理块已经加载满了；for(剩下的页面循环){if(当前页在内存)else(当前页不在内存){缺页累积。
替换页面；修改页表置当前页在页表的是否在内存标志为1。
将该页在内存的位置对应。
利用算法得到下次替换的物理块号。
}}输出缺页次，缺页率，淘汰页面次序。
}3.1.2 OPT替换算法实现伪函数void control::OPT(){control::init();//初始化页表等for(对每个页表循环处理){for(检查每个物理块){if (如果该页在内存物理块中)置判别标志为1}if(如果该页不在内存，并且物理快放满){缺页累加并权值数组每个记录元素清零for(物理块每个元素检查){for(从该页后面的那个页开始计算权值)权值累加;}得到最大权值所在的物理块，即是下次需要替换的页替换该页，加入内存}if(该页不在内存，并且内存物理块没有满){缺页累加直接加载进内存}}输出缺页次、缺页率和淘汰页号次序。
}3.2 main函数利用页式管理control类建立一个对象，来实现FIFO、OPT。
4使用说明及运行分析4.1使用说明及运行运行程序根据提示输入调入页面数和可使用的物理块数，再选择是用户输入还是计算机随机产生页面号。
观察页面调度过程，处理完各页面后，统计并显示缺页次数、缺页率和淘汰页面号次序。
4.2测试实例和运行结果4.2.1 FIFO算法输入给定的页面数：10输入给作业分配内存的物理块数：3随机生成页面请求序列，如图2：5 7 3 8 8 0 5 4 5 2图2运行结果如图3 图34.2.2 OPT算法输入给定的页面数：10输入给作业分配内存的物理块数：3随机生成页面请求序列，如图4：7 8 2 6 7 8 1 5 6 5图4运行结果如图5 图54.3结论与分析从运行结果看出程序能满足模型设计的要求，提示用户对请求序列的大小和可用内存数量进行限制，并提示用户输入请求序列号，或系统随机生成序列，按照不同的替换算法处理并且显示请求页面的调入和替换情况。
