課程設(shè)計--請求頁式存儲器管理

1、<p><b>　　課程設(shè)計說明書</b></p><p>　　題目: 請求頁式存儲器管理程序 </p><p>　　院 系： 計算機科學(xué)與工程學(xué)院 </p><p>　　專業(yè)班級： 計算機09-15班 </p><p>　　學(xué) 號： <

2、;/p><p>　　學(xué)生姓名： 某某某 </p><p>　　指導(dǎo)教師： 某 某 </p><p>　　2011年 12 月 18日 </p><p>　　課程設(shè)計（論文）任務(wù)書</p><p>　　2011年 10月 22日</p><p&

3、gt;<b>　　摘 要</b></p><p>　　分頁存儲管理，是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中</p><p>　　系統(tǒng)為每個進程建立一個

4、頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系。一個頁表中包含若干個表目，表目的自然序號對應(yīng)于用戶程序中的頁號，表目中的塊號是該頁對應(yīng)的物理塊號。</p><p>　　請求頁式存儲管理方式是一種實現(xiàn)虛擬存儲器的方式，是指在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面。當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。<

5、;/p><p>　　請求頁式存儲管理主要需要解決以下問題：系統(tǒng)如何獲知進程當(dāng)前所需頁面不在主存；當(dāng)發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入主存；當(dāng)主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據(jù)什么頁面淘汰算法選擇欲淘汰的頁面。</p><p>　　關(guān)鍵詞：虛擬存儲器 資源 缺頁 頁面淘汰算法</p><p><b>　　目 錄</b&g

6、t;</p><p><b>　　1 系統(tǒng)分析1</b></p><p><b>　　1.1設(shè)計內(nèi)容1</b></p><p>　　1.2 設(shè)計要求1</p><p><b>　　2 系統(tǒng)設(shè)計2</b></p><p>　　2.1 問題分析2&

7、lt;/p><p>　　2.2 算法與程序流程圖2</p><p><b>　　3 系統(tǒng)實現(xiàn)4</b></p><p><b>　　3.1數(shù)據(jù)結(jié)構(gòu)4</b></p><p><b>　　3.2函數(shù)聲明4</b></p><p><b>　　

8、3.3運行結(jié)果4</b></p><p><b>　　4 總結(jié)6</b></p><p><b>　　參考文獻7</b></p><p><b>　　附錄8</b></p><p><b>　　1 系統(tǒng)分析</b></p>

9、<p><b>　　1.1 設(shè)計內(nèi)容</b></p><p>　　設(shè)計一個請求頁式存儲管理方案，為簡單起見。頁面淘汰算法采用 FIFO頁面淘汰算法，并且在淘汰一頁時，只將該頁在頁表中修改狀態(tài)位。而不再判斷它是否被改寫過，也不將它寫回到輔存。</p><p><b>　　1.2 設(shè)計要求</b></p><p>

10、　　(1). 運行給出的實驗程序，查看執(zhí)行情況，進而分析算法的執(zhí)行過程，在理解FIFO頁面置換算法后，模擬程序?qū)崿F(xiàn)，并集成到參考程序中。</p><p>　　(2). 執(zhí)行頁面置換模擬程序，分析缺頁率的情況。最好頁框數(shù)和訪問序列長度可調(diào)</p><p>　　節(jié)，在使用同一組訪問序列數(shù)據(jù)的情況下，改變頁框數(shù)并執(zhí)行頁面置換模擬程序，查看缺頁率的變化。</p><p>　

11、　(3). 在每次產(chǎn)生置換時要求顯示分配狀態(tài)和缺頁率。程序的地址訪問序列通過隨機數(shù)產(chǎn)生，要求具有足夠的長度。最好頁框數(shù)和訪問序列長度可調(diào)節(jié)。</p><p>　　(4). 每個學(xué)生必須獨立完成課程設(shè)計，不能相互抄襲；</p><p>　　(5).設(shè)計完成后，將所完成的工作交由老師檢查；</p><p>　　(6).要求寫出一份詳細的設(shè)計報告。課程設(shè)計報告內(nèi)容包括：設(shè)

