操作系统实验-内存管理

广州大学学生实验报告开课学院及实验室：计算机科学与工程实验室2015年11月29日实验课程名称操作系统实验成绩实验项目名称实验3内存管理指导老师一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容1、常用页面置换算法模拟实验设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1）、最佳淘汰算法（OPT）2）、先进先出的算法（FIFO）3）、最近最久未使用算法（LRU）4）、最不经常使用算法（LFU）5）、最近未使用算法（NUR）命中率＝１－页面失效次数／页地址流长度2、在Linux环境下利用下列系统调用malloc()，free()编写一段程序实现内存分配与回收的管理。要求：1)、返回已分配给变量的内存地址；2)、返回释放后的内存地址；3)、释放已分配的内存空间后，返回释放内存后未使用内存的大小。三、实验原理一、虚拟存储系统UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。二、页面置换算法当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。常用的页面置换算法有1、最佳置换算法（Optimal）2、先进先出法（FisrtInFirstOut）3、最近最久未使用（LeastRecentlyUsed）4、最不经常使用法（LeastFrequentlyUsed）5、最近未使用法（NoUsedRecently）四、实验设备Win7下虚拟机VMware-workstation-11.0.0及CentOS-5.8-i386五、实验要求书写实验报告。提交实验报告。报告主要以操作结果以及分析回答实验中问题为主，可以以截图进行说明。六、实验程序T4:#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineINVALID-1#definetotal_instruction320/*指令流长*/#definetotal_vp32/*虚页长*/#defineclear_period50/*清0周期*/typedefstruct/*页面结构*/{intpn,pfn,counter,time;}pl_type;pl_typepl[total_vp];/*页面结构数组*/structpfc_struct{/*页面控制结构*/intpn,pfn;structpfc_struct*next;};typedefstructpfc_structpfc_type;pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];intpage[total_instruction],offset[total_instruction];intinitialize(int);intFIFO(int);intLRU(int);intLFU(int);intNUR(int);intOPT(int);intmain(){ints,i,j;srand(10*getpid());/*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/s=(float)319*rand()/32767/32767/2+1;//for(i=0;itotal_instruction;i+=4)/*产生指令队列*/{if(s0||s319){printf(Wheni==%d,Error,s==%d\n,i,s);exit(0);}a[i]=s;/*任选一指令访问点m*/a[i+1]=a[i]+1;/*顺序执行一条指令*/a[i+2]=(float)a[i]*rand()/32767/32767/2;/*执行前地址指令m'*/a[i+3]=a[i+2]+1;/*顺序执行一条指令*/s=(float)(318-a[i+2])*rand()/32767/32767/2+a[i+2]+2;if((a[i+2]318)||(s319))printf(a[%d+2],anumberwhichis:%dands==%d\n,i,a[i+2],s);}for(i=0;itotal_instruction;i++)/*将指令序列变换成页地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i=32;i++)/*用户内存工作区从4个页面到32个页面*/{printf(---%2dpageframes---\n,i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);}return0;}intinitialize(total_pf)/*初始化相关数据结构*/inttotal_pf;/*用户进程的内存页面数*/{inti;diseffect=0;for(i=0;itotal_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID;/*置页面控制结构中的页号，页面为空*/pl[i].counter=0;pl[i].time=-1;/*页面控制结构中的访问次数为0，时间为-1*/}for(i=0;itotal_pf-1;i++){pfc[i].next=&pfc[i+1];pfc[i].pfn=i;}/*建立pfc[i-1]和pfc[i]之间的链接*/pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0];/*空页面队列的头指针为pfc[0]*/return0;}intFIFO(total_pf)/*先进先出算法*/inttotal_pf;/*用户进程的内存页面数*/{inti,j;pfc_type*p;initialize(total_pf);/*初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NULL;/*忙页面队列头，队列尾链接*/for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID)/*页面失效*/{diseffect+=1;/*失效次数*/if(freepf_head==NULL)/*无空闲页面*/{p=busypf_head-next;pl[busypf_head-pn].pfn=INVALID;freepf_head=busypf_head;/*释放忙页面队列的第一个页面*/freepf_head-next=NULL;busypf_head=p;}p=freepf_head-next;/*按FIFO方式调新页面入内存页面*/freepf_head-next=NULL;freepf_head-pn=page[i];pl[page[i]].pfn=freepf_head-pfn;if(busypf_tail==NULL)busypf_head=busypf_tail=freepf_head;else{busypf_tail-next=freepf_head;/*free页面减少一个*/busypf_tail=freepf_head;}freepf_head=p;}}printf(FIFO:%6.4f\n,1-(float)diseffect/320);return0;}intLRU(total_pf)/*最近最久未使用算法*/inttotal_pf;{intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID)/*页面失效*/{diseffect++;if(freepf_head==NULL)/*无空闲页面*/{min=32767;for(j=0;jtotal_vp;j++)/*找出time的最小值*/if(minpl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];//腾出一个单元pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head-next=NULL;}pl[page[i]].pfn=freepf_head-pfn;//有空闲页面,改为有效pl[page[i]].time=present_time;freepf_head=freepf_head-next;//减少一个free页面}elsepl[page[i]].time=present_time;//命中则增加该单元的访问次数present_time++;}printf(LRU:%6.4f\n,1-(float)diseffect/320);return0;}intNUR(total_pf)/*最近未使用算法*/inttotal_pf;{inti,j,dp,cont_flag,old_dp;pfc_type*t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i++){if(pl[page[i]].pfn==INVALID)/*页面失效*/{diseffect++;if(freepf_head==NULL)/*无空闲页面*/{cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0;if(dp==old_dp)for(j=0;jtotal_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;freepf_head-next=NULL;}pl[page[i]].pfn=freepf_head-pfn;freepf_head=freepf_head-next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;jtotal_vp;j++)pl[j].counter=0;}printf(NUR:%6.4f\n,1-(float)diseffect/320);return0;}intOPT(total_pf)/*最佳置换算法*/inttotal_pf;{inti,j,max,maxpage,d,dist[total_vp];pfc_type*t;initialize(total_pf);for(i=0;itotal_instruction;i++){//printf(InOP