實驗編號4名稱頁面置換算法模擬實驗目的通過請求頁式存儲管理中頁面置換算法模擬設計，以便:1、了解虛擬存儲技術的特點2、掌握請求頁式存儲管理中頁面置換算法實驗內(nèi)容與環(huán)節(jié)設計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用FIF0和LRU算法計算訪問命中率?！闯绦蛟O計,，先用srand()函數(shù)和rand()函數(shù)定義和產(chǎn)生指令序列,然后將指令序列變換成相應的頁地址流，并針對不同的算法計算相應的命中率?！闯绦?>include<windows.h>“Windows版，隨機函數(shù)需要,GetCurrentProcessld()需要//#include<std1ib.h>//Linux版，隨機函數(shù)srand和rand需要include<stdio.h>^//printf()需要defineTRUE1defineFALSE0#defineINVALID-1#defineNULL0。freepf^head=freepf_head—>next;00}else3pmt[page[i]].counter=1；eif(i%c1ear_period==0)sfor(j=0;j<tota1_vp;j++)叩mt[j].counter=0;°)printf(11NUR：%6.4f1oat)NoPageCount/320)；實驗結果（寫出結果，截圖也可）請插，.江面長度。九16輸出隨機數(shù)：許輸入分配的物理塊水2?6〉：41：PIFO頁面置換2：LRU頁面置換3：OPT頁面置換請選擇頁面置換算法，

FIFOi2法頁面置換情況如下:TOC\o"1-5"\h\z33000636005365073657116575不缺頁9195701907219021不缺頁66982464026不缺頁164127641733417000555^0^9^0^3333313s5r?l缺頁次數(shù),13缺頁率，0.8125000555^0^9^0^3333313s5r?lF不缺頁919570195029502910261026142950291026102614不缺頁

不缺頁F77614F7761437613缺頁次數(shù),F7761437613缺頁次數(shù),13缺頁率，。.8125OPT苴士苦心府況如下:3657159021S4S1F730007700555^0^0^0^03657159021S4S1F730007700555^0^0^0^03333177777902費4頁頁頁4666赧?6靜^^6

