分頁式管理實驗報告

題 目 連續(xù)式與分頁式主存管理模式的模擬實現(xiàn) 學(xué)生姓名 學(xué) 號 學(xué) 院 專 業(yè) 計算機科學(xué)與技術(shù)專業(yè)指導(dǎo)教師 趙曉平二一二年六月十一日一、實驗?zāi)康哪M在連續(xù)分配與分頁管理兩種方式下，主存空間的分配與回收，幫助學(xué)生加深了解存儲器管理的工作過程。注意，該實驗為模擬實驗，并不要求進行真正的內(nèi)存分配與回收，主要是編寫程序模擬其中過程即可。二、實驗內(nèi)容 1 連續(xù)式分配1、 在連續(xù)分配方式下，設(shè)計一個動態(tài)分區(qū)分配與回收的內(nèi)存管理程序。2、 動態(tài)分區(qū)分配按作業(yè)需要的主存大小來分割分區(qū)。當要裝入一個作業(yè)時，根據(jù)作業(yè)需要、的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。3、 設(shè)置一張全局分區(qū)狀態(tài)表說明當前內(nèi)存分配狀態(tài)，例如下所示：05k10k14k26k32k640k操作系統(tǒng)區(qū)作業(yè)1作業(yè)3空閑區(qū)作業(yè)2空閑區(qū)4、 設(shè)置一張空閑分區(qū)表描述當前空閑分區(qū)分布狀況，可采用數(shù)組或鏈表來實現(xiàn)，數(shù)組可參考以下格式：起 址長 度狀 態(tài)第一欄14 K12 K未 分 配第二欄32 K96 K未 分 配MM空 表 目空 表 目M 說明：起址指出一個空閑區(qū)的主存起始地址。長度指出從起始地址開始的一個連續(xù)空閑的長度。狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對應(yīng)的由起址指出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應(yīng)的登記項目是空白（無效），可用來登記新的空閑區(qū)。5、 在作業(yè)撤銷后，系統(tǒng)需要回收分區(qū)。在空閑分區(qū)表中找到一個空表目登記回收分區(qū)的起址和長度，并且修改表目狀態(tài)為未分配。注意：由于分區(qū)的個數(shù)不定，所以空閑分區(qū)表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。6、 在回收分區(qū)時，應(yīng)考慮相鄰空閑分區(qū)合并。7、 在完成一次作業(yè)裝入后，都需要輸出：本次分配的分區(qū)起址與長度，全局分區(qū)狀態(tài)表，空閑分區(qū)表的內(nèi)容。若在分配中發(fā)生分割，需要說明分割后新空白分區(qū)的起址與長度。8、 在完成一次作業(yè)撤銷后，都需要輸出：本次回收的分區(qū)起址與長度，全局分區(qū)狀態(tài)表，空閑分區(qū)表的內(nèi)容。若發(fā)生相鄰空閑分區(qū)合并，需要說明哪幾個分區(qū)合并在一起，合并后的起址與長度2、分頁式管理1、 設(shè)計一個基本分頁存儲管理程序2、 分頁式存儲器把主存分成大小相等的若干塊，作業(yè)的信息也按塊的大小分頁，作業(yè)裝入主存時按頁分散存放在主存的空閑塊中。3、 系統(tǒng)用一張塊表記錄物理塊分配的情況，如下圖所示，其中狀態(tài)0表示未分配，1表示已分配。另外增加一個空閑塊數(shù)，記錄當前可用的物理塊總數(shù)。狀態(tài)第0塊1第1塊1第2塊0第3塊1第4塊0MM4、 需要為每個作業(yè)設(shè)置一張頁表，記錄頁號與塊號的對應(yīng)關(guān)系。頁 號塊 號0168172256MM5、 作業(yè)裝入內(nèi)存時，分配過程如下：a) 將空閑塊數(shù)乘上每塊空間，計算出可用空間總數(shù)，然后與作業(yè)需要空間比較，若不能滿足需要，提示不能裝入。b) 若能滿足需要，為作業(yè)創(chuàng)建頁表，在塊表中尋找足夠的空白塊，將頁號與塊號一一對應(yīng)，并填入頁表。同時修改塊表中各個塊的狀態(tài)c) 修改空閑塊數(shù)，記錄剩下空白塊總數(shù)。6、 作業(yè)撤銷后，需要回收物理塊，回收過程如下：a) 根據(jù)頁表，修改塊表中對應(yīng)各個物理塊的狀態(tài)b) 修改空閑塊數(shù)，記錄回收后空白塊總數(shù)。c) 撤銷頁表7、 每次作業(yè)裝入或回收，都需要輸出塊表、頁表的內(nèi)容，發(fā)生變化的塊號，以及空閑塊數(shù)。若塊表太大，可以用二維表格的方式輸出，或只輸出發(fā)生變化的塊號。三、實驗要求1、 根據(jù)例程，嘗試采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法其中的一種或多種算法實現(xiàn)3.2.1的動態(tài)分區(qū)分配。算法思想請參考課本的分區(qū)分配算法。2、 根據(jù)例程，嘗試實現(xiàn)3.2.1的分區(qū)回收功能。3、 根據(jù)例程，嘗試實現(xiàn)3.2.2的分頁系統(tǒng)功能4、 至少完成上述三項實驗內(nèi)容中的一個。5、 自行設(shè)定內(nèi)存總空間，大小單位為KB，分頁管理需要設(shè)定每個頁的大小。6、 隨機設(shè)置當前內(nèi)存分配狀態(tài)。7、 自行設(shè)計作業(yè)隊列，隊列中至少要有5個作業(yè)，設(shè)定各個作業(yè)空間大小，大小要適中。8、 輸出結(jié)果要盡量詳細清晰，如果輸出內(nèi)容比較多，可以考慮把輸出結(jié)果保存到文件中，通過文件來查看。9、 程序代碼要盡量加入注釋，提高程序的清晰度與可讀性。10. 在實驗報告中，一方面可以對實驗結(jié)果進行分析，一方面可以對兩種分配方式進行比較，分析它們的優(yōu)劣。四、實驗過程1.分頁式：/分頁存儲管理程序#include #include#include#include #include #define n 11 /模擬實驗中允許的最大進程數(shù)為n#define m 11 /模擬實驗中允許的最大分區(qū)個數(shù)為m#define M_SIZE 2000 struct float address; /分配給進程的起始地址float length; /分配給進程的空閑區(qū)長度，單位為字節(jié)int flag; /分配區(qū)表標志，用0已分配，用1表示未分配Used_Tablem; /分配分區(qū)表struct float address; float length; int flag; Free_tablem; float stand_length(int k)/隨機產(chǎn)生一個分區(qū)大小的函數(shù)float st_length20;srand(unsigned)time(NULL);/srand()函數(shù)產(chǎn)生一個當前時間開始的隨機種子for (int i=0;i20;i+)st_lengthi=float (rand()%1000);return st_lengthk;float process_length(int k)/隨機產(chǎn)生一個進程大小的函數(shù)float pt_length20;srand(unsigned)time(NULL);/srand()函數(shù)產(chǎn)生一個當前時間開始的隨機種子for (int i=0;i20;i+)pt_lengthi= float (rand()%500);return pt_lengthk;int process_num()/隨機產(chǎn)生一個進程個數(shù)的函數(shù)int num;int A10=1,2,3,4,5,6,7,8,9,10;srand(unsigned)time(NULL);num=rand()%10;return Anum;char srand_name(int k)/隨機產(chǎn)生一個進程的名字char A26=A,B,C,D,E,F,G,H,I, J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; return Ak;void allocate(char PRS_NAME,float X_K) /采用最優(yōu)分配算法為進程PRS_NAME分配X_K大小的空間 int i,k; float ad; k=-1; for(i=0;i=X_K&Free_tablei.flag=1) if(k=-1|Free_tablei.lengthFree_tablek.length) k=i; if(k=-1)/未找到可用空閑分區(qū)，返回 printf(無可用空閑區(qū)n); return; /找到可用空閑區(qū)，開始分配：if(Free_tablek.length-X_K=M_SIZE) Free_tablek.flag=0; ad=Free_tablek.address; X_K=Free_tablek.length; else Free_tablek.length=Free_tablek.length-X_K; ad=Free_tablek.address+Free_tablek.length; /修改已分配區(qū)表i=0; while(Used_Tablei.flag!=0&i=n) /無表目填寫已分分區(qū) printf(無表目填寫已分分區(qū)，錯誤n); /修正空閑區(qū)表 if(Free_tablek.flag=0) /前面找到的是整個空閑分區(qū) Free_tablek.flag=1; else /前面找到的是某個空閑分區(qū)的一部分 Free_tablek.length=Free_tablek.length+X_K; return; else /修改已分配表 Used_Tablei.address=ad; Used_Tablei.length=X_K; Used_Tablei.flag=PRS_NAME; return; /內(nèi)存分配函數(shù)結(jié)束 void reclaim(char PRS_NAME) /回收進程名為PRS_NAME的進程所占內(nèi)存空間 int i,k,j,s,t; float S,L; /尋找已分配表中對應(yīng)登記項 s=0; while(Used_Tables.flag!=PRS_NAME|Used_Tables.flag=0)&s=n)/在已分配表中找不到名字為PRS_NAME的進程 cout找不到該進程endl; return; /修改已分配表Used_Tables.flag=0; /取得歸還分區(qū)的起始地址S和長度LS=Used_Tables.address; L=Used_Tables.length; j=-1;k=-1;i=0; /尋找回收分區(qū)的空閑上下鄰，上鄰表目k，下鄰表目jwhile(im&(j=-1|k=-1) if(Free_tablei.flag=1) if(Free_tablei.address+Free_tablei.length=S)k=i;/找到上鄰if(Free_tablei.address=S+L)j=i;/找到下鄰 i+; if(k!=-1) if(j!=-1) / 上鄰空閑區(qū)，下鄰空閑區(qū)，三項合并 Free_tablek.length=Free_tablej.length+Free_tablek.length+L; Free_tablej.flag=1; else /上鄰空閑區(qū)，下鄰非空閑區(qū)，與上鄰合并Free_tablek.length=Free_tablek.length+L; else if(j!=-1) /上鄰非空閑區(qū)，下鄰為空閑區(qū)，與下鄰合并 Free_tablej.address=S; Free_tablej.length=Free_tablej.length+L; else /上下鄰均為非空閑區(qū)，回收區(qū)域直接填入 /在空閑區(qū)表中尋找空欄目 t=0; while(Free_tablet.flag=1&t=m)/空閑區(qū)表滿,回收空間失敗,將已分配表復(fù)原 cout內(nèi)存空閑表沒有空間,回收空間失敗endl; Used_Tables.flag=j; return; Free_tablet.address=S; Free_tablet.length=L; Free_tablet.flag=1; return; void main( ) int i,a; float p_length; char p_name; /空閑分區(qū)表初始化：int t_P;Free_table0.address=1000;for(t_P=0; t_Pm; t_P+)Free_tablet_P.length=stand_length(t_P); Free_tablet_P.flag=1; for(t_P=1;t_Pm;t_P+)Free_tablet_P.address=Free_tablet_P-1.address+Free_tablet_P-1.length; /空閑分區(qū)表初始化結(jié)束 /已分配表初始化：for(i=0;in;i+) Used_Tablei.flag=0; cout*分頁式主存管理的模擬實現(xiàn)*endlendl;cout*選擇以下標號實現(xiàn)其功能*endl;cout* 0:退出 2:回收進程和內(nèi)存 *endl;cout* 1:隨機產(chǎn)生進程并分配內(nèi)存 3:顯示內(nèi)存分配記錄 *endl;cout*endl;while(1) cout請輸入一個功能項(0-3) :a;switch(a) case 0: return; /a=0選擇退出程序結(jié)束 case 1: /a=1開始隨機的產(chǎn)生進程并分配空間int p_num=process_num();cout隨機產(chǎn)生p_num個進程endl;int p_p;cout進程名 進程大小endl;for(p_p=0;p_pp_num;p_p+)p_name=srand_name(p_p);p_length= process_length(p_p);coutp_name p_lengthendl;allocate(p_name,p_length); /分配內(nèi)存空間 cout要查看內(nèi)存分配請在提示命令出現(xiàn)后輸入3回車endl;break; case 2: /a=2回收內(nèi)存空間 coutp_name; reclaim(p_name); /回收內(nèi)存空間 break; case 3: /a=3顯示內(nèi)存情況 cout輸出空閑區(qū)表：endl;cout-endl;cout起始地址 分區(qū)大小 標志(0-已分配，1-未分配)endl; for(i=0;im;i+) printf(%6.0f%9.0f%6dn,Free_tablei.address,Free_tablei.length, Free_tablei.flag); cout已分配分區(qū)表：endl;cout-endl;cout起始地址 分區(qū)大小 進程名endl;for(i=0;in;i+) if(Used_Tablei.flag!=0) printf(%6.0f%9.0f%6cn,Used_Tablei.address,Used_Tablei.length, Used_Tablei.flag); break; default:cout請輸入正確的選項！endl; 截圖：2. 首次適應(yīng)算法實現(xiàn)動態(tài)分區(qū)分配代碼：#include#include#include#include#define getpch(type) (type*)malloc(sizeof(type)/*/#define NULL 0*/struct table char name10; char state; /* D(分配) or N(空閑)*/ int size; /*分區(qū)大小*/ int addr; /*起始地址*/ struct table *next; struct table *prev;*tab=NULL,*p;typedef struct table TABLE;UI()printf(n); printf( 首次適應(yīng)算法 n); printf( n); printf( 計科3班 顧志祥 n); printf(n);recycle(char n10)TABLE *pr=NULL;for(pr=tab;pr!=NULL;pr=pr-next)if(!strcmp(pr-name,n)&pr-state=D)if(pr-prev!=NULL&pr-prev-state=N) /*回收區(qū)的前一分區(qū)空閑*/if(pr-next-state=N) /*回收區(qū)的前后分區(qū)都空閑*/pr-state=N;pr-prev-size+=(pr-size+pr-next-size); /*合并分區(qū)大小*/pr-prev-next=pr-next-next; /*刪除回收分區(qū)及其后一空閑分區(qū)表項*/pr-next-next-prev=pr-prev;return 0;else pr-state=N;pr-prev-size+=pr-size;pr-next-prev=pr-prev;pr-prev-next=pr-next;return 0;else if(pr-next!=NULL&pr-next-state=N)pr-state=N;pr-size+=pr-next-size;if(pr-next-next!=NULL)pr-next-next-prev=pr;pr-next=pr-next-next;else pr-next=NULL;return 0;if(pr=NULL) printf(錯誤!此分區(qū)不存在或未分配作業(yè)或前后分區(qū)都不空閑!n); else printf(分區(qū)%s回收完畢!n,pr-name);return 0;allocate(int s)TABLE *pt=NULL,*q;for(pt=tab;pt!=NULL;pt=pt-next)if(pt-size=s&pt-state=N)pt-state=D;if(pt-sizes)q=getpch(TABLE);printf(請輸入分割出的分區(qū)ID:n); scanf(%s,q-name);q-size=pt-size-s; /*分割分區(qū)*/pt-size-=q-size;q-state=N;q-addr=pt-addr+pt-size;if(pt-next!=NULL)pt-next-prev=q; /*在空閑鏈中插入新的分區(qū)*/q-next=pt-next;pt-next=q;q-prev=pt;return 0;pt-next=q;q-prev=pt;q-next=NULL;return 0;/*for*/printf(沒有合適的分區(qū),此次分配失敗!n);return 0;display() TABLE *pt=tab; if(pt=NULL) return 0; printf(-空閑分區(qū)情況-n); printf(IDt狀態(tài)t大小t起始地址n); while(pt!=NULL) printf(%2st%3ct%3dt%5dn,pt-name,pt-state,pt-size,pt-addr); pt=pt-next; return 0;sorttable() /*分區(qū)按升序排列*/ TABLE *first, *second; if(tab=NULL) p-next=tab; tab=p; else first=tab; second=first-next; while(second!=NULL) first=first-next; second=second-next; first-next=p; InitTab() int num; int i,paddr=0; TABLE *pn; /*指向前一結(jié)點*/ pn=NUL