常用页面置换算法模拟实验.doc

目录一、摘要3二、正文4三、设计总结8四、参考文献10五、附录：源程序代码11摘 要 Windows中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺页中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页，为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。此设计为了了解Windows XP的操作接口及系统调用方式，熟悉Windows XP常用操作的实现过程，练习并掌握Visual C+开发环境。利用Windows SDK（System Development Kit）提供的API（应用程序接口）设计一个虚拟存储管理程序，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。（命中率页面失效次数页地址流长度）。关键字 Windows；请求调页；数据结构；存储管理 正 文一、设计思路 页面置换算法：当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。此设计为了了解Windows XP的操作接口及系统调用方式，熟悉Windows XP常用操作的实现过程，练习并掌握Visual C+开发环境。利用Windows SDK（System Development Kit）提供的API（应用程序接口）设计一个虚拟存储管理程序，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。二、设计目的 1、用C+语言实现页面置换算法。 2、了解内存分页管理策略。 3、掌握调页策略。 4、掌握一般常用的调度算法。 5、选取调度算法中的典型算法，模拟实现。三、设计任务1、了解Windows XP的操作接口及系统调用方式，熟悉Windows XP常用操作的实现过程，练习并掌握Visual C+开发环境。2、利用Windows SDK（System Development Kit）提供的API（应用程序接口）设计一个虚拟存储管理程序，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。（命中率页面失效次数页地址流长度）。四、调页策略1)何时调入页面如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。2)请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。3）从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1) 系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。(3) Windows方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应从对换区调入。由于Windows系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。3页面调入过程 每当程序所要访问的页面未在内存时， 便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外在原物理 块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。五、页面置换算法 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调。常见置换算法 最佳置换算法(Optimal)：它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法：LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。设计总结经过本次课程设计，完成题目“常用页面置换算法原理模拟实验”，了解Windows XP的操作接口及系统调用方式，熟悉Windows XP常用操作的实现过程，练习并掌握Visual C+开发环境。做课程设计是为了对平时学习的理论知识与实际操作相结合，在理论和实践上进一步巩固已学基本理论及应用知识并加以综合提高，学会将知识应用于实际的方法，提高分析和解决问题的能力。在做课程设计的过程中，深深感觉到自身所学知识的有限。有些题目书本上没有提及，所以就没有去研究过，做的时候突然间觉得自己真的有点无知，虽然现在去看依然可以解决问题，但还是浪费了许多，这一点是必须在以后的学习中加以改进的地方，同时也要督促自己在学习的过程中不断的完善自我。在设计过程中的思考和讨论，对现有知识能够运用计算机来解决现实生活中的实际问题确立了信心，对模块化程序设计思想有了比较清晰的印象，为今后的程序设计奠定了一定的心理和技术上的准备。这次课程设计加强了我对计算机操作系统的认识，对我个人而言是对所学课程内容掌握情况的一次自我验证。通过课程设计提高了我对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考，在分析问题、解决问题的过程中，更是获得一种成功的喜悦。 实验结果参考文献1. 汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出版社.2. 王清，李光明，计算机操作系统.冶金工业出版社.3. 孙钟秀等，操作系统教程. 高等教育出版社4. 曾明，Linux操作系统应用教程. 陕西科学技术出版社. 5. 张丽芬，刘利雄.操作系统实验教程. 清华大学出版社.6. 孟静，操作系统教程原理和实例分析. 高等教育出版社7. 周长林，计算机操作系统教程. 高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社 9. 任满杰，操作系统原理实用教程，电子工业出版社附录：源程序代码#include iostream.hconst int DataMax=100;const int BlockNum = 10;int DataShowBlockNumDataMax; / 用于存储要显示的数组bool DataShowEnableBlockNumDataMax; / 用于存储数组中的数据是否需要显示/int DataDataMax=4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1; / 测试数据/int N = 20; / 输入页面个数int DataDataMax; / 保存数据int BlockBlockNum; / 物理块int countBlockNum; / 计数器int N ; / 页面个数int M;/最小物理块数int ChangeTimes;void DataInput(); / 输入数据的函数void DataOutput();void FIFO(); / FIFO 函数void Optimal(); / Optimal函数void LRU(); / LRU函数int main(int argc, char* argv) DataInput();/ DataInput(); FIFO(); Optimal(); LRU(); return 0; int menu; while(true) coutendl; cout* 菜单选择 *endl; cout*endl; cout* 1-FIFO *endl; cout* 2-Optimal *endl; cout* 3-LRU *endl; cout* 0-EXIT *endl; cout*menu; switch(menu) case 1: FIFO();break; case 2: Optimal();break; case 3: LRU();break; default: break; if(menu!=1&menu!=2&menu!=3) break; void DataInput() coutM; while(M BlockNum) / 大于数据个数 coutM; coutN;while(N DataMax) / 大于数据个数 coutN;cout请输入页面访问序列：endl;for(int i=0;iDatai;void DataOutput() int i,j; for(i=0;iN;i+) / 对所有数据操作 coutDatai ; coutendl; for(j=0;jM;j+) cout ; for(i=0;iN;i+) / 对所有数据操作 if( DataShowEnableji ) coutDataShowji ; else cout ; coutendl; cout缺页次数: ChangeTimesendl; cout缺页率: ChangeTimes*100/N%endl;void FIFO() int i,j; bool find; int point; int temp; / 临时变量 ChangeTimes = 0; for(j=0;jM;j+) for(i=0;iN;i+) DataShowEnableji = false; / 初始化为false，表示没有要显示的数据 for(i=0;i=3的块，替换后计数值置1， / 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段 for(i=0;iN;i+) / 对有所数据操作 / 增加count for(j=0;jM;j+) countj+; find = false; / 表示块中有没有该数据 for(j=0;j M ) / 因为i是从0开始记，而M指的是个数，从1开始，所以i+1 /获得要替换的块指针 temp = 0; for(j=0;jM;j+) if( temp countj ) temp = countj; point = j; / 获得离的最远的指针 else point = i; / 替换 /Blockpoint = Datai; countpoint = 0; / 更新计数值 / 保存要显示的数据 for(j=0;jM;j+) DataShowji = Blockj; DataShowEnableiM?(j=i?j:i):ji = true; / 设置显示数据 / 输出信息 cout endl; cout endl; DataOutput();void Optimal() int i,j,k; bool find; int point; int temp; / 临时变量，比较离的最远的时候用 ChangeTimes = 0; for(j=0;jM;j+) for(i=0;iN;i+) DataShowEnableji = false; / 初始化为false，表示没有要显示的数据 for(i=0;iM;i+) counti = 0 ; / for(i=0;iN;i+) / 对有所数据操作 find = false; / 表示块中有没有该数据 for(j=0;jM;j+) if( Blockj = Datai ) find = true; if( find ) continue; / 块中有该数据，判断下一个数据 / 块中没有该数据，最优算法 ChangeTimes+; / 缺页次数+ for(j=0;jM;j+) / 找到下一个值的位置 find = false; for( k =i;k M ) / 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 /获得要替换的块指针 temp = 0; for(j=0;jM;j+) if( temp countj ) temp = countj; point = j; / 获得离的最远的指针 else point = i; / 替换 Blockpoint = Datai; / 保存要显示的数据 for(j=0;jM;j+