操作系統(tǒng)(含課程設(shè)計(jì)),平時(shí)作業(yè)2020秋華工答案

華南理工大學(xué)2020秋季“操作系統(tǒng)”課程平時(shí)作業(yè)一、題目：頁(yè)面置換算法模擬實(shí)驗(yàn)二、目的：本次實(shí)驗(yàn)旨在通過(guò)采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最少使用(LRU)置換算法對(duì)用戶輸入的頁(yè)面號(hào)請(qǐng)求序列進(jìn)行淘汰和置換，加深對(duì)頁(yè)面置換算法的理解。三、內(nèi)容和要求：1.認(rèn)真閱讀教材（計(jì)算機(jī)操作系統(tǒng)（第四版），湯小丹，西安電子科技大學(xué)出版社）P162頁(yè)5.3節(jié)頁(yè)面置換算法的實(shí)現(xiàn)思想。2.編寫一個(gè)頁(yè)面轉(zhuǎn)換算法模擬程序用于處理進(jìn)程的頁(yè)面訪問(wèn)序列串。3.使用C/C++語(yǔ)言編寫程序。4.用戶通過(guò)鍵盤輸入分配給進(jìn)程的物理內(nèi)存塊總數(shù)，再輸入用戶頁(yè)面號(hào)請(qǐng)求序列。5.分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最少使用(LRU)置換算法三種算法對(duì)頁(yè)面請(qǐng)求序列進(jìn)行處理。6.按照課本P163-P165頁(yè)圖所示的置換圖格式輸出每次頁(yè)面請(qǐng)求后各物理塊內(nèi)存放的頁(yè)面號(hào)，并算出總的缺頁(yè)率（缺頁(yè)次數(shù)/總的請(qǐng)求次數(shù)）。7.程序編寫完成后，實(shí)驗(yàn)時(shí)請(qǐng)輸入頁(yè)面號(hào)請(qǐng)求序列為4、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給進(jìn)程的物理塊數(shù)分別為3塊和4塊時(shí)，試用自己編寫的模擬程序進(jìn)行頁(yè)面轉(zhuǎn)換并輸出置換圖和缺頁(yè)次數(shù)、缺頁(yè)率，最后比較三種頁(yè)面置換算法的優(yōu)缺點(diǎn)。8.三種頁(yè)面置換算法的思想可參考教材P162-P165頁(yè)。四、實(shí)驗(yàn)要求：每人完成一份平時(shí)作業(yè)報(bào)告。報(bào)告分設(shè)計(jì)思想、數(shù)據(jù)定義、處理流程、源程序、運(yùn)行結(jié)果截圖、設(shè)計(jì)體會(huì)等部分。1.給出數(shù)據(jù)定義和詳細(xì)說(shuō)明。2.給出實(shí)現(xiàn)思想和設(shè)計(jì)流程。3.調(diào)試完成源程序。4.屏幕觀察運(yùn)行結(jié)果。5.總結(jié)自己的設(shè)計(jì)體會(huì)。編程語(yǔ)言及操作系統(tǒng)平臺(tái)不限。五、提交內(nèi)容：本平時(shí)作業(yè)每個(gè)人必須單獨(dú)完成。最后需提交的報(bào)告內(nèi)容包括：數(shù)據(jù)定義、算法思路及流程圖、源程序（關(guān)鍵代碼需要注釋說(shuō)明）、運(yùn)行截圖、心得體會(huì)或者總結(jié)。將以上內(nèi)容編寫為一個(gè)WORD文檔（.DOC）上傳到教學(xué)管理系統(tǒng)。平時(shí)作業(yè)嚴(yán)禁抄襲。發(fā)現(xiàn)抄襲（重復(fù)率97%以上）一律以不及格論。課作業(yè)內(nèi)容要完整，一定要有數(shù)據(jù)定義、算法思路、流程圖、心得體會(huì)、運(yùn)行輸出信息截屏等內(nèi)容，如果只提交源代碼則大作業(yè)成績(jī)記為不合格。在進(jìn)程運(yùn)行過(guò)程中，如果要訪問(wèn)的頁(yè)面不在內(nèi)存中，就需要將它們調(diào)入內(nèi)存，但是當(dāng)內(nèi)存沒(méi)有空閑空間時(shí)，為了確保該進(jìn)程能夠正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤的對(duì)換區(qū)中。但是應(yīng)該將哪個(gè)頁(yè)面調(diào)出，需要根據(jù)一定的算法來(lái)確定。通常，選擇換出頁(yè)面的算法稱為頁(yè)面換算法。1.最佳（Optimal）置換算法最佳置換算法是一種理想化的算法，它具有最好的性能，但實(shí)際上是無(wú)法實(shí)現(xiàn)的。通常使用最佳置換算法作為標(biāo)準(zhǔn)，來(lái)評(píng)價(jià)其他算法的優(yōu)劣。實(shí)現(xiàn)思路：本次實(shí)驗(yàn)為模擬最佳置換算法，用戶需求頁(yè)順序視為已知序列4、3、2、1、4、3、5、4、3、2、1、5。首先前三次調(diào)用不需要置換頁(yè)面，從第4次開始則需要開始判斷當(dāng)前每個(gè)物理塊中的頁(yè)面在未來(lái)調(diào)用的間隔是多少，取需求頁(yè)面間隔最長(zhǎng)的物理塊置換即可。2.先進(jìn)先出（FIFO）頁(yè)面置換算法FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(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è)指針，稱為替換指針，使它總是指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問(wèn)，比如，含有全局變量、常用函數(shù)、例程等的頁(yè)面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。實(shí)現(xiàn)思路：該算法實(shí)現(xiàn)較為簡(jiǎn)單，只需設(shè)置一個(gè)變量保存最老頁(yè)面的位置即可，需要置換時(shí)直接替換最老頁(yè)面。3.最近最久未使用（LRU）置換算法最近最久未使用的頁(yè)面置換算法是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況作出決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。實(shí)現(xiàn)思路：記錄每個(gè)物理塊的使用間隔，需要置換時(shí)就更換使用間隔最長(zhǎng)的物理塊的頁(yè)面。二、源程序（運(yùn)算所需數(shù)據(jù)說(shuō)明已在程序中注釋）和運(yùn)行輸出截圖1.最佳（Optimal）置換算法#include<stdio.h>ints[]={4,3,2,1,4,3,5,4,3,2,1,5};//用戶需求頁(yè)順序12intb[4];//物理塊inta[4][12];//最后輸出顯示intq=0;//缺頁(yè)次數(shù)//最佳置換算法尋找物理塊中最長(zhǎng)時(shí)間不使用的頁(yè)，參數(shù)值為當(dāng)前用戶需求頁(yè)的數(shù)量-1，返回值為物理塊中需要替換的頁(yè)位置intfindLong(intf){intx=0;inty=0;intj=0;for(j=f+1;j<12;j++){if(b[0]==s[j]){y=j-f;break;}elseif(j==12){return0;}}for(j=f+1;j<12;j++){if(b[1]==s[j]){if(j-f>y){y=j-f;x=1;}break;}elseif(j==12){return1;}}for(j=f+1;j<12;j++){if(b[2]==s[j]){if(j-f>y){y=j-f;x=2;}break;}elseif(j==12){return2;}}for(j=f+1;j<12;j++){if(b[3]==s[j]){if(j-f>y){y=j-f;x=3;}break;}elseif(j==12){return3;}}returnx;}voidopt(){intj=0;for(j=0;j<12;j++){if(j<4){b[j]=s[j];printf("需求頁(yè)面%d在物理塊%d中\(zhòng)n",s[j],j);}else{intk=findLong(j);b[k]=s[j];printf("需求頁(yè)面%d替換了物理塊%d中的頁(yè)面%d\n",s[j],k,b[k]);}}}/*最佳置換算法被淘汰頁(yè)是以后不再使用或者最長(zhǎng)時(shí)間不使用的因不能預(yù)知未來(lái)會(huì)使用哪個(gè)頁(yè)面所以無(wú)法實(shí)現(xiàn)模擬實(shí)驗(yàn)的條件為已知用戶所有需求頁(yè)*/intmain(){inti=0;for(i=0;i<12;i++){scanf("%d",&s[i]);}opt();return0;}2.先進(jìn)先出(FIFO)頁(yè)面置換算法#include<stdio.h>ints[]={4,3,2,1,4,3,5,4,3,2,1,5};//用戶需求頁(yè)順序12intb[3];//物理塊inta[3][12];//最后輸出顯示intq=0;//缺頁(yè)次數(shù)/*FIFO置換算法被淘汰頁(yè)是最老的頁(yè)面*/voidfifo(){//最老的頁(yè)面的物理塊位置intf=0;//模擬用戶需求頁(yè)面操作intj=0;for(j=0;j<12;j++){//判斷需求頁(yè)是否在物理塊中if(b[0]==s[j]||b[1]==s[j]||b[2]==s[j]){a[0][j]=b[0];a[1][j]=b[1];a[2][j]=b[2];}//如果需求頁(yè)不在物理塊中else{//將需求頁(yè)放入最老的物理塊位置b[f]=s[j];//最老的物理塊位置后移f=(f+1)%3;//記錄缺頁(yè)次數(shù)q++;//輸出顯示a[0][j]=b[0];a[1][j]=b[1];a[2][j]=b[2];}}//以下為輸出顯示printf("需求頁(yè):");for(j=0;j<12;j++){printf("%d",s[j]);}printf("\n物理塊1:");for(j=0;j<12;j++){printf("%d",a[0][j]);}printf("\n物理塊2:");for(j=0;j<12;j++){if(j==0){printf("");}else{printf("%d",a[1][j]);}}printf("\n物理塊3:");for(j=0;j<12;j++){if(j<2){printf("");}else{printf("%d",a[2][j]);}}printf("\n");printf("FIFO置換算法的缺頁(yè)數(shù)%d\n",q);//輸出缺頁(yè)率intqyl=q/12.0*100;printf("FIFO置換算法的缺頁(yè)率為%d%%",qyl);}intmain(){fifo();return0;}for(j=0;j<4;j++){if(j==u){l[j]=0;}else{l[j]++;if(l[j]>l[lo]){lo=j;}}}}voidlru(){inti,j,k;for(i=0;i<12;i++){//內(nèi)存未滿則直接調(diào)入內(nèi)存if(i<4){b[i]=s[i];updateTime(i);}elseif(b[0]==s[i]||b[1]==s[i]||b[2]==s[i]||b[3]==s[i]){//如果需求頁(yè)在內(nèi)存中則更新使用間隔for(j=0;j<4;j++){if(b[j]==s[i]){updateTime(j);break;}}}else{//更換最久未使用的頁(yè)面,并記錄當(dāng)前未使用的頁(yè)面b[lo]=s[i];updateTime(lo);//記錄缺頁(yè)次數(shù)q++;}//輸出顯示for(k=0;k<4;k++){a[k][i]=b[k];}}//以下為輸出顯示printf("需求頁(yè):");for(i=0;i<12;i++){printf("%d",s[i]);}printf("\n物理塊1:");for(i=0;i<12;i++){printf("%d",a[0][i]);}printf("\n物理塊2:");for(i=0;i<12;i++){printf("%d",a[1][i]);}printf("\n物理塊3:");for(i=0;i<12;i++){printf("%d",a[2][i]);}printf("\n物理塊4:");for(i=0;i<12;i++){printf("%d",a[3][i]);}printf("\n");printf("最近最久未使用(LRU)置換算法的缺頁(yè)數(shù)%d\n",q);//輸出缺頁(yè)率intqyl=q/12.0*100;printf("最近最久未使用(LRU)置換算法的缺頁(yè)率為%d%%",qyl);}intmain(){lru();return0;}for(j=0;j<4;j++){if(j==u){l[j]=0;}else{//使用間隔加1l[j]++;}}intlo=0;//記錄當(dāng)前最未使用的頁(yè)面的物理塊位置for(j=0;j+1<4;j++){if(l[j]<l[j+1]){lo=j+1;}}/*LRU置換算法被淘汰頁(yè)是最老的頁(yè)面*/voidlru(){//模擬用戶需求頁(yè)面操作intj=0;for(j=0;j<12;j++){//內(nèi)存未滿則直接調(diào)入內(nèi)存if(j<4){b[j]=s[j];updateTime(j);//如果需求頁(yè)在內(nèi)存中則不需要更換但是頁(yè)面使用間隔也要刷新，否則就需要查找更換位置}elseif(b[0]==s[j]){updateTime(0);}elseif(b[1]==s[j]){updateTime(1);}elseif(b[2]==s[j]){updateTime(2);}elseif(b[3]==s[j]){updateTime(3);}else{b[lo]=s[j];updateTime(lo);//記錄缺頁(yè)次數(shù)q++;}//輸出顯示a[0][j]=b[0];a[1][j]=b[1];a[2][j]=b[2];a[3][j]=b[3];}//以下為輸出顯示printf("需求頁(yè):");for(j=0;j<12;j++){printf("%d",s[j]