12、計目的、設(shè)計內(nèi)容、設(shè)計原理、算法實現(xiàn)、流程圖、源程序、運行示例及結(jié)果分析、心得體會、參考資料等。</p><p><b>　　2 系統(tǒng)設(shè)計</b></p><p><b>　　2.1 問題分析</b></p><p>　　分頁存儲管理，是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。相應(yīng)地

13、，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中</p><p>　　系統(tǒng)為每個進程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系。一個頁表中包含若干個表目，表目的自然序號對應(yīng)于用戶程序中的頁號，表目中的塊號是該頁對應(yīng)的物理塊號。</p><p>　　請求頁式存儲

14、管理方式是一種實現(xiàn)虛擬存儲器的方式，是指在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面。當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。</p><p>　　請求頁式存儲管理主要需要解決以下問題：</p><p>　　系統(tǒng)如何獲知進程當(dāng)前所需頁面不在主存；當(dāng)發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入主存；當(dāng)主

15、存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。</p><p>　　2.2 算法與程序流程圖</p><p>　　該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，是他總是指向最老的頁面。但該算法與進程實際運行的

16、規(guī)律不相適應(yīng)，因為在進程中，有些頁面經(jīng)常被訪問，比如，含有全局變量，常用函數(shù)，例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。</p><p>　　設(shè)計原理：需要進行頁面置換，即把內(nèi)存中裝入最早的那個頁面淘汰，換入當(dāng)前的頁面。</p><p>　　算法流程圖，如圖2-1所示。</p><p>　　圖2-1先進先出置換算法</p><p>

17、;<b>　　3 系統(tǒng)實現(xiàn)</b></p><p><b>　　3.1數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　請求分頁存儲管理方式當(dāng)中用到的主要數(shù)據(jù)結(jié)構(gòu)就是頁表項。與普通分頁管理存儲方式當(dāng)中的頁表項相比，請求分頁存儲管理方式的頁表項要進行相應(yīng)的補充，共程序在換進、換出內(nèi)存時參考。</p><p>　　具體而言，請求分頁存儲管

18、理方式的頁表項一般包括以下幾項：頁號、駐留位、內(nèi)存塊號、外存地址、訪問位、修改位、（存取控制、輔存地址）。其中，中斷位表示該頁是在內(nèi)存還是在外存；訪問位表示該頁最近被訪問過，根據(jù)訪問位來決定淘汰哪頁；修改位用于查看此頁是否在內(nèi)存中被修改過。</p><p>　　本程序中采用的頁表項數(shù)據(jù)結(jié)構(gòu)如下(由于以上所述的有些域在程序中用不到，因此進行了相應(yīng)的簡化)</p><p>　　struct p

19、ageinfo //頁面信息結(jié)構(gòu)結(jié)構(gòu)</p><p><b>　　{</b></p><p>　　int serial[100]; // 模擬的最大訪問頁面數(shù)，實際控制在20以上 int flag; // 標(biāo)志位，0表示無頁面訪問數(shù)據(jù)</p><p>　　int diseffect; // 缺頁次數(shù)</p

20、><p>　　int total_pf; // 分配的頁框數(shù)</p><p>　　int total_pn; // 訪問頁面序列長度 </p><p>　　} pf_info;</p><p><b>　　3.2函數(shù)聲明</b></p><p>　　Void initialize(

21、)//打印頁面走向狀態(tài)</p><p>　　void createps( )//打印當(dāng)前的頁面</p><p>　　void displayinfo( )//尋找內(nèi)存塊中與e相同的塊號</p><p>　　void fifo( )//尋找最近最長未使用的頁面</p><p>　　void findpage( )//記錄當(dāng)前內(nèi)存塊中頁面離下次

22、使用間隔長度</p><p><b>　　3.3運行結(jié)果</b></p><p>　　運行程序界面將顯示如圖3-1的結(jié)果：</p><p><b>　　圖3-1初始化結(jié)果</b></p><p>　　圖3-2 FIFO算法頁面置換結(jié)果</p><p><b>　　4

