實驗五 動態(tài)分區(qū)存儲管理模擬

1、實驗五 動態(tài)分區(qū)存儲管理模擬一、實驗?zāi)康纳钊肓私饪勺兎謪^(qū)存儲管理方式主存分配回收的實現(xiàn)。二、實驗預(yù)備知識可變分區(qū)存儲管理方式不預(yù)先將主存劃分成幾個區(qū)域，而把主存除操作系統(tǒng)占用區(qū)域外的空間看作一個大的空閑區(qū)。當(dāng)進程要求裝入主存時，根據(jù)進程需要主存空間的大小查詢主存內(nèi)各個空閑區(qū)，當(dāng)從主存空間找到一個大于或等于該進程大小要求的主存空閑區(qū)時，選擇其中一個空閑區(qū)，按進程需求量劃出一個分區(qū)裝入該進程。進程執(zhí)行完后，它所占的主存分區(qū)被回收，成為一個空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個空閑區(qū)。這個實驗主要需要考慮三個問題：(1) 設(shè)計記錄主存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)

2、和進程占用的區(qū)域；(2) 在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存分配算法；(3) 在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存回收算法。首先，考慮第一個問題：設(shè)計記錄主存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)和進程占用的區(qū)域。由于可變分區(qū)的大小是由進程需求量決定的，故分區(qū)的長度是預(yù)先不固定的，且分區(qū)的個數(shù)也隨主存分配和回收而變動?？傊蟹謪^(qū)情況隨時可能發(fā)生變化，數(shù)據(jù)表格的設(shè)計必須和這個特點相適應(yīng)。由于分區(qū)長度不同，因此設(shè)計的表格應(yīng)該包括分區(qū)在主存中的起始地址和長度。由于分配時空閑區(qū)有時會變成兩個分區(qū)：空閑區(qū)和已分分區(qū)，回收主存分區(qū)時，可能會合并空閑分區(qū)，這樣如果整個主存采用一張表格記錄已分分區(qū)和空閑區(qū)，就會使表格操

3、作繁瑣。主存分配時查找空閑區(qū)進行分配，然后填寫已分分區(qū)表，主要操作在空閑區(qū)；某個進程執(zhí)行完成后，將該分區(qū)變成空閑區(qū)，并將其與相鄰空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見，主存分配和回收主要是對空閑區(qū)的操作。這樣，為了便于對主存空間的分配和回收，就建立兩張分區(qū)表記錄主存使用情況，一張表格記錄進程占用分區(qū)的“已分分區(qū)表”；一張是記錄空閑區(qū)的“空閑區(qū)表”。這兩張表的實現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。在實驗中，采用順序表形式，用數(shù)組模擬。由于順序表的長度必須提前固定，所以無論是“已分分區(qū)表”還是“空閑區(qū)表”都必須事先確定長度。它們的長度必須是系統(tǒng)可能的最大項數(shù)，系統(tǒng)運行過程中才不會

4、出錯，因而在多數(shù)情況下，無論是“已分分區(qū)表”還是“空閑區(qū)表”都有空閑欄目。已分分區(qū)表中除了分區(qū)起始地址、長度外，也至少還要有一項“標(biāo)志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個進程占用分區(qū)的登記項，內(nèi)容為該進程的進程名；空閑區(qū)表中除了分區(qū)起始地址、長度外，也要有一項“標(biāo)志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個空閑區(qū)的登記項，內(nèi)容為“未分配”。在實際系統(tǒng)中，這兩個表格的內(nèi)容可能還要更多，實驗中僅僅使用上述必須的數(shù)據(jù)。為此，“已分分區(qū)表”和“空閑區(qū)表”在實驗中有如下的結(jié)構(gòu)定義：已分分區(qū)表的定義：#define n 10 /假定系統(tǒng)允許的進程數(shù)量最多為nstruct float addres

