計算機操作系統(tǒng)

1、淮海工學(xué)院計算機工程學(xué)院實驗報告書課i程名:操作系統(tǒng)原理A 題目：虛擬存儲器管理頁面置換算法模擬實驗班級：Z 計 121學(xué)號：2014140093姓名：薛慧君一、實驗?zāi)康呐c要求目的：請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換 算法的模擬，有助于理解虛擬存儲技術(shù)的特點，并加深對請求頁式虛存管理的頁面調(diào)度算法的 理解。要求：本實驗要求使用C語言編程模擬一個擁有若干個虛頁的進程在給定的若干個實頁中運行、 并在缺頁中斷發(fā)生時分別使用FIFO和LRU算法進行頁面置換的情形。其中虛頁的個數(shù)可以事 先給定（例如10個），對這些虛頁訪問的頁地址流（其長度可以事先給定，例如2

2、0次虛頁訪 問）可以由程序隨機產(chǎn)生，也可以事先保存在文件中。要求程序運行時屏幕能顯示出置換過程 中的狀態(tài)信息并輸出訪問結(jié)束時的頁面命中率。程序應(yīng)允許通過為該進程分配不同的實頁數(shù)， 來比較兩種置換算法的穩(wěn)定性。二、實驗說明設(shè)計中虛頁和實頁的表示本設(shè)計利用C語言的結(jié)構(gòu)體來描述虛頁和實頁的結(jié)構(gòu)。虛頁結(jié)構(gòu)實頁結(jié)構(gòu)在虛頁結(jié)構(gòu)中，pn代表虛頁號，因為共10個虛頁，所以pn的取值范圍是09。pfn代表實 頁號，當一虛頁未裝入實頁時，此項值為-1;當該虛頁已裝入某一實頁時，此項值為所裝入的實頁 的實頁號pfn。time項在FIFO算法中不使用，在LRU中用來存放對該虛頁的最近訪問時間。在實頁結(jié)構(gòu)中中，pn代表

3、虛頁號，表示pn所代表的虛頁目前正放在此實頁中。pfn代表實頁號， 取值范圍（0n-1）由動態(tài)指派的實頁數(shù)n所決定。next是一個指向?qū)嶍摻Y(jié)構(gòu)體的指針，用于多個 實頁以鏈表形式組織起來，關(guān)于實頁鏈表的組織詳見下面第4點。關(guān)于缺頁次數(shù)的統(tǒng)計為計算命中率，需要統(tǒng)計在20次的虛頁訪問中命中的次數(shù)。為此，程序應(yīng)設(shè)置一個計數(shù)器count， 來統(tǒng)計虛頁命中發(fā)生的次數(shù)。每當所訪問的虛頁的pfn項值不為-1，表示此虛頁已被裝入某實頁內(nèi)， 此虛頁被命中，count加1。最終命中率=count/20*100%。LRU算法中“最近最久未用”頁面的確定為了能找到“最近最久未用”的虛頁面，程序中可引入一個時間計數(shù)器co

4、untime，每當要訪問 一個虛頁面時，countime的值加1，然后將所要訪問的虛頁的time項值設(shè)置為增值后的當前 countime值，表示該虛頁的最后一次被訪問時間。當LRU算法需要置換時，從所有已分配實頁的虛 頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應(yīng)該將它置換出去。算法中實頁的組織因為能分配的實頁數(shù)n是在程序運行時由用戶動態(tài)指派的，所以應(yīng)使用鏈表組織動態(tài)產(chǎn)生的多個實 頁。為了調(diào)度算法實現(xiàn)的方便，可以考慮引入free和busy兩個鏈表：free鏈表用于組織未分配出 去的實頁，首指針為free_head，初始時n個實頁都處于free鏈表中；busy鏈表用于組織已分配出

5、 去的實頁，首指針為busy_head，尾指針為busy_tail，初始值都為null。當所要訪問的一個虛頁 不在實頁中時，將產(chǎn)生缺頁中斷。此時若free鏈表不為空，就取下鏈表首指針所指的實頁，并分配 給該虛頁。若free鏈表為空，則說明n個實頁已全部分配出去，此時應(yīng)進行頁面置換：對于FIFO 算法要將busy_head所指的實頁從busy鏈表中取下，分配給該虛頁，然后再將該實頁插入到busy 鏈表尾部；對于LRU算法則要從所有已分配實頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝 載它的那個實頁中置換出去，并在該實頁中裝入當前正要訪問的虛頁。三、程序流程圖還有指令嗎?LRU開始1r計算出

