操作系統(tǒng)原理課程設(shè)計模擬存儲器管理

1、上海電力學(xué)院課程設(shè)計報告課程名稱： 操作系統(tǒng)原理 題目名稱： 模擬存儲器管理 姓 名：  學(xué) 號： 班 級： 同 組 姓 名： 實驗時間： 11.12.2912.01.5 成 績：   評 語： 目錄目錄.21、 設(shè)計內(nèi)容及要求.32、 詳細(xì)設(shè)計.32.1原理概述.32.2主要數(shù)據(jù)結(jié)構(gòu).32.3算法流程圖.42.3.1主程序算法流程圖.42.3.2 optimal算法流程圖.52.3.3 fifo算法流程圖.62.3.4 lru算法流程圖.73、 實驗結(jié)果與分析.83.1 optimal頁面置換算法結(jié)果與分析.83.2 fifo 頁面置換算法結(jié)果與分析.

2、93.3 lru 頁面置換算法結(jié)果與分析.93.4 推出界面結(jié)果.114、 設(shè)計總結(jié).11附錄.12課程設(shè)計題目:模擬存儲器管理一、設(shè)計內(nèi)容及要求編寫程序模擬虛擬存儲器管理。假設(shè)為m頁的作業(yè)分配了n塊內(nèi)存（n<m）。輸入：系統(tǒng)分配的塊數(shù)，頁面引用序列。輸出：顯示每一次頁面引用內(nèi)存狀態(tài)。分別使用下面的頁面置換算法：（1）fifo頁面置換算法：（2）lru頁面置換算法：（3）最佳頁面置換算法：錢萬里負(fù)責(zé)構(gòu)思 葉陽偉 負(fù)責(zé)編寫二、詳細(xì)設(shè)計1）原理概述用一個數(shù)組page_table存儲就緒頁面隊列的序號和所在物理塊號，用另一個數(shù)組memory_table存儲物理塊中頁面序號和該物理塊被使用情況輸

3、出-1表示該物理塊未被暫用。2） 主要數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)體：page結(jié)構(gòu)體存儲就緒隊列頁面的相關(guān)情況struct pageint page_num;/頁號int memory_num;/所在物理塊號int p;/狀態(tài)位 0表示不在內(nèi)存物理塊中 1表示在物理塊中;memory結(jié)構(gòu)體用來構(gòu)造物理塊的相關(guān)使用情況struct memoryint memory_page_num;/物理塊中此刻存在的頁面序號int page_n;/頁面執(zhí)行順序號int a;/訪問字段;相關(guān)參數(shù)：page_size用來限定頁面就緒隊列數(shù)由用戶鍵入，memory_size表示分配的物理塊數(shù)由用戶鍵入page_table500 存

4、儲就緒隊列，限定該隊列最多為500，500可以修改memory_table100表示總共物理塊數(shù)及每個物理塊的使用情況，可用物理塊為100，可以修改其大小3） 算法（流程圖）主程序流程圖：optimal算法流程圖：fifo算法流程圖lru算法流程圖：源程序文件名：虛擬存儲器管理.cpp 執(zhí)行文件名:虛擬存儲器管理.exe3、 實驗結(jié)果與分析1. 當(dāng)輸入t=1時選擇 optimal頁面置換算法所謂的最佳頁面置換算法就是 其選擇的被淘汰頁面將是以后永不使用，或許是在最長時間內(nèi)不再被訪問的頁面。采用最佳頁面置換通?？杀ＷC獲得最低的缺頁率?，F(xiàn)假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串

5、：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1用最佳頁面置換算法就會得到下列物理塊使用情況：頁面號引用串70120304230321201701物理塊使用情況777222227000040001133311前三個7 0 1可以直接進(jìn)入內(nèi)存，由于7是未來最長時間不被使用的，所以把7換成2，得到2 0 1序列。由于0 已經(jīng)在內(nèi)存中，所以不需要替換，1是未來最長時間不被使用的，所以把1換成3，得到2 0 3序列由于0在內(nèi)存中則無需替換，又由于0是未來最長時間不被使用的所以把0替換成4，得到2 4 3序列。又由于2、3已在內(nèi)存中，所以不要替換。由于4在以后不被使用，所

