虛擬存儲器實驗報告.doc

佛山科學技術(shù)學院實 驗 報 告課程名稱 操作系統(tǒng)原理實驗 實驗項目 虛擬存儲器 專業(yè)班級 姓 名 學 號 指導教師 成 績 日 期 一、實驗目的1、了解虛擬存儲器的基本原理和實現(xiàn)方法。2、掌握幾種頁面置換算法。二、實驗內(nèi)容設計模擬實現(xiàn)采用不同內(nèi)外存調(diào)度算法進行頁面置換，并計算缺頁率。三、實驗原理內(nèi)存在計算機中的作用很大，電腦中所有運行的程序都需要經(jīng)過內(nèi)存來執(zhí)行，如果執(zhí)行的程序很大或很多，就會導致內(nèi)存消耗殆盡。為了解決這個問題，Window中運用了虛擬內(nèi)存技術(shù)，即拿出一部分硬盤空間來充當內(nèi)存使用，當內(nèi)存占用完時，電腦就會自動調(diào)用硬盤來充當內(nèi)存，以緩解內(nèi)存的緊張。虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。它是采用一定的方法將一定的外存容量模擬成內(nèi)存，同時對程序進出內(nèi)存的方式進行管理，從而得到一個比實際內(nèi)存容量大得多的內(nèi)存空間，使得程序的運行不受內(nèi)存大小的限制。虛擬存儲區(qū)的容量與物理主存大小無關(guān)，而受限于計算機的地址結(jié)構(gòu)和可用磁盤容量。虛擬內(nèi)存的設置主要有兩點，即內(nèi)存大小和分頁位置，內(nèi)存大小就是設置虛擬內(nèi)存最小為多少和最大為多少；而分頁位置則是設置虛擬內(nèi)存應使用那個分區(qū)中的硬盤空間。（一）頁式虛擬存儲器在頁式虛擬存儲系統(tǒng)中，將程序按統(tǒng)一的大小劃分成多個頁，同時也將虛擬存儲器劃分為同樣大小的頁，其中虛擬空間的頁稱為虛頁（邏輯頁），而主存空間的頁稱為實頁（物理頁），并對這些頁按地址從低到高的順序編號。在編程時，程序的虛地址由高位字段的虛頁號和低位字段的頁內(nèi)地址兩部分組成，虛頁號標識頁。虛地址到實地址之間的變換是由頁表來實現(xiàn)的。頁表是一張存放在主存中的虛頁號和實頁號的對照表，記錄著程序的虛頁調(diào)入主存時被安排在主存中的位置。若計算機采用多道程序工作方式，則可為每個用戶作業(yè)建立一個頁表，硬件中設置一個頁表基址寄存器，存放當前所運行程序的頁表的起始地址。頁表中的每一行記錄了與某個虛頁對應的若干信息，包括虛頁號、裝入位和實頁號等。頁表基址寄存器和虛頁號拼接成頁表索引地址。根據(jù)這個索引地址可讀到一個頁表信息字，然后檢測頁表信息字中裝入位的狀態(tài)。若裝入位為1，表示該頁面已在主存中，將對應的實頁號與虛地址中的頁內(nèi)地址相拼接就得到了完整的實地址；若裝入位為0，表示該頁面不在主存中，于是要啟動I/O系統(tǒng)，把該頁從輔存中調(diào)入主存后再供CPU使用，若主存已滿，還需要使用替換算法替換頁。（二）頁面置換算法在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。幾中常見的頁面置換方法如下：1. 最佳置換算法（OPT）：選擇永不使用或是在最長時間內(nèi)不再被訪問（即距現(xiàn)在最長時間才會被訪問）的頁面淘汰出內(nèi)存。2. 先進先出置換算法（FIFO）：選擇最先進入內(nèi)存即在內(nèi)存駐留時間最久的頁面換出到外存。3. 最近最久未使用置換算法（LRU）: 以“最近的過去”作為“最近的將來”的近似，選擇最近一段時間最長時間未被訪問的頁面淘汰出內(nèi)存4. 時鐘置換算法Clock :為進入內(nèi)存的頁面設置一個訪問位，當內(nèi)存中某頁被訪問，訪問位置一，算法在選擇一頁淘汰時，只需檢查訪問位，若為0，則直接換出，若為1，置該訪問位為0，檢測內(nèi)存中的下一個頁面的訪問位。5. 最少使用置換算法（LFU）：在內(nèi)存中為每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。選擇在最近時期使用最少的頁面作為淘汰頁6. 隨機置換算法（S）：產(chǎn)生一個取值范圍在0和N-1之間的隨機數(shù)，該隨機數(shù)即可表示應被淘汰出內(nèi)存的頁面。四、實驗步驟1定義頁表的存儲結(jié)構(gòu)，設置作業(yè)進程所占內(nèi)存空間為640K，頁面大小為1K/2K/4K/8K，隨機生成100個頁面，用于分配頁面大小的內(nèi)存總空間為32K。2初始化進程的頁面引用序列。3選擇下列六種置換算法中的三種編寫程序，進行頁面置換，并計算缺頁次數(shù)和缺頁率。 （1）最佳置換算法（OPT） （2）先進先出置換算法（FIFO）： （3）最近最久未使用算法（LRU） （4）時鐘置換算法（CLOCK） （5）最少使用置換算法（LFU） （6）隨機置換算法（S）4. 使用菜單形式，選擇不同的置換方法，顯示換頁過程、缺頁次數(shù)及缺頁率。五、實驗代碼#include#include#include#define M 3 /內(nèi)存頁數(shù)#define N 20 /頁面引用序列數(shù)#define Myprintf printf(-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-n) /*表格控制*/ /定義頁面的存儲結(jié)構(gòu)typedef struct pageint num; /記錄頁面號int time; /記錄調(diào)入內(nèi)存時間int visitBit; /訪問位Page;Page PM; /內(nèi)存單元數(shù)int cMN; /暫保存內(nèi)存當前的狀態(tài)int queueM=-1,-1,-1; /記錄調(diào)入內(nèi)存的頁面int front=0; /隊列頭指針int current=0;/初始化內(nèi)存單元、緩沖區(qū)void Init(Page *p,int cMN) int i,j; for(i=0;iM;i+) pi.num=-1; pi.time=N-i-1; pi.visitBit=0; for(i=0;iM;i+) for(j=0;jN;j+) cij=-1; /判斷頁面是否已在內(nèi)存中int Equation(int fold,Page *p) int i; for(i=0;iM;i+) if (fold=pi.num) return i; return -1; /先進先出頁面置換算法,加載的頁面已在內(nèi)存中,則/返回0。否則置換出最先調(diào)入內(nèi)存的頁，并返回1int FIFO(int fold,Page *p)int i,y;int val=Equation(fold,p);if(val0) /請求頁面不在內(nèi)存y=queuefront; /最先調(diào)入內(nèi)存的頁出隊queuefront=fold; /加入隊尾front=(front+1)%M;for(i=0;iM;i+)if(y=pi.num)pi.num=fold; /頁面置換break;return 1;return 0;/LRU置換算法/取得在內(nèi)存中停留最久的頁面,默認狀態(tài)下為最早調(diào)入的頁面int GetMax(Page *p) int i; int max=-1; int tag=0; for(i=0;imax) max=pi.time;tag=i; return tag; /LRU核心部分int LRU(int fold,Page *p) int i; int a; a=Equation(fold,p); if (a=0) pa.time=0; for(i=0;iM;i+) if (i!=a) pi.time+;return 0; else a=GetMax(p); pa.num=fold; pa.time=0; for(i=0;iM;i+) if (i!=a) pi.time+;return 1; /時鐘置換算法/取的內(nèi)存中訪問位為0的淘汰頁面int GetClockPage(Page *p)int i;for(i=0;iM;i+)if(0=pcurrent.visitBit)return current;elsepcurrent.visitBit=0;current=(current+1)%M;return current;int Clock(int fold,Page *p)int val;val=Equation(fold,p);if(val0) val=GetClockPage(p);pval.num=fold;pval.visitBit=1;return 1;return 0;/顯示換頁過程void Printf(int a,int q,int k)int i,j;printf(顯示換頁過程:n);Myprintf;for(j=0;jN;j+) printf(%2d |,aj);Myprintf; for(i=0;iM;i+) for(j=0;jN;j+) if(cij=-1) printf(%2c |,32); else printf(%2d |,cij); Myprintf;printf(n調(diào)入隊列為:); for(i=0;ik+1;i+) printf(%3d,qi); printf(n缺頁次數(shù)為：%6dn缺頁率：%16.6fn,k+1,(float)(k+1)/N);printf(n);int Menu()int i;printf(tt*頁面置換算法* n); printf(t 1.先進先出置換算法(FIFO) n);printf(t 2.最近最久未使用算法(LRU) n); printf(t 3.時鐘置換算法(CLOCK) n);printf(t 4.退出 n);printf(tt*請輸入您的選擇*n);scanf(%d,&i);getchar();return i;/主函數(shù)void main()int i,j,flag;int q100; /記錄調(diào)入隊列int k ; /調(diào)入隊列計數(shù)變量int aN=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;while(1)flag=Menu();switch(flag)case 1: /先進先出置換算法(FIFO)Init(P,c);k=-1;for(i=0;iN;i+)if(FIFO(ai,P)q+k=ai; /記錄調(diào)入頁面c0i=ai;for(j=0;jM;j+) cji=Pj.num;Printf(a,q,k);break;case 2: /最近最久未使用算法(LRU)Init(P,c);k=-1;for(i=0;iN;i+)if(LRU(ai,P)q+k=ai; /記錄調(diào)入頁面for(j=0;jM;j+) cji=Pj.num;Printf(a,q,k);break;case 3: /時鐘置換算法(CLOCK)Init(P,c);k=-1;for(i=0;iN;i+)if(Clock(ai,P)q+k=ai; /記錄調(diào)入頁面else /訪問頁已在內(nèi)存,訪問位置1for(j=0;jM;j+)if(ai=Pi.num)Pi.visitBit=1;current=(current+1)%M;for(j=0;jM;j+) cji=Pj.num;Printf(a,q,k);break;case 4:printf(歡迎使用！n);exit(1);break;六、實驗結(jié)果及分析1先進先出置換算法2.最近最久未使用算法3.時鐘置換算法4.