操作系統(tǒng).課程設(shè)計(jì)--頁面置換算法模擬設(shè)計(jì)

1、<p>　　操作系統(tǒng)課程設(shè)計(jì)報(bào)告</p><p>　　題目：頁面置換算法模擬設(shè)計(jì)</p><p>　　2013年1月16日</p><p><b>　　一、實(shí)驗(yàn)?zāi)康?</b></p><p>　　1、熟悉內(nèi)存分頁管理策略。</p><p>　　2、了解頁面置換的算法。</p>

2、<p>　　3、掌握一般常用的調(diào)度算法。</p><p>　　4、根據(jù)方案使算法得以模擬實(shí)現(xiàn)。 </p><p>　　5、鍛煉知識的運(yùn)用能力和實(shí)踐能</p><p>　　本次課程設(shè)計(jì)是在學(xué)習(xí)完《操作系統(tǒng)教程》后進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，讓學(xué)生更好的掌握操作系統(tǒng)的原理以及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解加強(qiáng)對學(xué)生的動手能力。

3、熟悉頁面置換算法及其實(shí)現(xiàn)，引入計(jì)算機(jī)操作性能評價方法的概念。</p><p><b>　　二、實(shí)驗(yàn)要求</b></p><p>　　計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。</p><p>　　A.FIFO先進(jìn)先出的算法</p><p>　　B.LRU最近最少使用算法</p><p>　　

4、Ｃ．OPT最佳淘汰算法（先淘汰最不常用的頁地址）</p><p><b>　　三、開發(fā)環(huán)境</b></p><p><b>　　軟件環(huán)境：w7</b></p><p>　　編程軟件 ：VC++6.0</p><p>　　運(yùn)行平臺： Win32 </p><p>　　硬

5、 件： 普通個人pc機(jī)</p><p><b>　　四．設(shè)計(jì)思想：</b></p><p><b>　　OPT基本思想：</b></p><p>　　是用一維數(shù)組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數(shù)組next[mSIZE]記錄物理塊中對應(yīng)頁面的最后訪問時間。每當(dāng)發(fā)

6、生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面。</p><p><b>　　FIFO基本思想：</b></p><p>　　是用隊(duì)列存儲內(nèi)存中的頁面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁時，就從隊(duì)頭刪除一頁，而從隊(duì)尾加入缺頁?；蛘呓柚o助數(shù)組time[mSIZE]記錄物理塊中對應(yīng)頁面的進(jìn)入時間，每次需要置換時換出進(jìn)入時

7、間最小的頁面。</p><p><b>　　LRU基本思想：</b></p><p>　　是用一維數(shù)組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數(shù)組flag[10]標(biāo)記頁面的訪問時間。每當(dāng)使用頁面時，刷新訪問時間。發(fā)生缺頁時，就從物理塊中頁面標(biāo)記最小的一頁，調(diào)出該頁，換入所缺的實(shí)驗(yàn)過程：</p><p

8、><b>　　流程圖：</b></p><p><b>　　源程序</b></p><p>　　#include<iostream.h></p><p>　　#include <stdlib.h></p><p>　　#include <time.h><

9、;/p><p>　　#include <stdio.h></p><p>　　#define L 320</p><p>　　int M; //內(nèi)存塊</p><p>　　struct Pro//定義一個結(jié)構(gòu)體</p><p><b>　　{</b></p>

10、<p>　　int num,time;</p><p><b>　　};</b></p><p>　　Input(int m,Pro p[L])//打印頁面走向狀態(tài)</p><p><b>　　{ </b></p><p>　　cout<<"請輸入頁面走向長度(

11、2~320)：";</p><p><b>　　do</b></p><p><b>　　{</b></p><p><b>　　cin>>m;</b></p><p>　　if(m>320||m<2)cout<<"實(shí)際頁

12、面長度須在2～320之間;請重新輸入： ";</p><p>　　else break;</p><p>　　}while(1);</p><p><b>　　int i,j;</b></p><p>　　j=time(NULL);//取時鐘時間</p><p>　　srand(j);/

13、/以時鐘時間x為種子，初始化隨機(jī)數(shù)發(fā)生器</p><p>　　cout<<"輸出隨機(jī)數(shù): ";</p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　p[i].num=rand( )%10;//產(chǎn)生1到10之間的隨即數(shù)放到

14、數(shù)組p中</p><p>　　p[i].time=0;</p><p>　　cout<<p[i].num<<" ";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　r

15、eturn m;</b></p><p><b>　　}</b></p><p>　　void print(Pro *page1)//打印當(dāng)前的頁面</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[M];</p><p&

16、gt;　　page=page1;</p><p>　　for(int i=0;i<M;i++)</p><p>　　cout<<page[i].num<<" ";</p><p>　　cout<<endl;</p><p><b>　　}</b></p&

17、gt;<p>　　int Search(int e,Pro *page1 )//尋找內(nèi)存塊中與e相同的塊號</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[M];</p><p>　　page=page1;</p><p>　　for(int i=0;i&

