頁面調(diào)度實驗報告

1、設(shè)計題目課 程 設(shè) 計 主 要 內(nèi)容一、課程設(shè)計的性質(zhì)、目的和作用頁式虛擬存儲器實現(xiàn)的一個難點是設(shè)計頁面調(diào)度（置換）算法，即將新頁面調(diào)入內(nèi)存時，如果內(nèi)存 中所有的物理頁都已經(jīng)分配出去，就要按某種策略來廢棄某個頁面，將其所占據(jù)的物理頁釋放出來， 供新頁面使用。本實驗的目的是通過編程實現(xiàn)幾種常見的頁面調(diào)度（置換）算法，加深讀者對頁面思 想的理解。二、課程設(shè)計的具體內(nèi)容先進先出調(diào)度算法最近最少調(diào)度算法最近最不常用調(diào)度算法 SECOND二次機會調(diào)度算法各種算法同時顯示三、課程設(shè)計的要求用自己熟悉的一種數(shù)據(jù)庫開發(fā)工具，VC+等。指 建議：從學(xué)生的工作態(tài)度、工作量，設(shè)計（論文）的創(chuàng)造性、學(xué)術(shù)性、實用性及書

2、面表達能力等方面給出評價。導(dǎo)教師評估簽名：200年 月 日、實驗內(nèi)容頁面調(diào)度算法目前有許多頁面調(diào)度算法，本實驗主要涉及先進先出調(diào)度算法、最近最少調(diào)度算 法、最近最不常用調(diào)度算法。本實驗使用頁面調(diào)度算法時作如下假設(shè)，進程在創(chuàng)建時 由操作系統(tǒng)為之分配一個固定數(shù)目物理頁，執(zhí)行過程中物理頁的數(shù)目和位置不會改 變。也即進程進行頁面調(diào)度時只能在分到的幾個物理頁中進行。下面對各調(diào)度算法的思想作一介紹。先進先出調(diào)度算法先進先出調(diào)度算法根據(jù)頁面進入內(nèi)存的時間先后選擇淘汰頁面，先進入內(nèi)存的頁面先淘汰，后進入內(nèi)存的后淘汰。本算法實現(xiàn)時需要將頁面按進入內(nèi)存的時間先后組 成一個隊列，每次調(diào)度隊首頁面予以淘汰。最近最少調(diào)

3、度算法先進先出調(diào)度算法沒有考慮頁面的使用情況，大多數(shù)情況下性能不佳。根據(jù)程序 執(zhí)行的局部性特點，程序一旦訪問了某些代碼和數(shù)據(jù)，則在一段時間內(nèi)會經(jīng)常訪問他 們，因此最近最少用調(diào)度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近 一段時間以來最少使用的頁面予以淘汰。 算法實現(xiàn)時需要為每個頁面設(shè)置數(shù)據(jù)結(jié)構(gòu)記 錄頁面自上次訪問以來所經(jīng)歷的時間。最近最不常用調(diào)度算法由于程序設(shè)計中經(jīng)常使用循環(huán)結(jié)構(gòu)，根據(jù)程序執(zhí)行的局部性特點，可以設(shè)想在一 段時間內(nèi)經(jīng)常被訪問的代碼和數(shù)據(jù)在將來也會經(jīng)常被訪問，顯然這樣的頁面不應(yīng)該被淘汰。最近最不常用調(diào)度算法總是根據(jù)一段時間內(nèi)頁面的訪問次數(shù)來選擇淘汰頁面， 每次淘汰訪問次數(shù)

4、最少的頁面。算法實現(xiàn)時需要為每個頁面設(shè)置計數(shù)器，記錄訪問次 數(shù)。計數(shù)器由硬件或操作系統(tǒng)自動定時清零。缺頁調(diào)度次數(shù)和缺頁中斷率、缺頁置換率計算缺頁中斷次數(shù)是缺頁時發(fā)出缺頁中斷的次數(shù)。缺頁中斷率=缺頁中斷次數(shù)/總的頁面引用次數(shù)*100%缺頁調(diào)度次數(shù)是調(diào)入新頁時需要進行頁面調(diào)度的次數(shù)缺頁置換率=缺頁調(diào)度次數(shù)/總的頁面引用次數(shù)*100%二、總體設(shè)計1、算法的原理說明FIFO先進先出調(diào)度算法：當頁面框滿時，最早進來的頁面調(diào)出；LRU最近最少使用調(diào)度算法：當頁面框滿時，最近最少使用的頁面調(diào)出LFU最近最不常用調(diào)度算法：當頁面框滿時，最近最不常用的頁面調(diào)出SECOND二次機會調(diào)度算法:當頁面框滿時，頁面調(diào)入

