分頁系統(tǒng)模擬實驗

實踐教學蘭州理工大學計算機與通信學院2013年秋季學期操作系統(tǒng)原理課程設(shè)計題目：分頁系統(tǒng)模擬實驗專業(yè)班級:計算機科學與技術(shù)基地班姓名: 孫要全學號： 11240311指導(dǎo)教師： 王旭陽成績：______________^目錄TOC\o"1-5"\h\z前言 3摘要 41設(shè)計思想 5\o"CurrentDocument"2相關(guān)的各模塊的偽碼算法 6\o"CurrentDocument"3函數(shù)的調(diào)用關(guān)系圖 12\o"CurrentDocument"4調(diào)試結(jié)果 14總結(jié) 17\o"CurrentDocument"參考文獻 18致謝 18附件I源程序代碼 20分頁式虛擬存儲系統(tǒng)將作業(yè)信息的副本存放在磁盤中，不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，僅裝入立即使用的頁面，在執(zhí)行過程中訪問到不在主存的頁面時，產(chǎn)生缺頁中斷，再把它們動態(tài)地裝入。虛擬存儲的基本思想是基于程序的局部性原理，僅把目前需要的部分程序加載到內(nèi)存，其余暫時不用的程序及數(shù)據(jù)還保留在輔存中。在進程運行過程中，如果所要執(zhí)行的程序不在內(nèi)存，系統(tǒng)要將要執(zhí)行的程序段自動調(diào)入內(nèi)存。此時如果內(nèi)存已滿，則要通過置換操作將暫時不用的程序段先調(diào)出到輔存，然后將所需的程序段調(diào)入內(nèi)存，繼續(xù)執(zhí)行該進程。虛擬存儲器的引入，實際上是利用了存儲管理中邏輯地址空間和物理地址空間的關(guān)系，將計算機的內(nèi)存和輔存結(jié)合起來，使得用戶感覺具有大容量的內(nèi)存，虛擬內(nèi)存在將邏輯地址轉(zhuǎn)換成物理地址時，必須通過一個內(nèi)存管理單元MMU（MemoryManagementUnit）來完成。存儲管理一直是操作系統(tǒng)中的重要組成部分，因為馮?諾依曼體系結(jié)構(gòu)就是建立在存儲程序概念上的，訪問存儲器的操作占CPU時間的70%左右。計算機系統(tǒng)中的存儲器一般分為主存儲器（簡稱主存、內(nèi)存）和輔助存儲器（簡稱輔存）。由于CPU只能直接與內(nèi)存進行通信，因此計算機系統(tǒng)的程序以及與該程序相關(guān)的數(shù)據(jù)，只有被裝入到內(nèi)存中才能有效地執(zhí)行。計算機系統(tǒng)能否高效地管理內(nèi)存空間，不僅直接反映存儲器的利用率，還會影響整個操作系統(tǒng)的性能。摘要請求分頁虛擬存儲系統(tǒng)時間作業(yè)信息的副本存放在磁盤這一類輔助存儲器中當作業(yè)被調(diào)度投入運行時，并不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，而僅僅裝入立即使用的那些頁面，至少要將作業(yè)的第一頁信息裝入主存，在執(zhí)行過程中訪問到不在主存的頁面時，再把它們動態(tài)裝入。分頁式虛擬存儲管理是請求分頁，當需要執(zhí)行某條指令或使用某個數(shù)據(jù)，而發(fā)現(xiàn)它們不再主存時，產(chǎn)生一個缺頁中斷系統(tǒng)從輔存中把該指令或數(shù)據(jù)所在的頁面調(diào)入內(nèi)存。關(guān)鍵詞：分頁虛擬輔存缺頁中斷1設(shè)計思想1.1算法思想1)先進先出法(FirstInFirstOut)：該算法總是淘汰最先進入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。在該算法的模擬過程中，每當頁面需要被置換進入內(nèi)存時，最先進入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組0號單元，即最頂部，這時缺頁數(shù)加1；當不需要進行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時，不需要操作，繼續(xù)讀下一條指令。這樣就實現(xiàn)了總是淘汰最先進入內(nèi)存的頁面，選擇了在內(nèi)存中駐留時間最久的頁面予以淘汰。最近最久未使用(LeastRecentlyUsed)：該算法將過去最長一段時間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當頁面需要被置換進入內(nèi)存時，最先進入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組0號單元，即最頂部，這時缺頁數(shù)加1；當不需要進行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時，將要訪問的指令移到內(nèi)存頂部，其他指令依次向下移一位，這樣就把最久不用的指令沉到了底部，有必要時淘汰，即實現(xiàn)了總是淘汰最近最久未使用的指令。1.2.功能設(shè)計：(1)voidchangeaddr(structPagep[],intlogaddr)的功能實現(xiàn)模擬請求分頁虛擬存儲管理中的硬件地址變化過程。chushihua()函數(shù)的功能：先由Srand()和Rand()函數(shù)定義和隨機產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流存入地址流數(shù)組里。FIFO()的功能：實現(xiàn)FIFO算法，淘汰最先進入內(nèi)存的頁面并根據(jù)缺頁數(shù)算出命中率。LRU()的功能：實現(xiàn)LRU算法,淘汰最近最久未使用的頁面并根據(jù)缺頁數(shù)算出命中率。2相關(guān)的各模塊的偽碼算法2.1voidchangeaddr(structPagep[],intlogaddr)//地址變換logaddr比上64為頁面號碼記為jlogaddr對64取余為頁面號碼記為kfor{f(找到對應(yīng)的頁面號碼)f(在內(nèi)存中){物理地址=對應(yīng)頁面的主存號*64+k輸出物理地址輸出此頁面的對應(yīng)信息}}Else{coutvv"該頁不在主存，產(chǎn)生缺頁中斷"vvendl;}詳細設(shè)計如下：voidchangeaddr(structPagep[]，intlogaddr)//地址變換{intj=logaddr/64;〃對應(yīng)的塊號intk=logaddr%64;〃對應(yīng)的偏移量intflag=0;intaddr;for(inti=0;iv8;i++){if(p[i].pno==j)〃找到對應(yīng)的頁號if(p[i].flag=l)〃頁面標志為1{addr=p[i].cno*64+k;coutvv"物理地址為："vvaddrvvendl;coutvv"詳細信息："vv"\t頁面號："vvp[i].pnovv"\t主存號:"vvp[i].cnovv"\t偏移量："vvkvvendl;flag=1;break;}}}if(flag==0)coutvv"該頁不在主存，產(chǎn)生缺頁中斷"vvendl;}2.2voidchushihua()//初始化函數(shù){intt;srand(time(O));〃隨機產(chǎn)生指令序列p=12+rand()%32;coutvv"地址流序列："；coutvvendl;for(inti=0;ivp;i++){t=1+rand()%9;yemianliu[i]=t;〃將隨機產(chǎn)生的指令數(shù)存入頁面流}for(i=p-1;i>=0;i--){coutvvyemianliu[i]vv"";}coutvvendl;2.3FIFO算法實現(xiàn)時：如M=4時進入一個頁面時If(此頁面在內(nèi)存中)則fifo[32]不變else{For循環(huán)把fifo[k]=fifo[k-1];最后fifo[0]=yemianliu[e]}詳細設(shè)計如下：voidFIFO(intn)//FIFO算法，n是M的值{inti;intq=p;inte;intqueye=0;intflag;intfifo[32]={0};while(q--){flag=0;e=q;for(i=0;i<n;i++)if(fifo[i]==yemianliu[q]){flag=1;break;}if(flag==0){intm=n-1;intk=m;while(m--){fifo[k]=fifo[k-1];k--;}fifo[0]=yemianliu[e];queye++;}}coutvv"M="vvnvv"時FIFO的命中率為："<<(1-((double)queye/p))*100<<"%"<<" ";}2.4LRU算法實現(xiàn)時：如M=4時進入一個頁面時If(此頁面在內(nèi)存中)則flag=1，記錄位置kelseflag=0；if(flag=1)把k前面的依次后移一位，即：lru[k]=lru[k-1];最后lru[0]=yemianliu[e]}If(flag==0){For循環(huán){把lru[k]=fifo[k-1];}最后lru[0]=yemianliu[e]}詳細設(shè)計如下：voidLRU(intn)//LRU算法{inti;intq=p;inte;intqueye=0;intflag;intflag1;inty;intlru[32]={0};while(q--){flag=0;e=q;for(i=0;i<n;i++){if(lru[i]==yemianliu[q]){flag=1;flag1=i;break;}if(flag==0){intm=n-1;intk=m;while(m--){lru[k]=lru[k-1];k--;}lru[0]=yemianliu[e];queye++;}elseif(flag==1){y=flag1;while(y--){lru[flag1]=lru[flag1-1];flag1--;}lru[0]=yemianliu[e];}}coutvv"M="vvnvv"時LRU的命中率為："<<(1-((double)queye/p))*100<<"%"<<endl;}