il不不1不不不3缺頁次數(shù)，I?缺頁率,0.625總結（收獲，未實現(xiàn)的環(huán)節(jié)）這次操作系統(tǒng)課程設計，讓我們對操作系統(tǒng)有了更深的結識，一方面操作系統(tǒng)是一管理電腦硬件與軟件資源的程序,同時也是計算機系統(tǒng)內(nèi)核與基石。操作系統(tǒng)是一個龐大的管理控制程序，大體涉及5個方面的管理功能:進程與解決機管理、作業(yè)管理、存儲管理、設備管理、文獻管理。我們這次課程設計的題目是頁面置換算法,是屬于存儲器管理。在進程運營過程中,若其訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存以無空閑空間時，為了保證該進程能正常的運營,系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的兌換區(qū)中，但應將哪個頁面調(diào)出,需根據(jù)一定的算法來擬定。通常，把選擇換成頁面的算法稱為頁面置換算法。通過本次課程設計，我們對頁面置換算法的了解更加的深刻。重要有以下置換算法：OPT（最佳置換算法）、FIFO（先進先出置換算法）、LRU（最近最久未使用算法）。每種算法都有各自的優(yōu)缺陷，OPT算法是實際中不能實現(xiàn)的，但是可以運用該算法去評價其它算法；FIFO算法與進程實際運營的規(guī)律不相合用，由于在進程中,有些頁面經(jīng)常被訪問;LRU算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的。在這次課程設計中，碰到了一些困難，例如怎么實現(xiàn)各種算法，如何進行函數(shù)調(diào)用及對數(shù)據(jù)的限制操作等,在碰到這些困難的時候，我們會去查閱資料，仔細看書，嘗試用不同的方法解決，在各種方法中選擇一種最佳的方法，有的時候會碰到不知道如何實現(xiàn)的函數(shù)，我們會查看MSDN,這次是用的C++語言做的，每一步都是自己獨立完畢的，這次課程設計我最大的收獲是學以致用，通過這次設計我們看到了自己學習的能力，我們相信在以后的學習中，會更加的努力上進。最后，還非常感謝辛勞的操作系統(tǒng)老師，一方面，由于他辛勞的為我們講解操作系統(tǒng)這門課，讓我們對操作系統(tǒng)有了一定的了解，為這次課程設計奠定了良好的基礎，另一方面,還要感謝他認真指導我們的這次課程設計，給了我們這次總體運用自己能力的機會，我們堅信:只要功夫深，鐵杵磨成針。definetota1_instraction320。。//共320條指令definetotal—vp32。?！ㄌ摯骓摴?2頁defineclear_period50。。//訪問次數(shù)清零周期typedefstruet{//定義頁表結構類型(頁面映射表PMT)“ntpn,pfn,counter,time;//頁號、頁框號(塊號)、一個周期內(nèi)訪問該頁面的次數(shù)、訪問時間}PMT；PMTpmt[32];typedefstructpfc_struct{〃頁面控制結構“ntpn,pfn;ostructpfe_struct*next;}pfc_type;Pfc_typepfc[32];pfc.type*freePLhead,*busypf_head,*busypf_tail;//空閑頁頭指針，，忙頁頭指針，忙頁尾指針intNoPageCount;〃缺頁次數(shù)inta[total__instruction];//指令流數(shù)組intpage[tota1—instruetion],offset[total_instruetion];//每條指令的頁和頁內(nèi)偏移voidinitia1ize(int);voidFIFO(int);//先進先出voidLRU(int);〃最近最久未使用voidNRU(int);〃最近最不經(jīng)常使用***************************************************************************main()******************************************************************voidmain(){inti,s;V/srand(10*getpid());//用進程號作為初始化隨機數(shù)隊列的種子?！癓inux版6srand(10*GetCurrentProcessId())；〃用進程號作為初始化隨機數(shù)的種子//Windows版0。s=rand()%320；//在[0,319]的指令地址之間隨機選取一起點mfor(i=0;i<total_instruction；i+=4){〃產(chǎn)生指令隊列oif(s<0||s>319){叩rintf("wheni==%d,error,s==%d\nn,i,s)；exit(0);6)8a[i]=s；〃任意選一指令訪問點m。(將隨機數(shù)作為指令地址m)。a[i+l]=a[i]+l；//順序執(zhí)行下一條指令-a[i+2]=rand()%(s+2);〃在[0,m+l]的前地址之間隨機選取一地址，記為a[i+3]=a[i+2]+1;〃順序執(zhí)行一條指令。s=a[i+2]+(int)rand()%(320-a[i+2]);//在[m-319]的指令地址之間隨機選取一起點moif((a[i+2]>318)||(s>319))printf(Ha[%d+2,anumberwhichis：%dands二%d\n\i,a[i+2],s);。for(i=0;i<total_instruction;i++){//將指令序列變成頁地址流PageLi]=aLi]/10;?offset[i]=a[i]%10;0)for(i=4;iv=32;i++){//內(nèi)存塊分別為4塊、5塊、...32塊時的命中率printf(u%2dpageframesn,i);oFIFO(i);〃計算用FIFO置換時，有i個內(nèi)存塊時的命中率?LRU⑴;〃最近最久未使用NRU(i);//最近最不經(jīng)常使用叩rintf(“\n");)/*1*IIII*1*■1**1*IIiI*t*III|I/*不***半***牛大不不不不不不不不大大拳拳大不舉不軍大牛不大不不半半半不大*不半不不不半半不大半不**不大不不*不不不不不不不**********initialize()形參：內(nèi)存塊數(shù)功能：初始化**************************************************************************Ivoidinitia1ize(inttota1_pf)//初始化相關數(shù)據(jù)結構，形參tota1_pf是用戶進程的內(nèi)存頁面數(shù)(nti;NoPageCount=0；//缺頁次數(shù),初始化為0for(i=0；i<tota1_vp；i++){3pmt[i].pn=i;//填邏輯頁號pmt[i].pfn=INVALID;//物理頁面號為-1oopmt[i].counter=0;〃置頁面控制結構中的訪問次數(shù)為0叩mt[i].time=-1;〃置頁面控制結構中的時間為-1for(i=0;i<total_pf-1;i++){〃建立pfc[i-1]和pfc[i]之間的連接gpfc[i].next=&pfc[i+1];pfc[i].pfn=i;)叩fc[total],next=NULL;pfc[total_pf-1].pfn=total—pf—1;6freepf_head=&pfc[0];//頁面隊列的頭指針為pfc[0])/III*1*I|*1**2*IIIIIII/半火亭不不舉亭亭大軍不小不亭亭大軍不舉大舉大不亭軍大不火舉牛斗不斗不舉不火大軍不不大不※不舉不不亭不大不軍大不軍斗小牛舉斗斗不不本************FIFO算法形參：內(nèi)存塊數(shù)輸出：命中率拳不AA不大拳拳拳拳不***大舉*亭*亭*大牛**拳拳拳半半半半不不不不不大*不半大牛不*舉不半*拳不不大牛斗舉半大7>7，7，7*7*7*7，*!>■!>7>7>7>7>7，7，7^7*I/rj*rj*/voidFIFO(inttotal_pf)〃形參total_Pf是用戶進程的內(nèi)存頁面數(shù)inti;pfc_type*p;initia1ize(total_Pf)；〃初始化相關數(shù)據(jù)結構ebusypf_head=busypf_tai1=NULL;for(i=0;i<total_instruction;i++){//訪問每條指令3if(pmt[page[i]].pfn==INVALID){〃缺頁3oNoPageCount+=1;〃失效(缺頁)次數(shù)增1^if(freepf_head==NULL){〃無空閑頁面op=busypf_head->next；eopmt[busypf_head->pn].pfn=INVALID;“^freepf_head=busypf_head;//釋放忙頁面隊列的第一個頁面ogfreepfLhead->next=NULL;ebusypf_head=p;}p=freepf_head->next;〃按FIFO方式調(diào)新頁面入內(nèi)存ofreepf_head->next=NULL;freepf_head—>pn=page[i];ooopmt[page[i]].pfn=freepf_head->pfn；aif(busypfLtaiI==NULL)busypf_head=busypf_tail=freepf_head;8。eIse{8obusypf_tai1->next=freepChead；//free頁面減少一個busypfLtail=freepf_head;bbb}肅reepf_head=p;°}°}叩rintf(nFIFO：%6.4f;l-(float)NoPageCount/320);)/********************************************************1**2*I*1**1**￡*.R.Rrj*?門?卜,.、..、^7^.R.R?卜LRU算法(最近最久未使用)形參:內(nèi)存塊數(shù)輸出:命中率*****************************************************************************/voidLRU(inttotal_pf)//形參total_pf是給用戶進程的內(nèi)存塊數(shù)“ntmin,minj,i,j,present_time;initialize(total_pf);present_time=0;sfor(i=0;i<total_instruction;i++){oif(pmt[page[i]].pfn==INVALID){〃頁面失效8。NoPageCount++；。if(freepfLhead==NULL){//無空閑頁面gmin=32767;“for(j=0;j<total_vp；j++)〃找出time的最小值。if(min>pmt|j].time&&pmt[j].pfn!=INVALID){。。。min=pmt[j].time;6°minj=j;00}^>freepf_head=&pfc[pmt[minj].pfn];〃騰出一個單元。。pmt[minj].pfn=INVALID;o。pmt[minj],time-1;e。freepf_head—>next=NULL；eg}3叩mt[page[i]].pfn=freepf_head—>pfn;〃有空閑頁面，改為有效bopmt[page[i]].time=present_time;。freepjhead=freepjhead—>next;//減少一個free頁面-Isepmt[page[i]].time=present_time;//更新該頁面的訪問時間（并非真的時間，而是循環(huán)次數(shù)，每執(zhí)行一條指令，時間加1）present_time++；〃當前時間加1°）叩rintf("LRU:%6.4fn,1-(float)NoPageCount/320);I********************************************************