軟件學(xué)院操作系統(tǒng)實(shí)驗(yàn)報(bào)告專(zhuān)業(yè)：軟件工程班級(jí)：RB軟工互學(xué)號(hào)：學(xué)生姓名：指導(dǎo)教師：PAGE第16頁(yè)共16頁(yè)實(shí)驗(yàn)四：請(qǐng)求頁(yè)式存儲(chǔ)管理一．實(shí)驗(yàn)?zāi)康纳钊肜斫庹?qǐng)求頁(yè)式存儲(chǔ)管理的原理，重點(diǎn)認(rèn)識(shí)其中的地址變換、缺頁(yè)中斷、置換算法等實(shí)現(xiàn)思想。二．實(shí)驗(yàn)屬性該實(shí)驗(yàn)為綜合性、設(shè)計(jì)性實(shí)驗(yàn)。三．實(shí)驗(yàn)儀器設(shè)備及器材普通PC386以上微機(jī)四．實(shí)驗(yàn)要求本實(shí)驗(yàn)要求4學(xué)時(shí)完成。本實(shí)驗(yàn)要求完成如下任務(wù)：（1）建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)：存儲(chǔ)塊表、頁(yè)表等；（2）實(shí)現(xiàn)基本分頁(yè)存儲(chǔ)管理，如分配、回收、地址變換；（3）在基本分頁(yè)的基礎(chǔ)上實(shí)現(xiàn)請(qǐng)求分頁(yè)存儲(chǔ)管理；（4）給定一批作業(yè)/進(jìn)程，選擇一個(gè)分配或回收模擬；（5）將整個(gè)過(guò)程可視化顯示出來(lái)。實(shí)驗(yàn)前應(yīng)復(fù)習(xí)實(shí)驗(yàn)中所涉及的理論知識(shí)和算法，針對(duì)實(shí)驗(yàn)要求完成基本代碼編寫(xiě)并完成預(yù)習(xí)報(bào)告、實(shí)驗(yàn)中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測(cè)試、記錄并分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)后認(rèn)真書(shū)寫(xiě)符合規(guī)范格式的實(shí)驗(yàn)報(bào)告（參見(jiàn)附錄A），并要求用正規(guī)的實(shí)驗(yàn)報(bào)告紙和封面裝訂整齊，按時(shí)上交。五、實(shí)驗(yàn)提示1、本實(shí)驗(yàn)雖然不以前面實(shí)驗(yàn)為基礎(chǔ)，但建議在其界面中繼續(xù)增加請(qǐng)求頁(yè)式存儲(chǔ)管理功能。2、數(shù)據(jù)結(jié)構(gòu)：內(nèi)存分配表、頁(yè)表空間（用數(shù)組實(shí)現(xiàn)），修改PCB結(jié)構(gòu)增加頁(yè)表指針、頁(yè)表長(zhǎng)度。3、存儲(chǔ)管理：編寫(xiě)內(nèi)存分配、內(nèi)存回收算法、頁(yè)面置換算法。4、主界面設(shè)計(jì)：在界面上增加一個(gè)請(qǐng)求分頁(yè)內(nèi)存分配按鈕、請(qǐng)求分頁(yè)內(nèi)存回收按鈕、裝入指定進(jìn)程的指定頁(yè)按鈕。觸發(fā)請(qǐng)求分頁(yè)內(nèi)存分配按鈕，彈出作業(yè)大小輸入框，輸入后調(diào)用內(nèi)存分配函數(shù)，在內(nèi)存分配表和頁(yè)表中看到分配的存儲(chǔ)塊。觸發(fā)請(qǐng)求分頁(yè)內(nèi)存回收按鈕，彈出進(jìn)程ID輸入框，輸入后調(diào)用內(nèi)存回收函數(shù)，在內(nèi)存分配表中看到回收后的狀態(tài)改變。功能測(cè)試：從顯示出的內(nèi)存分配表和頁(yè)表，可查看操作的正確與否。六、實(shí)驗(yàn)步驟任務(wù)分析：1.最佳頁(yè)面置換算法（OPT）：其所選擇的被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。2.最近最久未使用（LRU）算法：當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒(méi)有使用過(guò)的頁(yè)面予以置換。程序設(shè)計(jì)：程序功能模塊圖如下：請(qǐng)求分頁(yè)式儲(chǔ)存管理最近最久未使用算法先進(jìn)先出算法請(qǐng)求分頁(yè)式儲(chǔ)存管理最近最久未使用算法先進(jìn)先出算法（1）在同一進(jìn)程中的各個(gè)線程，都可以共享該進(jìn)程所擁有的資源，這表現(xiàn)在：所有線程都具有相同的地址空間（進(jìn)程的地址空間）。此外我們應(yīng)該還要用控制語(yǔ)句，控制線程的同步執(zhí)行。

