實(shí)驗(yàn)三模擬操作完整系統(tǒng)的頁面置換(共23頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上院 系：計(jì) 算 機(jī) 學(xué) 院實(shí)驗(yàn)課程： 操作系統(tǒng)實(shí)驗(yàn)項(xiàng)目：模擬操作系統(tǒng)的頁面置換指導(dǎo)老師： 陳紅英老師 開課時(shí)間：2011 2012年度第 2學(xué)期專 業(yè)：網(wǎng)絡(luò)工程班 級(jí)：10級(jí)學(xué) 生：yuth學(xué) 號(hào)：*華南師范大學(xué)教務(wù)處一、綜合設(shè)計(jì)實(shí)驗(yàn)題目 模擬操作系統(tǒng)的頁面置換1、 采用一種熟悉的語言，如 C、PASCAL 或C+ 等，編制程序，最好關(guān)鍵代碼采用C/C+ ，界面設(shè)計(jì)可采用其它自己喜歡的語言。 矚慫潤厲釤瘞睞櫪廡賴。2、 模擬操作系統(tǒng)采用OPT、FIFO 和LRU算法進(jìn)行頁面置換的過程。 3、 設(shè)程序中地址范圍為0 到32767 ，采用隨機(jī)數(shù)生成256 個(gè)指令地址，滿足

2、50%的地址是順序執(zhí)行，25%向前跳，25% 向后跳。聞創(chuàng)溝燴鐺險(xiǎn)愛氌譴凈。為滿足上述條件，可采取下列方法：設(shè)d0=10000，第 n個(gè)指令地址為dn，第 n+1 個(gè)指令地址為dn+1 ，n的取值范圍為0 到255。每次生成一個(gè) 1 到1024范圍內(nèi)的隨機(jī)數(shù)a，如果a落在1 到512 范圍內(nèi)，則dn+1 =dn+1。如果a落在513 到768范圍內(nèi)，則設(shè)置dn+1 為1 到dn范圍內(nèi)一個(gè)隨機(jī)數(shù)。如果a落在769 到1024范圍內(nèi)，則設(shè)置dn+1 為dn到32767 范圍內(nèi)一個(gè)隨機(jī)數(shù)。 殘騖樓諍錈瀨濟(jì)溆塹籟。例如：srand(); 初始化一個(gè)隨機(jī)函數(shù)。 a0 10*rand()/32767*25

3、5+1;a1=10*rand()/32767*a0語句可用來產(chǎn)生a0與a1中的隨機(jī)數(shù)?；虿捎靡韵路绞剑海?）通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令。指令的地址按下述原則生成： A：50%的指令是順序執(zhí)行的 B：25%的指令是均勻分布在前地址部分 C：25%的指令是均勻分布在后地址部分 具體的實(shí)施方法是： A：在0，319的指令地址之間隨機(jī)選取一起點(diǎn)m B：順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令 C：在前地址0,m+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m' D：順序執(zhí)行一條指令，其地址為m'+1 E：在后地址m'+2，3 19中隨機(jī)選取一條指令并執(zhí)行 F：重

4、復(fù)步驟A-E，直到320次指令 （2）將指令序列變換為頁地址流 設(shè)：頁面大小為1K； 用戶內(nèi)存容量4頁到32頁； 用戶虛存容量為32K。 在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為： 第 0 條-第 9 條指令為第0頁（對(duì)應(yīng)虛存地址為0，9） 第10條-第19條指令為第1頁（對(duì)應(yīng)虛存地址為10，19） 第310條-第319條指令為第31頁（對(duì)應(yīng)虛存地址為310，319） 按以上方式，用戶指令可組成32頁。 4、 頁面大小的取值范圍為1K，2K，4K，8K，16K 。按照頁面大小將指令地址轉(zhuǎn)化為頁號(hào)。對(duì)于相鄰相同的頁號(hào)，合并為一個(gè)。 釅錒極額閉鎮(zhèn)檜豬訣錐。

5、5、 分配給程序的內(nèi)存塊數(shù)取值范圍為1 塊，2 塊，直到程序的頁面數(shù)。 6、 分別采用OPT、FIFO 和LRU算法對(duì)頁號(hào)序列進(jìn)行調(diào)度，計(jì)算出對(duì)應(yīng)的缺頁中斷率。 7、 打印出頁面大小、分配給程序的內(nèi)存塊數(shù)、算法名、對(duì)應(yīng)的缺頁中斷率。 8、 分析頁面大小和分配給程序的內(nèi)存塊數(shù)對(duì)缺頁中斷率的影響。分析不同的頁面置換算法的調(diào)度性能。 二、中文摘要 這次實(shí)驗(yàn)是模擬操作系統(tǒng)的頁面置換，分別用先進(jìn)先出算FIFO、最近最久未使用算法LRU和最佳淘汰算法OPT等三種置換算法來管理管理內(nèi)存塊，并打印出頁面大小、分配給程序的內(nèi)存塊數(shù)、算法名、對(duì)應(yīng)的缺頁中斷率。最后對(duì)不同算法的調(diào)度性能。彈貿(mào)攝爾霽斃攬磚鹵廡。三、關(guān)

6、鍵詞 頁面置換 FIFO LRU OPT四、前言本實(shí)驗(yàn)的目的及要求1、掌握操作系統(tǒng)的頁面置換過程，加深理解頁式虛擬存儲(chǔ)器的實(shí)現(xiàn)原理。 2、掌握用隨機(jī)數(shù)生成滿足一定條件的指令地址流的方法。 3、掌握頁面置換的模擬方法。 五、實(shí)驗(yàn)設(shè)計(jì) （一）、需求分析1、 用一種熟悉的語言，如C、PASCAL或C+等，編制程序。2、 分別采用OPT、FIFO和LRU算法對(duì)頁號(hào)序列進(jìn)行調(diào)度。（二）、設(shè)計(jì)流程1、 根據(jù)實(shí)驗(yàn)?zāi)繕?biāo)，明確實(shí)驗(yàn)的具體任務(wù)；2、 編寫程序?qū)崿F(xiàn)頁面置換；3、 運(yùn)行程序，調(diào)試；4、 記錄并分析實(shí)驗(yàn)結(jié)果。（二）、關(guān)鍵技術(shù)根據(jù)實(shí)驗(yàn)要求，使得50%的指令地址是順序執(zhí)行，25%向前跳，25% 向后跳?？刹?/p>

