模擬頁式存儲管理-操作系統(tǒng)課程設(shè)計報告

1、.一、目的和要求1、設(shè)計目的通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法。2、設(shè)計要求根據(jù)模擬的頁式管理設(shè)計，掌握在頁式存儲管理中最基本的三種頁面調(diào)度算法 FIFO、LRU 以及 OPT。但在三種算法中均要求在調(diào)度程序中產(chǎn)生的頁面序列是隨機產(chǎn)生的， 而不是人為的輸入， 在執(zhí)行時只需改變頁面的大小及內(nèi)存容量就可以得到不同的頁面序列， 另外還需要說明隨機的性能和其性能可能對算法的影響，并對隨機性要有一定的參數(shù)控制能力。此外，計算并輸出FIFO、LRU 以及OPT 算法在不同內(nèi)存容量下的命中率。根據(jù)方法的執(zhí)行過程， 編寫一個解決上述問題的程序

2、，顯示訪問每個值頁面中的值。具體參數(shù)：訪問串的長度，訪問串，頁面?zhèn)€數(shù)。分別用 3 種不同的方法實現(xiàn)頁面的置換，并輸出相關(guān)信息。二、設(shè)計思路及過程1、概要設(shè)計1.1 問題概述頁腳模擬頁式存儲管理根據(jù)三種不同的置換算法， 依據(jù)其不同的算法方式， 分別計算該算法在不同情況下的命中率，并顯示各頁面的變化情況。1.2 內(nèi)容分析對于該課程設(shè)計中模擬的頁式存儲管理的頁面置換過程，只要掌握其中最基本的三種算法，包括FIFO、 LRU 及 OPT 。 但最重要的一點就是要求產(chǎn)生隨機序列，所以在編寫程序時要采用控制產(chǎn)生隨機值的種子數(shù)函數(shù)，如此能產(chǎn)生隨機的訪問序列。另外，不能在執(zhí)行完一次操作后就只能進行另外一種算法

3、的操作，必須還要有更加詳細的操作， 比如：是否要重新得到新序列？還是要不改變訪問序列而只改變訪問串的內(nèi)存容量？抑或是不操作就退出該算法以進行下一種調(diào)度算法？因此， 在執(zhí)行完每次操作后都必須要有提示語，看是否進入更細節(jié)的操作，還是退出本次算法的操作以進入下一種算法的調(diào)度。2、過程設(shè)計2.1 模塊設(shè)計在下圖的主模塊設(shè)計圖中，只注重描繪了頁式存儲管理的三種主要算法，未描繪出細節(jié)部分。 其中，在執(zhí)行每種算法時都會要求輸入你所需要的訪問串長度、隨機值以及同一種算法的不同內(nèi)存容量，如此就可以得出不同的命中率。另外，在執(zhí)行完該操作后又會出現(xiàn)三條提示語，是重新得到新序列？還是不改變訪問序列只改變訪問串的內(nèi)存容

4、量？抑或是不操作退出以進行下一種調(diào)度算法？這些在下圖中都未一一實現(xiàn)。= 2.2 算法原理分析1模擬頁式存儲管理要學(xué)成功實現(xiàn)算法， 首先要知道各個方法是怎么做的，即原理是怎樣的， 下面是三種算法的原理。FIFO 算法是先進先出，當當前內(nèi)存中沒有正要訪問的頁面時，置換出最先進來的頁面。LRU 算法是最近最久未使用， 當當前內(nèi)存中沒有正要訪問的頁面時，置換出在當前頁面中最近最久沒有使用的頁面。OPT 算法是未來最遠出現(xiàn)，當當前內(nèi)存中沒有正要訪問的頁面時，置換出當前頁面中在未來的訪問頁中最遠出現(xiàn)的頁面或再也不出現(xiàn)的頁面。2.3 程序流程圖本次課程設(shè)計的主要流程是3 種置換算法的流程圖，本人負責(zé)OPT

5、，流程圖如下所示：2模擬頁式存儲管理開始輸入內(nèi)存中分配頁數(shù)據(jù)第一個訪問頁初始化第一列值還有請求訪問頁？NY直接復(fù)制前一列內(nèi)容Y內(nèi)存中是否已存在？N內(nèi)存有空頁？NY直接插入替換內(nèi)存中將來不出現(xiàn)或離當前最遠的頁輸出全部頁面變化情況結(jié)束圖 2.2 OPT 算法流程圖三、數(shù)據(jù)定義int length,num_page,count,seed; /length記錄訪問串的長度，num_page 頁面數(shù)， count 記錄缺頁次數(shù)int result2030,order30,a10;/result記錄結(jié)果 ,order存儲訪問串 ,a 存儲當前頁面中的值int pos1,flag1,flag2,flag3;

