存储管理实验报告

《存储管理实验报告》由会员分享，可在线阅读，更多相关《存储管理实验报告（11页珍藏版）》请在装配图网上搜索。

1、软件学院计算机课程实验报告册课程名称计算机操作系统实验学期 2011年至 2012年 第 2学期学生所在院（系）软件学院年级 11 软件专业班级软工（ 1）班学生姓名朱水云学号1115114034指导教师陈自刚实验最终成绩软件学院实验室制2012年4月第1页共11页实验报告(三)实验名称：存储管理实验时间： 2012 年 4 月 25 号实验性质应用性设计性综合性一、实验目的及要求:实验教师：分数：存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换

2、算法。二、实验内容与分析设计:（ 1）通过随机数产生一个指令序列，共320 条指令。指令的地址按下述原则生成：50%的指令是顺序执行的；50%的指令是均匀分布在前地址部分；50%的指令是均匀分布在后地址部分。具体的实施方法是：在 0 ， 319的指令之间随即选取一起点m;顺序执行一条指令，即执行地址为m+1的指令；在前地址 0 ， m+1中随机选取一条指令并执行，该指令的地址为m；顺序执行一条指令，其地址为m + 1 ；在后地址 m + 2 ， 319 中随机选取一条指令并执行；重复上述步骤- ，直到执行320 次指令。（ 2）将指令序列变换为页地址流设：页面大小为 1k；用户内存容量为4页到

3、 32页；用户虚存容量为32k。在用户虚存中，按每k存放 10 条指令排在虚存地址，即320 条指令在虚存中的存放方式为：第 0 条 - 第 9 条指令为第0 页（对应虚存地址为0 ， 9 ）；第 10 条- 第 19 条指令为第一页（对应虚存地址为10 ， 19 ）；（ 3）计算并输出下述各种算法在不同内存容量下的命中率。先进先出的算法（FIFO）；最近最少使用算法（LRR)；最佳淘汰算法（OPT）先淘汰最不常用的页地址；最少访问页面算法（LFR）；最近最不经常使用算法（NUR）。其中和为选择内容。命中率 =1- 页面失效次数/ 页地址流长度在本实验中，页地址流长度为320，页面失效次数为每

4、次访问相应指令时，该指令所对应的页不在内存的次数。分析：随机数产生办法，Linux 或 UNIX系统提供函数strand()和 rand(),分别进行初始化和产生随机数。例如：srand ();语句可初始化一个随机数；a0=10*rand()/65535*319+1;第2页共11页a1=10*rand()/65535*a0;语句可用来产生a0 与 a1 中的随机数。三、实验步骤与调试过程:1，启动计算机并运行linux 系统2，打开中断进行程序书写3，根据 Linux 系统的 gcc 自带编译器进行运行编译4，分析运行出现的问题5，观察运行结果，并思考6，退出中断并写出实验报告调试过程 : 根

5、据编译提示的错误进行修改四、实验结果：结果一：4 page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.28125 page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.30946 page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.33447 page framesFIFO:0.3563LRU:0.3563OPT:0.4031LFU:0.3563NUR:0.35008 page framesFIFO:0.3

6、937LRU:0.3750OPT:0.4531LFU:0.3937NUR:0.37199 page framesFIFO:0.4219LRU:0.4094OPT:0.4844LFU:0.4156NUR:0.406210 page framesFIFO:0.4375LRU:0.4313OPT:0.5062LFU:0.4313NUR:0.425011 page framesFIFO:0.4813LRU:0.4625OPT:0.5531LFU:0.4500NUR:0.465612 page framesFIFO:0.5406LRU:0.4875OPT:0.5687LFU:0.4938NUR:0.48

7、7513 page framesFIFO:0.5500LRU:0.5188OPT:0.5969LFU:0.5062NUR:0.543714 page framesFIFO:0.5594LRU:0.5531OPT:0.6344LFU:0.5281NUR:0.546915 page framesFIFO:0.5687LRU:0.5844OPT:0.6687LFU:0.5469NUR:0.581316 page framesFIFO:0.5781LRU:0.5938OPT:0.6813LFU:0.5719NUR:0.596917 page framesFIFO:0.5906LRU:0.6156OPT

8、:0.6969LFU:0.6156NUR:0.615618 page framesFIFO:0.6156LRU:0.6312OPT:0.7156LFU:0.6344NUR:0.653119 page framesFIFO:0.6687LRU:0.6656OPT:0.7344LFU:0.6531NUR:0.671920 page framesFIFO:0.6875LRU:0.6969OPT:0.7500LFU:0.6719NUR:0.690621 page framesFIFO:0.6906LRU:0.7094OPT:0.7688LFU:0.6969NUR:0.718822 page frame

