實驗四 模擬一個指令序列,共有320條指令

20111060255曹加站計科實驗四一、模擬一個指令序列，共有320條指令（模擬320個頁號）50%的指令是順序執(zhí)行的25%的指令存放在當(dāng)前指令之前的地址25%的指令存放在當(dāng)前指令之后的地址實驗結(jié)果分析：

此實驗?zāi)M一個指令序列，共有320條指令：50%的指令是順序執(zhí)的，25%的指令是均勻分布在前地址部分，25%的指令是均勻分布在后地址部分。模擬頁面結(jié)構(gòu)模擬頁面頁面大小為1K物理內(nèi)存容量為4頁~32頁虛擬內(nèi)存容量為32K每頁內(nèi)存存放了10條指令實現(xiàn)幾種頁面置換算法輸出各頁面置換算法在一定的物理內(nèi)存容量下的命中率命中率=1-頁面失效次數(shù)/320當(dāng)CPU接收到缺頁中斷信號，中斷處理程序先保存現(xiàn)場，分析中斷原因，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁所在外存的物理塊號。如果此時內(nèi)存未滿，能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須按某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出，是否重新寫盤由頁表的修改位決定，然后將缺頁調(diào)入，修改頁表。利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個頁面的調(diào)入過程對用戶是透明的。

常用的頁面置換算法有

1、最佳置換算法（Optimal）

2、先進(jìn)先出法（FisrtInFirstOut）

3、最近最久未使用（LeastRecentlyUsed）

4、最不經(jīng)常使用法（LeastFrequentlyUsed）

5、最近未使用法（NoUsedRecently）由于OPT算法不能實現(xiàn)，實驗中也只能模擬，故在程序中沒有展示。注釋1：#definetotal_instruction320/*指令流長*/

#definetotal_vp32/*虛頁長*/

#defineclear_period50/*清0周期*/注釋1：#definetotal_instruction320/*指令流長*/

#definetotal_vp32/*虛頁長*/

#defineclear_period50/*清0周期*/typedefstruct/*頁面結(jié)構(gòu)*/

{

intpn,pfn,counter,time;

}pl_type;

pl_typepl[total_vp];/*頁面結(jié)構(gòu)數(shù)組*/structpfc_struct{/*頁面控制結(jié)構(gòu)*/

intpn,pfn;

structpfc_struct*next;

};注釋2：

注釋2：

srand(10*getpid());/*由于每次運行時進(jìn)程號不同，故可用來作為初始化隨機數(shù)隊列的“種子”*/

for(i=0;i<total_instruction;i+=4)/*產(chǎn)生指令隊列*/

a[i]=s;/*任選一指令訪問點m*/

a[i+1]=a[i]+1;/*順序執(zhí)行一條指令*/

a[i+2]=(float)a[i]*rand()/RAND_MAX;/*執(zhí)行前地址指令m'*/

a[i+3]=a[i+2]+1;/*順序執(zhí)行一條指令*/

注釋3：for(i=0;i<total_instruction;i++)/*將指令序列變換成頁地址流*/注釋3：for(i=0;i<total_instruction;i++)/*將指令序列變換成頁地址流*/for(i=4;i<=32;i++)/*用戶內(nèi)存工作區(qū)從4個頁面到32個頁面*/intinitialize(total_pf)/*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)*/

inttotal_pf;/*用戶進(jìn)程的內(nèi)存頁面數(shù)*/pl[i].pfn=INVALID;/*置頁面控制結(jié)構(gòu)中的頁號，頁面為空*/

pl[i].counter=0;

pl[i].time=-1;/*頁面控制結(jié)構(gòu)中的訪問次數(shù)為0，時間為-1*/注釋5：if(pl[page[i]].pfn==INVALID)/*頁面失效*/

{

diseffect+=1;/*失效次數(shù)*/

if(freepf_head==NULL)/*無空閑頁面*/

{

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head;/*釋放忙頁面隊列的第一個頁面*/

freepf_head->next=NULL;

busypf_head=p;

}

p=freepf_head->next;/*按FIFO方式調(diào)新頁面入內(nèi)存頁面*/注釋5：if(pl[page[i]].pfn==INVALID)/*頁面失效*/

{

diseffect+=1;/*失效次數(shù)*/

if(freepf_head==NULL)/*無空閑頁面*/

{

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head;/*釋放忙頁面隊列的第一個頁面*/

freepf_head->next=NULL;

busypf_head=p;

}

p=freepf_head->next;/*按FIFO方式調(diào)新頁面入內(nèi)存頁面*/busypf_tail->next=freepf_head;/*free頁面減少一個*/注釋4：for(i=0;i<total_pf-1;i++)

{

pfc[i].next=&pfc[i+1];

pfc[i].pfn=i;}/*建立pfc[i-1]和pfc[i]之間的鏈接*/

freepf_head=&pfc[0];/*空頁面隊列的頭指針為pfc[0]*/inttotal_pf;/*用戶進(jìn)程的內(nèi)存頁面數(shù)*/initialize(total_pf);/*初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)*/

busypf_head=busypf_tail=NULL;/*忙頁面隊列頭，隊列尾鏈接*/注釋6：注釋6：for(j=0;j<total_vp;j++)/*找出time的最小值*/freepf_head=&pfc[pl[minj].pfn];//騰出一個單元

pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效

pl[page[i]].time=present_time;

freepf_head=freepf_head->next;//減少一個free頁面

}

else

pl[page[i]].time=present_time;//命中則增加該單元的訪問次數(shù)注釋7：pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效

pl[page[i]].counter++;

freepf_head=freepf_head->next;//減少一個free頁面注釋7：pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效

pl[page[i]].counter++;

freepf_head=freepf_head->next;//減少一個free頁面實驗結(jié)果：先進(jìn)先出的算法（FIFO）：其總是選擇在內(nèi)存駐留時間最長的一頁將其淘汰。FIFO算法認(rèn)為先調(diào)入內(nèi)存的頁不再被訪問的可能性要比其他頁的大，因而選擇最先調(diào)入內(nèi)存的頁換出。實現(xiàn)FIFO算法需要把各個已分配頁面按分配時間順序鏈接起來，組成FIFO隊列，并設(shè)置一置換指針指向FIFO隊列的隊首頁面。這樣，當(dāng)要進(jìn)行置換時，只需把置換指針?biāo)傅腇IFO隊列前頭的頁順次換出，而把換入的頁鏈接在FIFO斷尾即可。最近最少使用算法（LRU）LRU是LeastRecentlyUsed近期最少使用算法。內(nèi)存管理的一種頁面置換算法，對于在內(nèi)存中但又不用的數(shù)據(jù)塊（內(nèi)存塊）叫做LRU，Oracle會根據(jù)哪些數(shù)據(jù)屬于LRU而將其移出內(nèi)存而騰出空間來加載另外的數(shù)據(jù)。實驗分析從結(jié)果看以上幾種算法，NUR命中率最高，其次是LFU算法和LRU算法，最后是FIFO算法。

實際上，從實驗數(shù)據(jù)觀測得到，存在這種由高到低的趨勢，但是效果不是很明顯。

效果不明顯的原因：

推測與指令流的產(chǎn)生方式有關(guān)系。因為指令流的產(chǎn)生方式要能體現(xiàn)局部性原理，所以該指令流產(chǎn)生設(shè)計為：50%的指令是順序執(zhí)的，25%的指令是均勻分布在前地址部分，25%的指令是均勻分布在后地址部分。但是這樣的指令流設(shè)計方式能否最佳地體現(xiàn)局部性原理，這還有待