實(shí)驗(yàn)12 頁面置換算法_第1頁
實(shí)驗(yàn)12 頁面置換算法_第2頁
實(shí)驗(yàn)12 頁面置換算法_第3頁
實(shí)驗(yàn)12 頁面置換算法_第4頁
實(shí)驗(yàn)12 頁面置換算法_第5頁
已閱讀5頁，還剩20頁未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、頁面置換算法執(zhí)行分析FIFO算法LRU算法程序代碼段注意紅框內(nèi)的代碼有修改運(yùn)行結(jié)果如右圖main()函數(shù)設(shè)每頁存放一條指令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內(nèi)存頁框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方式調(diào)頁面入內(nèi)存頁面*/ 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*/內(nèi)存頁框pfcpnpfnnextfreepf_head40-113-1執(zhí)行代碼段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方式調(diào)頁面入內(nèi)存頁面*/ 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*/內(nèi)存頁框pfcpnpfnnextfreepf_head4051-13-1執(zhí)行代碼段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方式調(diào)頁面入內(nèi)存頁面*/ 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*/內(nèi)存頁框pfcpnpfnnextfreepf_head40513-1執(zhí)行代碼段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方式調(diào)頁面入內(nèi)存頁面

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*/內(nèi)存頁框pfcpnpfnnextfreepf_head為空4051113-1執(zhí)行代碼段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; /*釋放忙頁面隊(duì)列的第一個頁面*/busypf_head= p; /*end if*/ p=freepf_head-next;/*按FIFO方式調(diào)頁面入內(nèi)存頁面*/ 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內(nèi)存頁框pfcpnpfnnextfreepf_head為空120-151113執(zhí)行代碼段32以次類推，訪問后續(xù)720條指令，請補(bǔ)充分析

11、演示過程diseffect值為（即缺頁數(shù)），算法效率為（即程序輸出）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內(nèi)存頁框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內(nèi)存頁框pfcpnpfnnext4013-12執(zhí)行代碼/*直接訪問頁面*/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內(nèi)存頁

14、框pfcpnpfnnext40513-132執(zhí)行代碼/*頁面失效*/ 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頁面走向執(zhí)行代碼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為空內(nèi)存頁框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頁面走向執(zhí)行代碼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為空內(nèi)存頁框pfcpnpfnnext40121113-112以次類推，訪問后續(xù)

18、820條指令，請補(bǔ)充分析演示過程diseffect值為（即缺頁數(shù)），算法效率為（即程序輸出）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內(nèi)存頁框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內(nèi)存頁框pfcpnpfnnextfreepf_head4013-1執(zhí)行代碼段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內(nèi)存頁框pfcpnpfnnextfreepf_head為-14051113-1執(zhí)行代碼段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內(nèi)存頁框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，選擇淘汰頁表項(xiàng)3，頁面號2訪問第7th條指令后pn

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論