5、s; /已分分區(qū)起始地址 float length; /已分分區(qū)長度，單位為字節(jié) int flag; /已分分區(qū)表登記欄標(biāo)志，“0”表示空欄目，實驗中只支持一個字符的進程名 used_tablen; /已分分區(qū)表空閑區(qū)表的定義：#define m 10 /假定系統(tǒng)允許的空閑區(qū)數(shù)量最多為mstruct float address; /空閑區(qū)起始地址 float length; /空閑區(qū)長度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標(biāo)志，“0”表示空欄目，用“1”表示未分配 free_tablem; /空閑區(qū)表其中分區(qū)起始地址和長度數(shù)值太大，超出了整型的表達范圍，所以采用了float類型。

6、然后，就要考慮如何在設(shè)計的數(shù)據(jù)表格上進行主存的分配。當(dāng)要裝入一個進程時，從空閑區(qū)表中查找標(biāo)志為“未分配”的空閑區(qū)，從中找到一個能容納該進程的空閑區(qū)。如果找到的空閑區(qū)正好等于該進程的長度，則把該分區(qū)全部分配給進程。這時應(yīng)該把該空閑區(qū)登記欄中的標(biāo)志改為“空”，同時在已分分區(qū)表中找到一個標(biāo)志為“空”的欄目登記新裝入進程所占用分區(qū)的起始地址、長度和進程名。如果找到的空閑區(qū)大于進程長度，則把空閑區(qū)分成兩部分，一部分用來裝入進程，另外一部分仍為空閑區(qū)。這時只要修改元空閑區(qū)的長度，且把新裝入的進程登記到已分分區(qū)表中。實驗示例程序中主存分配算法采用最佳適應(yīng)算法。最佳適應(yīng)算法是按進程要求挑選一個能滿足進程要求的

7、最小空閑區(qū)，這樣保證可以不去分割一個大的區(qū)域，使裝入大進程時比較容易得到滿足。但是最佳適應(yīng)算法容易出現(xiàn)找到的一個分區(qū)可能只比進程所要求的長度略大一點的情況，這時，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小的空閑區(qū)往往無法使用，影響了主存的使用。為了一定程度上解決這個問題，如果空閑區(qū)的大小比進程要求的長度略大一點，不再將空閑區(qū)分成空閑區(qū)和已分分區(qū)兩部分，而是將整個空閑區(qū)分配給進程。在實現(xiàn)最佳適應(yīng)算法時，可把空閑區(qū)按長度以遞增方式登記在空閑區(qū)中。分配時順序查找空閑表，查找到的第一個空閑區(qū)就是滿足進程要求的最小分區(qū)。這樣查找速度快，但是為使空閑區(qū)按長度以遞增順序登記在空閑分區(qū)表中，就必須在分配回收時進

8、行空閑區(qū)表的調(diào)整?？臻e區(qū)表調(diào)整時移動表目的代價要高于查詢整張表的代價，所以實驗中不采用空閑區(qū)有序登記在空閑表中的方法。動態(tài)分區(qū)方式的主存分配流程圖如圖5-1所示。YNNYNYNYYNNYNYN進程P申請xk大小的主存空間i=0; k=-1;i是空閑區(qū)表中一欄（i<=m）？第i欄標(biāo)志為“未分配”且滿足進程需求xk？i = i+1第i欄空閑區(qū)為第一個滿足需求的或第i欄空閑區(qū)長度小于第k欄空閑區(qū)長度？k = i是否找到滿足需求的分區(qū)k？主存分配失敗結(jié)束第k欄長度進程需求<=minsize？分配整個分區(qū)：第k欄狀態(tài)為“空”；ad=第k欄起始地址；xk=第k欄長度；切割空閑區(qū)：第k欄長度減去

9、xk；ad=第k欄起始地址第k欄長度；i=0第i欄是已分配區(qū)表中一欄且第i欄狀態(tài)不為空？i=i+1第i欄是已分配表中的一欄？空閑分區(qū)表第k欄狀態(tài)為空？填寫已分配空閑區(qū)：第j欄起始地址=ad；第j欄長度=xk；第j欄狀態(tài)=作業(yè)名J；空閑區(qū)表狀態(tài)未分配空閑區(qū)表第k欄長度加xk已分配分區(qū)表長度不足，分配失敗結(jié)束圖5-1 動態(tài)分區(qū)最佳分配算法流程圖最后，是可變分區(qū)方式下的主存回收問題?？勺兎謪^(qū)方式下回收主存空間時，應(yīng)該檢查是否有與歸還區(qū)相鄰的空閑區(qū)。若有，則應(yīng)該合并成一個空閑區(qū)。一個歸還區(qū)可能有上鄰空閑區(qū)，也可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無上鄰空閑區(qū)又無下鄰空閑區(qū)。在實現(xiàn)回

