計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)

1、計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)報(bào)告題目:模擬設(shè)計(jì)頁(yè)面調(diào)度編程專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：12級(jí)計(jì)算機(jī)二班姓名:朱紹鋒學(xué) 號(hào)：12838076趙飛12838064王偉12838039王焱焱12838045劉繼運(yùn)12838061譚兵12838053指導(dǎo)老師：郭偉光二O五年六月安徽農(nóng)業(yè)大學(xué)經(jīng)濟(jì)技術(shù)學(xué)院計(jì)算機(jī)操作系統(tǒng)目錄一、 實(shí)驗(yàn)?zāi)康?二、基本知識(shí)介紹12.1、 分頁(yè)12.2、頁(yè)面調(diào)入策略12.3、從何調(diào)入頁(yè)面22.4、頁(yè)面調(diào)入過(guò)程22.5、頁(yè)面置換算法 3三、頁(yè)面置換算法框架及 LRU算法實(shí)現(xiàn) 7四、 實(shí)驗(yàn)結(jié)果11I安徽農(nóng)業(yè)大學(xué)經(jīng)濟(jì)技術(shù)學(xué)院計(jì)算機(jī)操作系統(tǒng)、實(shí)驗(yàn)?zāi)康?）了解內(nèi)存分頁(yè)管理策略；2）掌握調(diào)頁(yè)策略；

2、3）掌握一般常用的頁(yè)面置換算法；4）選取頁(yè)面置換算法中的典型算法，模擬實(shí)現(xiàn)。二、基本知識(shí)介紹2.1、分頁(yè)分頁(yè)存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁(yè) 面或頁(yè)。2.2、頁(yè)面調(diào)入策略1）、何時(shí)調(diào)入頁(yè)面如果進(jìn)程的許多頁(yè)是存放在外存的一個(gè)連續(xù) 區(qū)域中，則一次調(diào)入若干個(gè)相鄰的頁(yè)，會(huì)比一次調(diào)入一頁(yè)的效率更 高效一些。但如果調(diào)入的一批頁(yè)面中的大多數(shù)都未被訪問(wèn)，則又是 低效的?？刹捎靡环N以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不 久之后便會(huì)被訪問(wèn)的頁(yè)面，預(yù)先調(diào)入內(nèi)存。如果預(yù)測(cè)較準(zhǔn)確，那么， 這種策略顯然是很有吸引力的。 但目前預(yù)調(diào)頁(yè)的成功率僅為50%且 這種策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程

3、序員指出應(yīng)該先調(diào)入哪 些頁(yè)。2）、請(qǐng)求調(diào)頁(yè)策略當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便即提出請(qǐng)求，由OS將其所需頁(yè)面調(diào)入內(nèi)存。由請(qǐng)示調(diào)頁(yè)策略所確定調(diào)入的頁(yè)，是一定會(huì)被訪問(wèn) 的，再加之請(qǐng)求調(diào)頁(yè)策略比較易于實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中， 大多采用此策略。但這種策略每次僅調(diào)入一頁(yè)，故須花費(fèi)較大的系 統(tǒng)開(kāi)銷，增加了磁盤I/O的啟用頻率。2.3、從何處調(diào)入頁(yè)面在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和 用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式， 而事件是采用離散分配方式，故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)

4、應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可 分成如下三種情況：1）、系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入 所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程 有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。2）、系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件， 都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不 必再將它們換出時(shí)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。3）、UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是 未運(yùn)行過(guò)的頁(yè)面，都從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的 頁(yè)面，由于被放在對(duì)換區(qū)，因此在下次時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于 UNIX系統(tǒng)允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)

5、面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無(wú)須再?gòu)膶?duì)換區(qū)調(diào)入。2.4、頁(yè)面調(diào)入過(guò)程每當(dāng)程序所要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁(yè)中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁(yè) 中斷處理程序。該程序通過(guò)查找頁(yè)表，得到該頁(yè)在外在原物理 塊后, 如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存， 然后修改頁(yè)表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中 選出一頁(yè)準(zhǔn)備換出；如果該頁(yè)未被修改過(guò)，可不必將該頁(yè)寫回磁盤； 但如果此頁(yè)已被修改，則必須將它寫回磁盤，然后再把所缺的頁(yè)調(diào) 入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，置其存在位“ 1”，并將此頁(yè)表 項(xiàng)寫入快表中。在缺頁(yè)調(diào)入內(nèi)存后，

