內(nèi)存管理(操作系統(tǒng))操作系統(tǒng)課程設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

11、ithm）。這種算法選擇最先調(diào)入主存儲(chǔ)器的頁面作為被替換的頁面。它的優(yōu)點(diǎn)是比較容易實(shí)現(xiàn)，能夠利用主儲(chǔ)存器中頁面調(diào)度情況的歷史信息，但是沒有反應(yīng)程序的局部性。因?yàn)樽钕日{(diào)入主存的頁面，很有可能是經(jīng)常使用的頁面。最近最少使用算法，即LFU（Least Frequently used algorithm）。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然這是一種非常合理的算法，因?yàn)榈侥壳盀橹棺钌偈褂玫捻撁?，和可能也是將來最少訪問的頁面。該算法即充分利用了主存中嗎調(diào)度的歷史信息，又正確反映了程序的局部性。但是這種算法實(shí)現(xiàn)起來非常的困難，它要為每個(gè)頁面設(shè)置一個(gè)很長(zhǎng)的計(jì)數(shù)器，并且要選擇一個(gè)固定的時(shí)鐘為每

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

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

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

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

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

17、#include<stdlib.h>#include<stdio.h>#include<time.h>#define TRUE 1#define FALSE 0#define INVALID -1#define zllc 320 /指令流長(zhǎng)#define xy 32 /虛頁長(zhǎng)#define clear 50 /清零周期typedef struct /頁面結(jié)構(gòu)int pn;/頁號(hào)int pfn;/頁面框架號(hào)int count; /計(jì)數(shù)器int time;/時(shí)間pc;pc plxy;/頁面線性結(jié)構(gòu)typedef struct pfc_struct/頁面控制結(jié)構(gòu)，

18、調(diào)度算法的控制結(jié)構(gòu)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調(diào)度算法int LRU(int);/LRU調(diào)度算法int LFU(int);/LFU調(diào)度算法int NUR(int);/NUR調(diào)度算法int OPT(int);/OPT調(diào)度算法/*主函數(shù)*/

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;/*初始化相關(guān)的數(shù)據(jù)結(jié)構(gòu)，pf表示內(nèi)存的塊數(shù)*/int initialize(int pf)int i;zhihuan = 0;for(i=0;i<xy;i+)pli.pn = i

21、;pli.pfn = INVALID;/質(zhì)頁面控制結(jié)構(gòu)中的頁號(hào)，頁面為空pli.count = 0;/頁面控制結(jié)構(gòu)中訪問次數(shù)pli.time = -1;/訪問時(shí)間for(i=0;i<pf-1;i+)/建立pfci-1與pfci之間的聯(lián)系pfci.next = &pfci+1;pfci.pfn = i;pfcpf-1.next = NULL;pfcpf-1.pfn = pf-1;free_head = &pfc0;/空頁面隊(duì)列的頭指針為pfc0return 0;/*先進(jìn)先出算法，pf為用戶進(jìn)程的內(nèi)存頁面數(shù)*/int FIFO(int pf)int i;pfc_type *p

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

23、t = NULL;/表明此頁面是空的組后一面busy_head = p;/更新頁面的頭隊(duì)列指針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/把剛剛換進(jìn)來的接在busy_tail的后面busy_tail->next = free_head;busy_tail = free_head;free

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

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

26、ei.time = present_time;/命中則增加該頁面的訪問次數(shù)present_time+;printf("LRU:%6.4f|",1-(float)zhihuan/320);return 0;/*最近未使用算法*/int NUR(int pf)int i,j,dp,cont_flag,old_dp;/這個(gè)算法用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/下一個(gè)頁面pldp.count = 0;dp+;if(dp=xy)/32個(gè)頁面找一遍，開始新的循環(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的使用頻率最小的內(nèi)存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;/減少一個(gè)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 <