7、取下列方法：設(shè)d0=10000，第 n個(gè)指令地址為dn，第 n+1 個(gè)指令地址為dn+1 ，n的取值范圍為0 到255。每次生成一個(gè) 1 到1024范圍內(nèi)的隨機(jī)數(shù)a，如果a落在1 到512 范圍內(nèi)，則dn+1 =dn+1。如果a落在513 到768范圍內(nèi)，則設(shè)置dn+1 為1 到dn范圍內(nèi)一個(gè)隨機(jī)數(shù)。如果a落在769 到1024范圍內(nèi)，則設(shè)置dn+1 為dn到32767 范圍內(nèi)一個(gè)隨機(jī)數(shù)。開一個(gè)數(shù)組address來記錄指令地址，另一個(gè)數(shù)組pagenum記錄指令地址轉(zhuǎn)換后所在的頁，這樣就得到原始程序的頁面訪問序列。然后將相鄰相同的頁號(hào)合并。謀蕎摶篋飆鐸懟類蔣薔。（三）詳細(xì)設(shè)計(jì) 1、設(shè)計(jì)算法流程圖

8、2、數(shù)據(jù)結(jié)構(gòu)/程序類，指明程序地址范圍和指令數(shù)class Programpublic:int AddressSize; /（0AddressSize） int StructureNum; /指令數(shù)public:Program(int m,int i)AddressSize=m;StructureNum=i; ;/內(nèi)存塊節(jié)點(diǎn)類class PhysicsPageNode public:int have; /是否有頁面占領(lǐng)該內(nèi)存塊，-1代表沒有，1代表有int Page_Num; /第幾頁占領(lǐng)該內(nèi)存塊int Elapsed_Time; /內(nèi)存塊的存在時(shí)間PhysicsPageNode *next;