23、 總結(jié)</b></p><p>　　通過這次課程設(shè)計讓我更深的了解算法的設(shè)計思想，并且對C語言進行了復(fù)習(xí)。 </p><p>　　對于頁面算法，我們平時上課時，只是知道了頁面置換算法是怎么做的，并沒有想如何去實現(xiàn)這些算法。在真正要做的時候才發(fā)現(xiàn)了問題。</p><p>　　在這次課程設(shè)計的過程中，我發(fā)現(xiàn)了自己的許多不足，特別是自己以前的c語言和數(shù)據(jù)結(jié)構(gòu)學(xué)

24、的不好，在寫代碼的時候有了許多的麻煩。最后，在老師和同學(xué)的幫助下，終于完成了這次課程設(shè)計。</p><p><b>　　參考文獻</b></p><p>　　[1] 徐孝凱.C++語言基礎(chǔ)教程.北京:清華大學(xué)出版社,2007</p><p>　　[2] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)應(yīng)用教程.北京:清華大學(xué)出版社,2007</p><p&

25、gt;　　[3] 張海藩.面向?qū)ο蟪绦蛟O(shè)計實用教程.北京: 清華大學(xué)出版社,2007</p><p>　　[4] 湯小丹, 梁紅兵 ,哲鳳屏, 湯子瀛編.計算機操作系統(tǒng).西安:西安電子科技大學(xué)出版社,2007</p><p>　　[5] 黃干平, 陳洛資編.計算機操作系統(tǒng).北京:科學(xué)出版社,1989</p><p>　　[6] 李勇, 劉恩林.計算機體系結(jié)構(gòu). 長沙

26、:國防科技大學(xué)出版社,1987</p><p>　　[7] 黃祥喜.計算機操作系統(tǒng)實驗教程.廣州:清中山大學(xué)出版社,1994</p><p>　　[8] 尤晉元.UNIX操作系統(tǒng)教程.西安: 西安電子科技大學(xué)出版社,1995</p><p>　　[9] 孟慶昌.操作系統(tǒng)教程 .北京:電子工業(yè)出版社,2004</p><p>　　[10] 陳向

27、群 楊芙清.操作系統(tǒng)教程.北京:北京大學(xué)出版社，2006</p><p><b>　　附錄</b></p><p><b>　　程序源代碼：</b></p><p>　　#include "windows.h"</p><p>　　#include <conio.h>

28、</p><p>　　#include <stdlib.h></p><p>　　#include <fstream.h></p><p>　　#include <io.h></p><p>　　#include <string.h></p><p>　　#include

29、 <stdio.h></p><p>　　void initialize(); //初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)</p><p>　　void createps(); //隨機生成訪問序列</p><p>　　void displayinfo(); //顯示當(dāng)前狀態(tài)及缺頁情況</p><p>　　void fifo();

30、 //先進先出算法</p><p>　　int findpage(); //查找頁面是否在內(nèi)存</p><p>　　int invalidcount = 0; // 缺頁次數(shù)</p><p>　　int vpoint; //頁面訪問指針</p><p>　　int page

31、frame[10]; // 分配的頁框</p><p>　　int pagehistory[10]; //記錄頁框中數(shù)據(jù)的訪問歷史</p><p>　　int rpoint; //頁面替換指針</p><p>　　int inpflag; //缺頁標(biāo)志，0為不缺頁，1為缺頁</p>

32、<p>　　struct PageInfo //頁面信息結(jié)構(gòu)</p><p><b>　　{</b></p><p>　　int serial[100]; // 模擬的最大訪問頁面數(shù)，實際控制在20以上</p><p>　　int flag; // 標(biāo)志位，0表示無頁面訪問數(shù)據(jù)</p>

33、<p>　　int diseffect; // 缺頁次數(shù)</p><p>　　int total_pf; // 分配的頁框數(shù)</p><p>　　int total_pn; // 訪問頁面序列長度</p><p>　　} pf_info;</p><p>　　//初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)</p>

