实验12 页面置换算法_第1页
实验12 页面置换算法_第2页
实验12 页面置换算法_第3页
实验12 页面置换算法_第4页
实验12 页面置换算法_第5页
已阅读5页，还剩20页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、页面置换算法执行分析FIFO算法LRU算法程序代码段注意红框内的代码有修改运行结果如右图main()函数设每页存放一条指令FIFO算法初始化后pn pfntime页表pl0-1-11-1-12-1-13-1-14-1-15-1-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为0busypf_head, busypf_tail为空指针freepf_head内存页框pfcpn

2、pfnnext013-12访问1st条指令后pn pfntime页表pl0-1-11-1-12-1-13-1-140-15-1-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为1busypf_head busypf_tailif(plpagei.pfn = INVALID) /*页面失效*/ diseffect +=1; p=freepf_head-next; /*按FI

3、FO方式调页面入内存页面*/ freepf_head-next=NULL; freepf_head-pn=pagei; plpagei.pfn=freepf_head-next-pfn;busypf_head=busypf_tail=freepf_head; freepf_head=p;/*end if*/内存页框pfcpnpfnnextfreepf_head40-113-1执行代码段2访问2nd条指令后pn pfntime页表pl0-1-11-1-12-1-13-1-140-151-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1

4、-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为2busypf_head busypf_tailif(plpagei.pfn = INVALID) /*页面失效*/ diseffect +=1; p=freepf_head-next; /*按FIFO方式调页面入内存页面*/ freepf_head-next=NULL; freepf_head-pn=pagei; plpagei.pfn=freepf_head-next-pfn;busypf_tail-next=freepf_he

5、ad;busypf_tail=freepf_head; freepf_head=p;/*end if*/内存页框pfcpnpfnnextfreepf_head4051-13-1执行代码段2访问3rd条指令后pn pfntime页表pl0-1-11-1-12-1-132-140-151-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为3busypf_head busypf_

6、tailif(plpagei.pfn = INVALID) /*页面失效*/ diseffect +=1; p=freepf_head-next; /*按FIFO方式调页面入内存页面*/ freepf_head-next=NULL; freepf_head-pn=pagei; plpagei.pfn=freepf_head-next-pfn;busypf_tail-next=freepf_head;busypf_tail=freepf_head; freepf_head=p;/*end if*/内存页框pfcpnpfnnextfreepf_head40513-1执行代码段32-14rd条指令直

7、接访问，访问5th条指令后pn pfntime页表pl0-1-11-1-12-1-132-140-151-16-1-17-1-18-1-19-1-110-1-1113-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为4busypf_head busypf_tailif(plpagei.pfn = INVALID) /*页面失效*/ diseffect +=1; p=freepf_head-next; /*按FIFO方式调页面入内存页面

8、*/ freepf_head-next=NULL; freepf_head-pn=pagei; plpagei.pfn=freepf_head-next-pfn;busypf_tail-next=freepf_head;busypf_tail=freepf_head; freepf_head=p;/*end if*/内存页框pfcpnpfnnextfreepf_head为空4051113-1执行代码段32if(plpagei.pfn = INVALID)/*页面失效*/ diseffect +=1; if(freepf_head) = NULL) /*无空闲页面，需页面淘汰*/p =busyp

9、f_head -next;plbusypf-head-pn.pfn= INVALID; freepf_head= busypf_head;freepf_head-next = NULL; /*释放忙页面队列的第一个页面*/busypf_head= p; /*end if*/ p=freepf_head-next;/*按FIFO方式调页面入内存页面*/ freepf_head-next=NULL; freepf_head-pn=pagei; plpagei.pfn=freepf_head-next-pfn;busypf_tail-next=freepf_head;busypf_tail=free

10、pf_head; freepf_head=p; 访问6th条指令后pn pfntime页表pl0-1-11-1-12-1-132-14-1-151-16-1-17-1-18-1-19-1-110-1-1113-1120-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为5busypf_head busypf_tail内存页框pfcpnpfnnextfreepf_head为空120-151113执行代码段32以次类推，访问后续720条指令，请补充分析

11、演示过程diseffect值为（即缺页数），算法效率为（即程序输出）LRU算法初始化后pn pfntime页表pl0-1-11-1-12-1-13-1-14-1-15-1-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为0p_time值为0freepf_head内存页框pfcpnpfnnext013-12/*页面失效*/diseffect +=1;plpagei.pfn=

12、freepf_head-next-pfn;plpagei.time=present_time;freepf_headpn=pagei; freepf_head=freepf_head-nex;present_time+;访问1st页4后pn pfntime页表pl0-1-11-1-12-1-13-1-14005-1-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为1p_t

