實(shí)驗(yàn)二報(bào)告-楊先宇

1、北方工業(yè)大學(xué)操作系統(tǒng)實(shí)驗(yàn)報(bào)告學(xué) 生 姓 名 楊 先宇 學(xué) 號(hào)班 級(jí) 計(jì)13-4 實(shí)驗(yàn)名稱儲(chǔ)存管理實(shí)驗(yàn)序號(hào)2實(shí)驗(yàn)日期2015.12.14實(shí)驗(yàn)人楊先宇一、實(shí)驗(yàn)?zāi)康暮鸵笳?qǐng)求頁式存儲(chǔ)管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)?zāi)康氖峭ㄟ^請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法的模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式存儲(chǔ)管理的頁面置換算法。二、相關(guān)背景知識(shí)1.先進(jìn)先出頁面淘汰算法（FIFO）地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁

2、面置換算法。最簡(jiǎn)單的頁面置換算法是先入先出（FIFO）法。優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁面，亦即在內(nèi)存中駐留時(shí)間最久的頁面。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把調(diào)入內(nèi)存的頁面根據(jù)先后次序鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行時(shí)的規(guī)律不適應(yīng)，因?yàn)樵谶M(jìn)程中，有的頁面經(jīng)常被訪問。2.最近最久未使用頁面淘汰法（LRU）關(guān)于操作系統(tǒng)的內(nèi)存管理，如何節(jié)省利用容量不大的內(nèi)存為最多的進(jìn)程提供資源，一直是研究的重要方向。而內(nèi)存的虛擬存儲(chǔ)管理，是現(xiàn)在最通用，最成功的方式 在內(nèi)存有限的情況下，擴(kuò)展一部分外存作為虛擬內(nèi)存，真正的內(nèi)存只存儲(chǔ)當(dāng)前運(yùn)行時(shí)所用得到信息。這無疑極大地?cái)U(kuò)充了內(nèi)存的功能，極大地提高了計(jì)算機(jī)的

3、并發(fā)度。虛擬頁式存儲(chǔ)管理，則是將進(jìn)程所需空間劃分為多個(gè)頁面，內(nèi)存中只存放當(dāng)前所需頁面，其余頁面放入外存的管理方式。然而，有利就有弊，虛擬頁式存儲(chǔ)管理減少了進(jìn)程所需的內(nèi)存空間，卻也帶來了運(yùn)行時(shí)間變長(zhǎng)這一缺點(diǎn)：進(jìn)程運(yùn)行過程中，不可避免地要把在外存中存放的一些信息和內(nèi)存中已有的進(jìn)行交換，由于外存的低速，這一步驟所花費(fèi)的時(shí)間不可忽略。因而，采取盡量好的算法以減少讀取外存的次數(shù)，也是相當(dāng)有意義的事情。三、實(shí)驗(yàn)內(nèi)容1.通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原則生成：1.50%的指令是順序執(zhí)行的；2.25%的指令是均勻分布在前地址部分；3.25%的指令是均勻分布在后地址部分；具體的實(shí)施

4、方法是：1.在0，319的指令地址之間隨機(jī)選取一起點(diǎn)m；2.順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；3.在前地址0，m+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m；4.順序執(zhí)行一條指令，其地址為m+1；5.在后地址m+2, 319中隨機(jī)選取一條指令并執(zhí)行；6.重復(fù)上述步驟15，直到執(zhí)行320次指令。2.將指令序列變換成頁地址流，設(shè)1.頁面大小為1K；2.用戶內(nèi)存容量為4頁到32頁；3.用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中存放的方式為：第0條至第9條指令為第0頁（對(duì)應(yīng)虛存地址為0，9）；第10條至第19條指令為第1頁（對(duì)應(yīng)虛存地址為1

