4存储管理--发给学生

1实验四存储管理1.实验目的通过请求页式存储管理中页面置换算法的模拟程序设计，了解虚拟存储技术的特点，掌握请求页式存储管理的FIFO（First-inFirst-outAlgorithm，先进先出置换算法）、OPT（OptimalAlgorithm，最佳置换算法）、LRU（LeastRecentlyUsedAlgorithm，最近最少使用置换算法）页面置换算法。了解LFU算法和NUR算法。2.实验类型：验证型3.实验学时：44.实验原理和知识点(1)请求页式虚拟内存管理页面置换原理我们已经知道，进程运行前须全部装入内存。采用虚拟内存管理技术，进程不必全部装入内存，而只要装入一部分就可以运行。这是怎么实现的呢？分页管理原理把内存物理空间划分为长度相等的块，每一块叫做一个页框（也叫页框、物理块），用同样的大小划分进程逻辑空间，将逻辑空间划分为一个个的页面，(图3.1)。进程装入内存时，以页为单位装入。由于页长等于页框长,一页恰好可以放到一个页框中。进程放入内存时，可以不连续存放。那么系统怎么知道某个页框是属于哪个进程的页呢？图3.1页面与页框页表某页面装入内存时，页面与页框的对应关系记录在页表中。CPU访问某一页面时，只要查页表就可以知道对应的页框，然后到该页框中取指令或操作数(图3.2)。2图3.2页表虚拟存储管理思想：进程不是一次性地全部装入内存，而只装入将要执行和调用的部分。其他部分则留在磁盘上，在需要的时候再动态装入。请求分页虚拟存储管理思想：进程执行时，只装入将要访问的一些页，其它页放在磁盘上。当需要访问那些其它页时，再从磁盘装入内存（图3.3）。图3.3请求分页虚存管理请求分页虚拟存储管理过程：进程访问某一页时，系统先查页表，若页表中有该页，则可以访问相应的页框。若页表中找不到该页，说明该页不在内存中而在磁盘上，这时，会产生缺页中断，然后由缺页中断处理程序从磁盘调入相应页，并修改页表。调入新页时，会有两种情况：情况1，有足够内存。直接调入新页即可。情况2，内存不够。这时，需要移走某些页，以腾出空间，然后调入新页到腾出的空间。这个过程称之为页面置换。当要置换一页时，移走那一页合适呢？这取决于采用什么置换算法。常用的置换算法有先进先出算法（FIFO）、理想淘汰算法（OPT）、最近最久未使用算法(LRU)(2)页面置换算法先进先出算法（FIFO）：置换最早调入内存的页面。最佳淘汰算法（OPT）：置换将来被访问的距当前页面最远的页面。最近最久未使用算法（LRU）：置换过去被访问的距当前时间页面最远的页面。(3)缺页率3(1)进程运行时，所要访问的页的序列称为引用串，又叫访问串。(2)缺页率＝(缺页数/访问串长度)×100%(3)命中率＝(1－缺页率)×100%【例】设操作系统分配给进程P共3个页框，P的访问串为7,0,1,2,0,3,0,4,2,3,0,3,2。①FIFO置换过程访问串7012030423032页框A7772222444000页框B000033322222页框C11110003333缺页××××××××××缺页数：10缺页率：10/13=76.9%②OPT置换过程访问串7012030423032页框A7772222222222页框B000000444000页框C11133333333缺页×××××××缺页数：7缺页率：(7/13)×100%=53.8%③LRU置换过程访问串7012030423032页框A7772222444000页框B000000003333页框C11133322222缺页×××××××××缺页数：9缺页率：(9/13)×100%=69.2%5.实验内容实验要求：如果已经给出正确的源代码，仅贴出包含自己姓名或者学号的运行截图，若没有正确的源代码，贴出改正后的或自己设计的算法源代码，并贴出包含自己姓名或者学号的运行截图。【任务1】设计算法模拟程序：从键盘输入访问串。计算FIFO算法在不同内存页框数时的缺页数和缺页率。(1)算法设计FIFO算法的原理是置换最早调入内存的页。实际算法设计是建立一个忙页面链，每访问一页，判断是否在此链中，若不在，则加入到链中。缺页时，若需替换，淘汰忙页面链首的页面。定义页表结构：structpl_type{intpn;//页号，是固定的。pageintfn;//页框号，是变化的。frame4};/*站在进程的角度，查找程序或数据所在页面对应的页号*/定义页框链表结构:structfl_type{intpn;//页号，是变化的。intfn;//页框号，是固定的。structfl_type*next;//链接指针};/*站在操作系统的角度，管理内存空间，确定分给进程的N个页框的使用情况：分为空闲页框链表和忙页框链表。*/定义页表：pl_typepl[512];准备页框链表结点空间：fl_typefl[512];定义空闲页框链表指针：fl_type*free_head；定义忙页框链表指针：fl_type*busy_head,*busy_tail;定义访问串：intpage[512];进程访问某页时，先用页号page[i]查页表pl[]，若找不到，则摘取空闲页框链表首结点作为忙页框链表尾结点，再把页号page[i]放入该结点pn成员，把该结点fn值填入页表。摘取空闲页框时，若无空闲页框（即free_head为NULL），则先摘取忙页框链表首结点并把它加入空闲页框链表，页表中相应的fn成员改为无效。下面以例子来说明。设：分配给进程的页框数为3，访问串为3,0,1,0,2,0,4,2。访问串page[]={3,0,1,0,2,0,4,2};初始化的空页表如图3.4所示。初始化代码为：for(i=0;i8;i++){//为了描述简单，这里假定页表长为8pl[i].pn=i;//页号pl[i].fn=INVALID;//页框号为-1，（开始时，-1表示页还未装入到页框）}图3.4空页表初始化的空闲页框链表如图3.5所示。分给进程的页框数为3，初始化代码为：for(i=1;i3;i++){fl[i-1].next=&fl[i];//建立fl[i-1]和fl[i]间的链表接fl[i-1].fn=i-1;}fl[3-1].next=NULL;//链表表末尾为空指针fl[3-1].fn=3-1;//末尾结点的页框号free_head=&fl[0];//空页框队列的头指针指向fl[0]图3.5空闲页框链表开始时，忙页框链表为空（图3.6）。5图3.6忙页框链表进程访问页号3（即page[0]），访问后的状态如图3.7所示。空闲页框分配步骤如下：(a)查页表：if(pl[page[0]].fn==-1)为真，发生缺页，缺页数加1。(b)保存空闲页框链表第2个结点:p=free_head-next;(c)摘取空闲页框头结点:free_head-next=NULL;(d)把页号3调入摘取的结点：free_head-pn=page[0];(e)修改页表，记录对应的页框号：pl[page[0]].fn=free_head-fn;(f)摘取的结点加入忙页框链表：busy_head=busy_tail=free_head;(g)空闲页框链表被摘走一个结点，头指针前移：free_head=p;图3.7访问页号3后的页表和页框链表进程访问页号3,0,1后，页表和页框链表状态如图3.8所示。图3.8访问页号3,0,1后的页表和页框链表6接下来访问页号0。查页表，由于0页已分配了页框（即已在内存中），可直接访问。页表和页框链表不发生变化。在接下来访问页号2。查页表，该页未分配页框，发生缺页。这时，无空闲页框（即free_head为NULL）。须淘汰忙页框链表首结点，淘汰步骤为：(a)保存忙页框链表第二个结点：p=busy_head-next;(b)修改页表，使相应页框号无效：pl[busy_head-pn].fn=-1;(c)摘取忙页框链表头结点，加入空闲页框链表：free_head=busy_head;free_head-next=NULL;(d)忙页框链表被摘走一个结点，头指针前移：busy_head=p;现在，有空闲页框了。接下来按前面所述的空闲页框分配步骤进行页框分配，再调入新页。访问后，页表和页框链表的状态如图3.9所示。图3.9访问页号3,0,1,0,2后的页表和页框链表(2)上机操作键入vipage.cpp（注：文件名扩展名须为.cpp）键入i并输入下列源代码。#includeiostream.h#includestdio.h#ifndefTRUE#defineTRUE1#defineFALSE0#endif#ifndefNULL#defineNULL0#endif#defineINVALID-1//定义结构类型structpl_type{//页表结构7intpn;//页号intfn;//页框号};structfl_type{//页框结构intpn;//页号intfn;//页框号structfl_type*next;//链表接指针};//定义结构变量pl_typepl[512];fl_typefl[512],*free_head,*busy_head,*busy_tail;intpage[512];//访问串（存放每条指令的页号）intTOTAL_PAGES;//访问串长度intdiseffect;//缺页故障数//初始化函数：初始化页表和页框链表//形参total_pf为分配给用户进程的内存页框数voidinitialize(inttotal_pf){inti;diseffect=0;//页故障数初始化为0//建立空页表for(i=0;i512;i++){pl[i].pn=i;//页号pl[i].fn=INVALID;//页框号为-1，（开始时，页还未装入到页框）}//建立空闲页框链表for(i=1;itotal_pf;i++)//{fl[i-1].next=&fl[i];//建立fl[i-1]和fl[i]间的链表接fl[i-1].fn=i-1;}fl[total_pf-1].next=NULL;//链表表末尾为空指针fl[total_pf-1].fn=total_pf-1;//末尾结点的页框号free_head=&fl[0];//空闲页框链表头指针指向fl[0]busy_head=busy_tail=NULL;//忙页框链表初始化为空}8//FIFO函数：计算FIFO算法下的缺页率voidFIFO(inttotal_pf){inti;fl_type*p;initialize(total_pf);//初始化页表和页框链表for(i=0;iTOTAL_PAGES;i++){if(pl[page[i]].fn==INVALID){//用页号page[i]查页表，若为INVALID,则页故障diseffect++;//记录缺页故障次数if(free_head==NULL){//若无空闲页框,下面5句淘汰一个忙页框,淘汰的是忙页框链表表的第一个页框p=busy_head-next;//保存空闲页框链表第2个结点pl[busy_head-pn].fn=INVALID;//修改忙页框链表头结点在页表中的页框号free_head=busy_head;//淘汰忙页框链表头结点，加入空闲页框链表首free_head-next=NULL;//断开忙页框链表头结点busy_head=p;//忙页框链表头指针前移}//将空闲页框分配给新页面page[i]p=free_head-next;//保存空闲页框链表第2个结点。free_head-next=NULL;//断开空闲页框链表头结点（即摘取空闲页框头结点）free_head-pn=page[i];//新页装入摘取的空闲页框结点pl[page[i]].fn=free_head-fn;//修改页表：记录装入的页框号//将新页加入忙页框链表if(busy_head==NULL){//若忙页框链表为