13、ime值为1freepf_head内存页框pfcpnpfnnext4013-12执行代码/*直接访问页面*/plpagei.time=present_time;present_time+;访问4th页4后pn pfntime页表pl0-1-11-1-12-11-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为3p_time值为4freepf_head内存页

14、框pfcpnpfnnext40513-132执行代码/*页面失效*/ diseffect +=1; /*无空闲页面，需页面淘汰*/ min=32767; for(j=0;jplj.time & plj.pfn!=INVALID)min=plj.time;minj=j; freepf_head = &pfcplminj.pfn; plminj.pfn=INVALID; plminj.time=-1; freepf_headpn=pagei; freepf_head-next=NULL; plpagei.pfn=freepf_head-next-pfn; plpagei.time=

15、present_time; freepf_head=freepf_head-nex;present_time+;访问6th页12后4 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向执行代码min为1, minj为5淘汰页5pn pfntime页表pl0-1-11-1-12-1-13224035-1-16-1-17-1-18-1-19-1-110-1-11134121513-1-116-1-114-1-115-1-117-1-118-1-119-1-1diseffect值为5p_time值为6freepf_head为空内存页框pfcpnpfnnext401

16、21113-132/*页面失效*/ diseffect +=1; /*无空闲页面，需页面淘汰*/ min=32767; for(j=0;jplj.time & plj.pfn!=INVALID)min=plj.time;minj=j; freepf_head = &pfcplminj.pfn; plminj.pfn=INVALID; plminj.time=-1; freepf_head-next=NULL; plpagei.pfn=freepf_head-next-pfn; plpagei.time=present_time; freepf_headpn=pagei; fre

17、epf_head=freepf_head-nex;present_time+;访问7th页1后4 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向执行代码min为2, minj为3淘汰页3pn pfntime页表pl0-1-11262-1-13-1-14035-1-16-1-17-1-18-1-19-1-110-1-11134121513-1-116-1-114-1-115-1-117-1-118-1-119-1-1diseffect值为6p_time值为7freepf_head为空内存页框pfcpnpfnnext40121113-112以次类推，访问后续

18、820条指令，请补充分析演示过程diseffect值为（即缺页数），算法效率为（即程序输出）OPT算法初始化后pn pfntime页表pl0-1-11-1-12-1-13-1-14-1-15-1-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为0freepf_head内存页框pfcpnpfnnext013-12访问1st条指令后pn pfntime页表pl0-1-11-1

19、-12-1-13-1-140-15-1-16-1-17-1-18-1-19-1-110-1-111-1-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为1内存页框pfcpnpfnnextfreepf_head4013-1执行代码段2/*页面失效*/diseffect +=1; plpagei.pfn=freepf_head-pfn;freepf_head-pn=pagei;freepf_head=freepf_head-next;依次

20、访问2st、3rd 、 4th 、 5th条指令后pn pfntime页表pl0-1-11-1-12-1-132-140-151-16-1-17-1-18-1-19-1-110-1-1113-112-1-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为4内存页框pfcpnpfnnextfreepf_head为-14051113-1执行代码段32/*页面失效*/diseffect +=1; plpagei.pfn=freepf_head-pfn;f

21、reepf_head-pn=pagei;freepf_head=freepf_head-next;访问第6th条指令后pn pfntime页表pl0-1-11-1-12-1-13-1-140-151-16-1-17-1-18-1-19-1-110-1-1113-1122-113-1-116-1-114-1-115-1-117-1-118-1-119-1-14 5 3 4 11 12 1 2 6 7 4 5 6 7 0 1 4 5 0 1页面走向diseffect值为5内存页框pfcpnpfnnextfreepf_head为-14051113-1122/*页面失效*/diseffect +=1;

22、if(freepf_head) = NULL) for(j=0;jtotal_vp; j+)if(plj.pfn!=INVALID) distj=32767;else distj=0; d=1; for( j =i+1; j total_instruction; j +)if(plpagej.pfn !=INVALID &distpagej=32767 ) distpagej=d;d+; max=-1; for(j=0;jtotal_vp;j+)if(maxnext=NULL; plmaxpage.pfn=INVALID; /end if 无空白页面 plpagei.pfn=freepf_head-pfn;freepf_head-pn=pagei;freepf_head=freepf_head-next;dist3327671132767564500102060708090100120130140150160170180190max为32767，maxpage为3，选择淘汰页表项3，页面号2访问第7th条指令后pn

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论