5、0，19）；第310條至第319條指令為第31頁（對(duì)應(yīng)虛存地址為310，319）；按以上方式，用戶指令可以組成32頁。3.計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。1.先進(jìn)先出頁面淘汰算法（FIFO）2.最近最久未使用頁面淘汰法（LRU）命中率=1 - 頁面失效次數(shù)/頁地址流長(zhǎng)度在本實(shí)驗(yàn)中，頁地址流長(zhǎng)度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令對(duì)應(yīng)的頁不在內(nèi)存的次數(shù)。4.隨機(jī)數(shù)產(chǎn)生辦法關(guān)于隨機(jī)數(shù)產(chǎn)生辦法，Linux或UNIX系統(tǒng)提供函數(shù)srand()和rand()，分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。四、關(guān)鍵數(shù)據(jù)結(jié)構(gòu)與函數(shù)的說明1. 全局變量const int maxn = 320; /

6、序列個(gè)數(shù)const int max = maxn +20;/數(shù)組大小const int maxp = max/10; /最大頁數(shù)int instmax;/指令序列int pagemax;/頁地址流int size; /內(nèi)存能容納的頁數(shù)bool inmaxp; /該頁是否在內(nèi)存里，提高效率int pinmaxp; /現(xiàn)在在內(nèi)存里的頁其中in數(shù)組是為了方便直接判斷該頁是否在內(nèi)存里，而不用遍歷內(nèi)存里所有頁來判斷。fault_n用來記錄缺頁次數(shù)。2.隨機(jī)指令序列的產(chǎn)生void produce_inst() int m, n; int num = 0; while(num maxn) m = rand(

7、) % maxn; instnum+ = (m+1)%maxn; if(num = maxn) break; m = (m+2) % maxn; if(m = 0) m = 160; n = rand() % m; instnum+ = (n+1)%maxn; if(num = maxn) break; n = (n+2) % maxn; m = maxn - n; if(m = 0) m = 160; m = rand() % m + n; instnum+ = m; 五、編譯與執(zhí)行過程截圖1先進(jìn)先出頁面淘汰算法（FIFO）2最近最久未使用頁面淘汰法（LRU）六、實(shí)驗(yàn)結(jié)果與分析1先進(jìn)先出頁面

8、淘汰算法（FIFO）FIFO最簡(jiǎn)單的頁置換算法，F(xiàn)IFO的頁置換的算法為每個(gè)頁記錄著該頁調(diào)入內(nèi)存的時(shí)間。當(dāng)必須置換一頁時(shí)，將選擇最舊的頁。注意并不需要記錄調(diào)入一頁的確切時(shí)間，可以創(chuàng)建一個(gè)FIFO隊(duì)列來管理內(nèi)存中的所有頁。隊(duì)列中的首頁將被置換。當(dāng)需要調(diào)入頁時(shí)，將它加入到隊(duì)列的尾部。FIFO的頁置換算法很好理解和實(shí)現(xiàn)，但是，其性能并不是很好。所替代的頁可能是很久以前使用的、現(xiàn)已不再使用的初始化模塊，另一方面，所替代的頁可能包含一個(gè)以前初始化的并且不斷使用的常用變量。2最近最久未使用頁面淘汰法（LRU）LRU置換為每個(gè)頁關(guān)聯(lián)該頁上次使用的時(shí)間。當(dāng)必須置換一次的時(shí)候，LRU選擇最長(zhǎng)時(shí)間沒有使用的頁，這

