內存管理(操作系統(tǒng))操作系統(tǒng)課程設計

1、附件2：封面（打印時清除本行內容。只許填空，不許變動結構）河南城建學院操作系統(tǒng)課程設計說明書設計題目： 存儲管理 專 業(yè)： 計算機科學與技術 指導教師： 邵國金 班 級： 0814121 學 號： 081412112 姓 名： 同 組 人： 計算機科學與工程學院2015 年 1 月 9日前言本課程設計是編制頁面置換算法FIFO、LRU、LFU、NUR和OPT的模擬程序,并模擬其在內存的分配過程。同時根據頁面走向，分別采用FIFO、LRU、LFU、NUR和OPT算法進行頁面置換，統(tǒng)計命中率；同時系統(tǒng)可以隨意設置當前分配給作業(yè)的物理塊數。 系統(tǒng)運行時，任意輸入一個頁面訪問序列，可以設定不同的頁面置

2、換算法和物理塊數，輸出其頁面淘汰的情況，計算其缺頁次數和缺頁率。系統(tǒng)結束后，比較同一個頁面訪問序列，可以得出在不同的頁面置換算法和物理塊數的情況下，其產生的缺頁次數和缺頁率。 使用FIFO算法，由于測試數據相同的頁面比較少，所以采用FIFO算法時，需要置換的頁面多，比較繁瑣，沒有優(yōu)化效果，所以FIFO算法性能不好。使用LRU的算法，此組數據顯示LRU的算法使用比較繁瑣，總的來說，NUR、LFU、LRU算法介于FIFO和OPT之間。通過系統(tǒng)模擬得出，OPT算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，較少應用；由于OPT算法在實際上難于實現，所以實際應用一般用LRU

3、算法。 本程序實現了操作系統(tǒng)中頁式虛擬存儲管理中缺頁中斷理想型淘汰算法，該算法在訪問串中將來再也不出現的或是在離當前最遠的位置上出現的頁淘汰掉。這樣，淘汰掉該頁將不會造成因需要訪問該頁又立即把它調入的現象。該程序能按要求隨機確定內存大小，隨機產生頁面數，進程數，每個進程的頁數，給進程分配的頁數等，然后運用理想型淘汰算法對每個進程進行計算缺頁數，缺頁率，被淘汰的序列等功能。 目錄一系統(tǒng)環(huán)境11.1硬件環(huán)境11.2軟件環(huán)境1二設計目的2三總體設計33.1程序設計組成框圖33.2流程圖4四詳細設計74.1模塊功能說明74.11數據結構74.12函數定義84.13變量定義84.2算法分析8五

4、調試與測試105.1調試方法105.11使用Vi編譯程序105.12運行程序125.2結果分析與討論135.3測試問題及采取措施13六源程序14七心得體會23八參考文獻24一系統(tǒng)環(huán)境1.1硬件環(huán)境PC機一臺，0.99G內存，2.0GHZ主頻1.2軟件環(huán)境設計和實驗將Windows環(huán)境下，gcc和虛擬機軟件VMWare2 設計目的存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。本設計的目的是通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式存儲管理的頁面置換算法。要求：(1)通過隨機數產生一個指令序列，共320條指令。指令的地址按下

5、述原則生成：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分。具體的實施方法是：在0，319的指令地址之間隨機選取一起點m；順序執(zhí)行一條指令，即執(zhí)行地址為m+l的指令；在前地址0，m+1中隨機選取一條指令并執(zhí)行，該指令的地址為m；順序執(zhí)行一條指令，其地址為m+1；在后地址m+2，319中隨機選取一條指令并執(zhí)行；重復上述步驟，直到執(zhí)行320次指令。(2)將指令序列變換成為頁地址流。設:頁面大小為1K；用戶內存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每頁存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條第9條指令

6、為第0頁(對應虛存地址為0，9)；第10條第19條指令為第1頁(對應虛存地址為10，19)； 第310條第319條指令為第31頁(對應虛存地址為310，319)。按以上方式，用戶指令可組成32頁。(3)計算并輸出下述各種算法在不同內存容量下的命中率（要為以下各種算法定義數據結構）。先進先出的算法(FIFO)；最近最少使用算法(LRU)；最近最不經常使用算法(NUR/NRU/CLOCK)。命中率=1-頁面失效次數/頁地址流長度在本設計中，頁地址流長度為320，頁面失效次數為每次訪問相應指令時，該指令所對應的頁不在內存的次數。(4)關于隨機數產生辦法，Linux/UNIX系統(tǒng)提供函數srand（）

