實(shí)驗(yàn)三動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收實(shí)驗(yàn)三動(dòng)態(tài)分區(qū)存儲(chǔ)

1、實(shí)驗(yàn)三 動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收1實(shí)驗(yàn)?zāi)康纳钊肓私鈩?dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收的實(shí)現(xiàn)。2實(shí)驗(yàn)預(yù)備知識(shí)存儲(chǔ)管理中動(dòng)態(tài)分區(qū)的管理方式。3實(shí)驗(yàn)內(nèi)容編寫(xiě)程序完成動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收的實(shí)現(xiàn)。實(shí)驗(yàn)具體包括：首先確定主存空間分配表；然后采用最優(yōu)適應(yīng)算法完成主存空間的分配，完成主存空間的回收；最后編寫(xiě)主函數(shù)對(duì)所作工作進(jìn)程測(cè)試。存分配時(shí)查找空閑區(qū)進(jìn)行分配，然后填寫(xiě)已分配區(qū)表，主要操作在空閑區(qū)；某個(gè)作業(yè)執(zhí)行完后，將該分區(qū)變成空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見(jiàn)，主存的分配和回收主要是對(duì)空閑區(qū)的操作。這樣為了便于對(duì)主存空間的分配和回收，就建立兩張分區(qū)表記錄主存

2、使用情，一張表格記錄作業(yè)占用分區(qū)的“已分配區(qū)表”；一張是記錄空閑區(qū)的“空閑區(qū)表”。這兩張表的實(shí)現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。在實(shí)驗(yàn)中，采用順序表形式，用數(shù)組模擬。由于順序表的長(zhǎng)度必須提前固定，所以無(wú)論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長(zhǎng)度。它們的長(zhǎng)度必須是系統(tǒng)可能的最大項(xiàng)數(shù)，系統(tǒng)運(yùn)行過(guò)程中才不會(huì)出錯(cuò)，因而在多數(shù)情況下，無(wú)論是“已分配區(qū)表”還是“空閑區(qū)表”都有空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長(zhǎng)度外，也至少還要有一項(xiàng)“標(biāo)志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個(gè)作業(yè)占用分區(qū)的登記項(xiàng)，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表中除了分區(qū)起始地址、長(zhǎng)度外，也要有一項(xiàng)“

3、標(biāo)志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個(gè)空閑區(qū)的登記項(xiàng)，內(nèi)容為“未分配”（。在實(shí)際系統(tǒng)中，這兩表格的內(nèi)容可能還要多，實(shí)驗(yàn)中僅僅使用上述必須的數(shù)據(jù)。為此,“已分配區(qū)表”和“空閑區(qū)表”在實(shí)驗(yàn)中有如下的結(jié)構(gòu)定義。已分配區(qū)表的定義：#define n 10 /假定系統(tǒng)允許的最大作業(yè)數(shù)量為nstructfloat address; /已分分區(qū)起始地址 float length; /已分分區(qū)長(zhǎng)度，單位為字節(jié) int flag; /已分配區(qū)表登記欄標(biāo)志，“0”表示空欄目，實(shí)驗(yàn)中只支持一個(gè)字符的作業(yè)名used_tablen; /已分配區(qū)表空閑區(qū)表的定義：#define m 10 /假定系統(tǒng)允許的空閑區(qū)

4、表最大為mstructfloat address; /空閑區(qū)起始地址 float length; /空閑區(qū)長(zhǎng)度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標(biāo)志，用“0”表示空欄目，用“1”表示未分配free_tablem; /空閑區(qū)表其中分區(qū)起始地址和長(zhǎng)度數(shù)值太大，超出了整型表達(dá)范圍，所以采用了float類(lèi)型。然后，就要考慮如何在設(shè)計(jì)的數(shù)據(jù)表格上進(jìn)行主存的分配。當(dāng)要裝入一個(gè)作業(yè)時(shí)，從空閑區(qū)表中查找標(biāo)志為“未分配”的空閑區(qū)，從中找出一個(gè)能容納該作業(yè)的空閑區(qū)。如果找到的空閑區(qū)正好等于該作業(yè)的長(zhǎng)度，則把該分區(qū)全部分配給作業(yè)。這時(shí)應(yīng)該把該空閑區(qū)登記欄中的標(biāo)志改為“空”，同時(shí)在已分配區(qū)表中找到一個(gè)

