操作系統(tǒng)存儲管理實驗報告

1、北京郵電大學(xué) 操作系統(tǒng)實驗 實驗報告實驗日期：2010-12-20 實驗名稱：存儲管理一、實驗?zāi)康?二、實驗內(nèi)容2三、實驗分析2對于伙伴算法2對于虛擬存儲區(qū)和內(nèi)存工作區(qū)的不同算法3四、編程實現(xiàn)3伙伴算法3原理3伙伴的概念3內(nèi)存的釋放4位圖法4偽代碼4運(yùn)行結(jié)果演示5最佳置換算法5基本思想5偽代碼實現(xiàn)5運(yùn)行結(jié)果演示6先進(jìn)先出法（Fisrt In First Out）6基本思想6偽代碼實現(xiàn)6運(yùn)行結(jié)果演示7 最近最久未使用（Least Recently Used）7基本思想7偽代碼實現(xiàn)7運(yùn)行結(jié)果演示7最不經(jīng)常使用法（Least Frequently Used）8基本思想8偽代碼實現(xiàn)8運(yùn)行結(jié)果演示8 最

2、近未使用法（No Used Recently）8基本思想8偽代碼實現(xiàn)9運(yùn)行結(jié)果演示9五、各種算法運(yùn)行綜合比較9六、實驗心得10七、程序源代碼11伙伴算法11最佳置換算法19先進(jìn)先出法22 最近最久未使用24最不經(jīng)常使用法27最近未使用法30一、實驗?zāi)康耐ㄟ^模擬實現(xiàn)內(nèi)存分配的伙伴算法和請求頁式存儲管理的幾種基本頁面置換算法，了解存儲技術(shù)的特點。掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。二、實驗內(nèi)容實現(xiàn)一個內(nèi)存管理的伙伴算法，實現(xiàn)內(nèi)存塊申請時的分配和釋放后的回收。設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法計算訪問命中率。1) 最佳置換算法（Opt

3、imal）2) 先進(jìn)先出法（Fisrt In First Out）3) 最近最久未使用（Least Recently Used）4) 最不經(jīng)常使用法（Least Frequently Used）5) 最近未使用法（No Used Recently）其中，命中率頁面失效次數(shù)頁地址流長度。試對上述算法的性能加以較各：頁面?zhèn)€數(shù)和命中率間的關(guān)系；同樣情況下的命中率比較。三、實驗分析對于伙伴算法，用隨機(jī)函數(shù)仿真進(jìn)程進(jìn)行內(nèi)存申請，并且以較為隨機(jī)的次序進(jìn)行釋放。對其碎片進(jìn)行統(tǒng)計，當(dāng)申請分配內(nèi)存失敗時區(qū)分實際空間不足和由于碎片而不能滿足。對于虛擬存儲區(qū)和內(nèi)存工作區(qū)的不同算法，其中主要的流程：首先用srand(

4、 )和rand( )函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。實驗可先從一個具體的例子出發(fā)。（1）通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成：A：50%的指令是順序執(zhí)行的B：25%的指令是均勻分布在前地址部分C：25%的指令是均勻分布在后地址部分具體的實施方法是：A：在0，319的指令地址之間隨機(jī)選取一起點mB：順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令C：在前地址0,m+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為mD：順序執(zhí)行一條指令，其地址為m+1E：在后地址m+2，319中隨機(jī)選取一條指令并執(zhí)行F：重復(fù)步驟A

5、-E，直到320次指令（2）將指令序列變換為頁地址流設(shè)：頁面大小為1K；用戶內(nèi)存容量4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第 0 條-第 9 條指令為第0頁（對應(yīng)虛存地址為0，9）第10條-第19條指令為第1頁（對應(yīng)虛存地址為10，19）第310條-第319條指令為第31頁（對應(yīng)虛存地址為310，319）按以上方式，用戶指令可組成32頁。四、編程實現(xiàn)伙伴算法原理：伙伴算法把所有的空閑頁面分為10個塊組，每組中塊的大小是2的冪次方個頁面，例如，第0組中塊的大小都為20（1個頁面），第1組中塊的大小為都為21（2個頁

