课程设计说明书题目: 页面置换算法院系：计算机科学与工程专业班级：物联网13-1班学号：20133030**学生姓名：**指导教师：**2015年 12月 30 日安徽理工大学课程设计（论文）任务书2015年11月18日安徽理工大学课程设计（论文）成绩评定表目录1问题描述 (1)1.1设计目的 (1)1.2算法描述 (1)1.3相关知识 (1)2需求分析 (3)2.1 先进先出淘汰算法算法(FIFO) (3)2.2 最久未使用淘汰算法算法(LRU) (4)2.3最佳淘汰算法算法(OPT) (4)3概要设计 (5)3.1置换算法思想 (5)3.1.1最佳置换算法(Optimal) (5)3.1.2先进先出页面置换算法(FIFO) (6)3.1.3 最近最久未使用置换算法置换算法(LRU) (7)3.2 程序设计思想 (8)4详细设计 (9)4.1最佳置换算法(Optimal)基本思想及相关代码 (9)4.2 先进先出页面置换算法(FIFO)基本思想及相关代码 (10)4.3最近最久未使用置换算法(LRU)基本思想及相关代码 (11)5调试分析 (13)6用户手册 (14)7测试结果 (16)8设计体会 (18)9参考文献 (19)1问题描述1.1设计目的操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。
操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。
一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。
由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。
要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。
本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。
1.2算法描述⑴先进先出页面置换算法(FIFO)优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。
该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。
但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。
⑵最近最久未使用页面置换算法(LRU)如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。
它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。
这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。
当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
⑶最佳置换页面置换算法(OPT)最佳页面置换算法是Belady于1966年提出的一种理论上的算法。
是一种保证最少的缺页率的理想化算法。
1.3相关知识虚拟存储器的引入：局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。
虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
虚拟存储器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。
请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。
页面分配：平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。
按比例分配算法，根据进程的大小按比例分配物理块。
考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。
页面置换算法：常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。
2需求分析本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页面调度算法与过程，以掌握这种有用的技术。
要求将其输入/输出处理程序编成 一个独立的进程模块并与其它请求输入/输出的进程并发运行。
并要求加入设备 管理子模块。
2.1 先进先出淘汰算法算法(FIFO)当需要淘汰一页时，总是选择主存中居留时间最长（即最老)的一页淘汰。
系统保留一张次序表，该表记录了作业程序的各页面进入主存的先后次序。
用数组作次序表可在主存中建立一个m(m 是分配给该作业的存储块数)个元素的页号表和一个调换指针。
如图2-1所示：图2-1替换指针用存储分块表作次序表该次序表以块号为序，依次各块的分配情况。
这里假定m ＝4，且4，5，1，2页以依次装入2，6，7，4各存储块中。
此时存储分块表如图2-2所示：图2-2替换以前块号 页号 指针当需要第6页时将替换第4页块号页号指针图2-3 替换之后2.2 最久未使用淘汰算法算法(LRU)当需要淘汰一页时，总是选择最长时间未被使用的那一页淘汰。
用硬件实现此算法每一页可以设置一个R位的寄存器；每次访问一页时，将该页所对应寄存器的最左一位置1；每隔时间t将所有的R位寄存器右移一位。
这样，在T＝Rt时间内，方问过的页多对应的寄存器R内时一个不全为0的整数，而没有访问过的页相对应的R之值为0。
当缺页中断时，选择R值最小的那页进行淘汰。
2.3最佳淘汰算法算法(OPT)当需要淘汰一页时，将选择以后永不使用的或许是在最长(未来)时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。
3概要设计3.1置换算法思想3.1.1最佳置换算法(Optimal)它是由Belady于1966年提出的一种理论上的算法。
其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人目前还无法预知一个进程在内的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。
算法流程如图3-1所示：图3-1最佳置换算法流程图3.1.2先进先出页面置换算法(FIFO)这是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
算法流程如图3-2所示：图3.2 先进先出页面置换算法流程图3.1.3 最近最久未使用置换算法置换算法(LRU)FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存时间，而页面调入的先后并不能反映页面的使用情况。
最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
算法流程如图3-3所示：图3-3 最近最久未使用算法流程图3.2 程序设计思想选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换。
如图3-4所示：图3-4 程序设计流程图4详细设计4.1最佳置换算法(Optimal)基本思想及相关代码是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。
数组next[mSIZE]记录物理块中对应页面的最后访问时间。
每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。
/*最佳置换算法*/void OPT(){int memery[10]={0};int next[10]={0}; /*记录下一次访问时间*/int i,j,k,l,m;int max; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE) /*如果不在物理块中*/{count++;/*得到物理快中各页下一次访问时间*/for(m=0;m<mSIZE;m++){for(l=i+1;l<pSIZE;l++)if(memery[m]==page[l])break;next[m]=l;}/*计算换出页*/max=next[0]>=next[1]?0:1;for(m=2;m<mSIZE;m++)if(next[m]>next[max])max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/memery[max]=page[i];for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else {for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}compute();print(count);}4.2 先进先出页面置换算法(FIFO)基本思想及相关代码地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。
当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。
而用来选择淘汰哪一页的规则叫做页面置换算法。
最简单的页面置换算法是先入先出法(FIFO)。
/*先进先出页面置换算法*/void FIFO(){int memery[10]={0};int time[10]={0}; /*记录进入物理块的时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*//*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){/*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE) /*如果不在物理块中*/{count++;/*计算换出页*/max=time[0]<time[1]?0:1;for(m=2;m<mSIZE;m++)if(time[m]<time[max])max=m;memery[max]=page[i];time[max]=i; /*记录该页进入物理块的时间*/for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++)temp[i][j]=memery[j];}}compute();print(count);}4.3最近最久未使用置换算法(LRU)基本思想及相关代码当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。