操作系統(tǒng)FIFO算法簡化版

1、NORTH CHINA UNIVERSITY OF TECHNOLOGY操作系統(tǒng)(2014年秋季學(xué)期)序號(hào)： 實(shí) 驗(yàn) 報(bào) 告系別：計(jì)算機(jī)學(xué)院班級(jí)：姓名： 學(xué)號(hào)：實(shí)驗(yàn)名稱：存儲(chǔ)管理總成績：評(píng)語： 日期：操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱存儲(chǔ)管理實(shí)驗(yàn)序號(hào)2實(shí)驗(yàn)日期2014.12.25實(shí)驗(yàn)人一、實(shí)驗(yàn)?zāi)康?、要求與環(huán)境1目的：（1）通過編寫程序?qū)崿F(xiàn)請(qǐng)求分頁存儲(chǔ)管理的Optimal、FIFO、LRU等頁面置換算法中的一種，掌握虛擬存儲(chǔ)管理中有關(guān)缺頁處理方法等內(nèi)容，鞏固有關(guān)虛擬存儲(chǔ)管理的教學(xué)內(nèi)容。（2）理解內(nèi)存分配原理，特別是以頁面為單位的虛擬內(nèi)存分配方法2.要求：在Windows XP、Windows 2000、W

2、in7、Linux等操作系統(tǒng)下，使用的VC、VB、java或C等編程語言，實(shí)現(xiàn)請(qǐng)求分頁存儲(chǔ)管理的一種頁面置換算法。3.環(huán)境：1. 硬件設(shè)備：PC機(jī)一臺(tái)2. 軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關(guān)的程序開發(fā)環(huán)境，如C C+Java 等編程語言環(huán)境。二、相關(guān)背景知識(shí)關(guān)于操作系統(tǒng)的內(nèi)存管理，如何節(jié)省利用容量不大的內(nèi)存為最多的進(jìn)程提供資源，一直是研究的重要方向。而內(nèi)存的虛擬存儲(chǔ)管理，是現(xiàn)在最通用，最成功的方式 在內(nèi)存有限的情況下，擴(kuò)展一部分外存作為虛擬內(nèi)存，真正的內(nèi)存只存儲(chǔ)當(dāng)前運(yùn)行時(shí)所用得到信息。這無疑極大地?cái)U(kuò)充了內(nèi)存的功能，極大地提高了計(jì)算機(jī)的并發(fā)度。虛擬頁式存儲(chǔ)管理

3、，則是將進(jìn)程所需空間劃分為多個(gè)頁面，內(nèi)存中只存放當(dāng)前所需頁面，其余頁面放入外存的管理方式。常用的頁面置換算法有OPT、FIFO、LRU、Clock、LFU、PBA等。這里重點(diǎn)介紹FIFO、OPT、LRU（1）先進(jìn)先出頁面置換算法（FIFO）FIFO算法這是最早出現(xiàn)的置換算法，該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO

4、算法并不能保證這些頁面不被淘汰。（2）最佳置換算法（OPT）它是由Belady于1966 年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪一個(gè)頁面是未來最長時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，但可以利用此算法來評(píng)價(jià)其它算法。（3）最近最久未使用置換算法（LRU）最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LR

5、U 置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間t,，當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。三、實(shí)驗(yàn)設(shè)計(jì)說明選擇置換算法，先輸入所有頁面號(hào)，為系統(tǒng)分配物理塊，依次進(jìn)行置換：FIFO基本思想：是用隊(duì)列存儲(chǔ)內(nèi)存中的頁面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁時(shí)，就從隊(duì)頭刪除一頁，而從隊(duì)尾加入缺頁?；蛘呓柚o助數(shù)組timemSIZE記錄物理塊中對(duì)應(yīng)頁面的進(jìn)入時(shí)間，每次需要置換時(shí)換出進(jìn)入時(shí)間最小的頁面。物理塊數(shù)：mSize 頁面引用個(gè)數(shù)：pSize，全局靜態(tài)變量物理塊

6、中的頁號(hào)，頁面引用串和輔助數(shù)組并進(jìn)行相關(guān)的初始化。打印函數(shù)print（），核心函數(shù)FIFO（）。缺頁率訪問缺頁次數(shù)/訪問總次數(shù)。四、實(shí)驗(yàn)設(shè)計(jì)的流程圖實(shí)驗(yàn)流程圖：開始初始化設(shè)置輸入分配物理塊，頁面選擇操作FIFO算法YN結(jié)束打印輸出FIFO模塊流程圖：新的指令頁面在物理塊中？中中？內(nèi)存內(nèi)頁面time+1內(nèi)存內(nèi)頁面time+1YN載入新頁面time=0內(nèi)存物理塊滿？N選擇time最大頁面換出Y四、程序代碼#include #include /*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁面號(hào)引用串個(gè)數(shù)*/static int memery10=0; /*物理塊中的

7、頁號(hào)*/static int page100=0; /*頁面號(hào)引用串*/static int temp10010=0; void FIFO();/*置換算法函數(shù)*/void print(unsigned int t);void designBy();/*主函數(shù)*/void main() int i,k,code;system(color 0A);designBy();printf(歡迎使用,請(qǐng)按任意鍵進(jìn)行初始化操作. n);/printf( );getchar();system(cls);system(color 0A);printf(請(qǐng)輸入物理塊的個(gè)數(shù)(M=10)：);scanf_s(%d,

8、&mSIZE);printf(請(qǐng)輸入頁面號(hào)引用串的個(gè)數(shù)(P=100)：);scanf_s(%d,&pSIZE);puts(請(qǐng)依次輸入頁面號(hào)引用串：);for(i=0;ipSIZE;i+) scanf_s(%1d,&pagei);system(cls);system(color 0A); do puts(輸入的頁面號(hào)引用串為：);for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i);getchar();system(cls); while (code!=2);getchar();/顯示設(shè)計(jì)者信息 void designBy()printf(n); p

9、rintf( 實(shí)驗(yàn)：頁面置換算法 n);printf( 班級(jí)： 信安12 n);printf( 姓名： n);printf(n);void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn,pagei);elseprintf(%d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)print

10、f( |%d|,tempij);elseprintf( |0|);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁面在物理塊中*/printf( | |);elseprintf( |%d|,tempij);/*每行顯示20個(gè)*/if(i%20=0)continue;printf(n);printf(-n);printf(缺頁次數(shù)：%dtt,t+mSIZE);printf(缺頁率：%d/%dn,t+mSIZE,pSIZE);prin

11、tf(置換次數(shù)：%dtt,t);printf(n-n);/*先進(jìn)先出頁面置換算法*/void FIFO() int memery10=0; int time10=0; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/ for(i=0;imSIZE;i+)/*前mSIZE個(gè)數(shù)直接放入*/ memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號(hào)是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進(jìn)入物理塊的時(shí)間*/ for(j=0;jmSIZE;j+) tempij=memeryj; e