實(shí)驗(yàn)四頁(yè)面置換算法代碼

1、實(shí)驗(yàn)四頁(yè)面置換算法模擬（2）一.題目要求：設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，編程序演示下述算法的具體實(shí)現(xiàn)過(guò)程，并計(jì)算訪問(wèn)命中率：要求設(shè)計(jì)主界面以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)1）最佳置換算法（OPT）:將以后永不使用的或許是在最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面換出。2）先進(jìn)先出算法（FIFO）:淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。3）最近最久未使用算法（LRU）:淘汰最近最久未被使用的頁(yè)面。4）最不經(jīng)常使用算法（LFU）.實(shí)驗(yàn)?zāi)康模?、用C語(yǔ)言編寫(xiě)OPT、FIFO、LRU,LFU四種置換算法2、熟悉內(nèi)存分頁(yè)管理策略。3、了解頁(yè)面置換的算法。4、掌握一般常用的調(diào)度

2、算法。5、根據(jù)方案使算法得以模擬實(shí)現(xiàn)。6、鍛煉知識(shí)的運(yùn)用能力和實(shí)踐能力。三.相關(guān)知識(shí)：1 .虛擬存儲(chǔ)器的引入：局部性原理：程序在執(zhí)行時(shí)在一較短時(shí)間內(nèi)僅限于某個(gè)部分；相應(yīng)的，它所訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域，它主要表現(xiàn)在以下兩個(gè)方面：時(shí)間局限性和空間局限性。2 .虛擬存儲(chǔ)器的定義：虛擬存儲(chǔ)器是只具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。3 .虛擬存儲(chǔ)器的實(shí)現(xiàn)方式：分頁(yè)請(qǐng)求系統(tǒng)，它是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的頁(yè)面形式虛擬存儲(chǔ)系統(tǒng)。請(qǐng)求分段系統(tǒng)，它是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后，所形成的段式虛擬存儲(chǔ)系統(tǒng)。4 .

3、頁(yè)面分配：平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。按比例分配算法，根據(jù)進(jìn)程的大小按比例分配物理塊?？紤]優(yōu)先的分配算法，把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)個(gè)進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)脑黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。5 .頁(yè)面置換算法：常用的頁(yè)面置換算法有OPT、FIFO、LRU、Clock、LFU、PBA等。四.設(shè)計(jì)思想：選擇置換算法，先輸入所有頁(yè)面號(hào)，為系統(tǒng)分配物理塊，依次進(jìn)行置換：OPT基本思想：是用一維數(shù)組pagepSIZE存儲(chǔ)頁(yè)面號(hào)序列，memerymSIZE是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組nextmSIZE記錄物理塊中對(duì)

4、應(yīng)頁(yè)面的最后訪問(wèn)時(shí)間。每當(dāng)發(fā)生缺頁(yè)時(shí)，就從物理塊中找出最后訪問(wèn)時(shí)間最大的頁(yè)面，調(diào)出該頁(yè)，換入所缺的頁(yè)面?！咎貏e聲明】若物理塊中的頁(yè)面都不再使用，則每次都置換物理塊中第一個(gè)位置的頁(yè)面。FIFO基本思想：是用隊(duì)列存儲(chǔ)內(nèi)存中的頁(yè)面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁(yè)時(shí)，就從隊(duì)頭刪除一頁(yè)，而從隊(duì)尾加入缺頁(yè)?；蛘呓柚o助數(shù)組timemSIZE記錄物理塊中對(duì)應(yīng)頁(yè)面的進(jìn)入時(shí)間，每次需要置換時(shí)換出進(jìn)入時(shí)間最小的頁(yè)面。LRU基本思想：是用一維數(shù)組pagepSIZE存儲(chǔ)頁(yè)面號(hào)序列，memerymSIZE是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組flag10標(biāo)記頁(yè)面的訪問(wèn)時(shí)間。每當(dāng)使用頁(yè)面時(shí)，刷新訪問(wèn)時(shí)間

5、。發(fā)生缺頁(yè)時(shí)，就從物理塊中頁(yè)面標(biāo)記最小的一頁(yè)，調(diào)出該頁(yè)，換入所缺的頁(yè)面五.流程圖：如下頁(yè)所示結(jié)束六.源代碼：如下頁(yè)所示【使用C語(yǔ)言】#include<stdio.h>#include<conio.h>#include<stdlib.h>/*全局變量*/intmSIZE;/*物理塊數(shù)*/intpSIZE;/*頁(yè)面號(hào)引用用個(gè)數(shù)*/staticintmemery10=0;/*物理塊中的頁(yè)號(hào)*/staticintpage100=0;/*頁(yè)面號(hào)引用用*/staticinttemp10010=0;/*輔助數(shù)組*/*置換算法函數(shù)*/voidFIFO();voidLRU()

6、;voidOPT();/*輔助函數(shù)*/voidprint(unsignedintt);voiddesignBy();voiddownload。；voidmDelay(unsignedintDelay);/*主函數(shù)*/voidmain()inti,k,code;system("color0A");designBy();printf("|請(qǐng)按任意鍵進(jìn)行初始化操作.|n");printf("1n")1printf(">>>");getch();system("cls");system