6、面），第9組中塊的大小都為29（512個頁面）。也就是說，每一組中塊的大小是相同的，且這同樣大小的塊形成一個鏈表。伙伴的概念，滿足以下三個條件的稱為伙伴： (1)兩個塊大小相同 (2)兩個塊地址連續(xù) (3)兩個塊必須是從同一個大塊中分離出來的。內(nèi)存的釋放，是分配的逆過程，也可以看作是伙伴的合并過程。當(dāng)釋放一個塊時，先在其對應(yīng)的鏈表中考查是否有伙伴存在，如果沒有伙伴塊，就直接把要釋放的塊掛入鏈表頭；如果有，則從鏈表中摘下伙伴，合并成一個大塊，然后繼續(xù)考查合并后的塊在更大一級鏈表中是否有伙伴存在，直到不能合并或者已經(jīng)合并到了最大的塊(2 個頁面)。位圖法，通常我們用位圖來實現(xiàn)整個過程中，位圖的某一

7、位對應(yīng)兩個互為伙伴的塊，為 l 表示其中一塊分配出去了，為0表示兩塊都空閑?；锇樗惴ㄖ袩o論是分配還是釋放內(nèi)存塊都只對相應(yīng)的位圖位進(jìn)行異或操作。分配內(nèi)存時對位圖的操作是為釋放過程服務(wù)，釋放過程根據(jù)位圖判斷伙 伴是否存在，如果對相應(yīng)位的異或操作得 1，則沒有伙伴可以合并，如果異或操作得0，就進(jìn)行合并，并且繼續(xù)按這種方式合并伙伴，直到不能合并為止。如上所述，伙伴算法綜合利用了位圖和鏈表的方式，較為高效地實現(xiàn)了內(nèi)存的分配和釋放，而且在釋放過程中盡可能的合并小塊內(nèi)存，有效的消除了內(nèi)存碎片。偽代碼struct node/*建立結(jié)構(gòu)數(shù)組，定義鏈表鏈接*/ int much; int flag,flag_le

8、ft,flag_right; struct node *leftchild,*rightchild,*father;/左右兒子父親指針;struct IN_T int num; int space; struct node *temp;void search_tree(struct node *head,int space,int really_need)/處理內(nèi)存請求 內(nèi)存節(jié)點的最大可用空間比應(yīng)該分配內(nèi)存小時 分配失敗 否則 如果內(nèi)存節(jié)點的大小正好等于應(yīng)該分配內(nèi)存 分配成功 否則 如果該內(nèi)存節(jié)點尚未分配子女節(jié)點 分配左右子女 遞歸處理該請求，依照做子女先分配 否則 若左右子女最小的可用空間比

9、需要的內(nèi)存還大 取小者分配內(nèi)存 否則 取可用空間比需要的內(nèi)存大者分配內(nèi)存 修改節(jié)點可用空間與碎片大小 void back_to_space(int i) 從釋放節(jié)點依次向上經(jīng)過每一個父節(jié)點，都要做釋放內(nèi)存的操作。 運(yùn)行結(jié)果演示隨機(jī)生成的20組內(nèi)存分配請求 這是內(nèi)存分配結(jié)果，其中，對于內(nèi)存不夠時會有顯示，提示最佳置換算法基本思想：發(fā)生缺頁時，有些頁面在內(nèi)存中，其中有一頁見很快被訪問（也包含緊接著的下一條指令的那頁），而其他頁面則可能要到10、100或者1000條指令后才會被訪問，每個頁面都可以用在該頁面首次被訪問前所要執(zhí)行的指令數(shù)進(jìn)行標(biāo)記。偽代碼實現(xiàn)void OPT() for(i=0;iLEN

10、;i+) 如果幀已經(jīng)填滿 若在幀中找到該頁命中，退出 否則找到最遠(yuǎn)使用的頁面置換 若幀未填滿 命中，則退出否則，加入空閑幀中運(yùn)行結(jié)果演示先進(jìn)先出法（Fisrt In First Out）基本思想：FIFO最簡單的頁置換算法，F(xiàn)IFO的頁置換的算法為每個頁記錄著該頁調(diào)入內(nèi)存的時間。當(dāng)必須置換一頁時，將選擇最舊的頁。注意并不需要記錄調(diào)入一頁的確切時間，可以創(chuàng)建一個FIFO隊列來管理內(nèi)存中的所有頁。隊列中的首頁將被置換。當(dāng)需要調(diào)入頁時，將它加入到隊列的尾部。 FIFO的頁置換算法很好理解和實現(xiàn)，但是，其性能并不是很好。所替代的頁可能是很久以前使用的、現(xiàn)已不再使用的初始化模塊，另一方面，所替代的頁可能