9、種策略為向后看最優(yōu)頁置換算法。LRU置換算法被認(rèn)為相當(dāng)不錯(cuò)，其主要問題是如何實(shí)現(xiàn)LRU置換，頁幀的排序序列按頁幀上次使用時(shí)間來定，有兩種可行方法：計(jì)算器 為每個(gè)頁表項(xiàng)關(guān)聯(lián)一個(gè)使用時(shí)間域，并為CPU增加一個(gè)邏輯時(shí)鐘或者計(jì)數(shù)器。對(duì)每次內(nèi)存引用，計(jì)算器都會(huì)增加，每次內(nèi)存引用的時(shí)候時(shí)鐘寄存器的內(nèi)容會(huì)被復(fù)制到相應(yīng)頁所對(duì)應(yīng)的頁表項(xiàng)的使用時(shí)間域內(nèi)。用這種方式就得到每頁的最近使用時(shí)間。置換具有最小時(shí)間的頁。這種方案需要搜索頁表已經(jīng)查找LRU也，且每次內(nèi)存訪問都要寫入內(nèi)存。在改變頁表時(shí)，因CPU調(diào)度，也必須保持時(shí)間。必須考慮時(shí)鐘溢出。棧 每當(dāng)引用一個(gè)頁，該頁就從棧中刪除并放在頂部。這樣，棧頂部總是最近使用的頁，

10、棧底部總是LRU頁。由于必須是從棧中刪除項(xiàng)，所以，該?？蓪?shí)現(xiàn)為具有頭部指針和尾指針的雙向鏈表。雖然每個(gè)更新有點(diǎn)費(fèi)事，但是置換不需要搜索；尾部指針指向棧底部，就是LRU頁。七、調(diào)試時(shí)遇到的問題及解決方法1.隨機(jī)指令序列的產(chǎn)生出現(xiàn)問題：發(fā)現(xiàn)有時(shí)按步驟操作可能會(huì)出錯(cuò)。要及時(shí)排錯(cuò)。八、調(diào)試后的程序源代碼1.先進(jìn)先出頁面淘汰算法（FIFO）#include#include#include#includeint str320;/320條指令 int page32;/物理內(nèi)存頁int page_lock32;int count_num32;int error=0;int already_given=0; i

11、nt 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(!find) error+; for(n=0;nnum;n+) page_lockn=0; if(already_givennum) pagealre

12、ady_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

13、4 orders m=least+rand()%(upper+1); /m /執(zhí)行m+1 strx+=find_page(m+1); n=least+rand()%(m+2);/ m /執(zhí)行n 和 n+1 strx+=find_page(n); strx+=find_page(n+1); n=n+2+rand()%(320-n-2); /執(zhí)行 n strx+=find_page(n); upper=n; least=0; i+; printf(當(dāng)前運(yùn)行的算法是OPT算法n); for(j=4;j33;j+) printf(%d:t,j); error=0; for(i=0;i32;i+) pa

14、gei=0; page_locki=0; i=0; error=0;already_given=0; page_schelduing_opt(j); printf(%.2f,%dt,1-(float)error/320,error); if(j-3)%3=0&j!=4) printf(n); printf(n); system(pause);2最近最久未使用頁面淘汰法（LRU）#include#include#include#includeint str320;/320條指令 int page32;/物理內(nèi)存頁int page_lock32;int count_num32;int error=

15、0;int already_given=0; int find_page(int i) return (i/10);int page_schelduing_fifo(int num) int i,j,m,n,count=0,find; for(i=0;inum;i+) pagei=-1; for(i=0;i320;i+) find=0; count=0; for(j=0;jalready_given;j+) if(pagej=stri) find=1;break; if(find=0) if(already_givennum) pagealready_given=stri; already_g

16、iven+; else if(already_given=num) for(j=0;jalready_given-1;j+) pagej=pagej+1; pagej=stri; error+; 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=least

17、+rand()%(m+2);/ m /執(zhí)行n 和 n+1 strx+=find_page(n); strx+=find_page(n+1); n=n+2+rand()%(320-n-2); /執(zhí)行 n strx+=find_page(n); upper=n; least=0; i+; printf(當(dāng)前運(yùn)行的算法是FIFO算法n); for(j=4;j33;j+) printf(%d:t,j); error=0; for(i=0;i32;i+) pagei=0; page_locki=0; i=0; error=0;already_given=0; page_schelduing_fifo(j); printf(%.2f,%dt,1-(float)error/320,error); if(j-3)%3=0&j!=4) print