2.

這個(gè)實(shí)驗(yàn)是要求我們采用算法模擬分頁(yè)存儲(chǔ)管理技術(shù)的FIFO和LRU算法。所以我們應(yīng)該先生成地址序列，有了地址序列，我們要找到它所在的虛頁(yè)，然后通過(guò)查找實(shí)頁(yè)，再判斷下一步動(dòng)作。假如要訪問(wèn)的虛頁(yè)不在內(nèi)存中，不命中，我們要替換實(shí)頁(yè)內(nèi)容。根據(jù)FIFO算法，直接替換最早進(jìn)入內(nèi)存中的那一頁(yè)就可以了。所以可以設(shè)立一個(gè)循環(huán)指針，記錄那個(gè)最早進(jìn)入內(nèi)存中的那頁(yè)。而對(duì)于LRU算法，我們要替換是到現(xiàn)在為止最長(zhǎng)時(shí)間沒(méi)被訪問(wèn)的頁(yè)，在這里我們可以用一個(gè)隊(duì)列來(lái)表示內(nèi)存。把最久沒(méi)使用的頁(yè)放在隊(duì)頭，然后替換進(jìn)去的頁(yè)放在隊(duì)尾就可以了。假如要訪問(wèn)的虛頁(yè)在內(nèi)存中，明顯是命中。對(duì)于FIFO算法，不處理，而對(duì)于LRU算法，我們還要把他的權(quán)值置0。開(kāi)始（2）系統(tǒng)功能流程圖：開(kāi)始開(kāi)始開(kāi)始還有指令？還有指令？NN還有指令？還有指令？YY找到了嗎？計(jì)算頁(yè)號(hào)計(jì)算頁(yè)號(hào)找到了嗎？找到了嗎？計(jì)算頁(yè)號(hào)計(jì)算頁(yè)號(hào)找到了嗎？YYNN新頁(yè)進(jìn)入計(jì)算過(guò)程數(shù)組第一位，其余為一次下移計(jì)算命中率結(jié)束比較現(xiàn)有頁(yè)面計(jì)數(shù)項(xiàng)的大小，新頁(yè)面替換最大項(xiàng)頁(yè)面計(jì)算命中率結(jié)束新頁(yè)進(jìn)入計(jì)算過(guò)程數(shù)組第一位，其余為一次下移計(jì)算命中率結(jié)束比較現(xiàn)有頁(yè)面計(jì)數(shù)項(xiàng)的大小，新頁(yè)面替換最大項(xiàng)頁(yè)面計(jì)算命中率結(jié)束（3）算法分析1.先進(jìn)先出

定義一個(gè)隊(duì)列存放頁(yè)面，頭指針記錄最先進(jìn)入隊(duì)列的頁(yè)面的位置，每次替換頭指針指向的頁(yè)面。2.最近最少使用