6、以用0 代換4.得到2 0 3序列。又由于3、2已在內(nèi)存中，所以不需要替換。又由于3在以后不被使用，所以把3替換成1.，得到2 0 1序列。又由于2、0、1已在內(nèi)存中，所以無需替換。又由于2在以后不被使用，所以把2替換成7，得到7 0 1序列。又由于0、1已在內(nèi)存中，所以不需替換。實驗結(jié)果與預(yù)想相同。2、當(dāng)輸入2選擇fifo頁面置換函數(shù)所謂先進(jìn)先出頁面置換算法，就是總是淘汰最先進(jìn)入內(nèi)存的頁面。假定系統(tǒng)為莫進(jìn)程分配了三個物理塊，并考慮有以下的頁面號引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1經(jīng)fifo函數(shù)預(yù)算后將得到下列關(guān)系：頁面號引用串70120304

7、230321201701物理塊使用情況777222444000777000333222111001110003332221前三個7 0 1 可以直接進(jìn)入內(nèi)存，由于7最先進(jìn)入內(nèi)存，則將7換成2，得到 2 0 1。由于0在內(nèi)存中，則無需置換。由于0最先進(jìn)入內(nèi)存，則把0替換成3得到2 3 1.由于1最先進(jìn)入內(nèi)存，則把1換成0得到2 3 0.由于2最先進(jìn)入內(nèi)存，則把2換成4，得到4 3 0.由于3最先進(jìn)入內(nèi)存，則把3換成2.得到4 2 0。由于0最先進(jìn)入內(nèi)存，則把0換成3，得到4 2 3.由于4最先進(jìn)入內(nèi)存，則把4換成0，得到0 2 3.由于2 3 已在內(nèi)存中，則無需置換。由于2最先進(jìn)入內(nèi)存，則把2換

8、成1得到0 1 3.由于3最先進(jìn)入內(nèi)存，則把3換成2，得到0 1 2。由于0已在內(nèi)存，則無需置換。由于0最先進(jìn)入內(nèi)存，則把0換成7，得到7 1 2.由于1最先進(jìn)入內(nèi)存，則把1換成0，得到7 0 2.由于2最先進(jìn)入內(nèi)存，則把2換成1，得到7 0 1.實驗結(jié)果與預(yù)想結(jié)果一樣；3、 輸入3進(jìn)入lru頁面置換算法 所謂的最近最久為使用頁面置換算法（lru）是選擇最近最久未使用的頁面予以淘汰。該算法富裕每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當(dāng)須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰； 現(xiàn)假定系統(tǒng)為某進(jìn)程分配了三個物理塊，并考慮有以下的頁

9、面號引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1經(jīng)最近最久未使用頁面置換算法得到下列信息： 頁面號引用串70120304230321201701物理塊使用情況777224440111000000333001133222227 前三個7 0 1可以直接 進(jìn)入內(nèi)存，由于7最近最久未使用，則把7換成2得到2 0 1.由于0已在內(nèi)存中，則無需置換。由于1最近醉酒未使用，則把1換成3得到2 0 3.由于0已在內(nèi)存中，則無需置換。由于2最近最久未使用，則把2換成4得到4 0 3。由于3最近最久未使用，則把3換成2，得到4 0 2.由于0最近最久未使用，則把0換成3

10、得到4 3 2 。由于4最近最久未使用，則把4換成0，得到0 3 2，由于3 2已在內(nèi)存，則無需置換。由于0最近最久未使用，則把0換成1，得到1 3 2.由于2已在內(nèi)存中，則無需置換。由于3最近最久未使用，則把3換成0得到1 0 2。由于1已在內(nèi)存中，則無需置換。由于2最近最久未使用，則把2換成7得到1 0 7.由于0 1已在內(nèi)存中，則無需置換。實驗結(jié)果與預(yù)想結(jié)果相同。假如有以下頁面號引用序列：4 7 0 7 1 0 1 2 1 2 6經(jīng)lru算法運(yùn)算之后得出以下結(jié)果：頁面號引用串47071012126物理塊使用情況444444444467777777777000000000111111122