6、頁號1r在實存對列中查找該頁號1找到了嗎新頁塊按實際循環(huán)入實存對列Y把新頁放入棧頂，同時向下移動其余頁號計算出命中率/結(jié)束計算出命中率四、主要程序清單#include #include /*全局變量*/int mSIZE;/*物理塊數(shù)*/int pSIZE;/*頁面號引用串個數(shù)*/static int memery10=0;/*物理塊中的頁號*/static int page100=0;/*頁面號引用串*/static int temp10010=0;/*輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();void LRU();void OPT();/*輔助函數(shù)*/void print(un

7、signed int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函數(shù)*/void main()int i,k,code;printf(請輸入物理塊的個數(shù)(M=10)：”);scanf(%d”,&mSIZE);printf(-請輸入頁面號引用串的個數(shù)(P=100)：);scanf(%d”,&pSIZE);puts(-請依次輸入頁面號引用串(連續(xù)輸入，無需隔開)：)；for(i=0;ipSIZE;i+)scanf(%1d”,&pagei); download();doputs(-輸入的頁面號引用串為：

8、);for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i”);getchar();while (code!=4);getchar();/*載入數(shù)據(jù)*/void download() printf(nFinish.n 載入成功!)；/*設(shè)置延遲*/void mDelay(unsigned int Delay)unsigned int i;for(;Delay0;Delay)for(i=0;i124;i+)printf( b);/*顯示設(shè)計者信息*/void print(unsigned int t)int i,j,k,l; int flag;for(k

9、=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i20*(k+1);i+) if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1) printf(%dn”,pagei);elseprintf(%d ”,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)printf( |%d|”,tempij); elseprintf( | |);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tem

10、pi-1l)flag+;if(flag=mSIZE)/*頁面在物理塊中*/printf( );elseprintf( |%d|”,tempij);/*每行顯示20個*/if(i%20=0)continue;printf(n)；printf(n); 操作系統(tǒng)原理 實驗報告 printf（缺頁次數(shù)：dtt”,t+mSIZE）;printf(缺頁率：d/%dn”,t+mSIZE,pSIZE);printf(置換次數(shù)：dtt”,t);printf(訪問命中率：d%n”,(pSIZE-(t+mSIZE)*100/pSIZE);printf(n);/*計算過程延遲*/void compute()int i

11、;printf(正在進行相關(guān)計算，請稍候);for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);/*先進先出頁面置換算法*/void FIFO()int memery10=0;int time10 = 0; /*記錄進入物理塊的時間*/int i,j,k,m;int max=0;/*記錄換出頁*/int count=0;/*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/for(i=0;imSIZE;i+)memeryi=pagei;timei=i;for(j=0;jmSIZE;j+) 操作系統(tǒng)原理 實驗報告

12、tempij=memeryj;for(i=mSIZE;ipSIZE;i+)/*判斷新頁面號是否在物理塊中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;if(k=mSIZE)/*如果不在物理塊中*/count+;/*計算換出頁*/max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m;memerymax=pagei;timemax=i;/*記錄該頁進入物理塊的時間*/for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+)tempij=m

13、emeryj;compute();print(count);/*最近最久未使用置換算法*/void LRU()int memery10=0;int flag10=0;/*記錄頁面的訪問時間*/int i,j,k,m;int max=0;/*記錄換出頁*/int count=0;/*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/for(i=0;imSIZE;i+)memeryi=pagei;flagi=i;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)/*判斷新頁面號是否在物理塊中*/for(j=0,k=0;jmSIZE;j+)if

14、(memeryj!=pagei)k+;elseflagj=i;/*刷新該頁的訪問時間*/if(k=mSIZE)/*如果不在物理塊中*/count+;/*計算換出頁*/max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m;memerymax=pagei;flagmax=i; /*記錄該頁的訪問時間*/for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);/*最佳置換算法*/void OPT()int m

15、emery10=0;int next10=0;/*記錄下一次訪問時間*/int max;/*記錄換出頁*/int count=0;/*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/for(i=0;imSIZE;i+)memeryi=pagei;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)/*判斷新頁面號是否在物理塊中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;if(k=mSIZE)/*如果不在物理塊中*/count+;/*得到物理快中各頁下一次訪問時間*/for(m=0;mmSIZE

16、;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時間都為pSIZE，則置換物理塊中第一個*/memerymax=pagei;for(j=0;jmSIZE;j+)tempij=memeryj;if(k=mSIZE)/*如果不在物理塊中*/count+;/*得到物理快中各頁下一次訪問時間*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1; for(m=2;mnextmax)max=m;/*下一次訪問時間都為pSIZE，則置換物理塊中第一個*/memerymax=pagei;for(j=0;jmSIZE;j+)操作系統(tǒng)原理實驗報告 tempij=memeryj;五、程序運行結(jié)果F