18、lt;M;i++)if(e==page[i].num)return i;//返回i值</p><p>　　return -1;</p><p><b>　　}</b></p><p>　　int Max(Pro *page1)//尋找最近最長未使用的頁面</p><p><b>　　{</b><

19、;/p><p>　　Pro *page=new Pro[M];</p><p>　　page=page1;</p><p>　　int e=page[0].time,i=0;</p><p>　　while(i<M) //找出離現(xiàn)在時間最長的頁面</p><p><b>　　{

20、</b></p><p>　　if(e<page[i].time) e=page[i].time;</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　for( i=0;i<M;i++)if(e==page[i].tim

21、e)return i;//找到離現(xiàn)在時間最長的頁面返回其塊號</p><p>　　return -1;</p><p><b>　　}</b></p><p>　　int Count(Pro *page1,int i,int t,Pro p[L])//記錄當(dāng)前內(nèi)存塊中頁面離下次使用間隔長度</p><p><b&g

22、t;　　{</b></p><p>　　Pro *page=new Pro[M];</p><p>　　page=page1;</p><p>　　int count=0;</p><p>　　for(int j=i;j<L;j++)</p><p><b>　　{</b><

23、;/p><p>　　if(page[t].num==p[j].num )break;//當(dāng)前頁面再次被訪問時循環(huán)結(jié)束</p><p>　　else count++;//否則count+1</p><p><b>　　}</b></p><p>　　return count;//返回count的值</p><

24、;p><b>　　}</b></p><p>　　int main()</p><p><b>　　{ </b></p><p><b>　　int c;</b></p><p>　　int m=0,t=0;</p><p>　　float n

25、=0;</p><p><b>　　Pro p[L];</b></p><p>　　m=Input(m,p);//調(diào)用input函數(shù)，返回m值</p><p>　　cout<<"請輸入物理塊數(shù)數(shù)m(4～32): ";</p><p><b>　　do</b><

26、;/p><p><b>　　{ </b></p><p><b>　　cin>>M;</b></p><p>　　if(M>32||M<4)</p><p>　　cout<<"內(nèi)存塊m須在4～32之間，請重新輸入m： ";</p>&

27、lt;p>　　else break;</p><p>　　}while(1); </p><p>　　Pro *page=new Pro[M];</p><p><b>　　do{</b></p><p>　　for(int i=0;i<M;i++)//初試化頁面基本情況</p><

28、p><b>　　{</b></p><p>　　page[i].num=0;</p><p>　　page[i].time=m-1-i;</p><p><b>　　}</b></p><p>　　i=0; </p><p>　　cout<<&

29、quot;1:FIFO頁面置換"<<endl;</p><p>　　cout<<"2:LRU頁面置換"<<endl;</p><p>　　cout<<"3:OPT頁面置換"<<endl;</p><p>　　cout<<"按其它鍵結(jié)束程

30、序；"<<endl;</p><p><b>　　cin>>c;</b></p><p>　　system("cls");</p><p>　　if(c==1)//FIFO頁面置換</p><p><b>　　{</b></p>&

31、lt;p><b>　　n=0;</b></p><p>　　cout<<" ****************************************** "<<endl;</p><p>　　cout<<endl;</p><p>　　cout<&

32、lt;" FIFO算法頁面置換情況如下: "<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<" ****************************************** "<<end

33、l;</p><p>　　while(i<m)</p><p><b>　　{</b></p><p>　　if(Search(p[i].num,page)>=0) //當(dāng)前頁面在內(nèi)存中</p><p>　　{ cout<<p[i].num<<"

34、"; //輸出當(dāng)前頁p[i].num</p><p>　　cout<<"不缺頁"<<endl;</p><p>　　i++; //i加1</p><p><b>　　}</b></p><p>　　else

35、 //當(dāng)前頁不在內(nèi)存中</p><p><b>　　{ </b></p><p>　　if(t==M)t=0;</p><p><b>　　else </b></p><p><b>　　{</b></p><p>

36、;　　n++; //缺頁次數(shù)加1</p><p>　　page[t].num=p[i].num; //把當(dāng)前頁面放入內(nèi)存中</p><p>　　cout<<p[i].num<<" ";</p><p>　　print(page);

37、 //打印當(dāng)前頁面</p><p>　　t++; //下一個內(nèi)存塊</p><p>　　i++; //指向下一個頁面</p><p><b>　　}</b></p><p><b>　　}&

38、lt;/b></p><p><b>　　}</b></p><p>　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl;</p><p>　　cout<<"不缺頁次數(shù)："&l

39、t;<(m-n)<<" 命中率："<<(1-n/m)<<endl; </p><p><b>　　}</b></p><p>　　if(c==2)//LRU頁面置換</p><p><b>　　{</b></p><p><b&

40、gt;　　n=0;</b></p><p>　　cout<<" ****************************************** "<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<"

41、 LRU算法頁面置換情況如下: "<<endl; </p><p>　　cout<<endl;</p><p>　　cout<<" ****************************************** "<<endl;</p><

42、p>　　while(i<m)</p><p><b>　　{</b></p><p><b>　　int a;</b></p><p>　　t=Search(p[i].num,page);</p><p>　　if(t>=0)//如果已在內(nèi)存塊中</p><p&

43、gt;<b>　　{</b></p><p>　　page[t].time=0;//把與它相同的內(nèi)存塊的時間置0</p><p>　　for(a=0;a<M;a++)</p><p>　　if(a!=t)page[a].time++;//其它的時間加1</p><p>　　cout<<p[i].num&

44、lt;<" ";</p><p>　　cout<<"不缺頁"<<endl;</p><p><b>　　}</b></p><p>　　else //如果不在內(nèi)存塊中</p><p><b>　　{ &l

45、t;/b></p><p>　　n++; //缺頁次數(shù)加1</p><p>　　t=Max(page); //返回最近最久未使用的塊號賦值給t</p><p>　　page[t].num=p[i].num; //進(jìn)行替換</p><p>　　page[t].time=0;

46、 //替換后時間置為0</p><p>　　cout<<p[i].num<<" ";</p><p>　　print(page);</p><p>　　for(a=0;a<M;a++)</p><p>　　if(a!=t)page[a].time++; /

47、/其它的時間加1</p><p><b>　　} </b></p><p><b>　　i++; </b></p><p><b>　　}</b></p><p>　　cout<<"缺頁次數(shù)："<<n<<"

48、 缺頁率："<<n/m<<endl; </p><p>　　cout<<"不缺頁次數(shù)："<<(m-n)<<" 命中率："<<(1-n/m)<<endl; </p><p><b>　　}</b></p><p

49、>　　if(c==3)//OPT頁面置換</p><p><b>　　{</b></p><p><b>　　n=0;</b></p><p>　　cout<<" ****************************************** "<<en

50、dl;</p><p>　　cout<<endl;</p><p>　　cout<<" OPT算法置換情況如下:"<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<" *******

51、*********************************** "<<endl;</p><p>　　while(i<m)</p><p><b>　　{</b></p><p>　　if(Search(p[i].num,page)>=0)//如果已在內(nèi)存塊中</p><p&g

52、t;<b>　　{</b></p><p>　　cout<<p[i].num<<" ";</p><p>　　cout<<"不缺頁"<<endl;</p><p><b>　　i++;</b></p><p>

53、<b>　　}</b></p><p>　　else//如果不在內(nèi)存塊中</p><p><b>　　{</b></p><p><b>　　int a=0;</b></p><p>　　for(t=0;t<M;t++)</p><p>　　if(

54、page[t].num==0)a++;//記錄空的內(nèi)存塊數(shù)</p><p>　　if(a!=0) //有空內(nèi)存塊</p><p><b>　　{</b></p><p><b>　　int q=M;</b></p><p>　　for(t=0;t<M;t++)</p><p