11、22由于前五個序列中有重復(fù)的頁面號，則不能直接全部調(diào)用，先調(diào)入前三個4 7 0 ，則后一個7已在內(nèi)存中，無需置換，然后1進(jìn)來，0也在內(nèi)存中，則無需置換，下個1也在內(nèi)存中則無需置換，然后2進(jìn)如內(nèi)存，后面的1 2也都在內(nèi)存中，所以無需置換，6不在內(nèi)存中而且物理塊全部被暫用，就要考慮置換了，由于4是最近最久未使用使用，則把4換成6得到6 7 0 1 2。4、選擇功能0則進(jìn)入推出界面4、 設(shè)計總結(jié)通過本次課程設(shè)計，我學(xué)到不少東西。比如解決多重循環(huán)跳出問題，以前沒敢用goto語句，因為大家都說它不太好，破壞了程序的結(jié)構(gòu)。不過有時候用起來還蠻方便的，便于編寫，也便于理解。這是我這次收獲的最大的好處。不過在

12、編寫程序的時候也遇到很多問題：1、 optimal算法：首先對這個算法的理解，一開始覺得這個算法真的蠻好的，不過實現(xiàn)起來還真像書上所說的有點難度，如果下一個要執(zhí)行的頁面已在內(nèi)存中則無需置換，但如果不在內(nèi)存中，就要考慮到置換了。我先是用memory .page_n記錄內(nèi)存中的頁面在以后出現(xiàn)的時間，然后用men記錄他們中的最大時間，然后這個最大時間就是說在未來最近一段時間不會被使用，然后我就用下一個頁面序號替換內(nèi)存中的在以后最長時間不被使用的頁面。2、 fifo算法：這個算法是最容易實現(xiàn)的，思路很簡單。就是逐個替換內(nèi)存塊中頁面，以實現(xiàn)先進(jìn)先出的功能。如果下一個要執(zhí)行的頁面已在內(nèi)存中，則無需置換，如

13、果不在內(nèi)存中，則要考慮置換了。我用m標(biāo)記將要唄置換的物理塊序號，該物理塊被替換后，m+1，這樣下一次替換的就是下一個物理塊，就這樣，先進(jìn)來的總是先出去。3、 lru算法lru算法，我感覺也蠻有意思的，我一開始想到的是把進(jìn)入內(nèi)存的頁面都標(biāo)記為1，出內(nèi)存的和不在內(nèi)存的我都標(biāo)記為0，然后下一次需要替換的時候，我就從前往后查找為1 的頁面，首先找到的肯定是最近最久未使用的，然后把下一個要執(zhí)行的頁面與此頁面做置換。然后我又想到了一個方法，就是每執(zhí)行一次頁面，就給每個頁面memory .a+1,再用maxcount標(biāo)記出a最大的物理塊，a值越大說明該頁面在物理塊中呆的時間越長，第一次是把第一塊物理塊的-1

14、換成等待頁面序列的第一個，然后memory0.a置0，這樣maxcount標(biāo)記的就變成第二塊物理塊了，然后以此類推，每個物理塊將被逐個置換。總之，通過這次課程設(shè)計，我是學(xué)到了很多東西，不僅僅是編程能力提高了，分析問題的能力也有所提高，我會再接再厲。附錄：程序源代碼/ 本程序內(nèi)容是關(guān)于 頁面置換算法的模擬 / 包含 最佳頁面置換算法(optimal) / 先進(jìn)先出頁面置換算法(fifo) / / 最近最久未使用頁面置換算法(lru) /#include<iostream>using namespace std;struct pageint page_num;/頁號int memory