11、包含一個以前初始化的并且不斷使用的常用變量。偽代碼實現(xiàn)void FIFO() for(i=0;iLEN;i+) 如果幀已經(jīng)填滿若在幀中找到該頁命中，退出 否則找到最先進(jìn)入的頁面置換 若幀未填滿 命中，則退出否則，加入空閑幀中 運(yùn)行結(jié)果演示 最近最久未使用（Least Recently Used）基本思想：LRU置換為每個頁關(guān)聯(lián)該頁上次使用的時間。當(dāng)必須置換一次的時候，LRU選擇最長時間沒有使用的頁，這種策略為向后看最優(yōu)頁置換算法。LRU置換算法被認(rèn)為相當(dāng)不錯，其主要問題是如何實現(xiàn)LRU置換，頁幀的排序序列按頁幀上次使用時間來定，有兩種可行方法： 計算器 為每個頁表項關(guān)聯(lián)一個使用時間域，并為CP

12、U增加一個邏輯時鐘或者計數(shù)器。對每次內(nèi)存引用，計算器都會增加，每次內(nèi)存引用的時候時鐘寄存器的內(nèi)容會被復(fù)制到相應(yīng)頁所對應(yīng)的頁表項的使用時間域內(nèi)。用這種方式就得到每頁的最近使用時間。置換具有最小時間的頁。這種方案需要搜索頁表已經(jīng)查找LRU也，且每次內(nèi)存訪問都要寫入內(nèi)存。在改變頁表時，因CPU調(diào)度，也必須保持時間。必須考慮時鐘溢出。棧 每當(dāng)引用一個頁，該頁就從棧中刪除并放在頂部。這樣，棧頂部總是最近使用的頁，棧底部總是LRU頁。由于必須是從棧中刪除項，所以，該?？蓪崿F(xiàn)為具有頭部指針和尾指針的雙向鏈表。雖然每個更新有點費(fèi)事，但是置換不需要搜索；尾部指針指向棧底部，就是LRU頁。偽代碼實現(xiàn)void LR

13、U() for(i=0;iLEN;i+) 如果幀已經(jīng)填滿 若在幀中找到該頁命中，并將該頁放到幀的最后，標(biāo)志最近使用退出 否則找到最近最不常用的頁面置換 若幀未填滿命中，則退出否則，加入空閑幀中運(yùn)行結(jié)果演示最不經(jīng)常使用法（Least Frequently Used）基本思想：即LFU算法（Least Frequently Used algorithm）。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然，這是一種非常合理的算法，因為到目前為止最少使用的頁面，很可能也是將來最少訪問的頁面。該算法既充分利用了主存中頁面調(diào)度情況的歷史信息，又正確反映了程序的局部性。該算法在需要淘汰某一頁時，首先淘汰

14、到當(dāng)前時間為止，被訪問次數(shù)最少的那一頁。該算法只要在頁表中給每一頁增設(shè)一個訪問計數(shù)器即可實現(xiàn)。每當(dāng)該頁被訪問時，訪問計數(shù)器加 1 ，而發(fā)生一次缺頁中斷時，則淘汰計數(shù)值最小的那一頁，并將所有的計數(shù)器清零。偽代碼實現(xiàn)void LFU()/最不經(jīng)常使用法 for(i=0;iLEN;i+) 如果幀已經(jīng)填滿 若在幀中找到該頁命中，該頁面標(biāo)志計數(shù)器加1，退出 否則找到計數(shù)值最小的頁面置換 若幀未填滿，命中該頁面標(biāo)志計數(shù)器加1，退出否則，加入空閑幀中運(yùn)行結(jié)果演示 最近未使用法（No Used Recently）基本思想：該算法在需要淘汰某一頁時，從那些最近一個時期內(nèi)未被訪問的頁中任選一頁淘汰。NRU為操作系