9、public:PhysicsPageNode()have=-1;Elapsed_Time=0; /剛生成時(shí)內(nèi)存塊的存在時(shí)間為0next = NULL;/模擬操作系統(tǒng)的頁面置換類class PageReplacement private:int *address; /存儲(chǔ)所有指令的地址 int *pagenum; /存儲(chǔ)所有指令地址所在的頁float instr_sum; /指令數(shù)public:int pagesize; /頁面大小(字節(jié))int mem_sum; /程序獲得的內(nèi)存塊數(shù)public:void transform(Program p); /分析程序p，得到指令頁面序列,初始化有關(guān)成

10、員廈礴懇蹣駢時(shí)盡繼價(jià)騷。PhysicsPageNode* getphysage(PhysicsPageNode* pp,int pn); /檢查指定頁是否已在內(nèi)存塊中煢楨廣鰳鯡選塊網(wǎng)羈淚。PhysicsPageNode* getfreepage(PhysicsPageNode* pp); /檢查是否有空的內(nèi)存塊鵝婭盡損鵪慘歷蘢鴛賴。PhysicsPageNode* getlongelapsed(PhysicsPageNode* pp); /獲得最長時(shí)間沒訪問的內(nèi)存塊籟叢媽羥為贍僨蟶練淨(jìng)。 void FIFO(); /先進(jìn)先出算法 void LRU(); /最近最久未使用算法 void OPT(

11、); /最佳淘汰算法;六、實(shí)驗(yàn)實(shí)現(xiàn)（一）、實(shí)驗(yàn)主要硬件軟件環(huán)境 32位PC機(jī)，VC+6.0（二）、主要功能模塊分析1、獲得頁號(hào)序列模塊分析程序指令，獲得頁面序列。Dn為地址，D0=10000；Dn的地址獲取方法：循環(huán)隨機(jī)一個(gè)數(shù)a1,1024;落在1-512，Dn=D（n-1）+1，513-768，Dn 為1D（n-1）的隨機(jī)數(shù)。如果a落在769-1024，Dn為D（n-1）到所分析程序地址大小（32767）。然后根據(jù)頁面大小，將各指令地址化為頁面號(hào)。最后將相鄰相同的頁號(hào)合并。預(yù)頌圣鉉儐歲齦訝驊糴。/*分析程序，功能：得到指令頁面序列。入口參數(shù)：一個(gè)程序類，指明程序地址范圍和指令數(shù)。*/void

