《操作系統(tǒng)》實驗五：頁面置換算法模擬

1、 實驗五. 請求頁式存儲管理的模擬實驗內(nèi)容:熟悉虛擬存儲管理的各種頁面置換算法，并編寫模擬程序?qū)崿F(xiàn)請求頁式存儲管理的頁面置換算法-最近最久未使用算法（LRU），要求在每次產(chǎn)生置換時顯示頁面分配狀態(tài)和缺頁率。實驗要求：1、運行給出的實驗程序，查看執(zhí)行情況，進而分析算法的執(zhí)行過程，在理解FIFO頁面置換算法和最近最久未使用算法（LRU）置換算法后，給出最佳置換算法的模擬程序?qū)崿F(xiàn)，并集成到參考程序中。2、執(zhí)行2個頁面置換模擬程序，分析缺頁率的情況。最好頁框數(shù)和訪問序列長度可調(diào)節(jié)，在使用同一組訪問序列數(shù)據(jù)的情況下，改變頁框數(shù)并執(zhí)行2個頁面置換模擬程序，查看缺頁率的變化。3、在每次產(chǎn)生置換時要求顯示分配

2、狀態(tài)和缺頁率。程序的地址訪問序列通過隨機數(shù)產(chǎn)生，要求具有足夠的長度。最好頁框數(shù)和訪問序列長度可調(diào)節(jié)。實驗的執(zhí)行結(jié)果如下圖所示（左下圖為FIFO執(zhí)行結(jié)果，右下圖為LRU執(zhí)行結(jié)果）： 程序源代碼：#include #include windows.h#include #include #include #include #include #include void initialize(); /初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)void createps(); /隨機生成訪問序列void displayinfo(); /顯示當前狀態(tài)及缺頁情況void fifo(); /先進先出算法int findpage();

3、/查找頁面是否在內(nèi)存void lru(); /最近最久未使用算法int invalidcount = 0; / 缺頁次數(shù)int vpoint; /頁面訪問指針int pageframe10; / 分配的頁框int pagehistory10; /記錄頁框中數(shù)據(jù)的訪問歷史int rpoint; /頁面替換指針int inpflag; /缺頁標志，0為不缺頁，1為缺頁struct PageInfo /頁面信息結(jié)構(gòu) int serial100; / 模擬的最大訪問頁面數(shù)，實際控制在20以上 int flag; / 標志位，0表示無頁面訪問數(shù)據(jù) int diseffect; / 缺頁次數(shù) int to

4、tal_pf; / 分配的頁框數(shù) int total_pn; / 訪問頁面序列長度 pf_info;/初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)void initialize() int i,pf;inpflag=0; /缺頁標志，0為不缺頁，1為缺頁pf_info.diseffect =0; / 缺頁次數(shù)pf_info.flag =0; / 標志位，0表示無頁面訪問數(shù)據(jù)printf(n請輸入要分配的頁框數(shù)：); / 自定義分配的頁框數(shù) scanf(%d,&pf);pf_info.total_pf =pf; for(i=0;i100;i+) / 清空頁面序列 pf_info.seriali=-1; / 隨機生成訪問序

5、列void createps(void )int s,i,pn; initialize(); /初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)printf(n請輸入要隨機生成訪問序列的長度：); /自定義隨機生成訪問序列的長度 scanf(%d,&pn); srand(rand(); /初始化隨機數(shù)隊列的種子s=(float) rand() / 32767) * 50 + pn; / 隨機產(chǎn)生頁面序列長度pf_info.total_pn = s;for(i=0;is;i+) /產(chǎn)生隨機訪問序列 pf_info.seriali=(float) rand() / 32767) * 16 ; /隨機數(shù)的大小在0-15之間 /