7、和rand（），分別進行初始化和產生隨機數。例如:srand()語句可初始化一個隨機數：a0=10*rand()/32767*319+1，a1=10*rand()/32767*a0； 語句可用來產生a0、a1、中的隨機數。三總體設計3.1程序設計組成框圖系統(tǒng)分為4個子模塊：初始化模塊，FIFO、LRU、LFU、NUR和OPT的五個算法模塊。初始化模塊：initialize( )初始化函數，給每個相關的頁面賦值。FIFO算法模塊：計算使用FIFO算法時的命中率。LRU算法模塊：計算使用LRU算法時的命中率。LFU算法模塊：計算使用OPT算法時的命中率。NUR算法模塊：計算使用LFU算法時的命中率

8、。OPT算法模塊：計算使用NUR算法時的命中率。Main()FIFO算法模塊LFU算法模塊NUR算法模塊OPT算法模塊LRU算法模塊Initialize()初始化函數3.2流程圖LFU NUR OPT四詳細設計本實驗的程序設計基本上按照實驗內容進行。即首先用srand()和rand()函數定義和產生指令序列,然后將指令序列變換成相應的頁地址流,并針對不同的算法計算出相應的命中率。相關定義如下:4.1模塊功能說明4.11數據結構(l)頁面類型typedef structintpn,pfn,count,time; pl_type;其中pn為頁號,pfn為面號,count為個周期內訪問該頁面次數ti

9、me為訪問時間。(2)頁面控制結構pfc_structintpn,pfn;struct pfc_struct*next;typedefstruct pfc_struct pfc_type;pfc_typepfcxy,*free_head,*busy_head;pfc_type*busy_tail;其中：pfcxy定義用戶進程虛頁控制結構,*free_head為空頁面頭的指針,*busy_head為忙頁面頭的指針,*busy_tail為忙頁面尾的指針。4.12函數定義(1)void initialize():初始化函數,給每個相關的頁面賦值。(2)void FIFO():計算使用FIFO算法時的

10、命中率。(3)void LRU():計算使用LRU算法時的命中率。(4)void OPT():計算使用OPT算法時的命中率。(5)void LFU():計算使用LFU算法時的命中率。(6)void NUR():計算使用NUR算法時的命中率。4.13變量定義(1)int azllc;指令流數據組。(2)int pagezllc;每條指令所屬頁號。(3)int offsetzllc;每頁裝入10條指令后取模運算頁號偏移值。(4)int pf:用戶進程的內存頁面數。(5)int zhihuan:頁面失效次數。4.2算法分析先進先出算法，即FIFO算法（First-In First-Out algor

11、ithm）。這種算法選擇最先調入主存儲器的頁面作為被替換的頁面。它的優(yōu)點是比較容易實現，能夠利用主儲存器中頁面調度情況的歷史信息，但是沒有反應程序的局部性。因為最先調入主存的頁面，很有可能是經常使用的頁面。最近最少使用算法，即LFU（Least Frequently used algorithm）。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然這是一種非常合理的算法，因為到目前為止最少使用的頁面，和可能也是將來最少訪問的頁面。該算法即充分利用了主存中嗎調度的歷史信息，又正確反映了程序的局部性。但是這種算法實現起來非常的困難，它要為每個頁面設置一個很長的計數器，并且要選擇一個固定的時鐘為每

12、個計數器定時計數。在選擇被替換頁面時，要從所有的計數器中選擇一個計數值最大的計數器。因此，通常使用如下一種簡單的方法。最久沒有使用算法。即LRU(Least Recently Used Algorithm)。這種算法把近期最久沒有被訪問的頁面作為被替換的頁面。它把LFU算法中要記錄數量上的多與少簡化成判斷有于無，因此實現起來比較容易。NUR算法在需要淘汰一頁時，從哪些最近一個時期內未被訪問的頁面中任選一頁淘汰。只要在頁面中增加一個訪問位即可實現。當某頁被訪問時，訪問位置1.否則，訪問位置0.系統(tǒng)周期性第對所有的引用位清零。當須淘汰一頁時從那些訪問位為0 的頁中選擇一頁進行淘汰。如果引用位全為1

13、或0，NRU算法退化為FIFO算法。最優(yōu)替換算法，即OPT(Optimal Replacement Algorithm).s上面介紹的幾種頁面替換算法主要是以主存儲器中頁面調度情況的歷史信息為依據的，它假設將來主存儲器中的頁面調度情況與過去一段時間內主存儲器中的頁面調度情況是相同的。當然這種假設不總是正確的。最好的算法是選擇將來醉酒不被訪問的頁面作為被替換的頁面，這種算法的命中率是最高的，它就是最有替換算法。要實現OPT算法，唯一的辦法就是讓程序先執(zhí)行一遍，記錄下實際的頁地址流情況。根據這個頁地址流才能找到藥被替換的頁面。顯然這樣做是不現實的。 因此OPT算法只是一種理想化的算法，然而它也是一

