頁面調(diào)度實(shí)驗(yàn)報(bào)告

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

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

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

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

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

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

7、umber;頁面號(hào)int R; /此頁面被調(diào)入時(shí)間，初次調(diào)入為零。每次調(diào)度R值加1；若命中則變回0；int hit; /命中次數(shù)page()pagenumber = 0;R = 0;hit = 0;4:隊(duì)列結(jié)點(diǎn)類定義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); /先進(jìn)

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);/二 次機(jī)會(huì)算法;6隊(duì)列類class Queue(public:int num;隊(duì)列中元素個(gè)數(shù)Node *front; /指向頭節(jié)點(diǎn)指針Node *rear; /指向尾節(jié)點(diǎn)指針public:Queue()(front = NULL;rear = NULL;num = 0;Queue();void add(page add_data); /入隊(duì)page

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

10、int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊(duì)列中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”每次淘汰的頁面號(hào):”；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)到隊(duì)列中Node *next;page out;page T_x;/for(int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊(duì)列中 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); /若命中則將其置換的隊(duì)尾，如同剛?cè)腙?duì) 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); /若命中則將其置換的隊(duì)尾，如同剛?cè)腙?duì) total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);next = next-link;coutendl;coutLRU 算法:endl;cout”每次淘汰的頁面號(hào):”；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)度算法每次瀏覽的頁面入隊(duì)，頁面號(hào)不同。當(dāng)使用LFU算法時(shí)先查找隊(duì)列中是否有該項(xiàng)，若有則出隊(duì)Queue Q1; 內(nèi)存中的頁面Queue Q2; 被置換出去的頁面Queue F_Q; 將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊(duì)列中Node *next,*next2;page out;page T_x;int min;/for(int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣

16、轉(zhuǎn)到隊(duì)列中 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í)間使用次數(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”每次淘汰的頁面號(hào):”；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)/二次機(jī)會(huì)算法Queue Q1; 內(nèi)存中的頁面Queue Q2; 被置換出去的頁面Queue FIFO_Q; /將文檔中的數(shù)構(gòu)成

20、的矩陣轉(zhuǎn)到隊(duì)列中Node *next,*next2;page out;page T_x;/for(int i = 0;i=T_num;i+)/將文檔中的數(shù)構(gòu)成的矩陣轉(zhuǎn)到隊(duì)列中 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、”每次淘汰的頁面號(hào):”；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虛擬存儲(chǔ)管理器的頁面調(diào)度endl;coutendl;cout07信息與計(jì)算科學(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