55、>　　if(page[t].num==0&&q>t)q=t;//把空內(nèi)存塊中塊號最小的找出來</p><p>　　page[q].num=p[i].num;</p><p><b>　　n++;</b></p><p>　　cout<<p[i].num<<" ";<

56、/p><p>　　print(page);</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p>

57、<p>　　int temp=0,s;</p><p>　　for(t=0;t<M;t++)//尋找內(nèi)存塊中下次使用離現(xiàn)在最久的頁面</p><p>　　if(temp<Count(page,i,t,p))</p><p><b>　　{</b></p><p>　　temp=C

58、ount(page,i,t,p);</p><p><b>　　s=t;</b></p><p>　　}//把找到的塊號賦給s</p><p>　　page[s].num=p[i].num;</p><p><b>　　n++;</b></p><p>　　cout

59、<<p[i].num<<" ";</p><p>　　print(page);</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&

60、lt;p><b>　　}</b></p><p>　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl;</p><p>　　cout<<"不缺頁次數(shù)："<<(m-n)<<&q

61、uot; 命中率："<<(1-n/m)<<endl; </p><p><b>　　}</b></p><p>　　}while(c==1||c==2||c==3);</p><p><b>　　return 0;</b></p><p><b>　　

62、}</b></p><p><b>　　實(shí)驗(yàn)截圖：</b></p><p><b>　　運(yùn)行開始</b></p><p><b>　　FIFO頁面置換</b></p><p><b>　　LRU頁面置換</b></p><p

63、><b>　　OPT頁面置換</b></p><p><b>　　實(shí)驗(yàn)小結(jié)：</b></p><p>　　通過頁面置換算法模擬程序的程序設(shè)計(jì)讓我對虛擬頁式存儲管理有了更深的了解。搞懂了頁面置換的思想以后，對編程就有了一定的思路。但是卻遇到了許多困難程序的調(diào)試也出現(xiàn)了許多的錯誤。但是經(jīng)過幾次上機(jī)操作在老師的指導(dǎo)和幫助下程序最終還是完成了。