使用最近未使用頁淘汰(NRU)算法模擬實現(xiàn)頁淘汰進程

使用最近未使用頁淘汰（NRU）算法模擬實現(xiàn)頁淘汰進程摘要：最近未使用頁淘汰（NRU）算法或者時鐘算法是實際使用的諸多頁淘汰算法中的一種。本課程設(shè)計是使用C程序設(shè)計語言，在windows平臺下對頁淘汰（NRU）算法模擬,通過頁淘汰（NRU）算法的模擬來進一步的加深對使用NRU算法的了解，及對C程序設(shè)計語言的使用。關(guān)鍵詞：頁淘汰NRU時鐘算法一．設(shè)計的背景介紹介紹相關(guān)概念，相關(guān)算法頁淘汰工作通常是由一個系統(tǒng)進程或線程完成的，該進程稱為頁淘汰進程。頁淘汰的時機：當內(nèi)存空閑頁面數(shù)低于系統(tǒng)所配置的最小閾值時啟動（喚醒）頁淘汰的進程，頁淘汰進程被啟動后就開始不停地選擇和淘汰釋放頁，直到內(nèi)存的空閑頁面數(shù)達到系統(tǒng)所配置的最大閾值為止。此后，頁淘汰進程進入睡眠（等待）狀態(tài)，直到下次因內(nèi)存空閑頁面數(shù)少于最小閾值而被再次喚醒（啟動）。最近未使用頁淘汰（NRU）算法的原理：該算法為每個頁面設(shè)置兩個硬件位—訪問位和修改位訪問位=0:該頁尚未被訪問過; 訪問位=1:該頁已經(jīng)被訪問過修改位=0:該頁尚未被修改過; 訪問位=1:該頁已經(jīng)被修改過開始時所有頁的訪問位,修改位都設(shè)為0,訪問/修改時再置1。當頁淘汰進程工作時，首先淘汰那些訪問位為0的頁。然后，如果還需要繼續(xù)淘汰（即空閑頁面尚未達到最大閾值），則淘汰那些訪問位為1但修改位為0的頁。最后如果空閑頁面還不夠，則淘汰那些修改位為1的頁。由于大多數(shù)頁遲早要被訪問，故頁淘汰進程定期遍歷內(nèi)存頁一將每頁的訪問位都置為0（周期性地對訪問位清零）。這種清除過程類似于時針在時鐘面上的運行故NRU算法又稱為時鐘（clock）算法。簡要介紹設(shè)計環(huán)境、設(shè)計工具利用VC++6.0/TC3.0在Dos/Windows平臺使用最近未使用頁淘汰（NRU）算法模擬實現(xiàn)頁淘汰進程二．設(shè)計思路和總體流程圖基本思路以命令行方式運行程序，調(diào)用read()函數(shù)讀入頁面請求隊列，按照頁面請求隊列的先后順序逐個處理請求頁面。調(diào)用nru()函數(shù)通過nru算法選擇要淘汰的頁面，將其淘汰，調(diào)入申請頁面，輸出相關(guān)結(jié)果的信息。數(shù)據(jù)文件格式說明第一行為工作集大小(wnum)第二行為申請頁面的總數(shù)(pnum)；第三行為頁號(pagenum),修改位(mbit)中間用"|"符號隔開；其余為一個頁面請求隊列，各行兩數(shù)分別表示頁面申請頁號和修改位，程序按請求的先后順序處理申請頁。用戶可根據(jù)需要任意修改工作集大小，申請頁面的總數(shù)，頁面請求隊列。文件樣例如下：wnum:3pnum:10pagenum|mbit1011301021301數(shù)據(jù)結(jié)構(gòu)定義⑴定義頁面請求隊列Pagetypedefstruct{intpagenum; //頁面號intmbit; //修改位⑵定義工作集Wspacetypedefstruct{intpageno;//頁面號intrbit;//訪問位intmbit;//修改位intstatus;//該頁的標志位，表示是否被占用}Wspace;⑶其他intpnum;//申請頁面的總數(shù)intwnum;//工作集大小intb[4];//標志位數(shù)組，四個數(shù)組元素分別表示工作集內(nèi)是否存在訪問位、修改位分別為00，01，10，11的頁面，初始值為0，當存在時置1總體流程圖開始圖1.程序總體流程圖根據(jù)總體流程圖進行模塊分割、模塊功能說明本程序共分成2個模塊：⑴文件讀入模塊：主要用于讀入文件信息，并將文件的內(nèi)容全部輸出，檢驗讀入是否正確。此模塊通過調(diào)用read()函數(shù)實現(xiàn)。⑵主體函數(shù)模塊：實現(xiàn)nru算法，這是本課程設(shè)計的主體模塊，通過調(diào)用nru()函數(shù)實現(xiàn)。調(diào)入每個申請頁，當工作集滿時運用nru算法選擇要淘汰的頁面，將其淘汰°nru()函數(shù)中包括兩個子函數(shù)print(),callin()?print()函數(shù)：信息輸出，主要用于輸出相關(guān)的結(jié)果信息，包括申請頁面的頁面號、修改位，工作集中的各頁頁面號、訪問位、修改位。在程序處理完一頁后調(diào)用此函數(shù)，使用戶能清楚的了解處理完一個申請頁面后工作集的內(nèi)容。?callin()函數(shù)：調(diào)入申請頁，主要完成四個操作：申請頁面調(diào)入；訪問位置1，表示被訪問；根據(jù)請求頁面的修改位修改工作集頁面的修改位；狀態(tài)位置1，表示該頁已經(jīng)被占用。該函數(shù)在三種情形下可調(diào)用①工作集存在空閑頁，調(diào)入申請頁時；②申請頁已在工作集中，修改訪問位和修改位時；③工作集滿時，需淘汰工作集內(nèi)的頁面，調(diào)入申請頁時。三．算法的實現(xiàn)模塊流程圖及算法實現(xiàn)1．文件讀入模塊主要用于讀入文件信息，并將文件的內(nèi)容全部輸出，檢驗讀入是否正確。通過read()函數(shù)實現(xiàn)。read()函數(shù)流程圖如下：

定義intargc,char*argv[]定義一個指向FILE類型的指針變量file,inti,chartemp[80]argc=2二二argc=2二二否f Exit(O)是開辟pnum個Page是開辟pnum個Page類型的結(jié)構(gòu)體圖2.read()函數(shù)流程圖具體的程序代碼如下：voidread(intargc,char*argv[],Page**page,int*pnum,int*wnum,Wspace**wspace){FILE*file;chartemp[80];inti;if(argc!=2)exit(0);if((file=fopen(argv[1],"r"))==NULL){printf("readfilefailed\n");exit(0);}fscanf(file,"%5s%d",temp,wnum);fscanf(file,"%5s%d",temp,pnum);fscanf(file,"%s",temp);*wspace=(Wspace*)malloc(sizeof(Wspace)**wnum);*page=(Page*)malloc(sizeof(Page)**pnum);for(i=0;i<*wnum;i++){(*wspace)[i].pageno=0;(*wspace)[i].rbit=0;(*wspace)[i].mbit=0;(*wspace)[i].status=0;}//遍歷工作集各頁，將各頁的頁面號，訪問位，修改位，狀態(tài)位置0printf("wnum:%d\n",*wnum);printf("pnum:%d\n",*pnum);printf("pagenummbit\n");for(i=0;i<*pnum;i++){fscanf(file,"%d%d",&((*page)+i)->pagenum,&((*page)+i)->mbit);printf("%d%d\n",((*page)+i)->pagenum,((*page)+i)->mbit);}fclose(file);}2-主體函數(shù)模塊，通過nru()函數(shù)實現(xiàn)，該函數(shù)可分為三部分圖3nru()函數(shù)流程圖j=o（C語言j從0開始）W■W■?查找第j個申請頁是否在工作集二—是^調(diào)入申請頁，修改修

改位，訪問位置1F查找工作集是否存在空閑頁F查找工作集是否存在空閑頁1VI、否位分個頁訪—仁bij十工作集是否存在某個頁訪問

位、修改位分別為01是f 1=>b[1]. 工作集是否存在某個頁訪問 .位、修改位分別為101=>b[2]1=>b[3]順序查找工作集的頁面，

*找到第1工作集是否存在某個頁訪問

位、修改位分別為01是f 1=>b[1]. 工作集是否存在某個頁訪問 .位、修改位分別為101=>b[2]1=>b[3]順序查找工作集的頁面，

*找到第1個訪問位和修改

位分別為00的頁面否順序查找工作集的頁面，

*找到第1個訪問位和修改

位分別為01的頁面b[2]==1證明b⑶一

定等于1順序查找工作集的頁面，*找到第1個訪問位和修改位分別為10的頁面1T..調(diào)入申請頁位，訪，修改修改嘴問位置1是（1）第一步，查找申請頁面是否已在工作集內(nèi)，若是則將該頁的訪問位置1，修改修改位，輸出相關(guān)信息，處理下一頁。（2）若申請頁不在工作集，則進入第二步：查找工作集是否存在空閑頁，若是則調(diào)入該申請頁，訪問位置1，修改修改位，輸出相關(guān)信息，處理下一頁。（3）若工作集不存在空頁，則進入第三步：運用NRU算法選擇需要淘汰的頁面，將其淘汰，調(diào)入申請頁，具體的做法是：定義數(shù)組b[4],每個數(shù)組元素表示一個標志位，初始值均為0。遍歷工作集，如果存在訪問位、修改位為00，01，10，11的頁面，對應(yīng)地分別將數(shù)組的b[0]、b[1]、b[2]、b[3]置1。此時，因為申請頁面不在工作集，工作集也不存在空閑頁面，因此，b數(shù)組肯定有一個元素為1。如果b[0]為1，查找第一個訪問位、修改位分別為00的頁面，將其淘汰，調(diào)入申請頁，訪問位置1，遍歷工作集各頁，將各頁的訪問位置0,轉(zhuǎn)第③步；若b[0]為0,則判斷：如果b[1]為1,查找第一個訪問位、修改位分別為01的頁面，將其淘汰，調(diào)入申請頁，訪問位置1，遍歷工作集各頁，將各頁的訪問位置0,轉(zhuǎn)第③步；若b[1]為0,則判斷：如果b[2]為1,查找第一個訪問位、修改位分別為10的頁面,將其淘汰,調(diào)入申請頁,訪問位置1,遍歷工作集各頁，將各頁的訪問位置0,轉(zhuǎn)第③步；若b[2]也為0,證明b[3]一定為1,此時工作集內(nèi)各頁訪問位、修改位均為11,可任意淘汰一頁,將其淘汰?，F(xiàn)選擇淘汰第0頁,調(diào)入申請頁，遍歷工作集各頁，將各頁的訪問位置0,轉(zhuǎn)第③步。每處理完一頁即調(diào)用print（）函數(shù)，將申請頁面的頁面號、修改位，工作集中的各頁面號、訪問位、修改位輸出,處理下一個申請頁。（4）所有的頁面申請頁都處理完畢,函數(shù)結(jié)束,返回。具體的程序代碼如下：voidnru（Page*page,Wspace*wspace,intpnum,intwnum,intb[4]）{inti,j,m,n,k;for（j=0;j<pnum;j++）//j表示申請頁面的序號，處理完一次，j自動加1,直至申請頁面全部處理完畢{for(m=0;m<wnum;m++)if(wspace[m].pageno==(page+j)->pagenum)break;//查找申請頁是否在工作集if(m<wnum){callin(page,wspace,m,j);print(page,wspace,j,wnum);}//若在工作集，則將該頁調(diào)入至此，訪問位置1，并輸出相關(guān)信息else{for(k=0;k<wnum;k++)if(wspace[k].status==0)break;//查找工作集是否存在空閑頁if(k<wnum){callin(page,wspace,k,j);print(page,wspace,j,wnum);}//若存在空閑頁，則將該頁調(diào)入至此，訪問位置1，并輸出相關(guān)信息else{for(i=0;i<4;i++)b[i]=0;//b數(shù)組各元素賦初始值為0for(m=0;m<wnum;m++){if(wspace[m].rbit==0&&wspace[m].mbit==0)b[0]=1;//工作集存在訪問位、修改位分別為00的頁面時，b[0]置1if(wspace[m].rbit==0&&wspace[m].mbit==1)b[1]=1;//工作集存在訪問位、修改位分別為01的頁面時，b[1]置1if(wspace[m].rbit==1&&wspace[m].mbit==0)b[2]=1;//工作集存在訪問位、修改位分別為10的頁面時，b[2]置1if(wspace[m].rbit==1&&wspace[m].mbit==1)b[3]=1;//工作集存在訪問位、修改位分別為11的頁面時，b[3]置1}if(b[0]==1){for(n=0;n<wnum;n++)if(wspace[n].rbit==0&&wspace[n].mbit==0)break;callin(page,wspace,n,j);//如果b[0]=1,查找第一個訪問位和修改位為00的頁面，調(diào)入申請頁至此for(n=0;n<wnum;n++)wspace[n].rbit=0;//遍歷工作集，將各頁訪問位置0print(page,wspace,j,wnum);//輸出相關(guān)信息}elseif(b[1]==1){for(n=0;n<wnum;n++)if(wspace[n].rbit==0&&wspace[n].mbit==1)break;callin(page,wspace,n,j);//如果b[1]=1,查找第一個訪問位和修改位為01的頁面，調(diào)入申請頁至此for(n=0;n<wnum;n++)wspace[n].rbit=0;//遍歷工作集，將各頁訪問位置0print(page,wspace,j,wnum);//輸出相關(guān)信息}elseif(b[2]==1){for(n=0;n<wnum;n++)if(wspace[n].rbit==1&&wspace[n].mbit==0)break;callin(page,wspace,n,j);//如果b[2]=l,查找第一個訪問位和修改位為10的頁面，調(diào)入申請頁至此for(n=0;n<wnum;n++)wspace[n].rbit=0;//遍歷工作集，將各頁訪問位置0print(page,wspace,j,wnum);//輸出相關(guān)信息}else{callin(page,wspace,0,j);//調(diào)入申請頁至工作集的第0頁for(n=0;n<wnum;n++)wspace[n].rbit=0;//遍歷工作集，將各頁訪問位置0print(page,wspace,j,wnum);//輸出相關(guān)信息}}}printf("\n");}}程序編譯及使用說明編譯說明：程序在C++或c語言環(huán)境下編譯實現(xiàn)。使用說明：在Dos環(huán)境下實現(xiàn)結(jié)果的顯示。開始一程序一MS-DOS方式一輸入程序名(及其所在路徑)與參數(shù)來啟動程序，例如程序hnru.cpp和數(shù)據(jù)文件hnru.txt存放在F：\1中,編譯完成后可在F:\l\debug產(chǎn)生可執(zhí)行文件hnru.ex