15、統(tǒng)請求分頁存儲管理中的頁面淘汰算法，又名近似的LRU置換算法。當(dāng)一存儲塊中的頁面訪問時，其相應(yīng)的“頁面訪問”位由硬件自動置“”，而由頁面管理體制軟件周期性地（設(shè)周期為，其值通常為幾百毫秒），把所有的頁面訪問位重新置為“”。這樣，在時間內(nèi)，某些被訪問的頁面，其對應(yīng)的訪問位為“”而未訪問的頁面，其對應(yīng)的訪問位為“”。查尋頁面訪問位為“”的頁面。在查找過程中，那些被訪問的頁所對應(yīng)的訪問位被重新置為 “”。由此可見，實際上這種近似LRU算法，已經(jīng)退化成一種“最近不用”的算法NRU（Not Recently Used）。偽代碼實現(xiàn)void NUR()/最近未使用法void NRU()/最近未使用法 fo

16、r(i=0;iLEN;i+) 模擬周期性將每一頁的計數(shù)器清0如果幀已經(jīng)填滿 若在幀中找到該頁命中，該頁面標(biāo)志計數(shù)器置1退出 否則找到計數(shù)值為0的頁面置換，并將新頁面計數(shù)器置1 若所有計數(shù)值為1，則選首頁置換 若幀未填滿，命中，該頁面標(biāo)志計數(shù)器置1，退出否則，加入空閑幀中，并將新頁面計數(shù)器置1 運(yùn)行結(jié)果演示五、各種算法運(yùn)行綜合比較因為每個算法在運(yùn)行時請求是隨機(jī)分配的，所以要比較不同算法的優(yōu)劣，需要將不同的算法放在一個程序中，并行執(zhí)行，打印在一塊，方便觀察綜上比較，幀較少時，OPT算法命中率較高。其次是LRU。六、實驗心得1：要編程的第一件事情是先把這個算法的思想弄明白，開始編伙伴算法時，沒有考慮

17、合并狀況，沒有設(shè)置對于相同伙伴的合并的判斷位，以至于到了后來只能重新修改結(jié)構(gòu)2：沒搞清楚伙伴的定義，未考慮到伙伴的地址必須塊地址連續(xù)，強(qiáng)行將兩個大小相同，但地址不知道連不連續(xù)的塊合并在一起，最后發(fā)現(xiàn)這樣會導(dǎo)致程序停止運(yùn)行，這個問題一直到寫報告時，將書上相關(guān)知識寫入文檔時才發(fā)現(xiàn)，然后豁然開朗，改變了合并方式，程序就可以正常運(yùn)行了。這個經(jīng)歷也讓我發(fā)現(xiàn)了邊寫實驗報告，邊編程的重要性，比一味的編程更重要的是，在發(fā)現(xiàn)錯誤時，首先要考慮的是自己的編程思想是否正確，其次才是語法問題。3：合并是一個鏈?zhǔn)絾栴}，不是合并一次就可以的，而是每一次合并都要一直檢測，在更大一級的鏈表中是否有伙伴存在，直到不能合并或者已

18、經(jīng)合并到了最大塊為止。4：位圖法是一種很好的標(biāo)志位方法。有了它可以很方便的尋找空閑塊，并進(jìn)行相關(guān)的合并分配操作。用二進(jìn)制的思想考慮問題，有時候可以事半功倍。5：很久以前是老師強(qiáng)制我們在編程前先畫流程圖，做為作業(yè)的一部分，現(xiàn)在，我發(fā)現(xiàn)先畫個流程圖或者先寫個偽代碼能讓人先對程序的整體框架有一個把握，就像樹的主干一樣。如果流程圖畫對了的話，接下來把程序的具體實現(xiàn)填充進(jìn)去，就可以很方便的實現(xiàn)程序功能了。在伙伴算法實現(xiàn)中，因為沒有從全局出發(fā)，導(dǎo)致的反復(fù)的修改程序，讓我體會到了一定要畫出正確的流程圖，或是先寫對偽代碼再進(jìn)行編程的重要性。在實驗報告中，為了簡潔，我沒有附加流程圖，但是將相應(yīng)的偽代碼寫入報告，

