操作系統(tǒng)課程設(shè)計(jì)-內(nèi)存FIFO,LRU頁面置換算法設(shè)計(jì)

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