頁(yè)面置換算法源程序?qū)嶒?yàn)報(bào)告

1、頁(yè)面置換一目的和要求（一）目的 存儲(chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。 本實(shí)驗(yàn)的目的是通過(guò)請(qǐng)求頁(yè)式管理中頁(yè)面置換算法的模擬設(shè)計(jì)，來(lái)了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式管理的頁(yè)面置換算法。（二）要求 模擬頁(yè)式虛擬存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和缺頁(yè)中斷，并用先進(jìn)先出調(diào)度算法（FIFO）處理缺頁(yè)中斷。二實(shí)驗(yàn)內(nèi)容（1）為了裝入一個(gè)頁(yè)面而必須調(diào)出一頁(yè)時(shí)，如果被選中調(diào)出的頁(yè)面在執(zhí)行中沒(méi)有修改過(guò)，則不必把該頁(yè)寫到磁盤上。因此，在頁(yè)表中可以增加是否修改過(guò)的標(biāo)志，當(dāng)執(zhí)行“存”指令 “寫”指令是把對(duì)應(yīng)頁(yè)的修改標(biāo)志置“1”表示該頁(yè)修改過(guò)，為“0”表示該頁(yè)沒(méi)有修改過(guò)。 （2）設(shè)

2、計(jì)一個(gè)地址轉(zhuǎn)換程序來(lái)模擬硬件的地址轉(zhuǎn)換和缺頁(yè)中斷。當(dāng)訪問(wèn)的頁(yè)在主存時(shí)則形成絕對(duì)地址，但不去模擬指令的執(zhí)行，可用輸出轉(zhuǎn)換后的絕對(duì)地址來(lái)表示一條指令已完成。當(dāng)訪問(wèn)的頁(yè)不在主存時(shí)則輸出“*該頁(yè)頁(yè)號(hào)”來(lái)表示硬件產(chǎn)生了一次缺頁(yè)中斷。調(diào)用模擬地址轉(zhuǎn)換程序。 （3）編制一個(gè)FIFO頁(yè)面調(diào)試程序。FIFO頁(yè)面調(diào)試算法總是先調(diào)出作業(yè)中最先進(jìn)入主存的那一頁(yè)，因此，可以用一個(gè)數(shù)組來(lái)構(gòu)成頁(yè)號(hào)隊(duì)列。數(shù)組中每個(gè)元素是該作業(yè)已在主存的頁(yè)面好，假定分配給作業(yè)的主存塊數(shù)為m，且該作業(yè)開始的m頁(yè)已裝入主存，則數(shù)組可有m個(gè)元素組成：P0，P1,Pm-1 她們的初值為：P0:=0,P1:=1,Pm-1:=m-1用一指針k指示當(dāng)要裝入

3、新頁(yè)時(shí)應(yīng)調(diào)出的頁(yè)在數(shù)組的位置,k的初值為0。當(dāng)產(chǎn)生缺頁(yè)中斷后,操作系統(tǒng)總是選擇Pk所指出的頁(yè)面調(diào)出,然后執(zhí)行: Pk:=要裝入的新頁(yè)頁(yè)號(hào) K:=(k+1)mod m （4）假定主存的每塊長(zhǎng)度為1024個(gè)字節(jié),現(xiàn)有一個(gè)共7頁(yè)的作業(yè),其副本也已在磁盤上.系統(tǒng)為該作業(yè)分配了4塊主存塊,且該作業(yè)的第0頁(yè)至第3頁(yè)已經(jīng)裝入主存,其余3頁(yè)尚未裝入主存,該作業(yè)的頁(yè)表如下:頁(yè)號(hào)標(biāo)志主存塊號(hào)修改標(biāo)志在磁盤上的位置0150011118001221900133110021400002250000236000121假設(shè)該作業(yè)依次執(zhí)行的指令如下:操作頁(yè)號(hào)頁(yè)內(nèi)地址+0070+1050*2015存3021取0056-6040

4、三實(shí)驗(yàn)流程圖開始取一條指令取指令中訪問(wèn)的頁(yè)號(hào)=>L查 頁(yè) 表頁(yè)標(biāo)記=1？形成絕對(duì)地址是“存”指令？置L頁(yè)修改標(biāo)記“1”輸出絕對(duì)地址輸出“*頁(yè)號(hào)”有后繼指令？取一條指令結(jié) 束J:=PkJ頁(yè)的修改標(biāo)記=1？輸出“OUTj”輸出“INL”Pk:=L k:=(k+1) mod m修改頁(yè)面是否是否否（產(chǎn)生缺頁(yè)中斷）是否四實(shí)驗(yàn)程序#include <iostream>#include <iostream.h>#include <iomanip.h>#include <ctype.h>#define N 6/實(shí)驗(yàn)中假定的頁(yè)表長(zhǎng)度#define M 4/主

5、存物理塊數(shù)structint lnumber; /頁(yè)號(hào) int flag; /表示該頁(yè)是否在主存，"1"表示在主存，"0"表示不在主存 int pnumber; /該頁(yè)所在主存塊的塊號(hào) int write; /該頁(yè)是否被修改過(guò)，"1"表示修改過(guò)，"0"表示沒(méi)有修改過(guò) int dnumber; /該頁(yè)存放在磁盤上的位置，即磁盤塊號(hào)pageN; /頁(yè)表定義int pM;/用數(shù)組模擬FIFO算法中的隊(duì)列(使用循環(huán)隊(duì)列)int head;void initial(void);int do_mmap(int);/模擬地址轉(zhuǎn)換

6、void do_page_fault(int);/缺頁(yè)中斷處理程序void run_first_instructon(int);/執(zhí)行進(jìn)程的第一條指令void run_a_instruction(int);/CPU執(zhí)行一條指令void print_page_and_fifoqueue(void);/輸出頁(yè)表和FIFO隊(duì)列main()int laddress, paddress;/邏輯地址，物理地址int lnumber, ad, pnumber;/頁(yè)號(hào)，頁(yè)內(nèi)地址和物理塊號(hào)initial();print_page_and_fifoqueue();/輸出頁(yè)表和FIFO隊(duì)列run_first_ins

7、tructon(0x0000);/運(yùn)行進(jìn)程的第一條指令的地址cout<<"輸入下一條指令的邏輯地址(032767)(-1 to end)"<<endl;cin>>laddress;while(laddress>32767)cout<<"輸入錯(cuò)誤! 請(qǐng)重新輸入下一條指令的邏輯地址(032767)(-1 to end)"<<endl;cin>>laddress;while(laddress!=-1)lnumber=laddress>>10;/取邏輯地址的頁(yè)號(hào)lnumbe

8、rif(pagelnumber.flag=1)/指令所在的頁(yè)面已裝入在內(nèi)存中paddress=do_mmap(laddress);/形成物理地址cout<<paddress<<"輸出轉(zhuǎn)換后的物理地址"<<endl;run_a_instruction(paddress);cout<<"此指令執(zhí)行是否修改所在頁(yè)lnumber="<<lnumber<<"(y/n?) "char change;cin>>change;if(tolower(change)=&#

9、39;y')pagelnumber.write=1;print_page_and_fifoqueue();else/缺頁(yè)中斷cout<<lnumber<<"輸出該頁(yè)的頁(yè)號(hào)表示硬件產(chǎn)生缺頁(yè)中斷"<<endl;do_page_fault(lnumber);/直接轉(zhuǎn)去缺頁(yè)中斷處理continue;/本循環(huán)結(jié)束，重新執(zhí)行指令cout<<"輸入下一條指令的邏輯地址(032767)，-1 to end)n"cin>>laddress;while(laddress>32767)/輸入正確性檢測(cè)c

10、out<<"輸入錯(cuò)誤! 請(qǐng)重新輸入下一條指令的邏輯地址(032767)(-1 to end)"<<endl;cin>>laddress;cout<<"進(jìn)程運(yùn)行結(jié)束!"<<endl;system("PAUSE");return 0; /手工初始化頁(yè)表和pM隊(duì)列void initial(void)int i;for(i=0; i<=5; i+)pagei.lnumber=i;if(i<=M-1)/預(yù)裝入算法初始化頁(yè)表的前四項(xiàng)cout<<"輸入頁(yè)號(hào)

11、為 "<<i<<" 所在內(nèi)存的物理塊號(hào)(預(yù)裝入前四個(gè)頁(yè)面)："cin>>pagei.pnumber;pagei.flag=1;/存在標(biāo)志置1/初始化FIFO的隊(duì)列head=0;for(i=0; i<=M-1; i+)pi=i;/輸出頁(yè)表和FIFO隊(duì)列void print_page_and_fifoqueue(void)int i;cout<<"輸出頁(yè)表！n"cout<<setw(10)<<"lnumber"<<setw(9)<&l

12、t;"flag"<<setw(10)<<"pnumber"<<setw(10)<<"write"<<setw(10)<<"dnumber"<<endl;for(i=0; i<=N-1; i+)cout<<setw(7)<<pagei.lnumber<<setw(10)<<pagei.flag<<setw(10)<<pagei.pnumber<<

13、setw(10)<<pagei.write<<setw(10)<<pagei.dnumber<<endl;cout<<"輸出FIFO對(duì)列:n"cout<<setw(10)<<"NO"<<setw(40)<<"page(已在主存的頁(yè)號(hào)lnumber)n"cout<<"head="<<head<<endl;for(i=0; i<=M-1;i+)cout<<se

14、tw(10)<<i<<setw(15)<<pi<<endl;/模擬地址轉(zhuǎn)換int do_mmap(int laddress)int lnumber, ad, pnumber, paddress;lnumber=laddress>>10;/取邏輯地址的頁(yè)號(hào)lnumberad=laddress&0x3ff;/頁(yè)內(nèi)地址pnumber=pagelnumber.pnumber;/從頁(yè)表中取得塊號(hào)pnumberpaddress=pnumber<<10|ad;return paddress;/CPU執(zhí)行一條指令，輸出物理地址表示

15、指令執(zhí)行完成void run_a_instruction(int paddress)cout<<paddress<<" 輸出物理地址表示指令執(zhí)行完成"<<endl;/執(zhí)行進(jìn)程的第一條指令void run_first_instructon(int laddress)int lnumber, ad, pnumber, paddress;lnumber=laddress>>10;/取邏輯地址的頁(yè)號(hào)if(pagelnumber.flag=1)paddress=do_mmap(laddress);/形成物理地址cout<<p

16、address<<"輸出轉(zhuǎn)換后的物理地址"<<endl;run_a_instruction(paddress);cout<<"此指令執(zhí)行(0x0000)是否修改所在頁(yè)面lnumber="<<lnumber<<"(y/n?) "char change;cin>>change;if(tolower(change)='y')/若指令執(zhí)行完時(shí)修改了頁(yè)面，則置write標(biāo)志位位1pagelnumber.write=1;print_page_and_fifoq

17、ueue();cout<<"*第一條指令執(zhí)行完成(地址為0x0000)*"<<endl;/頁(yè)面寫回磁盤void write_to_harddisk(int j)cout<<j<<"輸出已修改的淘汰的頁(yè)號(hào)表示該頁(yè)寫回了磁盤"<<endl;/缺頁(yè)中斷處理程序void do_page_fault(int lnumber)int j;/j是選擇淘汰的頁(yè)j=phead;phead=lnumber;/lnumber是新裝入的頁(yè)號(hào)head=(head+1)%M;/若淘汰出主存的頁(yè)j已修改，則寫會(huì)磁盤if(pagej.write=1)write_to_harddisk(j);/頁(yè)j寫回磁盤/修改頁(yè)表pagej.flag=0;/頁(yè)表中第j頁(yè)的存在標(biāo)志為0pagelnumber.flag=1;/頁(yè)表第lnumber的存在標(biāo)志為1pagelnumber.write=0;/頁(yè)表第lnumber的修改標(biāo)志為0pagelnumber.pnumber=pagej.pnumber;/第拉怒目布爾頁(yè)的主存塊號(hào)為第j頁(yè)原主存塊號(hào)cout<<lnumber<<"輸出該頁(yè)表示該頁(yè)調(diào)入了主存"<<e