6、 /pos1 位置變量， flag1 等為標志變量 char result130; / 記錄缺頁數(shù)組3模擬頁式存儲管理四、核心代碼三種置換算法中只列出本人負責(zé)部分（OPT 算法），具體代碼及注釋如下：void opt()/ 理想型int i,pos10,flag10;/i為 for 循環(huán)控制語句，pos 為位置變量， flag 標志變量while(1)flag1=flag2=0;for(i=0;i<length;i+)/訪問串遍歷if(!search(orderi)/查詢要訪問的頁是否在內(nèi)存中count+;result1i='*'if(anum_page-1!=-1) /

7、表示當前頁面已滿要淘汰一個memset(pos,-1,sizeof(pos);/初始 pos 數(shù)組memset(flag,0,sizeof(flag);/初始 flag 數(shù)組int j,k;for(j=i;j<length;j+)/找當前頁中的值在將來訪問串中對應(yīng)最近位置for( k=0;k<num_page;k+)if(orderj=ak&&flagk=0)posk=j;flagk=1;cout<<endl;int max=-10,max_pos;for( k=0;k<num_page;k+)/找出位置最遠的那個值if(posk=-1)/未出現(xiàn)則

8、跳出，替換該值max_pos=k;break;else if(max<posk)4模擬頁式存儲管理max=posk;max_pos=k;amax_pos=orderi;else / 還有空頁 ,直接調(diào)入內(nèi)存for(int j=0;j<num_page;j+)if(aj=-1)aj=orderi;break;else result1i=' 'for(int j=0;j<num_page;j+)resultji=aj;again();/ 再操作if(flag1=0&&flag2=0)break;其中的查詢函數(shù)search（）具體代碼如下 :bool

9、 search(int n)/ 查找當前內(nèi)存中是否已存在該頁int i;for(i=0;i<num_page;i+)if(ai=n)return true;return false;5模擬頁式存儲管理其中的再操作函數(shù)again（），具體代碼如下：void again()/ 用于再輸入print();int numpage,m;printf("* n");printf("1.重新輸入新序列.n");printf("2. 不改變訪問序列只改變頁面數(shù).n");printf("0. 不操作退出 .n");printf

10、("* n");printf("選擇所要操作 :");scanf("%d",&m);if(m=1)flag1=1;/ 重新輸入init();else if(m=2)flag2=1;cout<<"輸入新頁面數(shù)："cin>>numpage;num_page=numpage;memset(a,-1,sizeof(a);else return ;6模擬頁式存儲管理五、運行截圖根據(jù)不同的分工，限于紙張只列出部分截圖，以下是對OPT 調(diào)度算法的實驗截圖：圖 5.1 相同的內(nèi)存容量下不同的訪問串序

11、列17模擬頁式存儲管理圖 5.2 相同的內(nèi)存容量下不同的訪問串序列2依上圖 5.1 和 5.2 來看，OPT 調(diào)度算法在訪問串長度一致，隨機值不同以致產(chǎn)生不同的訪問串序列時，但頁面數(shù)相同的情況下，所得到的命中率也不同。圖 5.3不同的內(nèi)存容量下相同的訪問串序列在上圖 5.3 中就是對同一訪問串序列進行OPT 調(diào)度，只是改變其頁面的大小，得到了不同的命中率。8模擬頁式存儲管理六、小結(jié)生程序，并說明隨機的性能和其性能可能對算法的影響， 對隨機性要有一定的參數(shù)控制能力；計算并輸出 FIFO 及 LRU 算法在不同內(nèi)存容量下的命中率。做了這么多次課程設(shè)計了， 大致的過程都熟悉了， 每次的動手實踐， 調(diào)

12、動了我們主動學(xué)習(xí)的積極性 , 并引導(dǎo)我們根據(jù)實際編程要求 , 訓(xùn)練自己實際分析問題的能力及編程能力 , 并養(yǎng)成良好的編程習(xí)慣。 通過詳細的實例 , 循序漸進地啟發(fā)我們完成設(shè)計課程設(shè)計將要求。從拿到題目到完成整個編程， 從理論到實踐可以學(xué)到很多很多的東西， 同時不僅可以鞏固了以前所學(xué)過的知識， 而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通過這次課程設(shè)計使我懂得了理論與實際相結(jié)合是很重要的， 只有理論知識是遠遠不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會服務(wù)， 從而提高自己的實際動手能力和獨立思考的能力。 知識的獲得是無止境的，只要你想學(xué)，只要你行動，就一定會有所

13、收獲的?；厥走@兩個星期的課程設(shè)計，盡管很是頭痛，很多都不會，但經(jīng)過努力，我們還是學(xué)了不少知識的。這期間，老師給了我們許多幫助，非常感謝！9模擬頁式存儲管理附錄所有源程序代碼如下：#include<iostream>#include<stdlib.h>using namespace std;int length,num_page,count,seed;int result2030,order30,a10;int pos1,flag1,flag2,flag3;char result130;void init()memset(a,-1,sizeof(a);int i;cout

14、<<"輸入訪問串的長度:"cin>>length;cout<<"輸入種子數(shù)控制產(chǎn)生的隨機值："cin>>seed;srand(seed);cout<<"產(chǎn)生的隨機訪問串:"for(i=0;i<length;i+)/ cin>>orderi;orderi=rand()%10; cout<<orderi<<" "cout<<endl;cout<<"輸入頁面的個數(shù)："cin&g

15、t;>num_page;void print()10模擬頁式存儲管理int i,j;cout<<"(*表示缺頁 )"<<endl;cout<<endl;for( j=0;j<length;j+)printf("%2d ",orderj);cout<<endl;for( i=0;i<num_page;i+)for( j=0;j<length;j+)if(resultij=-1)printf("");elseprintf("%2d ",result

16、ij);cout<<endl;for( j=0;j<length;j+)printf("%2c ",result1j);cout<<endl;cout<<"缺頁率： "<<count<<"/"<<length;printf("=%.1lf",(count*1.0)/(length*1.0)*100);cout<<"%"<<endl;bool search(int n)/ 查找當期內(nèi)存是否已存在i

17、nt i;for(i=0;i<num_page;i+)if(ai=n)return true;return false;void again()/ 用于再輸入print();int numpage,m;printf("* n");printf("1.重新輸入新序列.n");printf("2.不改變訪問序列只改變頁面數(shù).n");printf("0. 不操作退出 .n");printf("* n");printf("選擇所要操作 :");scanf("%d&qu

18、ot;,&m);if(m=1)11模擬頁式存儲管理flag1=1;/ 重新輸入init();else if(m=2)flag2=1;cout<<"輸入新頁面數(shù)："cin>>numpage;num_page=numpage;memset(a,-1,sizeof(a);else return ;void fifo() /先進先出int i,thisn=0;while(1)count=0;flag1=flag2=0;for(i=pos1;i<length;i+)if(!search(orderi)count+;result1i='*&

19、#39;if(anum_page-1!=-1) /表示當前頁面已滿要淘汰一個athisn= orderi;thisn+;if(thisn>=num_page)thisn=0;elsefor(int j=0;j<num_page;j+)if(aj=-1)aj=orderi;break;else result1i=' 'for(int j=0;j<num_page;j+)resultji=aj;12模擬頁式存儲管理again();/ 再操作if(flag1=0&&flag2=0)break;void lru()/ 最久最近沒使用int i,pos1

20、0;while(1)count=0;flag1=flag2=0;memset(pos,-1,sizeof(pos);for(i=pos1;i<length;i+)if(!search(orderi)count+;result1i='*'if(anum_page-1!=-1) /表示當前頁面已滿要淘汰一個int j,k;for( j=0;j<i;j+)/ 查找當前頁中的值對應(yīng)的最近位置for( k=0;k<num_page;k+)if(orderj=ak)posk=j;int min=pos0,min_pos=0;for( k=1;k<num_page;k

21、+)/找出位置最遠的那個if(min>posk)min=posk;min_pos=k;amin_pos=orderi;else / 還有空頁for(int j=0;j<num_page;j+)if(aj=-1)13模擬頁式存儲管理aj=orderi;break;else result1i=' 'for(int j=0;j<num_page;j+)resultji=aj;again();/ 再操作if(flag1=0&&flag2=0)break;void opt()/ 理想型int i,pos10,flag10;while(1)flag1=fl

22、ag2=0;for(i=0;i<length;i+)if(!search(orderi)count+;result1i='*'if(anum_page-1!=-1) /表示當前頁面已滿要淘汰一個memset(pos,-1,sizeof(pos);memset(flag,0,sizeof(flag);int j,k;for(j=i;j<length;j+)/找出當前頁中的值在將來訪問串中對應(yīng)的最近位置for( k=0;k<num_page;k+)if(orderj=ak&&flagk=0)posk=j;flagk=1;cout<<endl;int max=-10,max_pos;for( k=0;k<num_page;k+)/找出位置最遠的那個值14模擬頁式存儲管理if(posk=-1)/未出現(xiàn)則跳出，替換該值max_pos=k;break;else if(max<