1、南昌大學實驗報告 -（3）存儲管理的模擬實現學生姓名： 張晨欣 學 號： 61004011132 專業班級： 電114班 實驗類型： 驗證 綜合 設計 創新 實驗日期： 實驗成績： 一、 實驗目的存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。本實驗的目的是通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式管理的頁面置換算法。二、 實驗內容1 過隨機數產生一個指令序列，共320條指令。其地址按下述原則生成：50%的指令是順序執行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分；具體的實施方法是：A. 在0

2、，319的指令地址之間隨機選區一起點M;B. 順序執行一條指令，即執行地址為M+1的指令；C. 在前地址0，M+1中隨機選取一條指令并執行，該指令的地址為M;D. 順序執行一條指令，其地址為M+1；E. 在后地址M+2，319中隨機選取一條指令并執行；F. 重復AE，直到執行320次指令。2 指令序列變換成頁地址流，設：（1） 頁面大小為1K；（2） 用戶內存容量為4頁到32頁；（3） 用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條第9條指令為第0頁（對應虛存地址為0，9）；第10條第19條指令為第1頁（對應虛存地址為10，19

3、）；。第310條第319條指令為第31頁（對應虛存地址為310，319）；按以上方式，用戶指令可組成32頁。3 計算并輸出下述各種算法在不同內存容量下的命中率。A. FIFO先進先出的算法B. LRU最近最少使用算法C. LFU最少訪問頁面算法三、 實驗要求1、 需寫出設計說明；2、 設計實現代碼及說明3、 運行結果；四、 主要實驗步驟1、 分析算法結構；2、 畫出算法的流程圖，即設計說明；3、 根據畫出的流程圖使用C語言編寫相應的代碼（代碼過長，放到最后）；程序主要由main函數和以下幾個函數組成：void initialization();初始化內存數據void FIFO();FIFO先進

4、先出算法；void LRU();LRU最久未使用算法；void LFU();LFU最近最久未使用算法；4、 檢查代碼，將編出的代碼編譯、鏈接，驗證其正確性。頁面置換算法整體結構FIFO頁面置換算法LRU頁面置換算法LFU頁面置換算法五、 實驗數據及處理結果六、 實驗體會或對改進實驗的建議我做實驗的時候，主要的難度是在幾個特殊情況的處理上，如LRU內存中的頁面都是之前沒有調用過的，那怎么辦，還有就是LFU中還沒有達到“一定時間間隔”的條件時怎么辦？另外就是由于實驗使用的是系統產生的隨機數，所以難以驗證實驗結果的正確性。七、 參考資料計算機操作系統計算機操作系統實驗指導書C程序設計C語言程序設計_

5、現代方法計算機操作系統教程習題解答與實驗指導(第二版)八、 實驗代碼#include <stdio.h>#include <stdlib.h>#include <time.h>int s,i;/s表示產生的隨機數，i表示物理塊數int m,n,h;/循環專用int k,g,f;/臨時數據int sum;/缺頁次數float r;/rate命中率int p320;/page頁數int a320;/執行的指令int pb32;/physical block用戶內存容量（物理塊）void initialization();void FIFO();void LRU(

6、);void LFU();void line();void start();void end();void main()start();srand(int) time (NULL);/以計算機當前時間作為隨機數種子for (n=0;n<320;n+=3)s=rand()%320+0;/隨機產生一條指令an=s+1;/順序執行一條指令s=rand()%(an+1);/執行前地址指令Man+1=s+1;s=rand()%(319-an+1)+(an+1+1);an+2=s;for (n=0;n<320;n+)pn=an/10;/得到指令相對的頁數printf("物理塊數t F

7、IFOtt LRUtt LFUn");line();for (i=4;i<=32;i+)printf("n %2d：",i);FIFO();LRU();LFU();end();void initialization()/用戶內存及相關數據初始化for (n=0;n<32;n+)pbn=-1;sum=0;r=0;k=0;g=-1;f=-1;void FIFO()/先進先出置換算法int time32;/定義進入內存時間長度數組int max;/max表示進入內存時間最久的，即最先進去的initialization();for(m=0;m<i;m+)

8、timem=m+1;for (n=0;n<320;n+)k=0;for (m=0;m<i;m+)if (pbm=pn)/表示內存中已有當前要調入的頁面g=m;break;for (m=0;m<i;m+)if (pbm=-1)/用戶內存中存在空的物理塊f=m;break;if (g!=-1)g=-1;elseif (f=-1)/找到最先進入內存的頁面max=time0;for(m=0;m<i;m+)if(timem>max)max=timem;k=m;pbk=pn;timek=0;/該物理塊中頁面停留時間置零sum+;/缺頁數+1elsepbf=pn;timef=0

9、;sum+;f=-1;for (m=0;m<i && pbm!=-1;m+)timem+;/物理塊中現有頁面停留時間+1r=1-(float)sum/320;printf("tt%6.4f",r);void LRU()/最近最少使用算法int time32;int max;initialization();for (m=0;m<i;m+)timem=m+1;for (n=0;n<320;n+)k=0;for (m=0;m<i;m+)if (pbm=pn)g=m;break;for (m=0;m<i;m+)if (pbm=-1)f

10、=m;break;if (g!=-1)timeg=0;g=-1;elseif (f=-1)max=time0;for (m=0;m<i;m+)if (timem>max)k=m;max=timem;pbk=pn;timek=0;sum+;elsepbf=pn;timef=0;sum+;f=-1;for (m=0;m<i && pbm!=-1;m+)timem+;r=1-(float)sum/320;printf("tt%6.4f",r);void LFU()/最少訪問頁面算法initialization();int time_lru32,t

11、ime32,min,max_lru,t;for (m=0;m<i;m+)timem=0;time_lrum=m+1;for (n=0;n<320;n+)k=0;t=1;for (m=0;m<i;m+)if (pbm=pn)g=m;break;for (m=0;m<i;m+)if (pbm=-1)f=m;break;if (g!=-1)time_lrug=0;g=-1;elseif (f=-1)if (n<=20)/將最少使用的間隔時間定位個單位max_lru=time_lru0;/在未達到“一定時間”的要求時，先采用LRU進行頁面置換for (m=0;m<i

12、;m+)if (time_lrum>max_lru)k=m;max_lru=time_lrum;pbk=pn;time_lruk=0;sum+;elsefor (m=0;m<i;m+)/計算一定時間間隔內物理塊中的頁面使用次數for (h=n-1;h>=n-51;h-)if (pbm=ph)timem+;min=time0;for (m=0;m<i;m+)if (timem<min)min=timem;k=m;for (m=0;m<i;m+)/應對出現頁面使用次數同樣少的情況if (timem=min)t+;if (t>1)/若使用次數同樣少，將次數相

13、同的頁面按照LRU進行頁面置換max_lru=time_lruk;for (m=0;m<i && timem=min;m+)if (time_lrum>max_lru)k=m;max_lru=time_lrum;pbk=pn;time_lruk=0;sum+;elsepbf=pn;time_lruf=0;sum+;f=-1;for (m=0;m<i && pbm!=-1;m+)time_lrum+;r=1-(float)sum/320;printf("tt%6.4f",r);void line() /美化程序，使程序運行時更加明朗美觀printf("-");void start() /表示算法開始line();printf