14、種很用的算法。實際上，經常把這種算法作為評價其他頁面替換算法好壞的標準。在其他條件相同的情況下，哪一種算法的命中率與OPT算法最接近，那么，它就是一種比較好的頁面替換算法。五調試與測試5.1調試方法5.11使用Vi編譯程序（1） 打開VMware、選中Red Hat Enterprise Linux、查看屬性、選項、共享文件夾添加（2） 查看root的主目錄mnthgfszhengzhengjingjing使用vi打開5.12運行程序5.2結果分析與討論 從上述結果可知,在內存頁面數較少(45頁面)時,5種算法的命中率差別不大,都是50%左右。在內存頁面為725個頁面之間時,5種算法的訪內命中

15、率大致在52%至87%之間變化。但是,FIFO算法與0PT算法之間的差別一般在610個百分點左右。在內存頁面為2532個頁面時,由于用戶進程的所有指令基本上都已裝入內存,從而命中率已較大。從而算法之間的差別不大。 比較上述5種算法,以OPT算法的命中率最高,NUR算法次之,再就是LFU算LRU算法,其次是FIF0算法。5.3測試問題及采取措施 本次課程設計中我們遇到的問題是，一開始沒有弄清楚rand和sand函數的使用方法，以至于運行時的到的結果與實際算起來的不相符，后來查閱資料，上網瀏覽搜索相關信息后，終于弄明白了是怎么回事。 函數rand()是真正的隨機數生成器，而srand()會設置供r

16、and()使用的隨機數種子。如果你在第一次調用rand()之前沒有調用srand()，那么系統(tǒng)會為你自動調用srand()。而使用同種子相同的數調用 srand()會導致相同的隨機數序列被生成。 srand(unsigned)time(NULL)則使用系統(tǒng)定時/計數器的值做為隨機種子。每個種子對應一組根據算法預先生成的隨機數，所以，在相同的平臺環(huán)境下，不同時間產生的隨機數會是不同的，相應的，若將srand（unsigned）time(NULL)改為srand(TP)（TP為任一常量），則無論何時運行、運行多少次得到的“隨機數”都會是一組固定的序列，因此srand生成的隨機數是偽隨機數。六源程序

17、#include<stdlib.h>#include<stdio.h>#include<time.h>#define TRUE 1#define FALSE 0#define INVALID -1#define zllc 320 /指令流長#define xy 32 /虛頁長#define clear 50 /清零周期typedef struct /頁面結構int pn;/頁號int pfn;/頁面框架號int count; /計數器int time;/時間pc;pc plxy;/頁面線性結構typedef struct pfc_struct/頁面控制結構，

18、調度算法的控制結構int pn;int pfn;struct pfc_struct *next;pfc_type;pfc_type pfcxy,*free_head,*busy_head,*busy_tail;int zhihuan,azllc;/a 為指令序列int pagezllc,offsetzllc;/地址信息int initialize(int);/初始化模塊int FIFO(int);/FIFO調度算法int LRU(int);/LRU調度算法int LFU(int);/LFU調度算法int NUR(int);/NUR調度算法int OPT(int);/OPT調度算法/*主函數*/