10、收時，首先，將進程歸還的區(qū)域在已分分區(qū)表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡?；然后，檢查空閑區(qū)表中標(biāo)志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。假定進程歸還得分區(qū)起始地址為S，長度為L，則：（1） 歸還區(qū)有下鄰空閑區(qū) 如果S+L正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址，則表明歸還區(qū)有一個下鄰空閑區(qū)。這時只要修改第j欄登記項的內(nèi)容： 起始地址=S； 第j欄長度=第j欄長度+L； 則第j欄指示的空閑區(qū)是歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)。（2） 歸還區(qū)有上鄰空閑區(qū) 如果空閑區(qū)表中某個登記欄目（假定為第k欄）的“起始地址+長度” 正好等于S，則表明歸還區(qū)有

11、一個上鄰空閑區(qū)。這時要修改第k欄登記項的內(nèi)容（起始地址不變）： 第k欄長度=第k欄長度+L； 則第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)。（3） 歸還區(qū)既有上鄰空閑區(qū)又有下鄰空閑區(qū) 如果S+L正好等于空閑區(qū)表中某個登記欄目（假定為第j欄）的起始地址，同時還有某個登記欄目（假定為第k欄）的“起始地址+長度” 正好等于S，這表明歸還區(qū)既有一個上鄰空閑區(qū)，又有一個下鄰空閑區(qū)。這時對空閑區(qū)表的修改如下： 第k欄長度=第k欄長度+第j欄長度+L；（第k欄起始地址不變）第j欄狀態(tài)=“空”；（將第j欄登記項刪除） 則第k欄指示的空閑區(qū)是歸還區(qū)和上、下鄰空閑區(qū)合并后的大空閑區(qū)；原來的下鄰空閑區(qū)登

12、記項（第j欄）被刪除，置為“空”。（4） 歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)如果在檢查空閑區(qū)表時，無上述三種情況出現(xiàn)，則表明歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)。這時，應(yīng)該在空閑區(qū)表中查找一個狀態(tài)為“空”的欄目（假定查到的是第t欄），則第t欄的內(nèi)容修改如下：第t欄起始地址=S；第t欄長度=L；第t欄狀態(tài)=“未分配”這樣，第t欄指示的空閑區(qū)是歸還區(qū)。按上述方法歸還主存區(qū)域的流程圖如圖5-2所示。由于是模擬實驗，沒有真正的主存要分配，所以在實驗中：首先，應(yīng)建立一張空閑區(qū)表，初始狀態(tài)只有一個空閑登記項（假定的主存空閑區(qū)）和一張所有狀態(tài)都為“空”的已分分區(qū)表，假定主存空間為110KB，操作系統(tǒng)占用10K

13、B，其余為空閑區(qū)；然后，可以選擇進行主存分配或主存回收，如果是分配，要求輸入進程名和所需主存空間大小，如果是回收，輸入回收進程的進程名，循環(huán)進行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。NYYYYYYYYYYNNNNNNNNNN已分配區(qū)表第s欄狀態(tài)為進程P(s<=n)？S=已分配區(qū)表第s欄起始地址L=已分配區(qū)表第s欄長度已分配區(qū)表第s欄狀態(tài)為空假設(shè)下鄰空閑區(qū)在第j欄j=-1;假設(shè)上鄰空閑區(qū)在第k欄k=-1;進程P歸還空間s=0s=s+1s為已分配區(qū)表中一欄？i=0第i欄不是空閑區(qū)表中一欄或回收分區(qū)的上下鄰空閑區(qū)均找到？第i欄狀態(tài)為“未分配”？第i欄為