15、_num;/所在物理塊號int p;/狀態(tài)位 0表示不在內(nèi)存物理塊中 1表示在物理塊中;struct memoryint memory_page_num;/物理塊中此刻存在的頁面序號int page_n;/頁面執(zhí)行順序號int a;/訪問字段;int page_size,memory_size;/頁面大小 物理塊大小page page_table500;/存儲頁面memory memory_table100;void reset()/頁面 物理塊初始化cout<<"請輸入頁面大小:"cin>>page_size;for(int i=0;i<pa

16、ge_size;i+)page_tablei.page_num=-1;page_tablei.memory_num=-1;page_tablei.p=0;/for(int i=0;i<page_size;i+)cout<<"請輸入物理塊數(shù):"cin>>memory_size;for(int j=0;j<memory_size;j+)memory_tablej.memory_page_num=-1;memory_tablej.page_n=-1;memory_tablej.a=0;/for(int j=0;j<memory_size;

17、j+)/void reset()void creat()/創(chuàng)建頁面和內(nèi)存分塊cout<<"請輸入需訪問的頁面序號:"for(int i=0;i<page_size;i+)cin>>page_tablei.page_num;/for(int i=0;i<page_size;i+)/void creat()/ optimal最佳置換算法 /void optimal()int mem=0;/記錄等待隊列中與內(nèi)存中序號相同的隊列號int num=0;/頁面號計數(shù)器for(int i=0;i<memory_size;i+)/前幾個未重復(fù)的可直

18、接送入內(nèi)存for(int v=0;v<memory_size;v+)if(page_tablenum.page_num=memory_tablev.memory_page_num)num+;if(num>=page_size)goto begin;/if(page_tablenum.page_num=memory_tablev.memory_page_num)/for(int v=0;v<memory_size;v+)memory_tablei.memory_page_num=page_tablenum.page_num;memory_tablei.page_n=num;pa

19、ge_tablenum.p=1;num+;/cout<<"此時在內(nèi)存中的頁面序號是:"<<endl;for(int j=0;j<memory_size;j+)cout<<memory_tablej.memory_page_num<<" "cout<<endl; /for(int i=0;i<memory_size;i+)begin:while(num<page_size)/如果下一個需要操作的頁面在內(nèi)存中則無需更換for(int m=0;m<memory_size;m+)

20、if(page_tablenum.page_num=memory_tablem.memory_page_num)num+=1;goto begin;/if(page_tablenum.page_num=memory_tablem.memory_page_num)/for(int m=0;m<memory_size;m+)/如果下一個等待頁面不在內(nèi)存中則根據(jù)最佳置換準(zhǔn)則進(jìn)行對換int q=0;loopp:for(;q<memory_size;)for(int h=num;h<page_size;h+)if(memory_tableq.memory_page_num=page_t

21、ableh.page_num)/找出內(nèi)存中頁面在等待序列中需等待的時間最長的序號if(h>mem)mem=h;/記錄與當(dāng)前內(nèi)存頁面號相等的 在等待序列中第一次出現(xiàn)的等待隊列序號memory_tableq.a=1;/如果在等待序列中找到與內(nèi)存中相等的頁面序號 則給該物理塊做標(biāo)記q+;goto loopp;/if(memory_tableq.memory_page_num=page_tableh.page_num)if(h=page_size-1)&&(page_tableh.page_num!=memory_tableq.memory_page_num)/如果內(nèi)存中此頁面在

22、以后不再出現(xiàn)則直接替換掉memory_tableq.memory_page_num=page_tablenum.page_num;num+=1;for(int l=0;l<memory_size;l+)cout<<memory_tablel.memory_page_num<<" "cout<<endl;page_tablenum.memory_num=0;goto begin;/if(h=page_size-1)&&(page_tableh.page_num!=memory_tableq.memory_page_nu

23、m)/for(int h=num;h<page_size;h+)/for(;q<memory_size;)for(int g=0;g<memory_size;g+)if(memory_tableg.memory_page_num=page_tablemem.page_num)memory_tableg.memory_page_num=page_tablenum.page_num;mem=0;num+=1;for(int l=0;l<memory_size;l+)cout<<memory_tablel.memory_page_num<<"