34、<p>　　void initialize() </p><p><b>　　{</b></p><p><b>　　int i,pf;</b></p><p>　　inpflag=0; //缺頁標(biāo)志，0為不缺頁，1為缺頁</p&g

35、t;<p>　　pf_info.diseffect =0; // 缺頁次數(shù)</p><p>　　pf_info.flag =0; // 標(biāo)志位，0表示無頁面訪問數(shù)據(jù)</p><p>　　printf("\n請輸入要分配的頁框數(shù)："); // 自定義分配的頁框數(shù) </p><p>　　scanf("%d

36、",&pf);</p><p>　　pf_info.total_pf =pf; </p><p>　　for(i=0;i<100;i++) // 清空頁面序列</p><p><b>　　{</b></p><p>　　pf_info.serial[i]=-1;</p>&

37、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　// 隨機生成訪問序列</p><p>　　void createps(void )</p><p><b>　　{</b></p><p>　　int

38、s,i,pn;</p><p>　　initialize(); //初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)</p><p>　　printf("\n請輸入要隨機生成訪問序列的長度："); //自定義隨機生成訪問序列的長度</p><p>　　scanf("%d",&pn);</p><p>　　sran

39、d(rand()); //初始化隨機數(shù)隊列的"種子"</p><p>　　s=((float) rand() / 32767) * 50 + pn; // 隨機產(chǎn)生頁面序列長度</p><p>　　pf_info.total_pn = s;</p><p>　　for(i=0;i<s;i++) //產(chǎn)生隨機訪問序列</

40、p><p><b>　　{ </b></p><p>　　pf_info.serial[i]=((float) rand() / 32767) * 16 ; //隨機數(shù)的大小在0-15之間 </p><p><b>　　} </b></p><p><b>　　}<

41、/b></p><p>　　// 顯示當(dāng)前狀態(tài)及缺頁情況</p><p>　　void displayinfo(void)</p><p><b>　　{ </b></p><p><b>　　int i,n;</b></p><p>　　if(vpoint==0)

42、</p><p><b>　　{ </b></p><p>　　printf("\n=============頁面訪問序列=============\n");</p><p>　　for(i=0; i<pf_info.total_pn; i++) </p><p><b>　　{

43、 </b></p><p>　　printf("%4d",pf_info.serial[i]);</p><p>　　if ((i+1) % 10 ==0) printf("\n"); //每行顯示10個 </p><p><b>　　}</b></p>

44、<p>　　printf("\n======================================\n");</p><p><b>　　}</b></p><p>　　printf("訪問%3d : 內(nèi)存<",pf_info.serial[vpoint]);</p><p>　

45、　for(n=0;n<pf_info.total_pf;n++) // 頁框信息</p><p><b>　　{</b></p><p>　　if (pageframe[n] >=0) </p><p>　　printf("%3d",pageframe[n]);</p><p>&

46、lt;b>　　else</b></p><p>　　printf(" ");</p><p><b>　　}</b></p><p>　　printf(" >");</p><p>　　if(inpflag==1) //缺頁標(biāo)志，0為不缺頁，1為

47、缺頁</p><p><b>　　{ </b></p><p>　　printf(" ==>缺頁 "); </p><p>　　printf("缺頁率%3.1f",(float)(pf_info.diseffect)*100.00/vpoint); </p><p><

48、b>　　}</b></p><p>　　printf("\n"); </p><p><b>　　}</b></p><p>　　// 查找頁面是否在內(nèi)存，1為在內(nèi)存，0為不在即缺頁</p><p>　　int findpage(int page)</p><p&

49、gt;<b>　　{ </b></p><p><b>　　int n;</b></p><p>　　for(n=0;n<pf_info.total_pf;n++) </p><p><b>　　{</b></p><p>　　pagehistory[n] ++; /

50、/ 訪問歷史加1</p><p><b>　　}</b></p><p>　　for(n=0;n<pf_info.total_pf;n++) </p><p><b>　　{</b></p><p>　　if (pageframe[n]==page )</p><p>

51、<b>　　{ </b></p><p>　　inpflag=0 ; //inpflag缺頁標(biāo)志，0為不缺頁，1為缺頁 </p><p>　　pagehistory[n]=0; //置訪問歷史為0</p><p><b>　　return 1;</b></p><p><b&

52、gt;　　}</b></p><p><b>　　}</b></p><p>　　inpflag=1; //頁面不存在，缺頁</p><p>　　return 0; </p><p><b>　　}</b></p><p>　　// FIFO頁面置換算

53、法</p><p>　　void fifo(void)</p><p><b>　　{</b></p><p>　　int n,count,pstate; </p><p>　　rpoint=0; // 頁面替換指針初始化為0</p><p>　　invalidcount =

54、0; // 缺頁數(shù)初始化為0</p><p>　　createps(); // 隨機生成訪問序列</p><p>　　count=0; // 是否裝滿是所有的頁框</p><p>　　for(n=0;n<pf_info.total_pf;n++) // 清除頁框信息</p><p><b>

55、　　{</b></p><p>　　pageframe[n]=-1;</p><p><b>　　}</b></p><p>　　inpflag=0; //缺頁標(biāo)志，0為不缺頁，1為缺頁</p><p>　　for(vpoint=0;vpoint<pf_info.total_pn;vpoint++)

56、 // 執(zhí)行算法</p><p><b>　　{ </b></p><p>　　pstate=findpage(pf_info.serial[vpoint]); //查找頁面是否在內(nèi)存</p><p>　　if(count<pf_info.total_pf) // 開始時不計算缺頁</p><p>

57、;<b>　　{</b></p><p>　　if(pstate==0) // 頁不存在則裝入頁面</p><p><b>　　{ </b></p><p>　　pageframe[rpoint]=pf_info.serial[vpoint];</p><p>　　rpoint=(rp

58、oint+1) % pf_info.total_pf;</p><p><b>　　count++;</b></p><p>　　} </p><p><b>　　}</b></p><p>　　else // 正常缺頁置換</p><p&

59、gt;<b>　　{</b></p><p>　　if(pstate==0) // 頁不存在則置換頁面</p><p><b>　　{ </b></p><p>　　pageframe[rpoint]=pf_info.serial[vpoint];</p><p>　　rpoint=(

60、rpoint+1) % pf_info.total_pf;</p><p>　　pf_info.diseffect++; // 缺頁次數(shù)加1 </p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　Sleep(10);

61、 </p><p>　　displayinfo(); // 顯示當(dāng)前狀態(tài)</p><p>　　} // 置換算法循環(huán)結(jié)束</p><p><b>　　_getch();</b></p><p><b>　　return;</b></p><p><b&g

62、t;　　}</b></p><p><b>　　// 主函數(shù)</b></p><p>　　int main()</p><p><b>　　{ </b></p><p><b>　　char ch;</b></p><p>　　system

