摘要在lｉnｕｘ中,为了提高内存利用率,提供了内外存进程对换机制,内存空间的分配和回收均以页为单位进行，一个进程只需要将其一部分调入内存便可运行；当操作系统发生缺页中断时，必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。
因而引入一种用来选择淘汰哪一页的算法——页面置换算法。
页面置换算法是操作系统中虚拟存储管理的一个重要部分。
页面置换算法在具有层次结构存储器的计算机中,为用户提供一个比主存储器容量大得多的可随机访问的地。
常见的页面置换算法有先来先服务算法(FIFO)，最近最久未使用算法(LＲＵ)和最佳适应算法(OＰT）。
关键字:操作系统；FIFＯ；LＲＵ；OPT；Linux目录1 绪论ﻩ１1．1设计任务 (1)１.2设计思想ﻩ11.3设计特点ﻩ11．４基础知识 (2)１．4.1 先进先出置换算法(FIFO)ﻩ21.4.2最近最久未使用算法（LRU) (3)１.4.３最佳置换算法(OPT) (3)2 各模块伪代码算法ﻩ42.1伪代码概念ﻩ42.２伪代码算法 (4)2.2.１主函数伪代码算法.............................................. 错误!未定义书签。
２.２.2延迟时间函数伪代码算法ﻩ62.2．3 FＩFO算法的伪代码ﻩ７２.2.4LRU算法的伪代码 (7)102．2.5 OPＴ算法的伪代码ﻩ3 函数调用关系图................................................................................................... １23．1函数声明ﻩ１23.1.１主要算法函数...................................................... 错误!未定义书签。
3.1．2辅助函数....................................................................................... 1２3.2程序函数调用关系图 (13)144 测试结果ﻩ14４.１数据初始化ﻩ4．2页面调度算法............................................................... 错误!未定义书签。
4.2.１先进先出算法................................................................................. 1５4.2.2最近最久未使用LRUﻩ15４.2．3最佳置换算法OPＴ (17)185 源程序ﻩ6 设计总结ﻩ３0参考文献 (31)致谢ﻩ3２１绪论１.1 设计任务１、了解UNIＸ的命令及使用格式,熟悉UNIX/LＩNＵX的常用基本命令,练习并掌握UＮIX提供的vｉ编辑器来编译C程序，学会利用gｃｃ、gｄb编译、调试Ｃ程序。
2、设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法(OPＴ）、先进先出算法(FＩFO)、最近最久未使用算法（LＲU）计算访问命中率。
(命中率＝１-页面失效次数／页地址流长度=1-缺页率）１．2设计思想在进程运行过程中,若期所有要访问的页面不在内存,而需把它们调入内存，但内存已无空闲空间时,为了保证进程正常进行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。
但应将哪个页面调出，须根据一定的算法来确定。
通常，把选择换出页面的算法称为页面置换算法。
置换算法的好坏将直接影响到系统的性能。
不适当的算法可能会导致进程发生“抖动”,即刚被换出的页很快又要被访问,需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，有需将它调入,如此频繁地更换页面,以致一个进程在运行中把大部分的时间都花费在页面置换工作上。
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
改进页面置换算法,可以降低页面失败率,从而有效地提高系统性能。
从理论上讲，应将那些以后不再会访问的页面置换出来，或把那些在较长时间内不会再访问的页面调出。
目前已有多种置换算法,它们都试图更接近于理论上的目标。
1.3设计特点本设计作品主要用Ｃ语言编写而成,结构简单,语言易懂,条理清晰。
本作品兼容性也非常的高，可以在各种可以编译C语言的编译软件上运行,并能够在cyg ｗin中运行,经多次调试,暂时未发现有何不足。
本程序的另一个优点是,程序可以计算大数量数据。
如，本程序可以计算的最大物理块个数达到了10000个,用户输入的页面引用串个数也能达到10000个以上。
但是,实际生活中系统的物理块个数一般不会达到10000个。
因此，我们在提示用户输入页面引用串个数是,只提示最大输入1０0个。
但是代码不足在于使用到了较多的ｓtatｉc全局变量使得整个代码质量不是很好,而且也只是简单的根据算法设计来模拟实现整个过程。
我通过先查找该页面是否在页帧中存在,若不存在则需要页面置换,通过刷新每个页帧的ｔime值来得到每次的最小值来进行页面的置换，最小值即代表着最近最少使用的页面。
经过测试,这个系统已经达到了题目中的全部要求。
这个程序有很多优点有一个是界面简明,简洁明了的程序菜单;一个是智能化的模块设计,减少了许多人工操作,如功能模块操作结束后,均会返回主菜单进行下一模板的运行,并提示是否再进行类似的操作，这样给用户带来了操作的方便，大大提高了学生选课的效率还有就是提示语言既简洁又明确,层次分明等等;当然也有缺点如程序仍然存在不合理的地方，例如程序某些部分输入错误不能立刻返回改正;信息表达方式不丰富,比较单一，缺少图片、音乐等元化表达方式。
FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。
这种算法基于CPＵ按线性顺序访问地址空间的这个假设上,许多时候,CＰU不是按吸纳型顺序访问地址空间的。
所以，那些在内存中停留时间最长的页往往被访问到。
这就造成ＦＩFＯ算法的缺页率不太理想。
并且,FIFO还有一个缺点就是Belady奇异现象。
实现FＩＦO算法无需硬件提供新的帮助,只采用循环数组管理驻留集即可。
OＰT算法被誉为“最佳算法”,因为他淘汰下次访问距当前最远的那些页中序号最小的一页。
所以，OＰＴ算法得出的缺页率是最小的。
但是，ＯPT算法在使用前必须先得知整个访问串,这很难实现。
因此，OPT算法知识一种概念中的算法。
LRU算法的实现耗费较高,并且需要硬件的支持，但是效果较好。
就缺页率而言，OPT算法最佳,FＩFO算法最差。
１.４基础知识1.４.１先进先出置换算法(FＩＦO)FIFO算法是最早出现的算法。
该算法总是淘汰最先进入内存的页面,即选择在内存驻留时间最久的页面予以淘汰。
该算法实现简单，只需要把一个进程已调入内存的页面按先来后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。
但是该算法与进程实际运行的规律不相符合,因为在进程中,有些页面经常被访问。
１.４.2 最近最久未使用算法（LＲＵ)选择最近一段时间最长时间没有被访问过的页面予以淘汰。
LＲU算法是根据页面调入内存后的使用情况进行决策。
由于无法预测各页面将来的使用情况,采取“最近的过去”作为“最近的将来”的近似。
选择最近最久未使用的页面予以淘汰。
实现:赋予每个页面一个方位字段，用来记录一个页面自上次被访问以来所经历的时间T,当要淘汰一个页面的,选择现有页面中其T值最大的,即最近最久未使用的页面予以淘汰。
1．4.３最佳置换算法(OPT)最佳置换算法所选择的被淘汰掉的页面,将是以后永久不再使用的，或许是在最长(未来)时间内不再被访问的页面。
采用最佳置算法,通常可保证获得最低的缺页率。
本模拟算法中，最佳页面置换算法实现所采用的思想是：循环读入每个页表项,若该页表在内存中，则读取下一个页表项。
若页表不存在内存中：一种情况是内存不满，则将页表放入内存中；若内存块已满，刚分别计算内存中各个页表再次被使用的时间，并将最久不被访问的调出，放入当前读入页表项。
2 各模块伪代码算法根据程序提示,用户先将需要计算的页面号引用串，物理块数量和引用串个数输入到文件流中。
待程序加载数据完成后,用户继续选择页面置换算法的类型，程序根据用户输入的信息来判断采用哪一种算法进行计算。
结构如图2.1所示。
图2．1 总体结构图2.1伪代码概念伪代码（英语：pseudｏｃoｄe),又称为虚拟代码，是高层次描述算法的一种方法。
使用伪代码的目的是让被描述的算法可以容易地以任何一种编程语言(Pascaｌ，C,Java,etc)实现。
因此，伪代码必须结构清晰、代码简单、可读性好,介于自然语言与编程语言之间。
以编程语言的书写形式指明算法职能。
使用伪代码,不用拘泥于具体实现。
它是半角式化、不标准的语言。
可以把整个算法运行过程的结构用接近自然语言的形式(可以使用任何一种你熟悉的文字,关键是把程序的意思表达出来）描述出来。
2.2伪代码算法2．2.1主函数伪代码算法该程序是按自上而下，自顶向下的设计思想进行设计的。
程序各个功能的实现之间的联系采用函数调用与函数嵌套。
main()函数是整个程序的入口,程序的开始就是从这里开始的，然后通过maｉｎ()函数调用其他函数来实现各个功能。
具体流程如图2.2所示。
图２.２主函数流程图Ｂegin ／＊算法开始＊/调用desigｎＢy()→显示出设计者信息ﻩScanf ｍSIZE,pSIZE,page[1０0] /*mＳＩＺE表示物理块,pSIZE表示页面号引用串个数，page［10０]表示一个引用串的页面号*/ﻩdo {ﻩﻩPrintf paｇe[ｉ］ﻩＳcanｆcodｅ/*ｃｏde是一个标记，用来判断用户输入是否符合要求*/ﻩﻩＳwiｔch(cｏde){ｃase1: ＦIFO() /*先进先出算法*／cａse ２: LRU(）／*最近最久未使用算法*/ﻩﻩｃase ３:ＯPＴ（) /*最佳置换算法*／ﻩcase 4:exｉt(０)/*退出程序＊／deｆauｌt:重新输入ﻩ}ﻩ}whｉｌｅ(ｃodｅ!=4)ﻩﻩGeｔch(用户输入)Ｅnd2．2．2延迟时间函数伪代码算法ﻩbeginﻩﻩ变量定义whｉle ｄｅlay>０{ｗｈilｅi<1２4ﻩ退格ﻩﻩﻩ}ﻩend图２.3 延迟时间函数流程图延迟时间函数主要由两个fｏr循环构成。
延迟时间函数在程序中主要起延迟时间的作用，相当于一个定时器,给程序数据加载，数据处理等提供时间保证。
使程序能够正常的进行。
其具体流程如图２.3所示。