19、int main()int s,i;srand(unsigned)time(NULL);s = rand()%320;for(i=0;i<zllc;i += 4)if(s<0|s>319)printf("When i = %d,Error,s=%d",i,s);exit(0);ai = s;ai+1 = ai+1;ai+2 = rand()%(ai+1+1);ai+3 = ai+2 + 1;s = rand()%(319-ai+3) +ai+3+1;if(ai+2>318|s>319)printf("a%d+2,a number wh

20、ich is:%d and s = %dn",i,ai+2,s);for(i=0;i<zllc;i+)/將指令序列變換為頁地址流pagei = ai/10;offseti = ai%10;for(i=4;i<=32;i+)printf("%2d page frames:t",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return 0;/*初始化相關的數據結構，pf表示內存的塊數*/int initialize(int pf)int i;zhihuan = 0;for(i=0;i<xy;i+)pli.pn = i

21、;pli.pfn = INVALID;/質頁面控制結構中的頁號，頁面為空pli.count = 0;/頁面控制結構中訪問次數pli.time = -1;/訪問時間for(i=0;i<pf-1;i+)/建立pfci-1與pfci之間的聯系pfci.next = &pfci+1;pfci.pfn = i;pfcpf-1.next = NULL;pfcpf-1.pfn = pf-1;free_head = &pfc0;/空頁面隊列的頭指針為pfc0return 0;/*先進先出算法，pf為用戶進程的內存頁面數*/int FIFO(int pf)int i;pfc_type *p

22、;/中間變量initialize(pf);/初始化數據結構busy_head = busy_tail = NULL;/忙頁面頭隊列，為隊列鏈接for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/頁面失效zhihuan+;/失效次數if(free_head = NULL)/無空閑頁面p = busy_head->next;/保存忙頁面的下一個頁面plbusy_head->pn.pfn = INVALID;/把這個頁面換出，更新它的數據成員free_head = busy_head;/釋放忙頁面隊列的第一個頁面free_head->nex

23、t = NULL;/表明此頁面是空的組后一面busy_head = p;/更新頁面的頭隊列指針p = free_head->next;free_head->pn = pagei;plpagei.pfn = free_head->pfn;free_head->next = NULL;/使busy的尾為空if(busy_tail = NULL)busy_tail = busy_head = free_head;else/把剛剛換進來的接在busy_tail的后面busy_tail->next = free_head;busy_tail = free_head;free

24、_head = p;/下一個空頁面printf("FIFO:%6.4f|",1-(float)zhihuan/320);return 0;/*最近最久未使用算法*/int LRU(int pf)int min,minj,i,j,present_time;/minj為最小值下標initialize(pf);present_time=0;for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/頁面失效zhihuan+;if(free_head = NULL)/無空閑頁面min = 32767;/設置最大值for(j=0;j<xy;j+

25、)/找出time最下值if(min>plj.time&&plj.pfn!=INVALID)min = plj.time;minj = j;free_head = &pfcplminj.pfn;/騰出一個單元plminj.pfn = INVALID;plminj.time = 0;free_head->next= NULL;plpagei.pfn = free_head->pfn;/有空閑頁面改為有效plpagei.time =present_time;free_head = free_head->next;/減少一個free頁面elseplpag

26、ei.time = present_time;/命中則增加該頁面的訪問次數present_time+;printf("LRU:%6.4f|",1-(float)zhihuan/320);return 0;/*最近未使用算法*/int NUR(int pf)int i,j,dp,cont_flag,old_dp;/這個算法用count用于訪問位initialize(pf);dp = 0;for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/頁面失效zhihuan+;if(free_head = NULL)/無空閑頁cont_flag =

27、 TRUE;old_dp = dp;while(cont_flag)/找到一訪問位count為0的頁面if(pldp.count = 0 && pldp.pfn != INVALID)cont_flag = FALSE;else/下一個頁面pldp.count = 0;dp+;if(dp=xy)/32個頁面找一遍，開始新的循環(huán)dp=0;free_head = &pfcpldp.pfn;pldp.pfn = INVALID;free_head->next = NULL;plpagei.pfn = free_head->pfn;plpagei.count = 1

28、;free_head->pn = pagei;free_head = free_head->next;elseplpagei.count = 1;if(i%clear = 0)for(j=0;j<xy;j+)plj.count = 0;printf("NUR:%6.4f|",1-(float)zhihuan/320);return 0;/*最少訪問頁面算法*/int LFU(int pf)int i,j,min,minpage;initialize(pf);for(i=0;i<zllc;i+)if(plpagei.pfn = INVALID)/頁面失

29、效zhihuan+;if(free_head = NULL)/無空閑頁面min = 32767;/獲取count的使用頻率最小的內存for(j=0;j<xy;j+)if(min>plj.count&&plj.pfn!=INVALID)min = plj.count;minpage=j;free_head = &pfcplminpage.pfn;plminpage.pfn = INVALID;plminpage.count=0;free_head->next=NULL;plpagei.pfn = free_head->pfn;plpagei.cou

30、nt+;free_head = free_head->next;/減少一個free頁面elseplpagei.count = plpagei.count+1;printf("LFU:%6.4f",1-(float)zhihuan/320);return 0;/*最佳置換算法*/int OPT(int pf)int i,j,k,l,max,maxpage;initialize(pf);for(i = 0; i < zllc; i+)if(plpagei.pfn = INVALID)/頁面失效 zhihuan+;max = maxpage = 0;if(free_head = NULL)/無頁面空閑for(j = 0; j < pf; j+)l = 1;for(k = i + 1; k <