9、sFIFO:0.7125LRU:0.7219OPT:0.7969LFU:0.7156NUR:0.734423 page framesFIFO:0.7156LRU:0.7406OPT:0.8125LFU:0.7250NUR:0.781224 page framesFIFO:0.7281LRU:0.7625OPT:0.8187LFU:0.7406NUR:0.771925 page framesFIFO:0.7469LRU:0.7750OPT:0.8344LFU:0.7594NUR:0.800026 page framesFIFO:0.8125LRU:0.8000OPT:0.8500LFU:0.78

10、12NUR:0.806327 page framesFIFO:0.8313LRU:0.8187OPT:0.8594LFU:0.8031NUR:0.828128 page framesFIFO:0.8438LRU:0.8375OPT:0.8688LFU:0.8344NUR:0.846929 page framesFIFO:0.8688LRU:0.8531OPT:0.8750LFU:0.8562NUR:0.856230 page framesFIFO:0.8781LRU:0.8719OPT:0.8781LFU:0.8750NUR:0.868831 page framesFIFO:0.8938LRU

11、:0.8750OPT:0.8844LFU:0.8844NUR:0.890632 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000 4 page framesFIFO:0.2594LRU:0.2562OPT:0.2687LFU:0.2437NUR:0.26255 page framesFIFO:0.3000LRU:0.3000OPT:0.3000LFU:0.2969NUR:0.2875第3页共11页6 page framesFIFO:0.3375LRU:0.3281OPT:0.3281LFU:0.3094NUR:0.32

12、817 page framesFIFO:0.3563LRU:0.3563OPT:0.3688LFU:0.3312NUR:0.34698 page framesFIFO:0.4031LRU:0.4094OPT:0.3875LFU:0.3406NUR:0.37819 page framesFIFO:0.4156LRU:0.4281OPT:0.4156LFU:0.3656NUR:0.412510 page framesFIFO:0.4281LRU:0.4469OPT:0.4313LFU:0.3750NUR:0.440611 page framesFIFO:0.4531LRU:0.4688OPT:0.

13、4594LFU:0.4281NUR:0.465612 page framesFIFO:0.4656LRU:0.4813OPT:0.4906LFU:0.4375NUR:0.493813 page framesFIFO:0.4750LRU:0.5000OPT:0.5219LFU:0.4625NUR:0.531214 page framesFIFO:0.4906LRU:0.5125OPT:0.5375LFU:0.4938NUR:0.550015 page framesFIFO:0.5312LRU:0.5250OPT:0.5625LFU:0.5281NUR:0.556316 page framesFI

14、FO:0.5406LRU:0.5625OPT:0.5813LFU:0.5531NUR:0.584417 page framesFIFO:0.5906LRU:0.5813OPT:0.6188LFU:0.5750NUR:0.603118 page framesFIFO:0.6000LRU:0.5906OPT:0.6344LFU:0.5906NUR:0.625019 page framesFIFO:0.6312LRU:0.6156OPT:0.6438LFU:0.6219NUR:0.643820 page framesFIFO:0.6406LRU:0.6344OPT:0.6625LFU:0.6438N

15、UR:0.675021 page framesFIFO:0.6969LRU:0.6594OPT:0.6875LFU:0.6656NUR:0.693722 page framesFIFO:0.7000LRU:0.6781OPT:0.7125LFU:0.6813NUR:0.684423 page framesFIFO:0.7156LRU:0.6906OPT:0.7312LFU:0.7188NUR:0.696924 page framesFIFO:0.7438LRU:0.7219OPT:0.7531LFU:0.7438NUR:0.746925 page framesFIFO:0.7594LRU:0.

16、7562OPT:0.7656LFU:0.7656NUR:0.771926 page framesFIFO:0.7750LRU:0.7812OPT:0.7937LFU:0.7781NUR:0.778127 page framesFIFO:0.8125LRU:0.7969OPT:0.8094LFU:0.8125NUR:0.796928 page framesFIFO:0.8344LRU:0.8313OPT:0.8281LFU:0.8313NUR:0.840629 page framesFIFO:0.8406LRU:0.8594OPT:0.8531LFU:0.8375NUR:0.840630 pag

17、e framesFIFO:0.8625LRU:0.8781OPT:0.8750LFU:0.8562NUR:0.859431 page framesFIFO:0.8812LRU:0.8812OPT:0.8906LFU:0.8781NUR:0.865632 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000五、疑难与小结：本实验的程序设计基本上按照实验内容进行。即首先用srand() 和 rand() 函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。从实验结果可知，在内存页面数

18、较少（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 total_instruction 320/*指令流长 */#defi

19、ne total_vp 32/*虚页长 */#define clear_period 50/*清 0周期*/typedef struct/*页面结构 */第4页共11页int pn;/页号 logic numberint pfn;/页面框架号 physical frame numberint counter; /计数器int time;/时间pl_type;pl_type pltotal_vp;/*页面线性结构- 指令序列需要使用地址*/typedef struct pfc_struct/*页面控制结构，调度算法的控制结构*/int pn;int pfn;struct pfc_struct *