12、 PageReplacement:transform(Program p)Sleep(10);srand(time(0);int a,q,r;/初始化instr_sum=p.StructureNum; address = new int instr_sum; /存儲(chǔ)所有指令的地址滲釤嗆儼勻諤鱉調(diào)硯錦。 pagenum = new int instr_sum;cout<<"原程序頁面鏈:"<<endl;address0=10000; /指令起始地址pagenum0=address0/pagesize; /指令地址所在的頁cout<<page

13、num0<<ends;for(int i=1;i<instr_sum;i+) a = 1 + rand()%1024;if(a<=512) /順序執(zhí)行addressi=addressi-1+1;else if(a<=768) /向前跳addressi=1 + rand()%(addressi-1);else if(a<=1024) /向后跳addressi = addressi-1 + rand()%(p.AddressSize-addressi-1);鐃誅臥瀉噦圣騁貺頂廡。/求得指令所在的頁q=addressi/pagesize;r=addressi%pa

14、gesize; if(r)pagenumi=q;else pagenumi=q-1;cout<<pagenumi<<ends; /輸出指令所在的頁面cout<<endl<<endl;/將相鄰相同的頁號(hào)合并int *newpagenum = new int instr_sum; newpagenum0=pagenum0;cout<<"將相鄰相同的頁號(hào)合并為一個(gè)后的頁面鏈"<<endl; int j=0; for(i=1;i<instr_sum;i+)if(newpagenumj != pagenum

15、i)j+;newpagenumj=pagenumi; instr_sum = j+1; /新的頁面訪問串的訪問數(shù)(j為下標(biāo)，所以加一) cout<<"新的頁面訪問串的訪問數(shù)="<<instr_sum<<endl;for(i=0;i<instr_sum;i+) pagenumi = newpagenumi; cout<<pagenumi<<ends; /輸出指令所在的頁面cout<<endl<<endl;2、FIFO模塊先進(jìn)先出算法：設(shè)置缺頁中斷次數(shù)breaktimes，當(dāng)中斷發(fā)生時(shí)，+

16、1. 獲取可用內(nèi)存塊數(shù)，根據(jù)內(nèi)存塊數(shù)，申請對(duì)應(yīng)長度的內(nèi)存塊鏈。然后進(jìn)行調(diào)度。內(nèi)存塊內(nèi)有一項(xiàng)Elapsed_Time作為存在時(shí)間，每調(diào)用一次，所有內(nèi)存塊得存在時(shí)間+。剛被調(diào)入時(shí)間為1.當(dāng)要淘汰時(shí)，比較在內(nèi)存塊中的各存在時(shí)間，把存在時(shí)間最大的換掉。擁締鳳襪備訊顎輪爛薔。/內(nèi)存頁的存在時(shí)間，為存在時(shí)間。void PageReplacement:FIFO() float breaktimes=0;int i,pn;/生成內(nèi)存頁空間PhysicsPageNode *head = new PhysicsPageNode();PhysicsPageNode *p=head,*ppn=NULL; for(i=

17、1;i<mem_sum;i+) /mem_sum:程序獲得的內(nèi)存塊數(shù)PhysicsPageNode *np=new PhysicsPageNode();p->next=np;p=np; for(i=0;i<instr_sum;i+)pn=pagenumi; /需要載入的頁號(hào)(這里還沒簡化)ppn=getphysage(head,pn); / 是否存在內(nèi)存頁if(ppn=NULL) / 載入的頁不在內(nèi)存頁中/缺頁中斷次數(shù)+1breaktimes+;/獲取空閑頁面ppn=getfreepage(head);if(ppn!=NULL) /獲取成功ppn->Page_Num=p

18、n;ppn->Elapsed_Time=1; else /獲取空閑頁失敗.置換存在時(shí)間最大的頁面ppn=getlongelapsed(head);ppn->Page_Num=pn;ppn->Elapsed_Time=1;else /載入的頁在內(nèi)存頁中。 /什么也不發(fā)生/將在內(nèi)存中的頁存在時(shí)間+1PhysicsPageNode *copp=head; while(copp!=NULL)copp->Elapsed_Time+;copp=copp->next;/輸出算法，頁面大小，缺頁中斷率等。cout<<"頁面大小="<<p

19、agesize<<" 內(nèi)存塊數(shù)="<<mem_sum<<" FIFO 缺頁中斷率="贓熱俁閫歲匱閶鄴鎵騷。cout.precision(2); /輸出小數(shù)點(diǎn)后兩位cout<<breaktimes/instr_sum<<endl;3、LRU模塊最近最久未使用頁面置換算法（LRU）LRU在固定時(shí)間內(nèi)將各個(gè)內(nèi)存頁的存在時(shí)間復(fù)位，增加計(jì)數(shù)器counter，每到30將所有內(nèi)存頁存在時(shí)間復(fù)位。并且每使用一次內(nèi)存頁，將是把存在時(shí)間減3個(gè)單位，這樣存在時(shí)間最大的就是最久未使用的。壇摶鄉(xiāng)囂懺蔞鍥鈴氈淚。void

20、PageReplacement:LRU() float breaktimes=0;int i,pn;/生成內(nèi)存頁空間PhysicsPageNode *head=new PhysicsPageNode();PhysicsPageNode *p=head,*ppn; for(i=1;i<mem_sum;i+)PhysicsPageNode *np=new PhysicsPageNode();p->next=np;p=np;int counter=0; /計(jì)數(shù)器for(i=0;i<instr_sum;i+)counter+;/增加計(jì)數(shù)器counter，每到30將所有內(nèi)存頁存在時(shí)間復(fù)

21、位。if(counter>30)counter=0; /計(jì)數(shù)器歸零PhysicsPageNode *q=head;/內(nèi)存頁存在時(shí)間復(fù)位while(q!=NULL)q->Elapsed_Time=1;q=q->next;pn=pagenumi; /需要載入的頁號(hào)ppn=getphysage(head,pn); / 是否存在內(nèi)存頁if(ppn=NULL)/ 載入的頁不在內(nèi)存頁中/缺頁中斷次數(shù)+1breaktimes+;/獲取空閑頁面ppn=getfreepage(head);if(ppn!=NULL) /獲取成功ppn->Page_Num=pn;ppn->Elapse

22、d_Time=1; else /獲取空閑頁失敗/存在時(shí)間最大的為最久未使用。因?yàn)槊渴褂靡淮问菧p3個(gè)單位的存在時(shí)間。 ppn=getlongelapsed(head); ppn->Page_Num=pn;ppn->Elapsed_Time=1;else /載入的頁在內(nèi)存頁中。 ppn->Elapsed_Time=ppn->Elapsed_Time-3;/輸出算法，頁面大小，缺頁中斷率等。cout<<"頁面大小="<<pagesize<<" 內(nèi)存塊數(shù)="<<mem_sum<<