3函數(shù)的調(diào)用關(guān)系圖1.FIFO()函數(shù)流程圖;2.2.LRU()函數(shù)流程圖:4調(diào)試結(jié)果請輸汎您的選擇訂蠶i函請輸汎您的選擇訂蠶i函歡迎使用分頁系統(tǒng)?！獔D4-1主菜單請輸入您的越擇訃過程模擬系統(tǒng)L 歡迎使用硬件地址霎檳過程模擬系統(tǒng) i.m 2.返回_工、 歡迎使用硬件地址變換過程橫擬系統(tǒng)請輸入您的選擇:圖4-2地址轉(zhuǎn)換菜單二二二歡迎使用分頁系塑礙|尊廳：：：：：：：：：：歡迎使用分頁系離健墨礬聖——請輸入您的選擇吃 :茨迎使用頁面置換模擬實驗養(yǎng)統(tǒng) 臨進入頁面晝換算法 冬返叵上-邇 -取迎使用頁面置換模規(guī)實驗索統(tǒng) 請輸入您的選擇：圖4-3頁面置換菜單1MUZ頁號禰記位斯存地址主存號01951110821119311310401550216021270213請輸入指俺的邏輯地址圖4-4頁面置換菜單廳岳寒嚴址111係細信息頁面號：1主存號詢偏移量:4?薯入您的選恥0襪記位G陽的邏輯眥存地咄:主存號95埔81191315212122131111主存,產(chǎn)生缺頁中斷圖4-5地址轉(zhuǎn)換請輸入扌靜的邏輯地址:11隊理地O=331詳細店息： 頁面號：0 主存號汚偏移量:11請輸入翌的謹擇普翌育鼻怎&估尿左+Ui+iL士左具圖4-6地址轉(zhuǎn)換圖4-7頁面置換圖4-9圖4-9頁面置換n=3時LRU的頁面置換詳情8484384938493849384138138513451845H=3時LRU的命中率為:15.3846Xn=4時LWJ的頁面置換詳情848438493844938S493384913841384S1384513S451H=4時LWJ的命中率為：38.4615X圖4-10頁面置換圖4-11頁面置換在兩周的課程設(shè)計中，我針對頁面模擬的有關(guān)資料進行了調(diào)查，分析。針對題目的要求我把任務(wù)先分成兩大模塊：一是地址轉(zhuǎn)換，二是頁面置換。地址轉(zhuǎn)換：輸入一個邏輯地址，求出此地址所在的頁面號碼以及偏移量。查表看其是否在表中，若在則有找到其內(nèi)存地址并由內(nèi)存地址和偏移量計算出物理地址，最后輸出其物理地址以及頁面信息。頁面置換我采用FIFO和LRU算法。首先隨即產(chǎn)生地址序列，然后在不同的M值下用FIFO算法和LRU算法。FIFO算法總是淘汰最先進入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。在該算法的模擬過程中，每當頁面需要被置換進入內(nèi)存時，最先進入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組0號單元，即最頂部，這時缺頁數(shù)加1；當不需要進行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時，不需要操作，繼續(xù)讀下一條指令。這樣就實現(xiàn)了總是淘汰最先進入內(nèi)存的頁面，選擇了在內(nèi)存中駐留時間最久的頁面予以淘汰。LRU算法將過去最長一段時間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當頁面需要被置換進入內(nèi)存時，最先進入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組0號單元，即最頂部，這時缺頁數(shù)加1；當不需要進行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時，將要訪問的指令移到內(nèi)存頂部，其他指令依次向下移一位，這樣就把最久不用的指令沉到了底部，有必要時淘汰，即實現(xiàn)了總是淘汰最近最久未使用的指令操作系統(tǒng)的發(fā)展是永無止境的，在前進的過程中必將有更多的知識需要我去學習與研究，并能將其應(yīng)用到實際的問題解決之中。由于分頁系統(tǒng)模擬的復(fù)雜以及自己能力的有限，在論述中不可能面面俱到，同時也由于我知識水平有限，文中的不足和錯誤在所難免，希望老師多多指點和更正。本課程設(shè)計是在指導(dǎo)教師王旭陽老師的指導(dǎo)下完成的，在此對老師表示感謝。參考文獻湯子瀛，哲鳳屏.《計算機操作系統(tǒng)》.西安電子科技大學學出版社.王清，李光明.《計算機操作系統(tǒng)》.冶金工業(yè)出版社.孫鐘秀等.操作系統(tǒng)教程.高等教育出版社曾明.Linux操作系統(tǒng)應(yīng)用教程.陜西科學技術(shù)出版社.張麗芬，劉利雄.《操作系統(tǒng)實驗教程》.清華大學出版社.孟靜，操作系統(tǒng)教程 原理和實例分析.高等教育出版社周長林，計算機操作系統(tǒng)教程.高等教育出版社張堯?qū)W，計算機操作系統(tǒng)教程，清華大學出版社任滿杰，操作系統(tǒng)原理實用教程，電子工業(yè)出版社致謝本次課程設(shè)計的順利完成離不開老師和同學們的幫助，在我遇到疑問的時候老師及時詳細的給我解答，讓我學到了很多。在此感謝操作系統(tǒng)王旭陽老師，您以往的基礎(chǔ)課程為我的這次課設(shè)打下了基礎(chǔ)。再次感謝操作系統(tǒng)課程設(shè)計指導(dǎo)老師王旭陽老師兩周來的辛勤指導(dǎo)，使我的這次課設(shè)能夠順利完成。感謝同學們幾天來的幫助，在他們無私的幫助下我的任務(wù)才能如此順利的完成。附件I源程序代碼#include<iostream>#include<process.h>#include<stdlib.h>#include<ctime>#include<cstdlib>usingnamespacestd;voidchushihua();〃初始化函數(shù)voidFIFO(intn);//FIFO算法，n是M的值voidLRU(intn);//LRU算法voidymzh();voidyemianzhihuan();voidchangeaddr(structPagep[],intlogaddr);voiddizhizhuanhuan();voidmenu();intyemianliu[32]={0};〃全局變量數(shù)組，地址流intp;structPage{intpno;//頁號intflag;//標志位intcno;//主存號intmodf;//修改位intaddr;//外存地址}Page;〃全局變量p是一共有多少地址流voidchushihua()〃初始化函數(shù){intt;srand(time(O));〃隨機產(chǎn)生指令序列p=12+rand()%32;coutvv"地址流序列："；cout<<endl;for(inti=0;i<p;i++){t=1+rand()%9;yemianliu[i]=t;〃將隨機產(chǎn)生的指令數(shù)存入頁面流}for(i=p-1;i>=0;i--){cout<<yemianliu[i]<<"";}cout<<endl;}voidFIFO(intn)//FIFO算法，n是M的值{coutvv"M="vvnvv"時FIFO的頁面置換詳情"；cout<<endl;inti;intj;intq=p;inte;intqueye=0;intflag;intfifo[32]={0};while(q--){flag=0;e=q;for(i=0;i<n;i++){if(fifo[i]==yemianliu[q]){flag=1;for(j=0;j<n&&fifo[j]!=0;j++)cout<<fifo[j];cout<<endl;break;}}if(flag==0){intm=n-1;intk=m;while(m--){fifo[k]=fifo[k-1];k--;}fifo[0]=yemianliu[e];for(j=0;j<n&&fifo[j]!=0;j++)cout<<fifo[j];cout<<endl;queye++;命中率為命中率為cout<<"M="<<n<<"時FIFO的"<<(1-((double)queye/p))*100<<"%"<<"";cout<<endl;cout<<endl;}voidLRU(intn)//LRU算法{coutvv"M="vvnvv"時LRU的頁面置換詳情";cout<<endl;inti;intj;intq=p;inte;intqueye=0;intflag;intflag1;inty;intlru[32]={0};while(q--){flag=0;e=q;for(i=0;i<n;i++){if(lru[i]==yemianliu[q]){flag=1;flag1=i;}if(flag==0){intm=n-1;intk=m;while(m--){lru[k]=lru[k-1];k--;}lru[0]=yemianliu[e];for(j=0;j<n&&lru[j]!=0;j++)cout<<lru[j];cout<<endl;queye++;}elseif(flag==1){y=flag1;while(y--){lru[flag1]=lru[flag1-1];flag1--;}lru[0]=yemianliu[e];for(j=0;j<n&&lru[j]!=0;j++)cout<<lru[j];cout<<endl;}cout<<"M="<<n<<"時LRU的命中率為"<<(1-((double)queye/p))*100<<"%"<<endl<<endl;}voidymzh(){chushihua();for(inti=3;i<5;i++){FIFO(i);LRU(i);}yemianzhihuan();}voidyemianzhihuan(){inta;cout<<" 歡迎使用頁面置換模擬實驗系統(tǒng) "<<endl;coutvv" \t\tl.進入頁面置換算法\t\t "vvendl;coutvv" \t\t2.返回上一級\t\t "vvendl;coutvv" 歡迎使用頁面置換模擬實驗系統(tǒng) "vvendl;coutvvendlvv"請輸入您的選擇:"；cin>>a;switch(a){casel:ymzh();case2:menu();break;default:coutvv"輸入有誤，請重新輸入！"vvendl;break;}}voidchangeaddr(structPagep[],intlogaddr){〃地址變換intj=logaddr/64;〃對應(yīng)的塊號intk=logaddr%64;〃對應(yīng)的偏移量intflag=0;intaddr;for(inti=0;iv8;i++){if(p[i].pno==j)〃找到對應(yīng)的頁號{if(p[i].flag=l)〃頁面標志為1{addr=p[i].cno*64+k;coutvv"物理地址為："vvaddivvendl;coutvv"詳細信息："vv"\t頁面號："vvp[i].pnovv"\t主存號:"vvp[i].cnovv"\t偏移量："vvkvvendl;flag=1;break;}if(flag==0)coutvv"該頁不在主存，產(chǎn)生缺頁中斷"vvendl;}voiddizhizhuanhuan(){inta;intins;//指令邏輯地址structPagep[8];p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011;p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012;p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013;p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015;p[4].p