操作系统课程设计报告-内存管理.doc

山东科技大学学生课程设计设计1 题目 内存管理一、问题描述与分析1、虚拟存储技术为了扩充内存容量，同时避免增加系统成本以及机器自身的限制，因此采取从逻辑上扩充内存容量的方法，即虚拟存储技术。2、解决方法程序运行之前，仅将当前需要运行的少数页面先装入内存便可继续运行，其余部分暂存在盘上。程序运行时，如果他所要访问的页面已调入内存，便可继续执行下去；但如果程序所要访问的页面尚未调入内存，此时程序应利用OS提供的请求调页功能，将他们调入内存，以是进程能继续执行下去。如果此时内存已满，无法再装入新的页面，则还需在利用页面的置换功能，将内存中暂时不用的页面调至盘上，腾出足够的内存空间，再将要访问的页面调入内存，使程序继续执行下去。二、设计要求和目的1、设计目的在本课程设计中，通过对“请求分页存储管理方式”中“页面置换算法”的模拟实现，进一步了解虚拟存储的特点，掌握请求分页存储管理的页面置换算法、2、设计要求模拟页面置换设计中，分别利用最佳置换算法（OPT）、最近最久未使用置换算法（LUR）、先进先出置换算法（FIFO）。需要提供一定数量的页面序列，这些页面序列为了减少人工输入的麻烦，而采用随机产生。在执行程序时，只要改变页面的大小，就可以达到不用的页面序列。同时，记录页面置换次数，最后计算并输出OPT、LUR、FIFO算法在不用页面数量下的缺页率。三、背景知识 在学习了操作系统这本书之后，了解到：为了扩充内存容量，采取虚拟存储技术，其中的核心思想就是从逻辑上扩充内存容量。所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。在虚拟存储器中，允许讲一个作业分多次调入内存，因此虚拟内存气的实现都毫无例外的建立在离散分配的存储器方式的基础上。于是采用了分页请求系统来实现。即，增加了请求调页和页面置换功能的所形成的页面虚拟存储系统。分页请求系统，它允许只装入少数页面的程序及数据，先启动运行。以后再通过调页功能及页面置换功能，陆续的把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供相应的硬件和软件支持。硬件支持包括：请求分页的页表机制、缺页中断机构、地址变换机构。软件支持在这里包括有用于实现请求调页的软件和实现页面置换的软件。他们在硬件的支持下，将程序正在运行时所需要的页面调入内存，再将内存中暂时不用的页面从内存置换到硬盘上。在进程运行过程中，若其所要访问的页面不在内存而要把他们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中，但应将哪个页面调出，需根据一定的算法来确定。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的页面更换频率，从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会在访问的页面调出。四、概要设计根据三种不同的置换算法，依据其不同的算法方式、算法思想，分别计算该算法在不同情况下的缺页率，并显示各页面的变化情况。对于该课程设计中模拟的请求分页存储管理的页面置换过程，只要掌握其中最基本的三种算法，包括FIFO、LRU及OPT。 同时要求产生随机序列。在下图的主模块设计图中，只注重描绘了分页存储管理的三种主要算法，未描绘出细节部分。其中，在执行每种算法时都会要求输入你所需要的访问串长度以及不同内存容量（物理块数），如此就可以得出不同的缺页率。OPTLURFIFO内存管理 请求分页存储管理的主模块设计图五、详细设计1、算法原理分析OPT算法是一种理论上的算法。所选择的被淘汰的页面是未来最远出现，当当前内存中没有正要访问的页面时，置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。采取OPT算法，通常可保证获得最低的缺页率。LRU算法是根据页面调入内存后的使用情况进行决策的。所选择的被淘汰的页面是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。 FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面进行淘汰。当当前内存中没有正要访问的页面时，置换出最先进来的页面。2、核心代码1）OPT算法：private void opt() /理想型int pos = new int10;int flag = new int10;boolean S = true;while(S)flag1=flag2=0;for(int i = 0;i length; i+)if(!search(orderi)count+;/result1i=*;if(anum_page-1!=-1) /表示当前页面已满要淘汰一个 for(int j=0 ;j10; j+) posj = -1; for(int j=0;j10;j+) flagj = 0;for(int j=i;jlength;j+)/找出当前页中的值在将来访问串中对应的最近位置for(int k=0;knum_page;k+)if(orderj=akflagk=0)posk=j;flagk=1;int max=-10,max_pos = 0;for(int k=0;knum_page;k+)/找出位置最远的那个值if(posk=-1)/未出现则跳出，替换该值max_pos=k;S = false;break;else if(maxposk)max=posk;max_pos=k;amax_pos=orderi;else /还有空页for(int j=0;jnum_page;j+)if(aj=-1)aj=orderi;S = false;break;else result1i= ;for(int j=0;jnum_page;j+)resultji=aj; if(flag1=0flag2=0) S = false;break; 其中的查询函数search（）的具体代码如下：private boolean search(int n) /查找当期内存是否已存在int i;for(i = 0; i num_page; i+)if(ai = n)return true;return false;2）、OPT程序流程图NNYY开始输入内存中分配页数NY还有请求访问页？内存中是否已存在？直接复制前一列内容内存有空页？直接插入替换内存中将来不出现或离当前最远的页输出全部页面变化情况结束据第一个访问页初始化第一列值3）LRU算法private void lru() /最久最近没使用int pos = new int10; /用来记录 距离当前页中的值最近位置boolean s = true;while(s)count=0;flag1=flag2=0;for(int i = 0; i 10; i+)posi = -1;for(int i = 0; i length; i+)if(!search(orderi) /表示当期内存不存在 /若页面同时满了就要进行页面置换count+;/result1i = *;if(anum_page-1 != -1) /表示当前页面已满要淘汰一个for(int j = 0;j i; j+) /找出当前页中的值在过去访问串中对应的最近位置for(int k = 0;k num_page; k+)if(orderj = ak)posk = j;int min=pos0,min_pos=0;for(int k = 1;k num_page; k+)/找出位置最远的那个if(min posk)min = posk;min_pos = k;amin_pos=orderi;else /还有空页for(int j = 0;j num_page; j+)if(aj = -1)aj=orderi;s = false;break;else result1i = ; /当期内存已经存在，不需要进行页面置换for(int j = 0;j num_page; j+)resultji = aj; if(flag1 = 0 flag2 = 0) s = false;break; 3）LRU程序流程图NNYY开始输入内存中分配页数NY还有请求访问页？内存中是否已存在？直接复制前一列内容内存有空页？直接插入替换内存中最近最远未用的一页输出全部页面变化情况结束据第一个访问页初始化第一列值4）FIFO算法private void fifo() /先进先出int thisn = 0;boolean s = true;while(s)count = 0;flag1 = 0;flag2 = 0;for(int i = 0; i length; i+)if(!search(orderi) /表示当期内存不存在 /若页面同时满了就要进行页面置换count+;/result1i = *;if(anum_page-1 != -1) /表示当前页面已满要淘汰一个athisn= orderi; /把第一个更新为当前的thisn+;if(thisn=num_page)thisn=0;elsefor(int j=0;jnum_page;j+)if(aj=-1)aj=orderi;s = false;break;else result1i = ; /当期内存已经存在，不需要进行页面置换for(int j=0;jnum_page;j+)resultji=aj; if(flag1=0flag2=0) s = false;break; 4）FIFO程序流程图NNYY开始输入内存中分配页数NY还有请求访问页？内存中是否已存在？直接复制前一列内容内存有空页？直接插入替换内存中驻留时间最久的页面输出全部页面变化情况结束据第一个访问页初始化第一列值六、结果分析1、界面提示弹出，输入访问串的长度页面提示弹出，输入访问串的长度页面2、运行结果1）OPT算法结果2）LRU算法结果2）FIFO算法结果七、总结本次课程设计目的是通过对请求分页存储管理方式中页面置换算法进行模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。随机页面产生程序，计算并输出FIFO及LRU算法在不同内存容量下的缺页率。页面置换算法，内容包括最佳置换算法（OPT）、最近最久未使用置换算法（LUR）、先进先出置换算法（FIFO），3种算法思想简单明确，选好数据结构，思路清晰便基本没问题了。这次操作系统的课程设计在接到内存管理的任务后，由于一开始不知道具体需要实现什么。在咨询过老师后，知道就是实现对置换算法的模拟。于是相对容易许多。对于随机页面产生程序，在网上查阅资料，使用了库函数random()，实现了简单的随机页面产生程序，功能基本完成。做了这么多次课程设计了，大致的过程都熟悉了，每次的动手实践，调动了我们主动学习的积极性, 并引导我们根据实际