定義一個(gè)二維數(shù)組，一維用來(lái)記錄頁(yè)面號(hào)，一維用來(lái)記錄該頁(yè)面被使用的次數(shù)，每次替換最近最少使用的頁(yè)面（3）程序結(jié)果：在運(yùn)行界面選擇某個(gè)算法，運(yùn)行結(jié)果，如圖1，圖2所示：圖1圖2調(diào)試與測(cè)試：1.第一道涉及線程的題編譯時(shí)總是發(fā)生錯(cuò)誤，原來(lái)編譯這類(lèi)程序在原有的編譯語(yǔ)言后要加上-pthread.2.第二個(gè)分頁(yè)算法我們?cè)谙到y(tǒng)結(jié)構(gòu)課已經(jīng)做過(guò)這個(gè)實(shí)驗(yàn)，所以有了一定的了解，加上一點(diǎn)修改就能夠使用了。所以沒(méi)太花功夫。七、實(shí)驗(yàn)總結(jié)通過(guò)實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解了虛擬存儲(chǔ)技術(shù)的特點(diǎn)。通過(guò)對(duì)頁(yè)面、頁(yè)表、地址轉(zhuǎn)換和頁(yè)面置換過(guò)程的模擬，加深對(duì)請(qǐng)求調(diào)頁(yè)系統(tǒng)的原理和實(shí)現(xiàn)過(guò)程的理解，也知道了幾種算法的效率，也驗(yàn)證了LRU算法的命中率平均的比FIFO算法要高。通過(guò)本次實(shí)驗(yàn)，我收獲了很多。我了解到編寫(xiě)程序不是首要任務(wù)，而是一種實(shí)現(xiàn)手段。我們最重要的是如何做好需求分析和理清思路，做出正確、簡(jiǎn)介的流程設(shè)計(jì)，這樣可以達(dá)到事半功倍的效果。八、附錄//#include<windows.h>//#include<iostream>#include"stdio.h"#include<conio.h>#include<malloc.h>#defineN16#definenum5/*進(jìn)程分配物理塊數(shù)目*/intA[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4};/*頁(yè)表映像*/typedefstructpage{intaddress;/*頁(yè)面地址*/structpage*next;}page;structpage*head,*run,*rear;voidjccreat()/*進(jìn)程分配物理塊*/{inti=1;page*p,*q;head=(page*)malloc(sizeof(page));p=head;for(i=1;i<=num;i++){q=(page*)malloc(sizeof(page));p->next=q;q->address=0;q->next=NULL;p=q;}rear=p;}intsearch(intn){page*p;inti=0;p=head;while(p->next){if(p->next->address==n){printf("Getitatthepage%d\n",i+1);run=p;return1;}p=p->next;i++;}return0;}voidchangeOPT(intn,intposition){inti;inttotal=0;intflag=1;intdistance[num];intMAX;intorder=0;page*p,*q;p=head->next;q=head->next;for(i=0;i<num;i++)distance[i]=100;i=0;while(p){if(p->address==0){flag=0;break;}p=p->next;i++;}if(!flag){p->address=n;printf("Changethepage%d\n",i+1);}else{while(q)}for(i=position;i<N;i++){if(q->address==A[i])distance[total]=i-position;}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++){if(distance[i]>MAX){MAX=distance[i];order=i;}}printf("Changethepage%d\n",order+1);i=0;while(p){if(i==order)p->address=n;i++;p=p->next;}}voidchangeLRU(intn){inti=0;intflag=1;page*p,*delect;p=head->next;while(p){if(p->address==0){flag=0;p->address=n;printf("Changethepage%d\n",i+1);break;}p=p->next;i++;}if(flag){delect=head->next;head->next=delect->next;printf("Delectfromthehead,andaddnewtotheend.\n");delect->address=n;rear->next=delect;rear=delect;rear->next=NULL;}}floatOPT(){inti;intlose=0;floatlosef;floatpercent;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}}losef=lose;percent=1-(losef/N);returnpercent;}floatLRU(){inti;intlose=0;floatlosef;floatpercent;page*p;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeLRU(A[i]);}else{p=run->next;run->next=p->next;rear->next=p;rear=p;rear->next=NULL;printf("Moveittoendofqueue.\n");}}losef=lose;percent=1-(losef/N);returnpercent;}main()/*主函數(shù)部分*/{floatpercent;intchoice;printf("Selectthearithmetic:\n(1)OPT\n(2)LRU\nyourchoiceis:");scanf("%d",&choice);/*選擇頁(yè)面置換算法*/jccreat();/*創(chuàng)建進(jìn)程*/if(choice==1)/*采用OPT算法置換*/{percent=OPT();/*計(jì)算OPT時(shí)的缺頁(yè)率*/printf("ThepercentofOPTis%f",percent);}elseif(choice==2)/*采用LRU算法置換*/{percent=LRU();/*計(jì)算LRU時(shí)的缺頁(yè)率*/printf("ThepercentofOPTis%f",percent);elseprintf("Yourchoiceisinvalid.");getch();}信息工程學(xué)院實(shí)驗(yàn)報(bào)告成績(jī)：課程名稱(chēng)：操作系統(tǒng)成績(jī)：指導(dǎo)教師（簽名）：實(shí)驗(yàn)項(xiàng)目名稱(chēng)：請(qǐng)求頁(yè)式存儲(chǔ)管理中常用頁(yè)面置換算法模擬實(shí)驗(yàn)時(shí)間：指導(dǎo)教師（簽名）：班級(jí)姓名：學(xué)號(hào)：一、實(shí)驗(yàn)?zāi)康?了解內(nèi)存分頁(yè)管理策略掌握調(diào)頁(yè)策略掌握一般常用的調(diào)度算法學(xué)會(huì)各種存儲(chǔ)分配算法的實(shí)現(xiàn)方法。了解頁(yè)面大小和內(nèi)存實(shí)際容量對(duì)命中率的影響。二、實(shí)驗(yàn)環(huán)境:PC機(jī)、windows2000操作系統(tǒng)、VC++6.0三、實(shí)驗(yàn)要求：本實(shí)驗(yàn)要求4學(xué)時(shí)完成。采用頁(yè)式分配存儲(chǔ)方案，通過(guò)分別計(jì)算不同算法的命中率來(lái)比較算法的優(yōu)劣，同時(shí)也考慮頁(yè)面大小及內(nèi)存實(shí)際容量對(duì)命中率的影響；實(shí)現(xiàn)OPT算法(最優(yōu)置換算法)