6、顯示當前狀態(tài)及缺頁情況void displayinfo(void) int i,n; if(vpoint=0) printf(n=頁面訪問序列=n); for(i=0; ipf_info.total_pn; i+) printf(%4d,pf_info.seriali); if (i+1) % 10 =0) printf(n); /每行顯示10個 printf(n=n); printf(訪問%3d : 內(nèi)存,pf_info.serialvpoint); for(n=0;n=0) printf(%3d,pageframen); else printf( ); printf( ); if(inpf

7、lag=1) /缺頁標志，0為不缺頁，1為缺頁 printf( =缺頁 ); printf(缺頁率%3.1f,(float)(pf_info.diseffect)*100.00/vpoint); printf(n); / 查找頁面是否在內(nèi)存，1為在內(nèi)存，0為不在即缺頁int findpage(int page) int n; for(n=0;npf_info.total_pf;n+) pagehistoryn +; / 訪問歷史加1for(n=0;npf_info.total_pf;n+) if (pageframen=page ) inpflag=0 ; /inpflag缺頁標志，0為不缺頁

8、，1為缺頁 pagehistoryn=0; /置訪問歷史為0 return 1; inpflag=1; /頁面不存在，缺頁 return 0; / FIFO頁面置換算法void fifo(void) int n,count,pstate; rpoint=0; / 頁面替換指針初始化為0 invalidcount = 0; / 缺頁數(shù)初始化為0 createps(); / 隨機生成訪問序列 count=0; / 是否裝滿是所有的頁框 for(n=0;npf_info.total_pf;n+) / 清除頁框信息 pageframen=-1; inpflag=0; /缺頁標志，0為不缺頁，1為缺頁

9、for(vpoint=0;vpointpf_info.total_pn;vpoint+) / 執(zhí)行算法 pstate=findpage(pf_info.serialvpoint); /查找頁面是否在內(nèi)存 if(countpf_info.total_pf) / 開始時不計算缺頁 if(pstate=0) / 頁不存在則裝入頁面 pageframerpoint=pf_info.serialvpoint;rpoint=(rpoint+1) % pf_info.total_pf;count+; else / 正常缺頁置換 if(pstate=0) / 頁不存在則置換頁面 pageframerpoint

10、=pf_info.serialvpoint;rpoint=(rpoint+1) % pf_info.total_pf;pf_info.diseffect+; / 缺頁次數(shù)加1 Sleep(10); displayinfo(); / 顯示當前狀態(tài) / 置換算法循環(huán)結(jié)束 getch(); return;/ LRU頁面置換算法void lru(void) int n,count,pstate,max; rpoint=0; / 頁面替換指針 invalidcount = 0; / 缺頁次數(shù)初始化為0 createps(); / 隨機生成訪問序列 count=0; / 是否裝滿所有的頁框 for(n=0

11、;npf_info.total_pf;n+) pageframen=-1; / 清除頁框信息 pagehistoryn=0; / 清除頁框歷史 inpflag=0; /缺頁標志，0為不缺頁，1為缺頁 for(vpoint=0;vpointpf_info.total_pn;vpoint+) / 執(zhí)行算法 pstate=findpage(pf_info.serialvpoint); /查找頁面是否在內(nèi)存 if(countpf_info.total_pf) / 開始時不計算缺頁 if(pstate=0) / 頁不存在則裝入頁面 pageframerpoint=pf_info.serialvpoint

12、; /把要調(diào)入的頁面放入一個空的頁框里rpoint=(rpoint+1) % pf_info.total_pf;count+; else / 正常缺頁置換 if(pstate=0)/ 頁不存在則置換頁面 max=0; for(n=1;npagehistorymax) max=n; rpoint=max; pageframerpoint=pf_info.serialvpoint; pagehistoryrpoint=0; pf_info.diseffect+; / 缺頁次數(shù)加1 Sleep(10); displayinfo(); / 顯示當前狀態(tài) / 置換算法循環(huán)結(jié)束 _getch(); ret

13、urn; /最佳置換算法 自己完成/ 主函數(shù)int main() char ch; system(cls) ; while ( true ) printf(*n); printf( 若要執(zhí)行FIFO頁面置算法請按1n);printf( 若要執(zhí)行LRU 頁面置算法請按2n); printf( 若要退出請按3n) ; printf(*n); printf( Enter your choice (1 or 2 or 3): ); do /如果輸入信息不正確，繼續(xù)輸入 ch = (char)getch() ;while(ch != 1 & ch != 2& ch != 3); printf(nn你按的是：%c ,現(xiàn)在為你執(zhí)行