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

1、<p><b>　　課程設(shè)計說明書</b></p><p>　　題目: 請求頁式存儲器管理程序 </p><p>　　院 系： 計算機(jī)科學(xué)與工程學(xué)院 </p><p>　　專業(yè)班級： 計算機(jī)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>　　分頁存儲管理，是將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中</p><p>　　系統(tǒng)為每個進(jìn)程建立一個

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

5、;/p><p>　　請求頁式存儲管理主要需要解決以下問題：系統(tǒng)如何獲知進(jìn)程當(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運(yùn)行結(jié)果4</b></p><p><b>　　4 總結(jié)6</b></p><p><b>　　參考文獻(xiàn)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). 運(yùn)行給出的實驗程序，查看執(zhí)行情況，進(jìn)而分析算法的執(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)和缺頁率。程序的地址訪問序列通過隨機(jī)數(shù)產(chǎn)生，要求具有足夠的長度。最好頁框數(shù)和訪問序列長度可調(diào)節(jié)。</p><p>　　(4). 每個學(xué)生必須獨(dú)立完成課程設(shè)計，不能相互抄襲；</p><p>　　(5).設(shè)計完成后，將所完成的工作交由老師檢查；</p><p>　　(6).要求寫出一份詳細(xì)的設(shè)計報告。課程設(shè)計報告內(nèi)容包括：設(shè)

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

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

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

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

16、規(guī)律不相適應(yīng)，因為在進(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量，常用函數(shù)，例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。</p><p>　　設(shè)計原理：需要進(jìn)行頁面置換，即把內(nèi)存中裝入最早的那個頁面淘汰，換入當(dāng)前的頁面。</p><p>　　算法流程圖，如圖2-1所示。</p><p>　　圖2-1先進(jìn)先出置換算法</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)中的頁表項相比，請求分頁存儲管理方式的頁表項要進(jìn)行相應(yīng)的補(bǔ)充，共程序在換進(jìn)、換出內(nèi)存時參考。</p><p>　　具體而言，請求分頁存儲管

18、理方式的頁表項一般包括以下幾項：頁號、駐留位、內(nèi)存塊號、外存地址、訪問位、修改位、（存取控制、輔存地址）。其中，中斷位表示該頁是在內(nèi)存還是在外存；訪問位表示該頁最近被訪問過，根據(jù)訪問位來決定淘汰哪頁；修改位用于查看此頁是否在內(nèi)存中被修改過。</p><p>　　本程序中采用的頁表項數(shù)據(jù)結(jié)構(gòu)如下(由于以上所述的有些域在程序中用不到，因此進(jìn)行了相應(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運(yùn)行結(jié)果</b></p><p>　　運(yùn)行程序界面將顯示如圖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語言進(jìn)行了復(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>　　參考文獻(xiàn)</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] 湯小丹, 梁紅兵 ,哲鳳屏, 湯子瀛編.計算機(jī)操作系統(tǒng).西安:西安電子科技大學(xué)出版社,2007</p><p>　　[5] 黃干平, 陳洛資編.計算機(jī)操作系統(tǒng).北京:科學(xué)出版社,1989</p><p>　　[6] 李勇, 劉恩林.計算機(jī)體系結(jié)構(gòu). 長沙

26、:國防科技大學(xué)出版社,1987</p><p>　　[7] 黃祥喜.計算機(jī)操作系統(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(); //隨機(jī)生成訪問序列</p><p>　　void displayinfo(); //顯示當(dāng)前狀態(tài)及缺頁情況</p><p>　　void fifo();

30、 //先進(jìn)先出算法</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>　　// 隨機(jī)生成訪問序列</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請輸入要隨機(jī)生成訪問序列的長度："); //自定義隨機(jī)生成訪問序列的長度</p><p>　　scanf("%d",&pn);</p><p>　　sran

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

40、p><p><b>　　{ </b></p><p>　　pf_info.serial[i]=((float) rand() / 32767) * 16 ; //隨機(jī)數(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(); // 隨機(jī)生成訪問序列</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>