63、("cls") ;</p><p>　　while ( true ) </p><p><b>　　{</b></p><p>　　printf("*******************************************\n");</

64、p><p>　　printf(" 若要執(zhí)行FIFO頁面置算法請按 1 \n");</p><p>　　printf(" 若要退出請按 2 \n") ;</p><p>　　printf("*******************************************\n");</p

65、><p>　　printf( "Enter your choice (1 or 2 ): "); </p><p><b>　　do</b></p><p>　　{ //如果輸入信息不正確，繼續(xù)輸入</p><p>　　ch = (char)_getch() ;</p><p&g

66、t;　　}while(ch != '1' && ch != '2'&& ch != '3');</p><p>　　printf("\n\n你按的是：%c ,現(xiàn)在為你執(zhí)行對應(yīng)操作。",ch);</p><p>　　if(ch == '2') //選擇2，退出</p>

67、;<p><b>　　{</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b>&l

68、t;/p><p>　　printf("\n\n----------*****執(zhí)行FIFO算法*****-----------\n");</p><p><b>　　fifo(); </b></p><p><b>　　}</b></p><p>　　system("cls&

69、quot;) ;</p><p><b>　　}</b></p><p>　　printf("\n\nPress Any Key To Continue:");</p><p>　　_getch() ; </p><p><b>　　return 0;</b></p>