1、精選優質文檔-傾情為你奉上實驗二 動態分區存儲管理方式的內存分配回收一、實驗目的深入了解動態分區存儲管理方式內存分配回收的實現。二、實驗主要內容 編寫程序完成動態分區存儲管理方式的內存分配回收的實現。實現具體內容包括：首先確定內存空間分配表；然后采用最優適應算法完成內存空間的分配與回收；最后編寫主函數對所做工作進行測試。三、實驗原理 動態分區管理方式預先不將內存劃分成幾個區域，而把內存除操作系統占用區域外的空間看作一個大的空閑區。當作業要求裝入內存時，根據作業需要內存空間的大小查詢內存內各個空閑區，當從內存空間中找到一個大于或等于該作業大小的內存空間區時，選擇其中一個空閑區，按作業要求劃出一個

2、分區裝入該作業。作業執行完后，它所占用的內存空間被收回，成為一個空閑區。如果該空閑區的相鄰分區也是空閑區，則需要將相鄰空閑區合并成一個空閑區。四、實驗方法與步驟 實現動態分區的分配與回收，主要考慮三個問題：第一，設計記錄內存使用情況的數據表格，用來記錄空閑區和作業占用的區域；第二，在設計的數據表格基礎上設計內存分配算法；第三，在設計的數據表格基礎上設計內存回收算法。1  設計記錄內存使用情況的數據表格由于動態分區的大小是由作業需求量決定的，故分區的長度是預先不固定的，且分區的個數也隨內存分配和回收變動。總之，所有分區情況隨時可能發生變化，數據表格的設計必須和這個特點相適應。由于分區長

3、度不同，因此設計的表格應該包括分區在內存中的起始地址和長度。由于分配時，空閑區有時會變成兩個分區：空閑區和已分分區，回收內存分區時，可能會合并空閑區，這樣如果整個內存采用一張表格記錄已分分區和空閑區，就會使表格操作繁瑣。內存分配時查找空閑區進行分配，然后填寫已分配分區表，主要操作在空閑區；某個作業執行完后，將該分區貶詞空閑區，并將其與相鄰的空閑區合并，主要操作也在空閑區。由此可見，內存的分配與回收主要是對空閑區的操作。這樣為了便于對內存空間的分配與回收，就建立兩張分區表記錄內存的使用情況：“已分配分區表”記錄作業占用分區，“空閑區表”記錄空閑區。這兩張表的實現方法一般有兩種：鏈表形式、順序表形

4、式。在本實驗中，采用順序表形式，用數組模擬。由于順序表的長度必須提前固定，所以無論是“已分配區表”還是“空閑區表”都必須事先確定長度。它們的長度必須是系統可能的最大項數，系統運行過程中才不會出錯，因此在多數情況下，無論是“已分配表區”還是“空閑區表”都是空閑欄目。已分配區表中除了分區起始地址、長度外，也至少還有一項“標志”，如果是空閑欄目，內容為“空”，如果為某個作業占用分區的登記項，內容為該作業的作業名；空閑區表除了分區起始地址、長度外，也要有一項“標志”，如果是空閑欄目，內容為“空”，如果為某個空閑區的登記項，內容為“未分配”。在實際系統中，這兩個表格的內容可能還要多，實驗中僅僅使用上述必

5、須的數據。為此，“已分配區表”和“空閑區表”在實驗中有如下的結構定義。已分配區表的定義：#define n 10 /假定系統允許的最大作業數量為nstructfloat address; /已分分區起始地址float length; /已分分區長度，單位為字節int flag; /已分配表區登記欄標志，用0表示空欄目，used_tablen; /已分配區表空閑區表的定義：#define m 10 /假定系統允許的空閑區表最大為mstructfloat address; /空閑區起始地址float length; /空閑區長度，單位為字節int flag; /空閑區表登記欄目用0表示空欄目，1表

6、示未分配?free_tablem; /空閑區表其中分區起始地址和長度數值太大，超出了整形表達范圍，所以采用float類型。2  在設計的表格上進行內存分配當要裝入一個作業時，從空閑區表中查找標志為“未分配”的空閑區，從中找一個能容納該作業的空閑區。如果找到的空閑區正好等于該作業的長度，則把該分區全部分配給該作業。這時應該把該空閑區登記欄中的標志改為“空”，同時在已分配區表中找到一個標志為“空”的欄目登記新裝入作業所占用分區的起始地址、長度和作業名。如果找到的空閑區大于作業長度，則把空閑區分成兩部分，一部分用來裝入作業，另一部分則仍然為空閑區，這時只要修改空閑區的長度，且把新裝入的作業

