存储器管理课程设计

课程设计报告课程：操作系统学号：0810110013姓名：班级：计算机科学与技术08本科师范教师：殷荣庆时间：2010年12月28日计算机科学与技术系设计名称：存储器管理日期：2010年12月28日设计内容：存储器是计算机系统的重要组成部分。近年来，存储器的容量虽然一直在不断扩大，但仍然不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有很大影响。页面置换算法是虚拟存储管理实现的关键，通过本次课程设计，我们能够理解页面是换算法的机制，在模拟实现FIFO,LRU,NRU和OPT几种经典页面置换算法的基础上，比较各种置换算法的效率以及优点，从而了解虚拟存储实现的过程。对比下列几种算法的命中率：（1）先进先出算法（FirstinFirstOut,FIFO）。（2）最近最少使用的算法（LeastRecentlyUsed,LRU）。（3）最近未使用算法（NeverUsedRecently,NUR）。（4）最佳置换算法（OptimalReplacement,OPT）。设计目的与要求：1、设计目的：本次课程设计主要为了了解内存的各种管理方式，要求掌握分区式、页式、段式、段页式存储管理方式，以及虚拟存储器的基本概念和请求调页、请求调段存储管理方式。明白一些基本概念和计算机的相关工作方式，如：处理机调度的基本概念、调度算法、实时调度、多处理机系统中的调度、死锁的基本概念、处理死锁的基本方法。通过动态优先权算法的模拟加深对进程概念和进程调度过程的理解。重点研究一下四点内容：（1）理解内存页面调度的机理。（2）掌握几种理论页面置换算法的实现方法。（3）了解HASH表数据结构的使用。（4）通过具体的上级操作与数据对比，比较各种各种调度算法的优劣。2、设计要求：自己编写代码，用各种不同的调度算法（先进先出算法、最近最少使用的算法、最近未使用算法、最佳置换算法）让计算机调度，计算出各种算法得出的命中率，根据计算机给出的命中率统计数据，比较各种调度算法的优劣。课程设计报告中要给出计算机统计出来的各种算法命中率的数据，然后说明对数据的具体分析步骤，最后总结出各种调度算法的优劣。设计环境或器材、原理与说明：一、设计环境：windowsxp操作系统、虚拟机、红帽Linux操作系统。二、设计器材：微型计算机三、设计原理：下面分别叙述各种页面调度机制的原理：1：FIFO页面置换算法：原理简述：（1）在分配内存页面数（AP）小于进程页面数（PP）时，当然是最先运行的AP个页面放入内存。（2）这时有需要处理的新页面，则将原来在内存中的AP个页面中最先进入的调出。（所以成为FIFO），然后将新页面放入。（3）以后如果再有新页面需要调入，则都按（2）的规则进行。算法特点：所使用的内存页面构成一个队列。图标描述：假设某个进程在硬盘上被划为5个页面（PP=5），以1，2，3，4，5分别表示，处理机调度他们的顺序（这取决于进程的本身）为：1,4,2,5,3,3,2,4,2,5.如果内存可以控制的页面数位3（AP=3），那么在使用FIFO算法时，这三个页面的内存使用情况如图所示：队列第1位1425333425队列第2位142555342队列第3位14222534不难看出本例子共患处页面8次，若用变量diseffect表示页面换入的次数，则diseffect=8.算法实现提示：要得到命中率，必须应该有一个常熟total_instructrion来记录页面总共使用的次数；此处需要一个变量记录总共换入页面的次数（需要换出页面，总是因为缺页中断而产生）diseffect.。（1）初始化。设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面序列，diseffect置零。（2）看main[]中是否有下一个元素，有就由main[]中获取该页面下标，并转到（3）；没有就转到（7）。（3）如果该page页已经在内存中，就转到（2）；否则就转到（4），同时未命中的diseffect加1.（4）观察pagecontrol是否占满，如果占满需将使用队列（（6）中建立的）中最先进入的（就是队列的第一个单元）pagecontrol单元清干净，同时将对应的page[]单元置为不在内存中。页面3进入，而此时三个页面中最先进入的页面4被调出页面5进入，而最先进入的页面1被调出虽然有页面需要处理，但是页面本身已在内存中，不需要再调入了（5）将该page[]与pagecontrol[]建立关系（可以改变pagecontrol.[]的标示位，也可以采用指针连接，总之至少要使对应的pagecontrol单元包含连个信息；一是他被使用了，二是哪个page[]单元使用的；page[]页包含两个信息；对应的pagecontrol单元号、本page[]单元已经在内存中。）（6）将用到的pagecontrol置入使用队列（这里的队列当然是一种先进先出的数据结构了，而不是泛指），返回（2）。（7）显示结果。2、LRY页面置换算法：原理简述：（1）当分配内存页面数（AP）小于进程页面数（PP）时候，当然把最先执行的AP个页面放入内存。（2）当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面（称为LRU）算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。图标描述：为了便于比较，我采用的例子和前面的一样。某进程在硬盘上被化为5个页面，用1,2,3,4,5表示，处理机处理他们的顺序为：“1,2,4,2,5,3,3,2,4,2,5.而内存可以控制的页面数为3（AP=3），那么在使用LRU算法时候，这三个页面的内存使用情况如图所示：最近1步使用1425332425最近2步使用142553242最近3步使用14225334虽然页面的位置发生改变，但是没有发生页面置换不难看出页面换入次数为7次，diseffect=7。算法实现提示：与前述算法一样，只有先得到diseffect才能获得最终的命中率。（1）初始化。主要是进出页面page[]和分配的内存页面pagecontrol[]，同时产生随机序列main[]，diseffect置零。（2）看序列main[]是否有下一个元素，如果有就从main[]获取该page[]的下标，并转到（3）；没有就转到（6）。（3）如果该page[]单元在内存中便改变页面属性，使他保留最近使用的信息，转到（2）；否则转到（4），同时diseffect加（1）。（4）判断是否有空闲内存页面，如果有就返回页面指针，转到（5）；否则在内存页面中找出最长时间没有使用的页面，将其清干净，并返回该页面指针。（5）如果需要处理的page[]与（4）中得到的pagecontrol[]之间建立连接，同时应该让对应page[]单元保存最近使用的信息，返回（2）。（6）如果序列处理完成，就输出结果。3、NUR页面置换算法：原理简述：所谓“最近未使用”首先是要对“近”作一个界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次进程页面处理工作中，都没有处理到的页面；那么可能会有以下几种情况。（1）如果这样的页面只有一个，就将其换出，放入需要处理的新页面。（2）如果有不止一个这样的页面，就在这些页面中任取一个换出（可以是下标最小的，或者是下标最大的），放入需要处理的页面。（3）如果没有这样的一个页面，就随意换出一个页面（可以是下标最小的，也可以是下标最大的）。算法特点：有一个循环周期，每到达这个周期，所有的页面存放是否被CPU处理的信息的属性均被至于初始态（没有被访问）。图标描述：还是用前面的例子，某进程在硬盘上被划为5个页面，用1,2,3,4,5表示，而处理机处理他们的顺序为：1,4,2,5,3,3,2,4,2,5.而内存可以控制的页面数为3（AP=3），CLEAR_PERIOD取5；循环周期内如果所有内存页面均被CPU处理或者多个页面未被CPU处理，取页码最小的页面换出。算法实现过程如下：内存页1号1115333335内存页2号444444444内存页3号22222222显示页面交换共6次，diseffect=6。算法实现提示：（1）初始化。设置连个数组page[ap]和pagecontrol[pp]分别表示进程页面和内存分配的页面，并产生一个随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理进程页面序列，diseffect置零，设定循环周期CLEZAR_PERIOD。（2）看main[]是否有下一个元素，如果有，就从main[]中获得一个CPU将处理页面的序号；如果没有就转到（8）。（3）如果待处理页面在内存中，就转到（2）；否则diseffect加（1），并转到（4）。（4）看是否有空闲页面存在，如果有，返回空闲页面内存指针，并转到（5）；进程的5号页面进入，由于内存中三个页面均使用到了，故换出页码最小的1号页面所有页面设为“未访问”进程的5号页面进入，由于内存中三个页面均使用到了，故换出页码最小的1号页面否则，在所有没有被访问且位于内存中的页面中按任意规则（或则取最近的一个页面；或者取下标最小的一个）取出一个，返回清空后的内存页面指针。（5）在待处理进程页面与内存页面之间建立一个联系，并标注该页被访问。（6）如果CPU业已处理了CLEAR_PERIOD个页面，就将所有页面设置为未访问。（7）返回（2）。（8）如果CPU所有处理工作完成，就返回结果。4、OPT页面置换算法：原理简述：讨论该算法的前提还是在分配给进程的内存页面不满足其所有逻辑页面的情况下进行。所谓的最佳置换算法是一种理想状态下的算法，它要求先遍历所有的CPU待处理的进程页面序列（实际上由于待处理的页面有时取决于先前处理的页面，所以在很多情况下不可能得到完整的待处理页面序列。在这个层面上才能说该算法是理想的），在这些页面中，如果有些已经在内存当中，而CPU不再处理的，就将其换出；而有些页面在内存中，并且CPU即将处理，就从当前位置算起，取最后才处理到的页面，将其换出，例如CPU待处理的页面序列为：13224525143411553421已经处理了5个页面（底纹为灰色），那么页面5是第一个待处理的页面；2是第二个；1是第四个；4是第五个；3是第六个。这时如要将页面5调入内存，而在已经调入内存的1,3,2,4号页面中，页面3才上最后被处理的页面，因此将选择页面3换出。图表描述：还是用前面的例子，某进程在硬盘上被划分为5个页面，用1,2,3,4,5表示，而处理机处理他们的顺序为：1,4,2,5,3,3,2,4,2,5.而内存可以控制的页面数为3（AP=3），如果所示：内存页1号1115333335内存页2号444444444内存页3号22222222共发生页面交换6次，diseffect=6。算法实现提示：为了简易地实现OPT算法，可以为每个进程页面设置一个间隔属性cDistance表示CPU将在第几部处理该页面，如果页面不再被CPU处理，可以被设置为某个很大的值（例如32767），这样每次换出的就是page[ap]和pagecontrol[pp]分别表示内存页面数和内存分配的页面数，并产生一个随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面序列，diseffect置零。然后扫描整个页面访问序列，对vDistance[TOTAL_VP]数组进行赋值，表示该页面将在第几步进行处理。（2）看main[]是否有下一个元素，有，就从序列main[]中获取一个CPU待处理的页面号；没有，就转到（6）。（3）如果该页面已经在内存中了，就转到（2）；否则转到（4）。经分析发现以后不再处