存储管理实验报告

软件学院计算机课程实验报告册课程名称实验学期2011年至2012年第 2学期学生所在院（系）软件学院年级11软件 专业班级软工（1） 班学生姓名朱水云 学号 1115114034指导教师陈自刚实验最终成绩软件学院实验室制2012年 4月实验报告（ 三 ）实验教师:分数：实验名称：存储管理实验时间：2012年4月25号实验性质 应用性设计性综合性一、实验目的及要求：存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目 的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储 管理的页面置换算法。二、实验内容与分析设计：（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 50%的指令是均匀分布在前地址部分； 50%的指令是均匀分布在后地址部分。具体的实施方法是： 在0, 319的指令之间随即选取一起点m; 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0, m+1中随机选取一条指令并执行，该指令的地址为n； 顺序执行一条指令，其地址为m+ 1； 在后地址m + 2，319中随机选取一条指令并执行； 重复上述步骤-，直到执行320次指令。（2）将指令序列变换为页地址流 设：页面大小为1k； 用户内存容量为4页到32页； 用户虚存容量为32k。在用户虚存中，按每k存放10条指令排在虚存地址，即320条指令在虚存中的存放方式为： 第0条-第9条指令为第0页（对应虚存地址为0, 9）；第10条-第19条指令为第一页（对应虚存地址为10，19）；（3）计算并输出下述各种算法在不同内存容量下的命中率。 先进先出的算法（FIFO）； 最近最少使用算法（LRR）； 最佳淘汰算法（OPT）先淘汰最不常用的页地址； 最少访问页面算法（LFR）； 最近最不经常使用算法（N UR）。 其中和为选择内容。命中率=1-页面失效次数/页地址流长度在本实验中，页地址流长度为320，页面失效次数为每次访问相应 指令时，该指令所对应的页不在内存的次数。分析：随机数产生办法，Linux或UNIX系统提供函数st rand （）和rand（），分别进行初始化和产生随机数。 例如：srand （）;语句可初始化一个随机数； a0=10*rand（）/65535*319+1;al=10*rand()/65535*a0;语句可用来产生a0与al中的随机数。三、实验步骤与调试过程：1, 启动计算机并运行linux系统2, 打开中断进行程序书写3, 根据Linux系统的gcc自带编译器进行运行编译4, 分析运行出现的问题5, 观察运行结果，并思考6, 退出中断并写出实验报告调试过程:根据编译提示的错误进行修改四、实验结果：结果一:4 page framesFIF0:0.2562LRU:0.25310PT:0.3031LFU:0.2812NUR:0.28125 page framesFIF0:0.2969LRU:0.29060PT:0.3500LFU:0.3219NUR:0.30946 page framesFIF0:0.3375LRU:0.32810PT:0.3844LFU:0.3375NUR:0.33447 page framesFIF0:0.3563LRU:0.35630PT:0.4031LFU:0.3563NUR:0.35008 page framesFIF0:0.3937LRU:0.37500PT:0.4531LFU:0.3937NUR:0.37199 page framesFIF0:0.4219LRU:0.40940PT:0.4844LFU:0.4156NUR:0.406210 page framesFIF0:0.4375LRU:0.43130PT:0.5062LFU:0.4313NUR:0.425011 page framesFIF0:0.4813LRU:0.46250PT:0.5531LFU:0.4500NUR:0.465612 page framesFIF0:0.5406LRU:0.48750PT:0.5687LFU:0.4938NUR:0.487513 page framesFIF0:0.5500LRU:0.51880PT:0.5969LFU:0.5062NUR:0.543714 page framesFIF0:0.5594LRU:0.55310PT:0.6344LFU:0.5281NUR:0.546915 page framesFIF0:0.5687LRU:0.58440PT:0.6687LFU:0.5469NUR:0.581316 page framesFIF0:0.5781LRU:0.59380PT:0.6813LFU:0.5719NUR:0.596917 page framesFIF0:0.5906LRU:0.61560PT:0.6969LFU:0.6156NUR:0.615618 page framesFIF0:0.6156LRU:0.63120PT:0.7156LFU:0.6344NUR:0.653119 page framesFIF0:0.6687LRU:0.66560PT:0.7344LFU:0.6531NUR:0.671920 page framesFIF0:0.6875LRU:0.69690PT:0.7500LFU:0.6719NUR:0.690621 page framesFIF0:0.6906LRU:0.70940PT:0.7688LFU:0.6969NUR:0.718822 page framesFIF0:0.7125LRU:0.72190PT:0.7969LFU:0.7156NUR:0.734423 page framesFIF0:0.7156LRU:0.74060PT:0.8125LFU:0.7250NUR:0.781224 page framesFIF0:0.7281LRU:0.76250PT:0.8187LFU:0.7406NUR:0.771925 page framesFIF0:0.7469LRU:0.77500PT:0.8344LFU:0.7594NUR:0.800026 page framesFIF0:0.8125LRU:0.80000PT:0.8500LFU:0.7812NUR:0.806327 page framesFIF0:0.8313LRU:0.81870PT:0.8594LFU:0.8031NUR:0.828128 page framesFIF0:0.8438LRU:0.83750PT:0.8688LFU:0.8344NUR:0.846929 page framesFIF0:0.8688LRU:0.85310PT:0.8750LFU:0.8562NUR:0.856230 page framesFIF0:0.8781LRU:0.87190PT:0.8781LFU:0.8750NUR:0.868831 page framesFIF0:0.8938LRU:0.87500PT:0.8844LFU:0.8844NUR:0.890632 page framesFIF0:0.9000LRU:0.90000PT:0.9000LFU:0.9000NUR:0.9000结果二：4 page framesFIF0:0.2594LRU:0.25620PT:0.2687LFU:0.2437NUR:0.26255 page framesFIF0:0.3000LRU:0.30000PT:0.3000LFU:0.2969NUR:0.28756pageframesFIFO:0.3375LRU:0.3281OPT:0.3281LFU:0.3094NUR:0.32817pageframesFIFO:0.3563LRU:0.3563OPT:0.3688LFU:0.3312NUR:0.34698pageframesFIFO:0.4031LRU:0.4094OPT:0.3875LFU:0.3406NUR:0.37819pageframesFIFO:0.4156LRU:0.4281OPT:0.4156LFU:0.3656NUR:0.412510pageframesFIFO:0.4281LRU:0.4469OPT:0.4313LFU:0.3750NUR:0.440611pageframesFIFO:0.4531LRU:0.4688OPT:0.4594LFU:0.4281NUR:0.465612pageframesFIFO:0.4656LRU:0.4813OPT:0.4906LFU:0.4375NUR:0.493813pageframesFIFO:0.4750LRU:0.5000OPT:0.5219LFU:0.4625NUR:0.531214pageframesFIFO:0.4906LRU:0.5125OPT:0.5375LFU:0.4938NUR:0.550015pageframesFIFO:0.5312LRU:0.5250OPT:0.5625LFU:0.5281NUR:0.556316pageframesFIFO:0.5406LRU:0.5625OPT:0.5813LFU:0.5531NUR:0.584417pageframesFIFO:0.5906LRU:0.5813OPT:0.6188LFU:0.5750NUR:0.603118pageframesFIFO:0.6000LRU:0.5906OPT:0.6344LFU:0.5906NUR:0.625019pageframesFIFO:0.6312LRU:0.6156OPT:0.6438LFU:0.6219NUR:0.643820pageframesFIFO:0.6406LRU:0.6344OPT:0.6625LFU:0.6438NUR:0.675021pageframesFIFO:0.6969LRU:0.6594OPT:0.6875LFU:0.6656NUR:0.693722pageframesFIFO:0.7000LRU:0.6781OPT:0.7125LFU:0.6813NUR:0.684423pageframesFIFO:0.7156LRU:0.6906OPT:0.7312LFU:0.7188NUR:0.696924pageframesFIFO:0.7438LRU:0.7219OPT:0.7531LFU:0.7438NUR:0.746925pageframesFIFO:0.7594LRU:0.7562OPT:0.7656LFU:0.7656NUR:0.771926pageframesFIFO:0.7750LRU:0.7812OPT:0.7937LFU:0.7781NUR:0.778127pageframesFIFO:0.8125LRU:0.7969OPT:0.8094LFU:0.8125NUR:0.796928pageframesFIFO:0.8344LRU:0.8313OPT:0.8281LFU:0.8313NUR:0.840629pageframesFIFO:0.8406LRU:0.8594OPT:0.8531LFU:0.8375NUR:0.840630pageframesFIFO:0.8625LRU:0.8781OPT:0.8750LFU:0.8562NUR:0.859431pageframesFIFO:0.8812LRU:0.8812OPT:0.8906LFU:0.8781NUR:0.865632pageframesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000五、疑难与小结: 本实验的程序设计基本上按照实验内容进行。即首先用srand()和rand()函数定义和产生指令序列，然后 将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。从实验结果可知，在内存页面数较少(45页)时，五种算法的命中率差别不大，都是30%左右。在内存 页面为718个页面之间时，5种算法的访内命中率大致在35%60%之间变化。但是，FIFO算法与OPT算法 之间的差别一般在610个百分点左右。在内存页面为2532个页面时，由于用户进程的所有指令基本上 都已装入内存，使命中率增加，从而算法之间的差别不大。FIFO的命中率比OPT的还高。六、主要算法和程序清单#define TRUE 1#define FALSE 0#define INVALID -1#define NULL 0#define tot al_ins true tion 320/*指令流长*/#define tot al_vp 32/*虚页长*/#define elear_period 50/*清 0 周期*/typedef st ruet/*页面结构*/int pn; int pfn; int counter; int time;pl_type; pl_type pltotal_vp; typedef struct pfc_struct int pn; int pfn;struct pfc_struct *next;pfc_type;pfc_type pfctotal_vp, *freepf_head, int diseffect,/页号 logic number/页面框架号 physical frame number/计数器/时间*busypf_head,atot al_ins true tion; /* a为指令序列*/offsettotal/*页面线性结构一-指令序列需要使用地址*/*页面控制结构，调度算法的控制结构*/*busypf_tail;int pagetotal_instruction, int initialize(int); int FIFO(int); int LRU(int); int LFU (int);int NUR(int); /not use recently int OPT(in t);int main()int s,i,j; srand(10*getpid();机数队列的“种子” */ s=(float)319*rand( )/32767/32767/2+1; for(i=0;itotal_instruction;i+=4)ins tructio n;/*地址信息*/*由于每次运行时进程号不同，故可用来作为初始化随/*正态分布*/*产生指令队列*/if(s0|s319)pri ntf( When i=%d,Error,s=%dn,i,s);exi t(0);ai=s;/*壬选一指令访问点m*/ai+1=ai+1;/*顺序执行一条指 令*/ai+2 = (floa t)ai*rand( )/32767/32767/2; /*执行前地址指令 m*/ ai+3=ai+2+1;/*顺序执行一条指 令*/s=(float)(318-ai+2)*rand( )/32767/32767/2+ai+2+2; if(ai+2318)|(s319)pri ntf (a%d+2,a number which is :%d and s=%dn,i,ai+2,s);for (i=0;inext; freepf_head-pn=pagei; plpagei.pfn二freepf_head-pfn;freepf_head-next=NULL; /*使 busy 的尾为 null*/ if(busypf_tail=NULL)busypf_tail=busypf_head=freepf_head;elsebusypf_tail-next=freepf_head; busypf_tail=freepf_head;freepf_head=p;printf(FIF0:%6.4fn,l-(float)diseffect/320); return 0;/*最近最久未使用算法least recently used*/int LRU (int total_pf)int min,minj,i,j,present_time; /*minj 为最小值下标*/ initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i+) /*页面失效*/if(plpagei.pfn=INVALID)/*无空闲页面*/diseffect+; if(freepf_head=NULL)/*设置最大值*/*找出time的最小值*/min=32767;for(j=0;jtotal_vp;j+)if(minplj.time&plj.pfn!=INVALID)min=plj.time; minj=j;freepf_head二&pfcplminj.pfn;/腾出一个单元plminj.pfn=INVALID;plminj.time=0; freepf_head-next=NULL;plpagei.pfn二freepf_head-pfn;/有空闲页面，改为有效plpagei.time二present_time;freepf_head=freepf_head-next;/减少一个 free 页面else plpagei. time二present_time;/命中则增加该单元的访问次数present_time+;prin tf(LRU:%6.4fn,l-(floa t)diseffec t/320); return 0;int NUR(int total_pf )/*最近未使用算法 Not Used recently count 表示*/int i,j,dp,co nt_ flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+)if (plpagei.pfn=INVALID)/*页面失效*/diseffect+;辻(freepf_head=NULL)/*无空闲页面*/cont_flag二TRUE; old_dp=dp;while(cont_flag)辻(pldp.counter=0&pldp.pfn!=INVALID)cont flag二FALSE;elsedp+;if(dp二二total_vp)dp=0; if(dp=old_dp)for(j=0;jtotal_vp;j+) plj.counter=0;freepf_head=&pfcpldp.pfn; pldp.pfn=INVALID;freepf_head-next=NULL;plpagei.pfn二freepf_head-pfn; freepf_head-pn=pagei; freepf_head=freepf_head-next;else plpagei.counter=1;if(i%clear_period=0) for(j=0;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4fn,l-(float)diseffect/320); return 0;int 0PT(int tot al_pf)/* 最佳置换算法*/int i,j, max,maxpage,d,dis ttot al_vp;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+)辻(plpagei.pfn=INVALID)/*页面失效*/diseffect+;辻(freepf_head=NULL)/*无空闲页面*/for(j=0;jtotal_vp;j+)辻(plj.pfn!=INVALID)distj=32767;elsedistj=0;for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)& (distj=32767)distj=j;max=0;for(j=0;jtotal_vp;j+)if(maxpfn; freepf_head=freepf_head-next;prin tf(0PT:%6.4fn,l-(floa t)diseffec t/320);return 0;/*该算法时根据已知的预测未知的，least frequency Used是最不经常使用置换法*/ int LFU (int total_pf)int i,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+)辻(plpagei.pfn=INVALID)/*页面失效*/diseffect+;辻(freepf_head=NULL)/*无空闲页面*/min=32767;/*获取counter的使用用频率最小的内存*/for(j=0;jpfn;/有空闲页面，改为有效plpagei.counter+;freepf_head=freepf_head-next;/减少一个 free 页面 else plpagei.counter;plpagei.counter=plpagei.counter+1; prin tf(LFU:%6.4fn,l-(floa t)diseffec t/320); return 0;