漳州師范學院操作系統課程設計內存FIFO、LRU頁面置換算法設計姓名：學號：系別：計算機科學與工程系專業：年級：指導教師：一、課程設計項目介紹（含項目介紹及設計目的）1.實驗目的：1.1通過這些算法的設計，深入理解虛擬存儲器管理的原理；1.2理解內存分頁管理策略，以及頁面與物理塊之間的關系；1.3掌握內存調頁策略；1.4理解常用的頁面置換算法，如LRU、FIFO等置換算法，并選取LRU、FIFO算法模擬實現；1.5通過統計比較算法的運行結果，了解各種置換算法的命中率高低，以加深對算法本身的認識。2.實驗項目介紹：項目程序是用C語言實現LRU、FIFO頁面置換算法，可運行在VC，C-FREE等編譯環境下。本程序是在假設系統采用固定分配局部置換策略的基礎上，來模擬內存的調頁策略和置換算法。FIFO算法主要是考慮頁面進入內存的時間長短，當缺頁時把進入最久的頁面置換掉；LRU算法以最近的過去作為最近的將來的參考，當產生缺頁時，把最近最久未使用的頁面置換掉。由于兩個算法的相似性，所以進行統一處理，并加以區分。二、總體設計（含系統的總體結構、原理框圖或各模塊介紹等）1.確定LRU、FIFO算法中的數據結構 定義了一個結構體structpage{intpagenum;intpagetime;};(pagenum為頁面號碼，pagetime為進入時間或者上次使用的時間)來模擬內存的頁面；用page定義一個結構體數組p_age[10],表示可供使用的內存頁面為10；定義一個整形數組intb[N]用來存放要訪問的內存頁面串，串的長度不要超過N，本程序N=100。 定義整形變量pagecount，num，time分別表示要申請的內存頁數和要訪問的內存頁面串的長度；整形變量time用來表示時間，初始化為1，當p_age[i]頁面進入時，p_age[i].pagetime=time++,此后每進入一個頁面，或者更新一個頁面，都把time賦給該內存頁面的時間對象，然后自加1。頁面的時間對象pagetime最大的那個頁面是剛訪問過或者剛進入的，pagetime最小的那個頁面當產生缺頁時將被替換掉； 變量misspage，missrate分別用來記錄缺頁數和缺頁率；變量flag用來標記要訪問的頁面是否在內存中，label用來標記已在內存中且pagetime最小的頁面；FIFO[]，LRU[]數組用來記錄每一次執行算法的缺頁率。2.核心算法的實現申請的內存頁數為pagecount,p_age[i]為內存中頁面,b[]為輸入的頁面串，num為b[]的長度；(1)初始化內存頁面(2)FIFO算法從i=0開始逐個調入頁面，查找b[]頁面串第i個頁面是否已經存在在內存當中，如果已經存在則用flag=1來做標記，i++并開始下個循環；如果不存在則flag=0，并查找已在內存中p_age[k]頁面的成員pagetime最小的頁面，并用label=k標記，查找到之后用b[i]頁面替換p_age[label]，并且p_age[lable].pagetime=time++；繼續循環，直到i=num，執行完之后輸出缺頁數和缺頁率。(3)LRU算法從i=0開始逐個調入頁面，查找b[]頁面串第i個頁面是否已經存在在內存當中，如果已經存在則用flag=1來做標記，并更新該內存頁面的pagetime(訪問時間)對象，i++開始下個循環；如果不存在則flag=0，并查找已在內存中p_age[k]頁面的成員pagetime最小的頁面，并用label=k標記，查找到之后用b[i]頁面替換p_age[label],并且p_age[lable].pagetime=time++；繼續循環，直到i=num，執行完之后輸出缺頁數和缺頁率。重新調用主程序，開始另一個實例的輸入（option==4）統計缺頁率，計算平均缺頁率（option==3）執行最近最久未使用LRU算法（option==2）重新調用主程序，開始另一個實例的輸入（option==4）統計缺頁率，計算平均缺頁率（option==3）執行最近最久未使用LRU算法（option==2）執行先進先出FIFO算法（option==1）主程序3．程序結構圖三、詳細設計（含主要的數據結構、程序流程圖、關鍵代碼段及注釋等）入口入口startstart輸入申請的內存頁數N、頁面串的長度、輸入頁面串輸入申請的內存頁數N、頁面串的長度、輸入頁面串OOption==1||2輸入option輸入optionOption==5初始化內存及變量Option==5初始化內存及變量退出 Y退出Option==4NOption==4逐個讀入頁面Y 逐個讀入頁面N頁面是否在內存中Option==3N頁面是否在內存中Option==3 Y統計缺頁率、計算平均缺頁率并輸出結果NY統計缺頁率、計算平均缺頁率并輸出結果在內存中第一次查找到pagetime最小的頁面在內存中第一次查找到pagetime最小的頁面Kp_age[k]LRU算法?Y將存在在內存中的頁面p_age[k].pagetime=time+++++置換頁面將存在在內存中的頁面p_age[k].pagetime=time+++++置換頁面p_age[k].pagenum=b[i]p_age[k].pagetime=time++N輸出缺頁數和缺頁率Y是否還有未讀頁面N輸出缺頁數和缺頁率Y是否還有未讀頁面程序代碼：structpage //用結構體模擬內存{intpagenum; //內存頁號intpagetime; //對FIFO算法是進入時間，LRU是訪問時間};#include<stdio.h>voidmain(){pagep_age[10]; //定義一個10個頁面的內存結構intb[100]; //用來保存要訪問的頁面序列intpagecount,num,time,mintime,misspage;//pagecount是要申請的內存頁數，num為要訪問的頁面序列的長度，time變量是//用來模擬時間inti,j,k,option,flag,lable; //option是選項，用來調用程序功能floatmissrate;staticfloatFIFO[100]={0},LRU[100]={0}; //用來記錄每次的缺頁率staticintf=0,l=0; //f,l分別代表FIFO[]和LRU[]的長度printf("**************************************************\n");printf(" WELCOMETOHERE!\n");printf("***************************************************\n");printf("請輸入模擬的內存頁數！\n");scanf("%d",&pagecount);printf("請輸入要輸入的頁面數！\n");scanf("%d",&num);printf("請輸入頁面序列！\n");for(i=0;i<num;i++){scanf("%d",&b[i]);}printf("************************************************\n");printf(" 選擇FIFO算法請輸入1! \n");printf(" 選擇LRU算法請輸入2! \n");printf(" 缺頁率統計請輸入3!\n");printf(" 重新輸入序列請輸入4! \n");printf(" 選擇退出輸入5! \n");printf("************************************************\n");while(scanf("%d",&option)){if(option==5) //輸入5則退出程序{ break;}else if(option==4) //輸入4返回重新輸入內存頁數和頁面序列 { main(); break; } else if(option==3) //統計缺頁率，計算平均缺頁率 { missrate=0; //統計FIFO算法的缺頁率 for(i=0;i<f;i++) { printf("%f",FIFO[i]); missrate=missrate+FIFO[i]; } if(f==0) //FIFO[]中還沒有記錄時 { missrate=0; } else { missrate=missrate/f; } printf("FIFO算法的平均缺頁率是:%f\n\n",missrate); missrate=0; //統計LRU算法的缺頁率 for(i=0;i<l;i++) { missrate=missrate+LRU[i]; printf("%f",LRU[i]); } if(l==0) { missrate=0; } else { missrate=missrate/l; } printf("LRU算法的平均缺頁率是:%f\n\n\n",missrate); }//開始執行FIFO和LRU算法，兩個算法類似，所以用同一個函數，并進行控制區分elseif(option==1||option==2) { misspage=0; time=1; for(k=0;k<pagecount;k++) //初始化申請的內存 { p_age[k].pagenum=-1; p_age[k].pagetime=-1; } for(i=0;i<num;i++) //逐個調入頁面 { flag=0; for(k=0;k<pagecount;k++) //查找要調入的頁面是否已在內存 { if(p_age[k].pagenum==b[i]) { flag=1; //flag==1標記要讀入的頁面已在內存中 if(option==2) //如果是LRU算法,則更新頁面的訪問時間 { p_age[k].pagetime=time++; } for(j=0;j<pagecount;j++) //不缺頁時輸出內存中的頁面 {if(p_age[j].pagenum>=0) printf("%d",p_age[j].pagenum); } printf("\n"); } } if(flag==0) //要訪問的頁面不在內存中，產生缺頁 { mintime=p_age[0].pagetime; lable=0; for(k=1;k<pagecount;k++)//查找已在內存中且時間最小的頁面 { if(p_age[k].pagetime<mintime) { mintime=p_age[k].pagetime; lable=k; //label標記第一次找到的時間最小的頁面 } } p_age[lable].pagenum=b[i]; //將時間最小的頁面置換出 p_age[lable].pagetime=time++; //記錄進入時間 printf("第%d頁缺頁\n",i+1); misspage++; //缺頁數加1 } } missrate=float(misspage)/num; //計算缺頁率 if(option==1) //記錄FIFO算法的缺頁率 { FIFO[f]=missrate; f++; } elseif(option==2) //記錄LRU算法的缺頁率 { LRU[l]=missrate; l++; } printf("缺頁數是%d,缺頁率是%f\n",misspage,missrate); printf("\n\n\n"); }}}四、運行結果（含運行及測試結果和用戶使用說明書）1.運行結果1.1程序運行提示輸入1.2輸入1執行FIFO算法1.3輸入2執行LRU算法1.4輸入3統計缺頁率1.5輸入4重新輸入內存頁數和頁面序列1.6輸入5退出程序2.使用說明書 運行程序，在DOS界面中將顯示歡迎界面，提示輸入內存頁數和頁面序列的長度以及頁面序列；回車后出現選項提示：輸入1則執行FIFO算法,輸入2執行LRU算法,輸入3進行缺頁率統計并計算平均缺頁率，輸入4返回main()函數，重新執行程序，此時可以再次輸入內存頁數和頁面序列，輸入5的話則退出程序。五、課程設計小結與心得體會（不小于300字）（四號宋體） 本次課程設計主要可以分為兩個階段，一個算法的理解和設計，一個是程序的編制和算法的改進執行。第一個階段是要了解內存的分配策略、內存調頁策略以及FIFO和LRU算法的執行原理。程序中采用的分配策略是固定分配局部置換，即為進程分配一定書面的物理塊，在整個運行期間都不再改變，采用該策略時，如果進程在運行過程中發現缺頁，則只能從該進程在內存中的n個頁面中選出一個頁換出，然后再調入一個頁，以保證分配給該進程的內存空間不變。采用的調頁策略是請求調頁策略，他的原理是當進程在運行中需要訪問某部分程序和數據時，若發現其所在的頁面不在內存，便即提出請求，由OS將其所需頁面調入內存。這種策略每次僅調入一頁，故須花費較大的系統開銷，增加了磁盤I/O的啟用頻率。程序中的FIFO算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現簡單，但是算法