操作系統(tǒng)實驗三

操作系統(tǒng)實驗存儲分配收藏實驗目的1.了解動態(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構和分配算法，并進一步加深對動態(tài)分區(qū)存儲管理方式及實現(xiàn)過程的理解。2.通過對頁面、頁表、地址轉(zhuǎn)換和頁面轉(zhuǎn)換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解。實驗內(nèi)容和步驟、動態(tài)分區(qū)分配方式的模擬1用C語言分別實現(xiàn)采用首次適應算法和最佳適應算法的動態(tài)分區(qū)分配過程alloc()和回收過程free()。其中，空閑分區(qū)通過空閑分區(qū)鏈管理；在進行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。2假設初始狀態(tài)下，可用的內(nèi)在空間為640KB，并有下列的請求序列：作業(yè)1申請130KB作業(yè)2申請60KB作業(yè)3申請100KB作業(yè)2釋放60KB作業(yè)4申請200KB作業(yè)3釋放100KB作業(yè)1釋放130KB作業(yè)5申請140KB作業(yè)6申請60KB作業(yè)7申請50KB作業(yè)6釋放60KB請分別采用首次適應算法和最佳適應算法進行內(nèi)存塊的分配和回收，要求每次分配和回收后顯示出空閑內(nèi)存分區(qū)鏈的情況。3源代碼如下：/*動態(tài)分區(qū)分配方式的模擬*#include#include#define Free 0 /空閑狀態(tài)#define Busy 1 /已用狀態(tài)#define OK 1/完成#define ERROR 0 /出錯#define MAX_length 640 /最大內(nèi)存空間為640KBtypedef int Status;typedef struct freearea/定義一個空閑區(qū)說明表結(jié)構int ID;/分區(qū)號long size;/分區(qū)大小long address; /分區(qū)地址int state;/狀態(tài)ElemType;/-線性表的雙向鏈表存儲結(jié)構-typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趨指針struct DuLNode *next;/后繼指針DuLNode,*DuLinkList;DuLinkList block_first; /頭結(jié)點DuLinkList block_last;/尾結(jié)點Status alloc(int);/內(nèi)存分配Status free(int); /內(nèi)存回收Status First_fit(int,int);/首次適應算法Status Best_fit(int,int); /最佳適應算法void show();/查看分配Status Initblock();/開創(chuàng)空間表Status Initblock()/開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_last-prior=block_first;block_last-next=NULL;block_last-data.address=0;block_last-data.size=MAX_length;block_last-data.ID=0;block_last-data.state=Free;return OK;/-分配主存-Status alloc(int ch)int ID,request;coutID;coutrequest;if(request0 |request=0)cout分配大小不合適，請重試！endl;return ERROR;if(ch=2) /選擇最佳適應算法if(Best_fit(ID,request)=OK) cout分配成功！endl;else cout內(nèi)存不足，分配失?。ndl;return OK;else /默認首次適應算法if(First_fit(ID,request)=OK) cout分配成功！endl;else cout內(nèi)存不足，分配失?。ata.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/有大小恰好合適的空閑塊p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空閑塊能滿足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;/-最佳適應算法-Status Best_fit(int ID,int request)int ch; /記錄最小剩余空間DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp-data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /記錄最佳插入位置while(p) /初始化最小空間和最佳位置if(p-data.state=Free &(p-data.sizerequest | p-data.size=request) )q=p;ch=p-data.size-request;break;p=p-next;while(p)if(p-data.state=Free & p-data.size=request)/空閑塊大小恰好合適p-data.ID=ID;p-data.state=Busy;return OK;break;if(p-data.state=Free & p-data.sizerequest)/空閑塊大于分配需求if(p-data.size-requestdata.size-request;/更新剩余最小值q=p;/更新最佳位置指向p=p-next;if(q=NULL) return ERROR;/沒有找到空閑塊else/找到了最佳位置并實現(xiàn)分配temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;/-主存回收-Status free(int ID)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(p-prior-data.state=Free)/與前面的空閑塊相連p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;if(p-next-data.state=Free)/與后面的空閑塊相連p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;break;p=p-next;return OK;/-顯示主存分配情況-void show()cout+n;cout+主存分配情況+n;coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDendl;cout起始地址：data.addressendl;cout分區(qū)大?。篸ata.size KBendl;coutdata.state=Free) cout空閑endl;else cout已分配endl;coutnext;/-主函數(shù)-void main()int ch;/算法選擇標記cout動態(tài)分區(qū)分配方式的模擬n;cout*n;cout* 1)首次適應算法2)最佳適應算法*n;cout*n;coutch;Initblock(); /開創(chuàng)空間表int choice;/操作選擇標記while(1)cout*n;cout*1:分配內(nèi)存2:回收內(nèi)存*n;cout*3:查看分配0:退出*n;cout*n;coutchoice;if(choice=1) alloc(ch); /分配內(nèi)存else if(choice=2)/內(nèi)存回收int ID;coutID;free(ID);else if(choice=3) show();/顯示主存else if(choice=0) break; /退出else /輸入操作有誤cout輸入有誤，請重試！endl;continue;二、請求調(diào)頁存儲管理方式的模擬1假設每個頁面中可存放10條指令，分配給一個作業(yè)的內(nèi)存塊數(shù)為42用C語言模擬一作業(yè)的執(zhí)行過程。該作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將相應頁調(diào)入內(nèi)存。如果4個內(nèi)存塊中均已裝入該作業(yè)，則需進行頁面轉(zhuǎn)換。最后顯示其物理地址，并轉(zhuǎn)下一條指令。在所有320條指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。3置換算法：請分別考慮OPT、FIFO和LRU算法。4作業(yè)中指令的訪問次序按下述原則生成：50%的指令是順序執(zhí)行的25%的指令是均勻分布在前地址部分25%的指令是均勻分布在后地址部分具體的實施辦法：在0,319之間隨機選取一條起始指令，其序號為m順序執(zhí)行下一條指令，即序號為m+1的指令通過隨機數(shù)，跳轉(zhuǎn)到前地址部分0,m-1中的某條指令處，其序號為m1；順序執(zhí)行下一條指令，即序號為m1+1的指令通過隨機數(shù)，跳轉(zhuǎn)到后地址部分m1+2,319中的某條指令處，其序號為m2;順序執(zhí)行下一條指令，即序號為m2+1的指令重復跳轉(zhuǎn)到前地址部分、順序執(zhí)行、跳轉(zhuǎn)到后地址部分、順序執(zhí)行的過程，直至執(zhí)行320條指令。5關鍵知識在進程運行過程中，若其所要訪問的頁面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應將哪個頁面調(diào)出，所以需要根據(jù)一定的算法來確定。在這一過程中，選擇換出頁面的算法稱為頁面置換算法。一個好的頁面置換算法，應具有較低的頁面更換頻率。頁面置換算法的好壞，將直接影響到系統(tǒng)的性能。以下分別是實驗要求的三個頁面置換算法的介紹及設計思想。最佳置換算法（Optimal）：最佳置換算法是Blady在理論上提出的一種算法。其所選擇的被淘汰頁是將來不再被使用，或者是在最遠的將來才被訪問的頁面。采用這種頁面置換算法，保證有最少的缺頁率。但由于目前還無法預知一個進程在內(nèi)存的若干個頁面中，哪個在最長的時間內(nèi)不會被訪問，因而，現(xiàn)實中該算法是無法實現(xiàn)的。因此在該算法的模擬過程中，頁面訪問次序必須是給定的，具體實現(xiàn)為：對每一個物理塊設置一個整數(shù)型的訪問標志位，當需要置換物理塊中的某一頁時，將每一個物理塊中的頁面號與當前需調(diào)入頁以后的每一頁面號進行比較，若物理塊中的頁面號與所有的頁面號都不同，則該頁即為將來不再使用的頁，將訪問標記設置為1000，表示將來不會用，設置為一個很大數(shù)；若找到頁號相同的則將其訪問次序記入訪問標記，比較訪問標記，最大的即為最久不會被訪問的，將其換出。先進先出法（First In First Out）：該算法總是淘汰最先進入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。在該算法的模擬過程中，每當某一頁面進入內(nèi)存時（包括頁面置換時頁面的置入），物理塊中各頁面訪問標記自動加一，置換后，將置換頁面所在的物理塊中訪問標記減一；這樣能防止當物理塊訪問標記出現(xiàn)兩個以上相同的值的錯誤執(zhí)行，更好地模擬了先進先出法；最近最久未使用（Least Recently Used）：該算法以最近的過去作為不久將來的近似，將過去最長一段時間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當物理塊中的頁面被訪問時，便將其訪問標記置為1以后每執(zhí)行一條指令，便將物理塊中各頁面的訪問標記加一，需置換時訪問標記最大的便是將要被置換的。四、源代碼#include #include#include#include#define Bsize 4typedef struct BLOCK/聲明一種新類型物理塊類型int pagenum;/頁號int accessed;/訪問字段，其值表示多久未被訪問BLOCK;int pc;/程序計數(shù)器，用來記錄指令的序號int n;/缺頁計數(shù)器，用來記錄缺頁的次數(shù)static int temp320;/用來存儲320條隨機數(shù)BLOCK blockBsize; /定義一大小為4的物理塊數(shù)組void init( );/程序初始化函數(shù)int findExist(int curpage);/查找物理塊中是否有該頁面int findSpace( );/查找是否有空閑物理塊int findReplace( );/查找應予置換的頁面void display ( );/顯示void suijishu( );/產(chǎn)生320條隨機數(shù),顯示并存儲到temp320void pagestring( );/顯示調(diào)用的頁面隊列void OPT( );/OPT算法void LRU( );/ LRU算法void FIFO( );/FIFO算法void init( )for(int i=0;iBsize;i+)blocki.pagenum=-1;blocki.accessed=0;pc=n=0;int findExist(int curpage)for(int i=0; iBsize; i+)if(blocki.pagenum = curpage )return i;/檢測到內(nèi)存中有該頁面，返回block中的位置return -1;int findSpace( )for(int i=0; iBsize; i+)if(blocki.pagenum = -1)return i;/找到空閑的block，返回block中的位置return -1;int findReplace( )int pos = 0;for(int i=0; iblockpos.accessed)pos = i;/找到應予置換頁面，返回BLOCK中位置return pos;void display( )for(int i=0; iBsize; i+)if(blocki.pagenum != -1)printf( %02d,blocki.pagenum);coutpc;cout*按照要求產(chǎn)生的320個隨機數(shù)：*endl;for(int i=0;i320;i+)tempi=pc;if(flag%2=0) pc=+pc%320;if(flag=1) pc=rand( )% (pc-1);if(flag=3) pc=pc+1+(rand( )%(320-(pc+1);flag=+flag%4;printf( %03d,tempi);if(i+1)%10=0) coutendl;void pagestring( )for(int i=0;i320;i+)printf( %02d,tempi/10);if(i+1)%10=0) coutendl;void OPT( )int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=tempi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace ( );if(space != -1)blockspace.pagenum = curpage;display( );n=n+1;elsefor(int k=0;kBsize;k+)for(int j=i;j320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/將來不會用，設置為一個很大數(shù)elseblockk.accessed = j;break;position = findReplace( );blockposition.pagenum = curpage;display( );n+;cout缺頁次數(shù):nendl;cout缺頁率:(n/320.0)*100%endl;/-void LRU( )int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=tempi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pagenum = curpage;display( );n=n+1;elseposition = findReplace( );blockposition.pagenum = curpage;display( );n+;else blockexist.accessed = -1;/恢復存在的并剛訪問過的BLOCK中頁面accessed為-1for(int j=0; j4; j+)blockj.accessed+;cout缺頁次數(shù):nendl;cout缺頁率:(n/320.0)*100%endl;/-void FIFO( )int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=tempi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pagenum = curpage;display( );n=n+1;elseposition = findReplace( );blockposition.pagenum = curpage;display( );n+;blockposition.accessed-;for(int j=0; jBsize; j+)blockj.accessed+;cout缺頁次數(shù):nendl;cout缺頁率:(n/320.0)*100%endl;void main( )intselect;cout請輸入第一條指令號(0320)：;suijishu( );cout*對應的調(diào)用頁面隊列*endl;pagestring( );docout*endl;cout-1:OPT2:LRU3:FIFO4:退出-endl;cout*endl;coutselect;cout*endl;init( );switch(select)case 1:cout最佳置換算法OPT:endl;cout*endl;OPT( );break;case 2:cout最近最久未使用置換算法LRU:endl;cout*endl;LRU( );break;case 3:cout先進先出置換算法FIFO:endl;cout*endl;FIFO( );break;default: ;while(select!=4);問題討論1采用首次適應算法和最佳適應算法，對內(nèi)存的分配和回收速度有什么不同的影響？答：最佳適應算法（Best Fit）：它從全部