5、時R=0,當被訪問時R = 1。發(fā)生替換時，先檢查最 老的頁面的R,如果為0則調(diào)出，若為1，則令R = 0，修改裝入時間，如剛被裝 入一樣。然后繼續(xù)搜索可替換頁面2、設(shè)計思路本設(shè)計模擬實現(xiàn)中有以下幾點：1 ：數(shù)據(jù)由data.txt和data2.txt.文檔中提取。Txt文檔必須放入與程序dubug相同的目 錄。如果想添加數(shù)據(jù)，可以在此目錄下新添文本文檔。2：輸入txt文件名自動獲取頁面號3：用隊列來表示內(nèi)存，且最多只能存放3個頁面4：每次執(zhí)行算法結(jié)束，第一行輸出每次淘汰的頁面號，若未淘汰則用表示。第二行 顯示缺頁的總次數(shù)。5：本程序涉及4個類，頁面類，算法類，隊列結(jié)點類，隊列類。三、模擬實現(xiàn)1

6、：程序所需C+的庫#include#include#include#include /文件輸入輸出函數(shù)庫#include異常處理2：從Txt文檔中提取頁面號If stream infile(T_name);while(!infile.eof()( /eof()，infile 的文件尾狀態(tài)infileArray_data; /讀數(shù)據(jù)的時候因為數(shù)據(jù)間有一個空格才能完整的讀 出，T_datai = Array_data;if(infile.eof() break;i+;T_num+;if(infile.eof() break;3:頁面類定義class page 頁面類public:int pagen