、LRU算法(LeastRecently)

、FIFO算法(FirstINFirstOut)的模擬；會(huì)使用某種編程語(yǔ)言。實(shí)驗(yàn)前應(yīng)復(fù)習(xí)實(shí)驗(yàn)中所涉及的理論知識(shí)和算法，針對(duì)實(shí)驗(yàn)要求完成基本代碼編寫(xiě)、實(shí)驗(yàn)中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測(cè)試、記錄并分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)后認(rèn)真書(shū)寫(xiě)符合規(guī)范格式的實(shí)驗(yàn)報(bào)告，按時(shí)上交。四、實(shí)驗(yàn)內(nèi)容和步驟：編寫(xiě)程序，實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理中常用頁(yè)面置換算法LRU算法的模擬。要求屏幕顯示LRU算法的性能分析表、缺頁(yè)中斷次數(shù)以及缺頁(yè)率。在上機(jī)環(huán)境中輸入程序，調(diào)試，編譯。設(shè)計(jì)輸入數(shù)據(jù)，寫(xiě)出程序的執(zhí)行結(jié)果。根據(jù)具體實(shí)驗(yàn)要求，填寫(xiě)好實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)結(jié)果及分析：實(shí)驗(yàn)結(jié)果截圖如下：利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)，棧底是最近最久未被使用的頁(yè)面號(hào)。當(dāng)訪問(wèn)第5個(gè)數(shù)據(jù)“5”時(shí)發(fā)生了缺頁(yè)，此時(shí)1是最近最久未被訪問(wèn)的頁(yè)，應(yīng)將它置換出去。同理可得，調(diào)入隊(duì)列為：123456713205，缺頁(yè)次數(shù)為12次，缺頁(yè)率為80%。六、實(shí)驗(yàn)心得：本次實(shí)驗(yàn)實(shí)現(xiàn)了對(duì)請(qǐng)求頁(yè)式存儲(chǔ)管理中常用頁(yè)面置換算法LRU算法的模擬。通過(guò)實(shí)驗(yàn)，我對(duì)內(nèi)存分頁(yè)管理策略有了更多的了解。最近最久未使用（LRU）置換算法的替換規(guī)則：是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況來(lái)進(jìn)行決策的。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁(yè)面的時(shí)候選擇現(xiàn)有頁(yè)面中其時(shí)間值最大的進(jìn)行淘汰。最佳置換算法的替換規(guī)則：其所選擇的被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。先進(jìn)先出(FIFO)頁(yè)面置換算法的替換規(guī)則：該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱(chēng)為替換指針，使它總是指向最老的頁(yè)面。三種替換算法的命中率由高到底排列OPT>LRU>FIFO。本次的程序是在網(wǎng)上查找的相關(guān)代碼然后自己進(jìn)行修改，先自己仔細(xì)地研讀了這段代碼，在這過(guò)程中我對(duì)C++代碼編寫(xiě)有了更深的了解?？傊敬螌?shí)驗(yàn)使我明白要學(xué)會(huì)把課堂上的理論應(yīng)用到實(shí)際操作中。我需要在今后熟練掌握課堂上的理論基礎(chǔ)，只有堅(jiān)實(shí)的基礎(chǔ)，才能在實(shí)際操作中更得心應(yīng)手。附錄：#include"iostream.h"#include<iomanip.h>constintDataMax=100;constintBlockNum=10;intDataShow[BlockNum][DataMax];//用于存儲(chǔ)要顯示的數(shù)組boolDataShowEnable[BlockNum][DataMax];//用于存儲(chǔ)數(shù)組中的數(shù)據(jù)是否需要顯示intData[DataMax];//保存數(shù)據(jù)intBlock[BlockNum];//物理塊intcount[BlockNum];//計(jì)數(shù)器intN;//頁(yè)面?zhèn)€數(shù)intM;//最小物理塊數(shù)intChangeTimes;voidDataInput();//輸入數(shù)據(jù)的函數(shù)voidDataOutput();voidLRU();//LRU函數(shù)///*intmain(intargc,char*argv[]){DataInput();//DataInput();LRU();return0;}//*/voidDataInput(){cout<<"請(qǐng)輸入最小物理塊數(shù)：";cin>>M;while(M>BlockNum)//大于數(shù)據(jù)個(gè)數(shù){cout<<"物理塊數(shù)超過(guò)預(yù)定值，請(qǐng)重新輸入：";cin>>M;}cout<<"請(qǐng)輸入頁(yè)面的個(gè)數(shù)：";cin>>N;while(N>DataMax)//大于數(shù)據(jù)個(gè)數(shù){cout<<"頁(yè)面?zhèn)€數(shù)超過(guò)預(yù)定值，請(qǐng)重新輸入：";cin>>N;}cout<<"請(qǐng)輸入頁(yè)面訪問(wèn)序列："<<endl;for(inti=0;i<N;i++)cin>>Data[i];}voidDataOutput(){inti,j;for(i=0;i<N;i++)//對(duì)所有數(shù)據(jù)操作{cout<<Data[i]<<””;}cout<<"\n"<<endl;for(j=0;j<M;j++){cout<<"";for(i=0;i<N;i++)//對(duì)所有數(shù)據(jù)操作{if(DataShowEnable[j][i])cout<<DataShow[j][i]<<"|";elsecout<<"|";}cout<<endl;}cout<<"\n缺頁(yè)次數(shù):"<<ChangeTimes<<endl;cout<<"缺頁(yè)率:"<<ChangeTimes*100/N<<"%"<<endl;}voidLRU(){inti,j;boolfind;intpoint;