19、來表明編程思想。6：下面對于五種頁面的置換算法進(jìn)行了編程實驗。這部分實現(xiàn)起來就比較簡單了，因為老師給出了實現(xiàn)的分析，對于如何入手寫出了詳細(xì)的方法?！皩τ谔摂M存儲區(qū)和內(nèi)存工作區(qū)的不同算法，其中主要的流程：首先用srand( )和rand( )函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。”并給出了具體的例子來幫我們分析實驗。這部分的難點就在于區(qū)分不同的算法，并對各種算法的排序問題和取代給出自己的方法。7：最佳置換算法使用的是最遠(yuǎn)使用的頁面置換，又叫向前看最優(yōu)置換算法。而LRU選擇最長時間沒有使用的頁，這種策略為向后看最優(yōu)頁置換算法。8：LRU置換

20、算法關(guān)于頁幀的排序序列按頁幀上次使用時間來定，有兩種可行方法：計算器和棧。在這次實驗中我選用了計算法方法，這只需要加標(biāo)志位即可，用棧的話還得另外再加操作，比較復(fù)雜。9：在打印各種算法的命中率時，我想按照制表法來打印，結(jié)果發(fā)現(xiàn)總是有錯位現(xiàn)象，因為每次請求是隨機(jī)分配，所以無法限定打印方式，總是有錯位現(xiàn)象。10：這次實現(xiàn)，通過編程的實驗，讓我對各種算法的原理了解的更為深刻，同時也熟悉了一下編程的方法，將C編程方法溫習(xí)了一下。溫故而知新，學(xué)到了很多。七、程序源代碼伙伴算法#include#include#include#includestruct node int much; int flag,fla

21、g_left,flag_right; struct node *leftchild,*rightchild,*father;struct IN_T int num; int space; struct node *temp;struct IN_T str20;struct node *root,*temp_root,*temp;struct node *temp_l,*temp_r;int total_space=1024,space_num1025;int apply_num=0,release_num=0,find_space=0,str_lock20;void produce_num()