20、next;pfc_type;pfc_type pfctotal_vp, *freepf_head, *busypf_head, *busypf_tail;int diseffect, atotal_instruction; /* a为指令序列 */int pagetotal_instruction, offsettotal_instruction;/*地址信息 */int initialize(int);int FIFO(int);int LRU(int);int LFU(int);int NUR(int); /not use recentlyint OPT(int);int main( )i

21、nt s,i,j;srand(10*getpid();/*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/s=(float)319*rand( )/32767/32767/2+1; /*正态分布 */for(i=0;itotal_instruction;i+=4)/*产生指令队列 */if(s319)printf(When i=%d,Error,s=%dn,i,s);exit(0);ai=s;/*任选一指令访问点m*/ai+1=ai+1;/*顺序执行一条指令*/ai+2=(float)ai*rand( )/32767/32767/2; /*执行前地址指令m*/ai+3=ai

22、+2+1;/*顺序执行一条指令*/s=(float)(318-ai+2)*rand( )/32767/32767/2+ai+2+2;if(ai+2318)|(s319)printf(a%d+2,a number which is :%d and s=%dn,i,ai+2,s);for (i=0;itotal_instruction;i+) /*将指令序列变换成页地址流*/第5页共11页pagei=ai/10;offseti=ai%10;for(i=4;i=32;i+)/*用户内存工作区从4 个页面到32 个页面 */printf(-%2d page frames-n,i);FIFO(i);LR

23、U(i);LFU(i);NUR(i);OPT(i);return 0;/* 初始化相关数据结构total_pf表示内存的块数*/int initialize(int total_pf)int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pfn=INVALID;/*置页面控制结构中的页号，页面为空*/pli.counter=0;/*页面控制结构中的访问次数为0*/pli.time=-1;/*访问的时间 */for(i=0;itotal_pf-1;i+)/* 建立 pfci-1和 pfci之间的链接 */pfci.next=&pfci+1;pfci.pfn=i;p

24、fctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; /* 空页面队列的头指针为 pfc0*/ return 0;int FIFO(int total_pf)/*先进先出算法total_pf:用户进程的内存页面数*/int i,j;pfc_type *p;/* 中间变量 */initialize(total_pf);/*初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/for(i=0;inext;plbusypf_head-pn.pf

25、n=INVALID;freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/freepf_head-next=NULL; /*表明还是缺页*/busypf_head=p;p=freepf_head-next;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;bu

26、sypf_tail=freepf_head;freepf_head=p;printf(FIFO:%6.4fn,1-(float)diseffect/320);return 0;int LRU (int total_pf)/*最近最久未使用算法least recently used*/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(f

27、reepf_head=NULL)/*无空闲页面 */min=32767;/* 设置最大值 */for(j=0;jplj.time&plj.pfn!=INVALID)第7页共11页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;/减少一个f

28、ree页面elseplpagei.time=present_time;/命中则增加该单元的访问次数present_time+;printf(LRU:%6.4fn,1-(float)diseffect/320);return 0;int NUR(int total_pf )/*最近未使用算法Not Used recently count表示 */int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+)if (plpagei.pfn=INVALID)/*页面失效

29、*/diseffect+;if(freepf_head=NULL)/*无空闲页面 */cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pldp.counter=0&pldp.pfn!=INVALID)cont_flag=FALSE;第8页共11页elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;jnext=NULL;plpagei.pfn=freepf_head-pfn;freepf_head-pn=pagei;freepf_head=freepf_head-next;elseplpagei.counter

30、=1;if(i%clear_period=0)for(j=0;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4fn,1-(float)diseffect/320);return 0;int OPT(int total_pf)/*最佳置换算法 */int i,j, max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/*页面失效 */diseffect+;if(freepf_head=NU

31、LL)/*无空闲页面 */for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)distj=32767;else第9页共11页distj=0;for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)&(distj=32767)distj=j;max=0;for(j=0;jtotal_vp;j+)if(maxnext=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;printf(OPT:%6.4fn,1-(float)dis

32、effect/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+)if(plpagei.pfn=INVALID)/*页面失效 */diseffect+;if(freepf_head=NULL)/*无空闲页面 */min=32767;/* 获取 counter的使用用频率最小的内存*/for(j=0;jplj.cou

33、nter&plj.pfn!=INVALID)第10页共11页min=plj.counter;minpage=j;freepf_head=&pfcplminpage.pfn;plminpage.pfn=INVALID;plminpage.counter=0;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn;/有空闲页面 , 改为有效plpagei.counter+;freepf_head=freepf_head-next;/减少一个free页面elseplpagei.counter;plpagei.counter=plpagei.counter+1;printf(LFU:%6.4fn,1-(float)diseffect/320);return 0;第11页共11页