虛擬存儲器實驗報告.doc

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