7、("color0B");printf("請(qǐng)輸入物理塊的個(gè)數(shù)(M<=10):");scanf("%d”,&mSIZE);printf("請(qǐng)輸入頁(yè)面號(hào)引用用的個(gè)數(shù)(P<=100):");scanf("%d”,&pSIZE);puts("請(qǐng)依次輸入頁(yè)面號(hào)引用用(連續(xù)輸入，無(wú)需隔開(kāi))：”)；for(i=0;i<pSIZE;i+)scanf("%1d",&pagei);download();system("cls");system(&

8、quot;color0E");doputs（"輸入的頁(yè)面號(hào)引用用為："）;for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)(if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d",pagei);printf('*n");printf（"*請(qǐng)選擇頁(yè)面置換算法：ttt*n"）;

9、printf("*n");printf("*1.先進(jìn)先出(FIFO)2.最近最久未使用(LRU)*n");printf("*3.最佳(OPT)4.退出*n");printf('*n");printf("請(qǐng)選擇操作：bb");scanf("%d”,&code);switch(code)(case 1:FIFO();break;case 2:LRU();break;case 3:OPT();break;case 4:system("cls");system(&qu

10、ot;color0A");designBy();/*顯示設(shè)計(jì)者信息后退出*/printf("|謝謝使用頁(yè)面置換算法演示器！正版授權(quán)®W);printf("1n)1exit(0);default:printf("輸入錯(cuò)誤，請(qǐng)重新輸入：");)printf("按任意鍵重新選擇置換算法：>>>");/getch();system("cls");while(code!=4);getch();)/*載入數(shù)據(jù)*/voiddownload()(inti;system("color0

11、D");printf("n");printf("正在載入數(shù)據(jù)，請(qǐng)稍候!n");printf("1n)1printf("Loadingn");printf("O");for(i=0;i<51;i+)printf("b");for(i=0;i<50;i+)(mDelay(pSIZE+mSIZE)/2);printf(">");)printf("nFinish.n載入成功，按任意鍵進(jìn)入置換算法選擇界面：>>>&quo

12、t;);getch();/*設(shè)置延遲*/voidmDelay(unsignedintDelay)(unsignedinti;for(;Delay>0;Delay-)(for(i=0;i<124;i+)(printf("b");/*顯示設(shè)計(jì)者信息*/voiddesignBy()(printf("n")1printf("|頁(yè)面置換算法|n");printf("|n")1voidprint(unsignedintt)inti,j,k,l;intflag;for(k=0;k<=(pSIZE-1)/20;k

13、+)(for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)(if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d",pagei);for(j=0;j<mSIZE;j+)(for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+)(if(i>=j)printf("|%d|",tempij);elseprintf("

14、|");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+)for(flag=0,l=0;l<mSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁(yè)面在物理塊中*/printf("");elseprintf("|%d|",tempij);/*每行顯示20個(gè)*/if(i%20=0)continue;printf("n");printf("An");printf("缺頁(yè)次數(shù)：%dtt”

15、,t+mSIZE);printf("缺頁(yè)率：%d/%dn”,t+mSIZE,pSIZE);printf("置換次數(shù)：%dtt",t);printf("訪問(wèn)命中率:%d%n”,(pSIZE-(t+mSIZE)*100/pSIZE);printf("An");/*計(jì)算過(guò)程延遲*/voidcompute()inti;printf("正在進(jìn)行相關(guān)計(jì)算，請(qǐng)稍候")；for(i=1;i<20;i+)(mDelay(15);if(i%4=0)printf("bbbbbbbbbbbb");elseprin

16、tf("')；)for(i=0;i+<30;printf("b");for(i=0;i+<30;printf("");for(i=0;i+<30;printf("b");)/*先進(jìn)先出頁(yè)面置換算法*/voidFIFO()(intmemery10=0;inttime10=0;/*記錄進(jìn)入物理塊的時(shí)間*/inti,j,k,m;intmax=0;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/for(i=0;i<mSIZE;i+)(memeryi=pagei

17、;timei=i;for(j=0;j<mSIZE;j+)tempij=memeryj;for(i=mSIZE;i<pSIZE;i+)(/*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;j<mSIZE;j+)(if(memeryj!=pagei)k+;if(k=mSIZE)/*如果不在物理塊中*/(count+;/*計(jì)算換出頁(yè)*/max=time0<time1?0:1;for(m=2;m<mSIZE;m+)if(timem<timemax)max=m;memerymax=pagei;timemax=i;/*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/for(j=0;j

18、<mSIZE;j+)tempij=memeryj;elsefor(j=0;j<mSIZE;j+)tempij=memeryj;compute();print(count);/*最近最久未使用置換算法*/voidLRU()intmemery10=0;intflag10=0;/*記錄頁(yè)面的訪問(wèn)時(shí)間*/inti,j,k,m;intmax=0;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/for(i=0;i<mSIZE;i+)(memeryi=pagei;flagi=i;for(j=0;j<mSIZE;j+)tempij=memery

19、j;for(i=mSIZE;i<pSIZE;i+)(/*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;j<mSIZE;j+)(if(memeryj!=pagei)k+;elseflagj=i;/*刷新該頁(yè)的訪問(wèn)時(shí)間*/if(k=mSIZE)/*如果不在物理塊中*/count+;/*計(jì)算換出頁(yè)*/max=flag0<flag1?0:1;for(m=2;m<mSIZE;m+)if(flagm<flagmax)max=m;memerymax=pagei;flagmax=i;/*記錄該頁(yè)的訪問(wèn)時(shí)間*/for(j=0;j<mSIZE;j+)tempij=memeryj;else(for(j=0;j<mSIZE;j+)tempij=memeryj;compute();print(count);/*最佳置換算法*/voidOPT()(intmemery10=0;intnext10=0;/*記錄下一次訪問(wèn)時(shí)間*/inti,j,k,l,m;intmax;/*記錄換出頁(yè)*/intcount=0;/*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/for(i=0;i<m