計算機工程學院
實驗報告書
課程名：《
操作系統原理A
》
題
目：
虛擬存儲器管理
頁面置換算法模擬實驗
班
級：
學
號：
姓
名：
評語：
成績：
指導教師：
批閱時間：
****年**月**日
一、實驗目的與要求
1.目的：
請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換算法的模擬，有助于理解虛擬存儲技術的特點，并加深對請求頁式虛存管理的頁面調度算法的理解。
2.要求：
本實驗要求使用C語言編程模擬一個擁有若干個虛頁的進程在給定的若干個實頁中運行、并在缺頁中斷發生時分別使用FIFO和LRU算法進行頁面置換的情形。其中虛頁的個數可以事先給定（例如10個），對這些虛頁訪問的頁地址流（其長度可以事先給定，例如20次虛頁訪問）可以由程序隨機產生，也可以事先保存在文件中。要求程序運行時屏幕能顯示出置換過程中的狀態信息并輸出訪問結束時的頁面命中率。程序應允許通過為該進程分配不同的實頁數，來比較兩種置換算法的穩定性。
二、實驗說明
1．設計中虛頁和實頁的表示
本設計利用C語言的結構體來描述虛頁和實頁的結構。
pn
pfn
time
pn
pfn
next
虛頁結構
實頁結構
在虛頁結構中，pn代表虛頁號，因為共10個虛頁，所以pn的取值范圍是0—9。pfn代表實頁號，當一虛頁未裝入實頁時，此項值為-1；當該虛頁已裝入某一實頁時，此項值為所裝入的實頁的實頁號pfn。time項在FIFO算法中不使用，在LRU中用來存放對該虛頁的最近訪問時間。
在實頁結構中中，pn代表虛頁號，表示pn所代表的虛頁目前正放在此實頁中。pfn代表實頁號，取值范圍（0—n-1）由動態指派的實頁數n所決定。next是一個指向實頁結構體的指針，用于多個實頁以鏈表形式組織起來，關于實頁鏈表的組織詳見下面第4點。
2．關于缺頁次數的統計
為計算命中率，需要統計在20次的虛頁訪問中命中的次數。為此，程序應設置一個計數器count，來統計虛頁命中發生的次數。每當所訪問的虛頁的pfn項值不為-1，表示此虛頁已被裝入某實頁內，此虛頁被命中，count加1。最終命中率=count/20*100%。
3．LRU算法中“最近最久未用”頁面的確定
為了能找到“最近最久未用”的虛頁面，程序中可引入一個時間計數器countime，每當要訪問一個虛頁面時，countime的值加1，然后將所要訪問的虛頁的time項值設置為增值后的當前countime值，表示該虛頁的最后一次被訪問時間。當LRU算法需要置換時，從所有已分配實頁的虛頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應該將它置換出去。
4．算法中實頁的組織
因為能分配的實頁數n是在程序運行時由用戶動態指派的，所以應使用鏈表組織動態產生的多個實頁。為了調度算法實現的方便，可以考慮引入free和busy兩個鏈表：free鏈表用于組織未分配出去的實頁，首指針為free_head，初始時n個實頁都處于free鏈表中；busy鏈表用于組織已分配出去的實頁，首指針為busy_head，尾指針為busy_tail，初始值都為null。當所要訪問的一個虛頁不在實頁中時，將產生缺頁中斷。此時若free鏈表不為空，就取下鏈表首指針所指的實頁，并分配給該虛頁。若free鏈表為空，則說明n個實頁已全部分配出去，此時應進行頁面置換：對于FIFO算法要將busy_head
所指的實頁從busy鏈表中取下，分配給該虛頁，然后再將該實頁插入到busy鏈表尾部；對于LRU算法則要從所有已分配實頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個實頁中置換出去，并在該實頁中裝入當前正要訪問的虛頁。
三、程序流程圖
四、主要程序清單
#include
#include
/*全局變量*/
int
mSIZE;
/*物理塊數*/
int
pSIZE;
/*頁面號引用串個數*/
static
int
memery[10]={0};
/*物理塊中的頁號*/
static
int
page[100]={0};
/*頁面號引用串*/
static
int
temp[100][10]={0};
/*輔助數組*/
/*置換算法函數*/
void
FIFO();
void
LRU();
void
OPT();
/*輔助函數*/
void
print(unsigned
int
t);
void
designBy();
void
download();
void
mDelay(unsigned
int
Delay);
/*主函數*/
void
main()
{
int
i,k,code;
printf(“請輸入物理塊的個數(M<=10)：“);
scanf(“%d“,&mSIZE);
printf(“請輸入頁面號引用串的個數(P<=100)：“);
scanf(“%d“,&pSIZE);
puts(“請依次輸入頁面號引用串(連續輸入，無需隔開)：“);
for(i=0;i
scanf(“%1d“,&page[i]);
download();
do
{
puts(“輸入的頁面號引用串為：“);
for(k=0;k<=(pSIZE-1)/20;k++)
{
for(i=20*k;(i
{
if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
printf(“%d＼n“,page[i]);
else
printf(“%d
“,page[i]);
}
}
printf(“*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*＼n“);
printf(“*
請選擇頁面置換算法：＼t＼t＼t
*＼n“);
printf(“*
-----------------------------------------*＼n“);
printf(“*
1.先進先出(FIFO)
2.最近最久未使用(LRU)
*＼n“);
printf(“*
3.退出
*＼n“);
printf(“*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*＼n“);
printf(“請選擇操作：[
]＼b＼b“);
scanf(“%d“,&code);
switch(code)
{
case
1:
FIFO();
break;
case
2:
LRU();
break;
case
3:
OPT();
break;
case
4:
system(“cls“);
//system(“color
0A“);
exit(0);
default:
printf(“輸入錯誤，請重新輸入：“);
}
printf(“按任意鍵重新選擇置換算法：>>>“);
getchar();
}
while
(code!=4);
getchar();
}
/*載入數據*/
void
download()
{
printf(“＼nFinish.＼n載入成功!“);
}
/*設置延遲*/
void
mDelay(unsigned
int
Delay)
{
unsigned
int
i;
for(;Delay>0;Delay--)
{
for(i=0;i<124;i++)
{
printf(“
＼b“);
}
}
}
/*顯示設計者信息*/
void
print(unsigned
int
t)
{
int
i,j,k,l;
int
flag;
for(k=0;k<=(pSIZE-1)/20;k++)
{
for(i=20*k;(i
{
if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
printf(“%d＼n“,page[i]);
else
printf(“%d
“,page[i]);
}
for(j=0;j { for(i=20*k;(i if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20*k;(i { for(flag=0,l=0;l if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*頁面在物理塊中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行顯示20個*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺頁次數：%d＼t＼t“,t+mSIZE); printf(“缺頁率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置換次數：%d＼t＼t“,t); printf(“訪問命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*計算過程延遲*/ void compute() { int i; printf(“正在進行相關計算，請稍候“); for(i=0;i++<30;printf(“＼b“)); for(i=0;i++<30;printf(“ “)); for(i=0;i++<30;printf(“＼b“)); } /*先進先出頁面置換算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/ /*前mSIZE個數直接放入*/ for(i=0;i { memery[i]=page[i]; time[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計算換出頁*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*記錄該頁進入物理塊的時間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } compute(); print(count); } /*最近最久未使用置換算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/ /*前mSIZE個數直接放入*/ for(i=0;i { memery[i]=page[i]; flag[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新該頁的訪問時間*/ } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計算換出頁*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*記錄該頁的訪問時間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } compute(); print(count); } /*最佳置換算法*/ void OPT() { int memery[10]={0}; int next[10]={0}; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數*/ /*前mSIZE個數直接放入*/ for(i=0;i { memery[i]=page[i]; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*得到物理快中各頁下一次訪問時間*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*計算換出頁*/ max=next[0]>=next[1]?0:1; for(m=2;m if(next[m]>next[max]) max=m; /*下一次訪問時間都為pSIZE,則置換物理塊中第一個*/ memery[max]=page[i]; for(j=0;j temp[i][j]=memery[j]; } } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*得到物理快中各頁下一次訪問時間*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*計算換出頁*/ max=next[0]>=next[1]?0:1; for(m=2;m if(next[m]>next[max]) max=m; /*下一次訪問時間都為pSIZE,則置換物理塊中第一個*/ memery[max]=page[i]; for(j=0;j temp[i][j]=memery[j]; } } 五、程序運行結果 ①FIFO ②LRU 六、實驗體會 在做該次作業的時候，通過對課本相關內容的溫習，以及對自己在網絡上找到的一些資源的了解。我對操作系統中頁面調度的算法有了很大程度的了解，加深了對課程上知識的理解，也懂得了如何在程序中將這些算法實現，在程序中基本上實現了所要求的算法以及相關的性能分析，基本上實現了課程的要求。 這次作業也暴露了自己在某些方面的不足之處，自己的語言功底有一定的不足，以及一開始對某個算法不夠熟悉，將算法實現設計的比較復雜，此次自己的程序存在一些思想上的漏洞，反映出此次程序設計的要求有了一定的限制。
點擊咨詢