5、標(biāo)志為“空”的欄目登記新裝入作業(yè)所占用分區(qū)的起始地址、長(zhǎng)度和作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長(zhǎng)度，則把空閑區(qū)分成兩部分，一部分用來(lái)裝入作業(yè)，另外一部分仍為空閑區(qū)。這時(shí)只要修改原空閑區(qū)的長(zhǎng)度，且把新裝入的作業(yè)登記到已分配區(qū)表中。實(shí)驗(yàn)中主存分配算法采用“最優(yōu)適應(yīng)”算法。最優(yōu)適應(yīng)算法是按作業(yè)要求挑選一個(gè)能滿(mǎn)足作業(yè)要求的最小空閑區(qū)，這樣保證可以不去分割一個(gè)大的區(qū)域，使裝入大作業(yè)時(shí)比較容易得到滿(mǎn)足。但是最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個(gè)分區(qū)可能只比作業(yè)所要求的長(zhǎng)度略大一點(diǎn)的情況，這時(shí)，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小的空閑區(qū)往往無(wú)法使用，卻影響了主存的使用。為了一定程度上解決這個(gè)問(wèn)題，如果空閑區(qū)的大

6、小比作業(yè)要求的長(zhǎng)度略大一點(diǎn)，不再將空閑區(qū)分成已分分區(qū)和空閑區(qū)兩部分，而是將整個(gè)空閑區(qū)分配給作業(yè)。在實(shí)現(xiàn)最優(yōu)適應(yīng)算法時(shí)，可把空閑區(qū)按長(zhǎng)度以遞增方式登記在空閑區(qū)表中。分配時(shí)順序查找空閑表，查找到的第一個(gè)空閑區(qū)就是滿(mǎn)足作業(yè)要求的最小分區(qū)。這樣查找速度快，但是為使空閑區(qū)按長(zhǎng)度以遞增順序登記在空閑表中，就必須在分配回收時(shí)進(jìn)行空閑區(qū)表的調(diào)整。空閑區(qū)表調(diào)整時(shí)移動(dòng)表目的代價(jià)要高于查詢(xún)整張表的代價(jià)，所以實(shí)驗(yàn)中不采用空閑區(qū)有序登記在空閑表中的方法。動(dòng)態(tài)分區(qū)方式的主存分配流程圖如圖2.4所示。最后是動(dòng)態(tài)分區(qū)方式下的主存回收問(wèn)題。動(dòng)態(tài)分區(qū)方式下回收主存空間時(shí)，應(yīng)該檢查是否有與歸還區(qū)相鄰的空閑區(qū)。若有，則應(yīng)該合并成一個(gè)

7、空閑區(qū)。一個(gè)歸還區(qū)可能有上鄰空閑區(qū)，也可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無(wú)上鄰空閑區(qū)也無(wú)下鄰空閑區(qū)。在實(shí)現(xiàn)回收時(shí)，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡?，然后檢查空閑區(qū)表中標(biāo)志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。假定作業(yè)歸還的分區(qū)起始地址為s，長(zhǎng)度為l，則： 歸還區(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ū)； 歸還

8、區(qū)有上鄰空閑區(qū)如果空閑區(qū)表中某個(gè)登記欄目（假定為第k欄）的“起始地址+長(zhǎng)度”正好等于s，則表明歸還區(qū)有一個(gè)上鄰空閑區(qū)。這時(shí)要修改第k欄登記項(xiàng)的內(nèi)容（起始地址不變）：第k欄長(zhǎng)度=第k欄長(zhǎng)度+l；于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)；2 歸還區(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)

9、刪除）這樣，第k欄指示的空閑區(qū)是歸還區(qū)和上、下鄰空閑區(qū)合并后的大空閑區(qū)；原來(lái)的下鄰空閑區(qū)登記項(xiàng)（第j欄）被刪除，置為“空”。 2.4 動(dòng)態(tài)分區(qū)最優(yōu)分配算法流程圖4圖2.5 動(dòng)態(tài)分區(qū)回收流程圖 歸還區(qū)既無(wú)上鄰空閑區(qū)又無(wú)下鄰空閑區(qū)如果在檢查空閑區(qū)表時(shí)，無(wú)上述三種情況出現(xiàn)，則表明歸還區(qū)既無(wú)上鄰空閑區(qū)又無(wú)下鄰空閑區(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ū)域的流程圖如圖2.5所示。由于是實(shí)驗(yàn)，沒(méi)有真正的主存要分配，所以在實(shí)驗(yàn)中，首先應(yīng)建

10、立一張空閑區(qū)表，初始狀態(tài)只有一個(gè)空閑登記項(xiàng)（假定的主存空閑區(qū)）和一張所有狀態(tài)都為“空”的已分配區(qū)表，假定主存空間110kb，操作系統(tǒng)占用10kb,其余為空閑區(qū)；然后，可以選擇進(jìn)行主存分配或主存回收，如果是分配，要求輸入作業(yè)名和所需主存空間大小，如果是回收，輸入回收作業(yè)的作業(yè)名，循環(huán)進(jìn)行主存分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分配和回收是否正確。4提示與講解動(dòng)態(tài)分區(qū)管理方式預(yù)先不將主存劃分成幾個(gè)區(qū)域，而把主存除操作系統(tǒng)占用區(qū)域外的空間看作一個(gè)大的空閑區(qū)。當(dāng)作業(yè)要求裝入主存時(shí)，根據(jù)作業(yè)需要的主存空間的大小查詢(xún)主存內(nèi)各個(gè)空閑區(qū)，當(dāng)從主存空間中找到一個(gè)大于或等于該作業(yè)大小的主存空閑

