操作系統課程第七次實驗報告
姓名
學號
系
計算機
任課教師
指導教師
評閱教師
實驗地點
綜合樓B102
實驗時間
2012-9-26
實驗課表現
出勤和個人表現Q1(15+15（組長評分）=30分)
得分：
實驗
總分
(Q1+Q2+Q3+Q4)
實驗完成情況Q2(45分(組長與教師評分的加權平均))
得分：
實驗編號與實驗名稱：
實驗七、常用頁面置換算法模擬實驗
實驗目的：
通過模擬實現請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現過程，并比較它們的效率。
實驗內容及要求（詳見實驗講義與實驗指導書）：
要求：
1）要求用你熟悉的程序設計語言編寫和調試一個頁面置換模擬程序；要求在主函數中測試。
2）實驗報告中必須包括：設計思想、數據定義（包括詳細說明）、處理流程（詳細算法描述和算法流程圖）、源代碼、運行結果、體會等部分。
3）必須模擬本實驗內容中提到的算法中的至少2種頁面置換算法。
4）
比較不同頁面置換算法的效率
內容：編寫一個程序，使用以下頁面置換算法中的某2種分別模擬一個分頁系統，并統計同一個頁面訪問序列情況下不同頁面置換算法引發的缺頁中斷次數。
1、第二次機會算法（Second
Chance）
2、最近最少使用算法（Least
Recently
Used，LRU）
3、最不常用算法（Not
Frequently
Used，NFU）
4、最近未使用算法（Not
Recently
Used，NRU）
5、時鐘頁面置換算法
6、老化算法（aging）
頁框的數量固定為4，虛擬頁面數為8。實驗輸入為訪問頁面序列，比如0，1，3，2，7，1
實驗用到的軟件（：）
DevC++,Visio
實驗內容及關鍵步驟（代碼）Q3（15分）
得分：
流程圖：輸入頁面訪問序列
取訪問的頁號
查頁表
是否缺頁？
是
置缺頁標志flag為’*’
按算法不同淘汰一頁面
調入所訪問的頁面
否
FIFO算法流程圖
LRU算法流程圖：
函數關系解釋圖：
實現結果：
圖1
圖2
代碼：
#include
#include
#define
MEMORY_SIZE
/*物理塊數*/
#define
PROESS_SIZE
/*頁面號引用串個數*/#include
#include
/*全局變量*/
int
mSIZE=4;
int
pSIZE=8;
static
int
memery[4]={0};
/*物理塊中的頁號*/
static
int
page[8]={0};
/*頁面號引用串*/
static
int
temp[8][4]={0};
/*輔助數組*/
/*置換算法函數*/
void
FIFO();
void
LRU();
void
OPT();
void
designBy();
/*輔助函數*/
void
print(unsigned
int
t);
/*主函數*/
int
main()
{
int
i,k,code;
designBy();
system(“color
0A“);
puts(“請依次輸入頁面號(8個)：“);
for(i=0;i
scanf(“%1d“,&page[i]);
system(“cls“);
system(“color
0E“);
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:
system(“cls“);
system(“color
0A“);
exit(0);
default:
printf(“輸入錯誤，請重新輸入：“);
}
printf(“按任意鍵重新選擇置換算法：>>>“);
getch();
system(“cls“);
}while
(code!=3);
getch();
}
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 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]; } } 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 designBy() { printf(“┏━━━━━━━━━━━━━━━━━━━━━━━━━┓＼n“); printf(“┃㊣ 實驗七：頁面置換算法 ㊣┃＼n“); printf(“┃ 學號：1001010042 ┃＼n“); printf(“┃ 姓名：黃浩全 4.9.9.0>┃＼n“); printf(“┣━━━━━━━━━━━━━━━━━━━━━━━━━┫＼n“); } 實驗過程中遇到的問題解決辦法與實驗體會Q4（需手寫，10分） 得分： 1、在FIFO算法可以很容易用數組實現，而LRU算法可以用數組實現，不過用結構體會更明顯簡單。結構體成員變量可以記錄頁號進入的時間，和最近使用的記錄。相對比數組更容易理解和實現。 2:首先，FIFO（先進先出）算法和LRU（最近未使用算法）兩者之間，FIFO算法明顯會比LRU容易理解，而且比LRU算法較容易實現，但在性能方面，LRU的確在優化方面做的比較理想。再且在考慮頁框和頁表號之間的問題用代碼可以容易模擬，但是真是在物理內存塊中是如何實現，那確實是很難以理解，需要真正理解到內存內部的知識才知道這兩個算法是怎么實現的。 評閱教師特殊評語： 評閱教師： 日 期：
點擊咨詢