7、umber;頁面號int R; /此頁面被調(diào)入時間，初次調(diào)入為零。每次調(diào)度R值加1；若命中則變回0；int hit; /命中次數(shù)page()pagenumber = 0;R = 0;hit = 0;4:隊列結(jié)點類定義class Nodepublic:page data;Node *link;5算法類class Algorithmpublic:Node *next0;int total;/缺頁的總頁數(shù)int total_hit;/命 中次數(shù)public:Algorithm()(total = 0;total_hit = 0;void FIFO(int T_data,int T_num); /先進

8、先出算法void LRU(int T_data,int T_num); /最近最少使用調(diào)度算法void LFU(int T_data,int T_num);/最近最不常用調(diào)度算法void SECOND(int T_data,int T_num);/二 次機會算法;6隊列類class Queue(public:int num;隊列中元素個數(shù)Node *front; /指向頭節(jié)點指針Node *rear; /指向尾節(jié)點指針public:Queue()(front = NULL;rear = NULL;num = 0;Queue();void add(page add_data); /入隊page

9、putout();出隊void Exchange(page data); /若隊列中含有此頁，則將此頁與隊尾交換位置bool look(page datas); 查看是否有相同項void output(); /輸出矩陣page ChooseOut(page N1); /將隊中某項出隊;7：算法實現(xiàn)函數(shù)void Algorithm:FIFO(int T_data,int T_num)( /先進先出算法Queue Q1; 內(nèi)存中的頁面Queue Q2; 被置換出去的頁面Queue FIFO_Q; /將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊列中Node *next;page out;page T_x;/for(

10、int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊列中T_x.pagenumber = T_datai;FIFO_Q.add(T_x);/next = FIFO_Q.front;while(next != NULL)(if(Q1.num data);total = total + 1;else(if(Q1.look(next-data) = false)(Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);else(if(Q

11、1.look(next-data) = false)(out = Q1.putout();Q2.add(out);Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);next = next-link;coutendl;coutFIFO 算法:endl;cout”每次淘汰的頁面號:”；Q2.output();coutendl;cout缺頁中斷total_hitendl;cout置換中斷totalendl;cout缺頁中斷率”total_hit/(t

12、otal_hit+total)endl;cout置換中斷率total/(total_hit+total)endl;coutendl;/void Algorithm:LRU(int T_data,int T_num)/最近最少使用調(diào)度算法Queue Q1; 內(nèi)存中的頁面Queue Q2; 被置換出去的頁面Queue FIFO_Q; /將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊列中Node *next;page out;page T_x;/for(int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊列中 T_x.pagenumber = T_datai;FIFO_Q.add(T_x);/ne

13、xt = FIFO_Q.front;while(next != NULL)if(Q1.num data);total = total + 1;elseif(Q1.look(next-data) = false)Q1.add(next-data);total = total + 1;elseQ1.Exchange(next-data); /若命中則將其置換的隊尾，如同剛?cè)腙?total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);elseif(Q1.look(next-data) = false)out = Q1.putout();

14、Q2.add(out);Q1.add(next-data);total = total + 1;else(Q1.Exchange(next-data); /若命中則將其置換的隊尾，如同剛?cè)腙?total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);next = next-link;coutendl;coutLRU 算法:endl;cout”每次淘汰的頁面號:”；Q2.output();coutendl;cout缺頁中斷total_hitendl;cout置換中斷totalendl;cout缺頁中斷率total_hit/(total

15、_hit+total)endl;cout置換中斷率total/(total_hit+total)endl;coutendl;/void Algorithm:LFU(int T_data,int T_num)(/最近最不常用調(diào)度算法每次瀏覽的頁面入隊，頁面號不同。當使用LFU算法時先查找隊列中是否有該項，若有則出隊Queue Q1; 內(nèi)存中的頁面Queue Q2; 被置換出去的頁面Queue F_Q; 將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊列中Node *next,*next2;page out;page T_x;int min;/for(int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣

16、轉(zhuǎn)到隊列中 T_x.pagenumber = T_datai;F_Q.add(T_x);/next = F_Q.front;while(next != NULL)if(Q1.num data);total = total + 1;else(if(Q1.look(next-data) = false)(Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;next2 = Q1.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = nex

17、t2-link;next2-data.hit = next2-data.hit + 1;out.pagenumber = -1;/*Q2.add(out);else(if(Q1.look(next-data) = false)(next2 = Q1.front;min = Q1.front-data.hit;while(next2 != NULL)(if(next2-data.hit data.hit;next2 = next2-link;next2 = Q1.front;while(next2-data.hit != min)(置換出 next2-data 即最近一段時間使用次數(shù)最少的nex

18、t2 = next2-link;out = Q1.ChooseOut(next2-data);Q2.add(out);Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;next2 = Ql.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = next2-link;next2-data.hit = next2-data.hit + 1;out.pagenumber = -1;/* Q2.add(out);next = next-l

19、ink;coutendl;coutLFU 算法:endl;cout”每次淘汰的頁面號:”；Q2.output();coutendl;cout缺頁中斷total_hitendl;cout置換中斷totalendl;cout缺頁中斷率total_hit/(total_hit+total)endl;cout置換中斷率total/(total_hit+total)endl;coutendl;void Algorithm:SECOND(int T_data,int T_num)/二次機會算法Queue Q1; 內(nèi)存中的頁面Queue Q2; 被置換出去的頁面Queue FIFO_Q; /將文檔中的數(shù)構(gòu)成

20、的矩陣轉(zhuǎn)到隊列中Node *next,*next2;page out;page T_x;/for(int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊列中 T_x.pagenumber = T_datai;FIFO_Q.add(T_x);/next = FIFO_Q.front;while(next != NULL)if(Q1.num data);total = total + 1;else(if(Q1.look(next-data) = false)(Q1.add(next-data);total = total + 1;else(total_hit = total_hi

21、t + 1;next2 = Q1.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = next2-link;next2-data.R = 1;out.pagenumber = -1;/*Q2.add(out);else(if(Q1.look(next-data) = false)(next2 = Q1.front;while(next2 != NULL)(if(next2-data.R = 1)( next2-data.R = 0; Q1.Exchange(next2-data);else(out = Q1.p

22、utout();Q2.add(out);Q1.add(next-data);total = total + 1;break;next2 = Q1.front;else(total_hit = total_hit + 1;next2 = Q1.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = next2-link;next2-data.R = 1;out.pagenumber = -1；/*Q2.add(out);next = next-link;coutendl;coutSECOND 算法:endl;cout

23、”每次淘汰的頁面號:”；Q2.output();coutendl;cout缺頁中斷total_hitendl;cout置換中斷totalendl;cout缺頁中斷率”total_hit/(total_hit+total)endl;cout置換中斷率total/(total_hit+total)endl;coutendl;8：主函數(shù)void main()(coutendlendlendl;coutendl;cout虛擬存儲管理器的頁面調(diào)度endl;coutendl;cout07信息與計算科學(xué)2班endl;cout陶弘杰20074704endl;cout2009.12.7endl;coutendl;coutendl;int x = 9;while(x != 0)(cout 1:FIFO 算法;2:LRU算法；3:LFU 算法endl;cout 4:SECOND算法；5:應(yīng)用全部算法；0:退出”x;if(x = 0 ) break;int T_data258;int T_num = 0;char T_name50;int Array_data ;cout= 1 & x = 5)(coutT_na