14、回收分區(qū)的上鄰？第i欄為回收分區(qū)的下鄰？i=i+1j=ij=i回收分區(qū)有上鄰？回收分區(qū)有下鄰？回收分區(qū)有下鄰？和上下鄰三項合并：第k欄長度=第k欄長度+第j欄長度+L；第j欄狀態(tài)=“空”和上鄰合并：第k欄長度=第k欄長度+L和下鄰合并：第j欄長度=第j欄長度+L；第j欄起始地址=St=0第t欄是空閑表中非空欄？空閑區(qū)表滿？t=t+1歸還分區(qū)填入空閑區(qū)表：第t欄起始地址=S；第t欄長度=L；第t欄狀態(tài)=“未分配”；已分配區(qū)表第s欄狀態(tài)為J；空閑表長度不足，回收失敗結(jié) 束未找到進程，回收失敗結(jié) 束Y圖5-2 動態(tài)分區(qū)回收流程圖三、實驗內(nèi)容編寫程序完成可變分區(qū)存儲管理方式的主存分配回收的實現(xiàn)。在已給

15、參考示例程序的基礎(chǔ)上，完成如下任務(wù)：（1）采用鏈表形式的主存分區(qū)空閑表；（2）采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最差適應(yīng)算法完成主存空間的分配和回收；（3）編寫主函數(shù)對所做工作進行測試。 參考程序#define n 10 /假定系統(tǒng)允許的進程數(shù)量最多為n#define m 10 /假定系統(tǒng)允許的空閑區(qū)數(shù)量最多為m#define minisize 100struct float address; /已分分區(qū)起始地址 float length; /已分分區(qū)長度，單位為字節(jié)int flag; /已分分區(qū)表登記欄標(biāo)志，“0”表示空欄目，實驗中只支持一個字符的進程名 used_tablen; /已分分

16、區(qū)表struct float address; /空閑區(qū)起始地址 float length; /空閑區(qū)長度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標(biāo)志，“0”表示空欄目，用“1”表示未分配 free_tablem; /空閑區(qū)表allocate(char P , float xk) /采用最佳適應(yīng)算法為進程P分配xk大小的主存空間 int i, k; float ad; k= -1; for(i=0; i<m; i+) /尋找主存空間中大于xk的最小空閑區(qū)登記項kif(free_tablei.length>=xk && free_tablei.flag=1)

17、 if(k= -1 | free_tablei.length<free_tablek.length) k=i;if(k= -1) /未找到可用空閑區(qū)，返回 printf(“無可用空閑區(qū)n”);return;/找到可用空閑區(qū)，開始分配：若空閑區(qū)大小與要求分配的空間差小于或等于minisize，則空閑區(qū)全部分配；若空閑區(qū)大小與要求分配的空間差大于minisize，則從空閑區(qū)劃出一部分分配if(free_tablek.length-xk<=minisize)free_tablek.flag=0;ad=free_tablek.address;xk= free_tablek.length;e

18、lse free_tablek.length= free_tablek.length-xk; ad= free_tablek.address+ free_tablek.length;/修改已分分區(qū)表i=0;while(used_tablei.flag!=0 && i<n) /尋找空表目 i+;if(i>=n) /無表目填寫已分分區(qū) printf(“無表目填寫已分分區(qū)，錯誤！n”); /修正空閑區(qū)表 if(free_tablek.flag=0) /前面找到的是整個空閑區(qū) free_tablek.flag=1; else /前面找到的是某個空閑區(qū)的一部分 free_ta

19、blek.length= free_tablek.length+xk; return;else /修改已分分區(qū)表 used_tablei. address=ad; used_tablei. length=xk; used_tablei.flag=J;return;/主存分配函數(shù)結(jié)束reclaim(char P) /回收進程名為P的進程所占的主存空間 int i,k,j,s,t; float S,L; /尋找已分分區(qū)表中對應(yīng)登記項 s=0; while(used_tables.flag!=P | used_tables.flag=0) && s<n)s+; if(s>=n) /已分分區(qū)表中找不到名為P的進程，返回 printf(“找不到該進程n”);return;/修改已分分區(qū)表used_tables.flag=0;/取得歸還分區(qū)的起始地址S和長度LS= used_tables. address;L= used_tables. length;j=-1;k=-1;i=0;/尋找歸還