11、區(qū)時(shí)，選擇其中一個(gè)空閑區(qū)，按作業(yè)需求量劃出一個(gè)分區(qū)裝入該作業(yè)。作業(yè)執(zhí)行完后，它所占的主存分區(qū)被收回，成為一個(gè)空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個(gè)空閑區(qū)。實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的分配和回收，主要考慮的問(wèn)題有三個(gè)：第一，設(shè)計(jì)記錄主存使用情況的數(shù)據(jù)表格，用來(lái)記錄空閑區(qū)和作業(yè)占用的區(qū)域；第二，在設(shè)計(jì)的數(shù)據(jù)表格基礎(chǔ)上設(shè)計(jì)主存分配算法；第三，在設(shè)計(jì)的數(shù)據(jù)表格基礎(chǔ)上設(shè)計(jì)主存回收算法。首先，考慮第一個(gè)問(wèn)題：設(shè)計(jì)記錄存分配時(shí)查找空閑區(qū)進(jìn)行分配，然后填寫(xiě)已分配區(qū)表，主要操作在空閑區(qū)；某個(gè)作業(yè)執(zhí)行完后，將該分區(qū)變成空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑區(qū)。由此可見(jiàn)，主存的分配和回

12、收主要是對(duì)空閑區(qū)的操作。這樣為了便于對(duì)主存空間的分配和回收，就建立兩張分區(qū)表記錄主存使用情，一張表格記錄作業(yè)占用分區(qū)的“已分配區(qū)表”；一張是記錄空閑區(qū)的“空閑區(qū)表”。這兩張表的實(shí)現(xiàn)方法一般有兩種，一種是鏈表形式，一種是順序表形式。在實(shí)驗(yàn)中，采用順序表形式，用數(shù)組模擬。由于順序表的長(zhǎng)度必須提前固定，所以無(wú)論是“已分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長(zhǎng)度。它們的長(zhǎng)度必須是系統(tǒng)可能的最大項(xiàng)數(shù)，系統(tǒng)運(yùn)行過(guò)程中才不會(huì)出錯(cuò)，因而在多數(shù)情況下，無(wú)論是“已分配區(qū)表”還是“空閑區(qū)表”都有空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長(zhǎng)度外，也至少還要有一項(xiàng)“標(biāo)志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個(gè)作業(yè)占用

13、分區(qū)的登記項(xiàng)，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表中除了分區(qū)起始地址、長(zhǎng)度外，也要有一項(xiàng)“標(biāo)志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個(gè)空閑區(qū)的登記項(xiàng)，內(nèi)容為“未分配”（。在實(shí)際系統(tǒng)中，這兩表格的內(nèi)容可能還要多，實(shí)驗(yàn)中僅僅使用上述必須的數(shù)據(jù)。為此,“已分配區(qū)表”和“空閑區(qū)表”在實(shí)驗(yàn)中有如下的結(jié)構(gòu)定義。已分配區(qū)表的定義：#define n 10 /假定系統(tǒng)允許的最大作業(yè)數(shù)量為nstructfloat address; /已分分區(qū)起始地址 float length; /已分分區(qū)長(zhǎng)度，單位為字節(jié) int flag; /已分配區(qū)表登記欄標(biāo)志，“0”表示空欄目，實(shí)驗(yàn)中只支持一個(gè)字符的作業(yè)名used_tabl

14、en; /已分配區(qū)表空閑區(qū)表的定義：#define m 10 /假定系統(tǒng)允許的空閑區(qū)表最大為mstructfloat address; /空閑區(qū)起始地址 float length; /空閑區(qū)長(zhǎng)度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標(biāo)志，用“0”表示空欄目，用“1”表示未分配free_tablem; /空閑區(qū)表其中分區(qū)起始地址和長(zhǎng)度數(shù)值太大，超出了整型表達(dá)范圍，所以采用了float類(lèi)型。然后，就要考慮如何在設(shè)計(jì)的數(shù)據(jù)表格上進(jìn)行主存的分配。當(dāng)要裝入一個(gè)作業(yè)時(shí)，從空閑區(qū)表中查找標(biāo)志為“未分配”的空閑區(qū)，從中找出一個(gè)能容納該作業(yè)的空閑區(qū)。如果找到的空閑區(qū)正好等于該作業(yè)的長(zhǎng)度，則把該分區(qū)全

