實(shí)驗(yàn)五 動(dòng)態(tài)分區(qū)存儲(chǔ)管理模擬

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

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

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

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

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

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

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

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

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

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

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

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

13、b，其余為空閑區(qū)；然后，可以選擇進(jìn)行主存分配或主存回收，如果是分配，要求輸入進(jìn)程名和所需主存空間大小，如果是回收，輸入回收進(jìn)程的進(jìn)程名，循環(huán)進(jìn)行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。nyyyyyyyyyynnnnnnnnnn已分配區(qū)表第s欄狀態(tài)為進(jìn)程p(s<=n)？s=已分配區(qū)表第s欄起始地址l=已分配區(qū)表第s欄長(zhǎng)度已分配區(qū)表第s欄狀態(tài)為空假設(shè)下鄰空閑區(qū)在第j欄j=-1;假設(shè)上鄰空閑區(qū)在第k欄k=-1;進(jìn)程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ū)有下鄰？和上下鄰三項(xiàng)合并：第k欄長(zhǎng)度=第k欄長(zhǎng)度+第j欄長(zhǎng)度+l；第j欄狀態(tài)=“空”和上鄰合并：第k欄長(zhǎng)度=第k欄長(zhǎng)度+l和下鄰合并：第j欄長(zhǎng)度=第j欄長(zhǎng)度+l；第j欄起始地址=st=0第t欄是空閑表中非空欄？空閑區(qū)表滿？t=t+1歸還分區(qū)填入空閑區(qū)表：第t欄起始地址=s；第t欄長(zhǎng)度=l；第t欄狀態(tài)=“未分配”；已分配區(qū)表第s欄狀態(tài)為j；空閑表長(zhǎng)度不足，回收失敗結(jié) 束未找到進(jìn)程，回收失敗結(jié) 束y圖5-2 動(dòng)態(tài)分區(qū)回收流程圖三、實(shí)驗(yàn)內(nèi)容編寫程序完成可變分區(qū)存儲(chǔ)管理方式的主存分配回收的實(shí)現(xiàn)。在已給

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

16、區(qū)表struct float address; /空閑區(qū)起始地址 float length; /空閑區(qū)長(zhǎng)度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標(biāo)志，“0”表示空欄目，用“1”表示未分配 free_tablem; /空閑區(qū)表allocate(char p , float xk) /采用最佳適應(yīng)算法為進(jìn)程p分配xk大小的主存空間 int i, k; float ad; k= -1; for(i=0; i<m; i+) /尋找主存空間中大于xk的最小空閑區(qū)登記項(xiàng)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ū)，錯(cuò)誤！n”); /修正空閑區(qū)表 if(free_tablek.flag=0) /前面找到的是整個(gè)空閑區(qū) free_tablek.flag=1; else /前面找到的是某個(gè)空閑區(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) /回收進(jìn)程名為p的進(jìn)程所占的主存空間 int i,k,j,s,t; float s,l; /尋找已分分區(qū)表中對(duì)應(yīng)登記項(xiàng) s=0; while(used_tables.flag!=p | used_tables.flag=0) && s<n)s+; if(s>=n) /已分分區(qū)表中找不到名為p的進(jìn)程，返回 printf(“找不到該進(jìn)程n”);return;/修改已分分區(qū)表used_tables.flag=0;/取得歸還分區(qū)的起始地址s和長(zhǎng)度ls= used_tables. address;l= used_tables. length;j=-1;k=-1;i=0;/尋找歸還