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

1、計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)報告題目:模擬設(shè)計(jì)頁面調(diào)度編程專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級：12級計(jì)算機(jī)二班姓名:朱紹鋒學(xué) 號：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)康?二、基本知識介紹12.1、 分頁12.2、頁面調(diào)入策略12.3、從何調(diào)入頁面22.4、頁面調(diào)入過程22.5、頁面置換算法 3三、頁面置換算法框架及 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)存分頁管理策略；2）掌握調(diào)頁策略；

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

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

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

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

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

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

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

9、換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支 持硬件。為了了解一個進(jìn)程在內(nèi)存中的各個頁面各有多少時間未被進(jìn) 程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有寄存器或者堆棧的支持。下一頁面是否在物理快中物理快是否裝 滿開始頁面裝入物理塊中N三、頁面置換算法框架及 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; /*記錄頁面號*/int time; /*記錄調(diào)入內(nèi)存時間*/Page; /*頁面邏輯結(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)存中停留最久的頁面，默認(rèn)狀態(tài)下為最早調(diào)入的頁面*/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;/*判斷頁面是否已在內(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)入頁面 */ 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)存單元中的頁面*/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缺頁次數(shù)為：%6dn缺頁率：%16.6f",K+1,(float)(K+1)/N);prin tf("nAre you continuin g!t ?"); while(getchar()='y');-13 -四