24、 "cout<<endl;page_tablenum.memory_num=0;/if(memory_tableg.memory_page_num=page_tablemem.page_num)/for(int g=0;g<memory_size;g+)for(int gg=0;gg<memory_size;gg+)memory_tablegg.a=0;/while(num<page_size)/void optimal()/ 先進(jìn)先出頁面置換算法 /void fifo()int num=0;/頁面計數(shù)器int m=0;/物理塊計數(shù)器int aa=0;f

25、or(int i=0;i<memory_size;i+) for(int v=0;v<memory_size;v+) if(page_tablenum.page_num=memory_tablev.memory_page_num) num+; if(num>=page_size) goto begin; /if(page_tablenum.page_num=memory_tablev.memory_page_num) /for(int v=0;v<memory_size;v+) memory_tablei.memory_page_num=page_tablenum.pa

26、ge_num; memory_tablei.page_n=num; page_tablenum.p=1; num+; /cout<<"此時在內(nèi)存中的頁面序號是:"<<endl; for(int j=0;j<memory_size;j+) cout<<memory_tablej.memory_page_num<<" " cout<<endl; /for(int i=0;i<memory_size;i+)begin:while(num<page_size)for(int k=0;k

27、<memory_size;k+)if(page_tablenum.page_num=memory_tablek.memory_page_num)num+;goto begin;/if(page_tablenum.page_num=memory_tablek.memory_page_num)/for(int k=0;k<memory_size;k+)/如果下一個頁面不在內(nèi)存中，則按照先進(jìn)先出頁面置換方法進(jìn)行下列操作memory_tablem.memory_page_num=page_tablenum.page_num;num+;m+;m=m%memory_size;for(int l

28、=0;l<memory_size;l+)cout<<memory_tablel.memory_page_num<<" "cout<<endl;/while(num<page_size)/void fifo()/ lru頁面置換算法 /void lru()int num=0;for(int i=0;i<memory_size;i+)for(int v=0;v<memory_size;v+)if(page_tablenum.page_num=memory_tablev.memory_page_num)num+;if(n

29、um>=page_size)goto begin;/if(page_tablenum.page_num=memory_tablev.memory_page_num)/for(int v=0;v<memory_size;v+)memory_tablei.memory_page_num=page_tablenum.page_num;memory_tablei.page_n=num;page_tablenum.p=1;num+;/cout<<"此時在內(nèi)存中的頁面序號是:"<<endl;for(int j=0;j<memory_size;j

30、+)cout<<memory_tablej.memory_page_num<<" "cout<<endl; /for(int i=0;i<memory_size;i+)begin: while(num<page_size) /cout<<"如果下一個要執(zhí)行的頁面已經(jīng)在內(nèi)存中則無需進(jìn)行頁面置換"<<endl;for(int k=0;k<memory_size;k+)if(page_tablenum.page_num=memory_tablek.memory_page_num)pa

31、ge_tablememory_tablek.page_n.p=0;memory_tablek.page_n=num;page_tablenum.p=1;num+;goto begin;/if(page_tablenum.page_num=memory_tablek.memory_page_num)continue;/for(int k=0;k<memory_size;k+)/如果下一個要執(zhí)行的頁面不在內(nèi)存中 則根據(jù)lru算法執(zhí)行下列代碼for(int l=0;l<page_size;l+)for(int a=0;a<memory_size;a+)if(page_tablel.

32、page_num=memory_tablea.memory_page_num)&&(page_tablel.p=1)page_tablememory_tablea.page_n.p=0;memory_tablea.memory_page_num=page_tablenum.page_num;memory_tablea.page_n=num;page_tablenum.p=1;num+;/cout<<"此時在內(nèi)存中的頁面序號為:"<<endl;for(int b=0;b<memory_size;b+)cout<<memory_tableb.memory_page_num<<" "cout<<endl;goto begin;/if(page_tablel.page_num=memory_tablea.memory_page_num)&&(page_tablel.p=1)continue;/for(int a=0;a<memory_size;a+)/f