15、部分配給作業(yè)。這時(shí)應(yīng)該把該空閑區(qū)登記欄中的標(biāo)志改為“空”，同時(shí)在已分配區(qū)表中找到一個(gè)標(biāo)志為“空”的欄目登記新裝入作業(yè)所占用分區(qū)的起始地址、長(zhǎng)度和作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長(zhǎng)度，則把空閑區(qū)分成兩部分，一部分用來(lái)裝入作業(yè)，另外一部分仍為空閑區(qū)。這時(shí)只要修改原空閑區(qū)的長(zhǎng)度，且把新裝入的作業(yè)登記到已分配區(qū)表中。實(shí)驗(yàn)中主存分配算法采用“最優(yōu)適應(yīng)”算法。最優(yōu)適應(yīng)算法是按作業(yè)要求挑選一個(gè)能滿(mǎn)足作業(yè)要求的最小空閑區(qū)，這樣保證可以不去分割一個(gè)大的區(qū)域，使裝入大作業(yè)時(shí)比較容易得到滿(mǎn)足。但是最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個(gè)分區(qū)可能只比作業(yè)所要求的長(zhǎng)度略大一點(diǎn)的情況，這時(shí)，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小

16、的空閑區(qū)往往無(wú)法使用，卻影響了主存的使用。為了一定程度上解決這個(gè)問(wèn)題，如果空閑區(qū)的大小比作業(yè)要求的長(zhǎng)度略大一點(diǎn)，不再將空閑區(qū)分成已分分區(qū)和空閑區(qū)兩部分，而是將整個(gè)空閑區(qū)分配給作業(yè)。在實(shí)現(xiàn)最優(yōu)適應(yīng)算法時(shí)，可把空閑區(qū)按長(zhǎng)度以遞增方式登記在空閑區(qū)表中。分配時(shí)順序查找空閑表，查找到的第一個(gè)空閑區(qū)就是滿(mǎn)足作業(yè)要求的最小分區(qū)。這樣查找速度快，但是為使空閑區(qū)按長(zhǎng)度以遞增順序登記在空閑表中，就必須在分配回收時(shí)進(jìn)行空閑區(qū)表的調(diào)整?？臻e區(qū)表調(diào)整時(shí)移動(dòng)表目的代價(jià)要高于查詢(xún)整張表的代價(jià)，所以實(shí)驗(yàn)中不采用空閑區(qū)有序登記在空閑表中的方法。動(dòng)態(tài)分區(qū)方式的主存分配流程圖如圖2.4所示。最后是動(dòng)態(tài)分區(qū)方式下的主存回收問(wèn)題。動(dòng)態(tài)

17、分區(qū)方式下回收主存空間時(shí)，應(yīng)該檢查是否有與歸還區(qū)相鄰的空閑區(qū)。若有，則應(yīng)該合并成一個(gè)空閑區(qū)。一個(gè)歸還區(qū)可能有上鄰空閑區(qū)，也可能有下鄰空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無(wú)上鄰空閑區(qū)也無(wú)下鄰空閑區(qū)。在實(shí)現(xiàn)回收時(shí)，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài)變?yōu)椤翱铡保缓髾z查空閑區(qū)表中標(biāo)志為“未分配”的欄目，查找是否有相鄰空閑區(qū)；最后，合并空閑區(qū)，修改空閑區(qū)表。假定作業(yè)歸還的分區(qū)起始地址為s，長(zhǎng)度為l，則： 歸還區(qū)有下鄰空閑區(qū)如果s+l正好等于空閑區(qū)表中某個(gè)登記欄目（假定為第j欄）的起始地址，則表明歸還區(qū)有一個(gè)下鄰空閑區(qū)。這時(shí)只要修改第j欄登記項(xiàng)的內(nèi)容：起始地址=s；第j欄長(zhǎng)

18、度=第j欄長(zhǎng)度+l；則第j欄指示的空閑區(qū)是歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)； 歸還區(qū)有上鄰空閑區(qū)如果空閑區(qū)表中某個(gè)登記欄目（假定為第k欄）的“起始地址+長(zhǎng)度”正好等于s，則表明歸還區(qū)有一個(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ū)；原來(lái)的下鄰空閑區(qū)登記項(xiàng)（第j欄）被刪除，置為“空”。 2.4 動(dòng)態(tài)分區(qū)最優(yōu)分配算法流程圖6圖2.5 動(dòng)態(tài)分區(qū)回收流程圖 歸還區(qū)既無(wú)上鄰空閑區(qū)又無(wú)下鄰空閑區(qū)如果在檢查空閑區(qū)表時(shí)，無(wú)上述三種情況出現(xiàn)，則表明歸還區(qū)既無(wú)上鄰空閑區(qū)又無(wú)下鄰空閑區(qū)。這