7、登記到已分配區表中。內存分配算法目前一般采用三種算法：首次適應算法、循環首次適應算法、最佳適應算法。本實驗中采用最佳適應算法為作業分配內存。最佳適應算法會出現空閑分區分割后剩下的空閑分區很小以至于無法使用的情況，為了在一定程度上解決這個問題，如果空閑分區的大小比作業要求的長度略大一點，不再將空閑區分區分割成已分分區和空閑分區兩部分，而是將整個空閑區分配給作業。 在實現最佳適應算法時，可把空閑分區按長度遞增方式登記在空閑區表中。分配時順序查找空閑表，查找到的第一個空閑區就是滿足作業要求的最小分區。這樣查找速度快，但是為使空閑區按照長度遞增登記在空閑表中，就必須在分配回收時進行空閑區的調整。空閑區

8、表調整時移動表項的代價要高于查詢整張表的代價，所以實驗中不采用空閑區有序登記在空閑表中的方法。3  動態分區方式下的內存回收 動態分區方式下回收內存空間時應該檢查是否有與回收區相鄰的空閑區域。若有，則應該合并成一個空閑區。一個回收區可能有上鄰空閑區，也可能有下鄰空閑區，或者既有上鄰空閑區又有下鄰空閑區，或者既無上鄰空閑區也無下鄰空閑區。 在實現回收時，首先將作業歸還的區域在已分配表中找到，將該欄目的狀態變為“空”，然后檢查空閑區表中標志為“未分配”欄目，查找是否又相鄰空閑區；最后合并空閑區，修改空閑區表。假定歸還作業的分區起始地址為S，長度為L，則：1）  回收區又下鄰空閑

9、區如果SL正好等于空閑區表中某個登記欄目（假定為第j欄）的起始地址則表明歸還區有一個下鄰空閑區。這時候只需要修改第j欄登記項的內容： 起始地址S；第j欄長度第j欄長度L則第j欄指示的空閑區時歸還區和下鄰空閑區合并后的大空閑區。2）  回收區又上鄰空閑區如果空閑區表中某個登記欄目（假定為第k欄）的“起始地址長度”正好等于S，則表明歸還區有一個上鄰空閑區。這時要修改第k欄登記項的內容（起始地址不變）： 第k欄長度第k欄長度L；于是第k欄指示的空閑區是歸還區和上鄰空閑區合并后的大空閑區。3）  回收區既有上鄰空閑區又有下鄰空閑區如果SL正好等于空閑區表中某個登記欄目（假定為第j欄

10、）的起始地址，同時還有某個登記欄目（假定為第k欄）的“起始地址長度”正好等于S，這表明歸還區既有一個上鄰空閑區又又一個下鄰空閑區。此時對空閑區的修改如下： 第k欄的長度第k欄的長度第j欄的長度L；（第k 欄的起始地址不變） 第j欄的狀態“空”（將第j欄的登記項刪除） 這樣，第k欄指示的空閑區是歸還區和上、下鄰空閑區合并后的大空閑區；原來的下鄰空閑區登記項（第j欄）被刪除，置為“空”。4）  回收區既無上鄰空閑區又無下鄰空閑區如果在檢查空閑區表時，無上述三種情況出現，則表明歸還區既無上鄰空閑區又無下鄰空閑區。這時，應該在空閑區表中查找一個狀態為“空”的欄目（假定查到的是第t欄），則第t欄的內容修改如下： 第t欄起始地址S； 第t欄的長度L； 第t欄的狀態“未分配”；這樣，第t欄指示的空閑區是歸還區。 由于是實驗，沒有真正的內存要分配，所以在實驗中，首先應建立一張空閑區表，初始狀態只有一個空閑登記項（假定的內存空閑區）和一張所有狀態都為“空”的已分配區表，假定內存空間100KB，全部為空閑區（實際上操作系統需要占用一部分）；然后，可以選擇進行內存分配或回收，如果是分配，要求輸入作業名和所需內存空間大小；