23、" LRU 缺頁中斷率="蠟變黲癟報(bào)倀鉉錨鈰贅。cout.precision(2); /輸出小數(shù)點(diǎn)后兩位cout<<breaktimes/instr_sum<<endl;4、OPT模塊最優(yōu)淘汰算法OPT當(dāng)頁面存在時(shí)，存在時(shí)間參數(shù)不變化。當(dāng)要淘汰一個(gè)頁時(shí)，預(yù)讀未來50頁，并用內(nèi)存頁的存在時(shí)間計(jì)數(shù)。然后淘汰存在時(shí)間最短的。計(jì)數(shù)方法，未來出現(xiàn)1次，將存在時(shí)間減3個(gè)單位。到時(shí)候存在時(shí)間值最大的將被淘汰。 買鯛鴯譖曇膚遙閆擷凄。void PageReplacement:OPT() float breaktimes=0;int i,pn;/生成內(nèi)存頁空間Phys

24、icsPageNode *head=new PhysicsPageNode();PhysicsPageNode *p=head,*ppn=NULL; for(i=1;i<mem_sum;i+)PhysicsPageNode *np=new PhysicsPageNode();p->next=np;p=np;for(i=0;i<instr_sum;i+)pn=pagenumi; /需要載入的頁號(hào)ppn=getphysage(head,pn); / 是否存在內(nèi)存頁if(ppn=NULL) / 載入的頁不在內(nèi)存頁中/缺頁中斷次數(shù)+1breaktimes=breaktimes+1;/

25、獲取空閑頁面ppn=getfreepage(head);if(ppn!=NULL) /獲取成功ppn->Page_Num=pn;ppn->Elapsed_Time=1; else /獲取空閑頁失敗/在這里增加預(yù)讀未來50個(gè)頁面計(jì)數(shù)。int nextpage=i+1; /從下一頁開始算。int endread=i+50;int nextpagenum;PhysicsPageNode *temp;temp=head;/先復(fù)位。while(temp!=NULL)temp->Elapsed_Time=1;temp=temp->next;/下面預(yù)讀未來頁面并計(jì)數(shù)for(;(nex

26、tpage<endread)&&(nextpage<=instr_sum);nextpage+)綾鏑鯛駕櫬鶘蹤韋轔糴。nextpagenum=pagenumnextpage;temp=getphysage(head,nextpagenum);if(temp!=NULL)temp->Elapsed_Time=temp->Elapsed_Time-3;ppn=getlongelapsed(head);ppn->Page_Num=pn;ppn->Elapsed_Time=1;else /載入的頁在內(nèi)存頁中。 /在OPT中無需變化。 /輸出算法，頁面

27、大小，缺頁中斷率等。cout<<"頁面大小="<<pagesize<<" 內(nèi)存塊數(shù)="<<mem_sum<<" OPT 缺頁中斷率="驅(qū)躓髏彥浹綏譎飴憂錦。cout.precision(2); /輸出小數(shù)點(diǎn)后兩位cout<<breaktimes/instr_sum<<endl;5、輔助模塊/檢查指定頁是否在已內(nèi)存塊中PhysicsPageNode* PageReplacement:getphysage(PhysicsPageNode* pp,int pn)貓蠆驢繪燈鮒誅髏貺廡。PhysicsPageNode *tmp=pp;while(tmp!=NULL)if(tmp->Page_Num = pn)return tmp; /找到對(duì)應(yīng)的頁并返回elsetmp=tmp->next;return NULL; /沒找到，返回NULL/檢查是否有空的內(nèi)存塊PhysicsPageNode* PageReplacement:getfreepage(PhysicsPageNode* pp)鍬籟饗逕瑣筆襖鷗婭薔。P