22、 int i; for(i=0;i0) space_numt-; total_space=total_space-t; return t; else int temp=t; t=t*2; while(t0) space_numt-; int temp_2=t/2; while(temp_2=temp) space_numtemp_2+; temp_2=temp_2/2; total_space=total_space-temp; break; else t=t*2; if(tmuch=space&(head-flag=0) if(space=really_need) head-flag=1;

23、temp=head; else int x=space/really_need; x=x/2; while(x) temp_l=(struct node*)malloc(sizeof(struct node); temp_r=(struct node*)malloc(sizeof(struct node); head-flag=1; head-leftchild=temp_l; head-rightchild=temp_r; temp_l-father=head; temp_l-much=(head-much)/2; temp_l-flag=1; temp_l-leftchild=NULL;

24、temp_l-rightchild=NULL; temp_r-father=head; temp_r-much=(head-much)/2; temp_r-flag=0; temp_r-leftchild=NULL; temp_r-rightchild=NULL; x=x/2; head=head-leftchild; temp=head; search_tree(head-leftchild,space,really_need); search_tree(head-rightchild,space,really_need); void back_to_space(int i) struct

25、node *tempx=(struct node*)malloc(sizeof(struct node); int or_not=0; total_space=total_space+stri.space; tempx=stri.temp; printf(already release the %d of %dn,stri.space,stri.num); tempx-flag=0; space_numtempx-much+; tempx=tempx-father; if(tempx) if(tempx-leftchild-flag=0) tempx-flag_left=0; else tem

26、px-flag_left=1; if(tempx-rightchild-flag=0) tempx-flag_right=0; else tempx-flag_right=1; while(tempx!=NULL)&(tempx-flag+(tempx-flag_left)+(tempx-flag_right)=1) tempx-flag=0; tempx-flag_left=tempx-flag_right=0; space_num(tempx-leftchild)-much=space_num(tempx-leftchild)-much-2; space_numtempx-much+; t

27、empx-leftchild=tempx-rightchild=NULL; tempx=tempx-father; if(tempx) if(tempx-leftchild-flag=0) tempx-flag_left=0; else tempx-flag_left=1; if(tempx-rightchild-flag=0) tempx-flag_right=0; else tempx-flag_right=1; int how_much_space(int a) if(a512) return 1024; if(a256) return 512; if(a128) return 256;

28、 if(a64) return 128; if(a32) return 64; if(a16) return 32; if(a8) return 16; if(a4) return 8; if(a2) return 4; if(a1) return 2; else return 1;DWORD WINAPI release() while(1) Sleep(rand()%3); if(apply_num) int c=rand()%apply_num; if(str_lockc=0) back_to_space(c); str_lockc=1; release_num+; if(release

29、_num=20) break; DWORD WINAPI apply() while(1) Sleep(rand()%3); int t=how_much_space(strapply_num.num); /need how big space if(total_space=t) int have_space=search(t); if(have_space) temp_root=root; search_tree(temp_root,have_space,t); strapply_num.space=t; strapply_num.temp=(struct node*)malloc(size

30、of(struct node); strapply_num.temp=temp; printf(already give %d the %dn,strapply_num.num,t); apply_num+; if(apply_num=20) break; else printf(There is no space to apply %d because of fragment.n,strapply_num.num); Sleep(2000); else printf(There is no much space to apply %d!n,strapply_num.num); Sleep(2

31、000); int main() DWORD ThreadId1,ThreadId2; HANDLE ThreadHandle1,ThreadHandle2; /根節(jié)點的初始化，貌似方法比較2。 root=(struct node*)malloc(sizeof(struct node); temp_root=(struct node*)malloc(sizeof(struct node); temp=(struct node*)malloc(sizeof(struct node); root-father=NULL; root-leftchild=NULL; root-rightchild=N

32、ULL; root-much=1024; root-flag=0; root-flag_left=root-flag_right=0; temp_root=root; / srand (time(NULL); produce_num(); int i; for(i=0;i1025;i+) space_numi=0; space_num1024=1; for(i=0;i20;i+) str_locki=0; ThreadHandle1=CreateThread(NULL,0,release,NULL,0,&ThreadId1); ThreadHandle2=CreateThread(NULL,0

33、,apply,NULL,0,&ThreadId2); if(ThreadHandle1!=NULL) WaitForSingleObject(ThreadHandle1,INFINITE); CloseHandle(ThreadHandle1); if(ThreadHandle2!=NULL) WaitForSingleObject(ThreadHandle2,INFINITE); CloseHandle(ThreadHandle2); system(pause);最佳置換算法#include#include#include#includeint str320;/320條指令 int page

34、32;/物理內(nèi)存頁int page_lock32;int count_num32;int error=0;int already_given=0; int find_page(int i) return (i/10);int page_schelduing_opt(int num) int i,j,m,n,count,find; for(i=0;inum;i+) pagei=-1;page_locki=0; for(i=0;i320;i+) find=0; count=0; for(j=0;jalready_given;j+) if(pagej=stri) find=1; break; if(

35、!find) error+; for(n=0;nnum;n+) page_lockn=0; if(already_givennum) pagealready_given=stri; already_given+; else for(m=i;m320&(countnum);m+) for(n=0;nnum;n+) if(strm=pagen) page_lockn=1; count+; for(n=0;nnum;n+) if(page_lockn=0) pagen=stri; break; main() int i,j,m,n,upper,least,x=0; for(i=0;i320;i+) stri=i; i=0; upper=319; least=0; srand (time(NULL); while(i80) /every time 4 orders m=least+rand()%(upper+1); /m /執(zhí)行m+1 strx+=find_page(m+1); n=lea