6、利用修改后的頁(yè)表，去形成所 要訪問(wèn)數(shù)據(jù)的物理地址，再去訪問(wèn)內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過(guò)程 對(duì)用戶是透明的。2.5、頁(yè)面置換算法在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存而需把它們調(diào) 入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng) 必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)， 送磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè) 頁(yè)面調(diào)出，須根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法 稱為頁(yè)面置換算法(Page_Replacement Algorithms)。一個(gè)好的頁(yè)面 置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后 不再會(huì)訪問(wèn)的頁(yè)面換出，或?qū)⒛切┰谳^長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào) 出。常見(jiàn)置換算法

7、有：1)、最佳置換算法(Optimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的 被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被 訪問(wèn)的頁(yè)面。采用最佳置換算法，通常可保證獲得最低的缺頁(yè)率。但 由于人目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，但可以 利用此算法來(lái)評(píng)價(jià)其它算法。頁(yè)面裝入物理塊中選擇物理塊中距離該頁(yè)表之后最遠(yuǎn)的或不在出現(xiàn)的頁(yè)表與之置換完成2)、先進(jìn)先出(FIFO)頁(yè)面置換算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法

8、實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并3）、LRU置換算法FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情 況。最近最久未使用（LRU置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使 用情況進(jìn)行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況， 只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。 該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn) 字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t,當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用 的頁(yè)面予以淘汰。LRU置

9、換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支 持硬件。為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)面各有多少時(shí)間未被進(jìn) 程訪問(wèn)，以及如何快速地知道哪一頁(yè)是最近最久未使用的頁(yè)面，須有寄存器或者堆棧的支持。下一頁(yè)面是否在物理快中物理快是否裝 滿開(kāi)始頁(yè)面裝入物理塊中N三、頁(yè)面置換算法框架及 LRU算法實(shí)現(xiàn)#i nclude <stdafx.h> #in clude<stdio.h>#in clude<c oni o.h> #defi ne M 3#defi ne N 20#define Mypri ntf-+-+-+-+-|n") /*顯示格式 */typed

10、ef struct pageint num; /*記錄頁(yè)面號(hào)*/int time; /*記錄調(diào)入內(nèi)存時(shí)間*/Page; /*頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/Page bM; /*內(nèi)存單元數(shù)*/in t cMN; /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/int queue100; /* 記錄調(diào)入隊(duì)列*/int K; /*調(diào)入隊(duì)列計(jì)數(shù)變量*/*初始化內(nèi)存單元、緩沖區(qū)*/void In it(Page *b,i nt cMN)int i,j;for(i=0;i<N;i+)bi. num=-1;bi.time=N-i-1;for(i=0;i<M;i+)for(j=0;j<N;j+

11、)cij=-1;/*取得在內(nèi)存中停留最久的頁(yè)面，默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面*/int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;i<M;i+)if(bi.time>max)max=bi.time;tag=i;return tag;/*判斷頁(yè)面是否已在內(nèi)存中*/int Equati on (i nt fold,Page *b)int i;for(i=0;i<M;i+)if (fold=bi. num)return i;return -1;/*LRU核心部分*/void Lru(i nt fold,Page *b)int

12、i;int val;val=Equatio n( fold,b);if (val>=0)bval.time=0; for(i=0;i<M;i+)if (i!=val)bi.time+;elsequeue+K=fold;/* 記錄調(diào)入頁(yè)面 */ val=GetMax(b);bval. num=fold; bval.time=0;for(i=0;i<M;i+)if (i!=val)bi.time+;/*主程序*/int mai n()int aN=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1; int i,j;doK=-1;In it(b, c)

13、;for(i=0;i<N;i+)Lru(ai,b);cOi=ai;/*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/for(j=0;j<M;j+)cji=bj. num;/*結(jié)果輸出*/prin tf(" 內(nèi)存狀態(tài)為：n");Mypri ntf;for(j=0;j<N;j+)prin tf("|%2d ",aj);prin tf("|n");Mypri ntf;for(i=0;i<M;i+)for(j=0;j<N;j+)if(cij=-1)prin tf("|%2c ",32);elseprin tf("|%2d ",cij);prin tf("|n");Mypri ntf;printf("n調(diào)入隊(duì)列為:");for(i=0;i<K+1;i+)prin tf("%3d",queuei);prin tf("n缺頁(yè)次數(shù)為：%6dn缺頁(yè)率：%16.6f",K+1,(float)(K+1)/N);prin tf("nAre you continuin g!t ?"); while(getchar()='y');-13 -四