實驗三動態分割槽儲存管理方式的主存分配**
一、實驗目的
深入了解動態分割槽儲存管理方式主存分配**的實現。
二、實驗預備知識
儲存管理中動態分割槽的管理方式。
三、實驗內容
編寫程式完成動態分割槽儲存管理方式的主存分配**的實現。實驗具體包括：首先確定主存空間分配表；然後採用最優適應演算法完成主存空間的分配和**；最後編寫主函式對所做工作進行測試。
四、提示與講解
動態分割槽管理方式預先不將主存劃分成幾個區域，而把主存除作業系統占用區域外的空間看作乙個大的空閒區。當作業要求裝入主存時，根據作業需要主存空間的大小查詢主存內各個空閒區，當從主存空間中找到乙個大於或等於該作業大小的主存空閒區時，選擇其中乙個空閒區，按作業需求量劃出乙個分割槽裝入該作業。作業執行完後，它所佔的主存分割槽被收回，成為乙個空閒區。
如果該空閒區的相鄰分割槽也是空閒區，則需要將相鄰空閒區合併成乙個空閒區。
實現動態分割槽的分配和**，主要考慮的問題有三個：第一，設計記錄主存使用情況的資料**，用來記錄空閒區和作業占用的區域；第二，在設計的資料**基礎上設計主存分配演算法；第三，在設計的資料**基礎上設計主存**演算法。
首先，考慮第乙個問題：設計記錄主存使用情況的資料**，用來記錄空閒區和作業占用的區域。
由於動態分割槽的大小是由作業需求量決定的，故分割槽的長度是預先不固定的，且分割槽的個數也隨主存分配和**變動。總之，所有分割槽情況隨時可能發生變化，資料**的設計必須和這個特點相適應。由於分割槽長度不同，因此設計的**應該包括分割槽在主存中的起始位址和長度。
由於分配時空閒區有時會變成兩個分割槽：空閒區和已分分割槽，**主存分割槽時，可能會合併空閒分割槽，這樣如果整個主存採用一張**記錄已分分割槽和空閒區，就會使**操作繁瑣。主存分配時查詢空閒區進行分配，然後填寫已分配區表，主要操作在空閒區；某個作業執行完後，將該分割槽變成空閒區，並將其與相鄰的空閒區合併，主要操作也在空閒區。
由此可見，主存的分配和**主要是對空閒區的操作。這樣為了便於對主存空間的分配和**，就建立兩張分割槽表記錄主存使用情況，一張**記錄作業占用分割槽的「已分配區表」；一張是記錄空閒區的「空閒區表」。這兩張表的實現方法一般有兩種，一種是鍊錶形式，一種是順序表形式。
在實驗中，採用順序表形式，用陣列模擬。由於順序表的長度必須提前固定，所以無論是「已分配區表」還是「空閒區表」都必須事先確定長度。它們的長度必須是系統可能的最大項數，系統執行過程中才不會出錯，因而在多數情況下，無論是「已分配區表」還是「空閒區表」都有空閒欄目。
已分配區表中除了分割槽起始位址、長度外，也至少還要有一項「標誌」，如果是空閒欄目，內容為「空」，如果為某個作業占用分割槽的登記項，內容為該作業的作業名；空閒區表中除了分割槽起始位址、長度外，也要有一項「標誌」，如果是空閒欄目，內容為「空」，如果為某個空閒區的登記項，內容為「未分配」。在實際系統中，這兩**的內容可能還要多，實驗中僅僅使用上述必須的資料。為此,「已分配區表」和「空閒區表」在實驗中有如下的結構定義。
已分配區表的定義：
#define n 10 //假定系統允許的最大作業數量為n
struct
used_table[n]; //已分配區表
空閒區表的定義：
#define m 10 //假定系統允許的空閒區表最大為m
struct
free_table[m]; //空閒區表
其中分割槽起始位址和長度數值太大，超出了整型表達範圍，所以採用了float型別。
然後，就要考慮如何在設計的資料**上進行主存的分配。
當要裝入乙個作業時，從空閒區表中查詢標誌為「未分配」的空閒區，從中找出乙個能容納該作業的空閒區。如果找到的空閒區正好等於該作業的長度，則把該分割槽全部分配給作業。這時應該把該空閒區登記欄中的標誌改為「空」，同時在已分配區表中找到乙個標誌為「空」的欄目登記新裝入作業所占用分割槽的起始位址、長度和作業名。
如果找到的空閒區大於作業長度，則把空閒區分成兩部分，一部分用來裝入作業，另外一部分仍為空閒區。這時只要修改原空閒區的長度，且把新裝入的作業登記到已分配區表中。
實驗中主存分配演算法採用「最優適應」演算法。最優適應演算法是按作業要求挑選乙個能滿足作業要求的最小空閒區，這樣保證可以不去分割乙個大的區域，使裝入大作業時比較容易得到滿足。但是最優適應演算法容易出現找到的乙個分割槽可能只比作業所要求的長度略大一點的情況，這時，空閒區分割後剩下的空閒區就很小，這種很小的空閒區往往無法使用，影響了主存的使用。
為了一定程度上解決這個問題，如果空閒區的大小比作業要求的長度略大一點，不再將空閒區分成已分分割槽和空閒區兩部分，而是將整個空閒區分配給作業。在實現最優適應演算法時，可把空閒區按長度以遞增方式登記在空閒區表中。分配時順序查詢空閒表，查詢到的第乙個空閒區就是滿足作業要求的最小分割槽。
這樣查詢速度快，但是為使空閒區按長度以遞增順序登記在空閒表中，就必須在分配**時進行空閒區表的調整。空閒區表調整時移動表目的代價要高於查詢整張表的代價，所以實驗中不採用空閒區有序登記在空閒表中的方法。
動態分割槽方式的主存分配流程如圖4所示。
圖4 動態分割槽最優分配演算法流程圖
最後是動態分割槽方式下的主存**問題。
動態分割槽方式下**主存空間時，應該檢查是否有與歸還區相鄰的空閒區。若有，則應該合併成乙個空閒區。乙個歸還區可能有上鄰空閒區，也可能有下鄰空閒區，或者既有上鄰空閒區又有下鄰空閒區，或者既無上鄰空閒區也無下鄰空閒區。
在實現**時，首先將作業歸還的區域在已分配表中找到，將該欄目的狀態變為「空」，然後檢查空閒區表中標誌為「未分配」的欄目，查詢是否有相鄰空閒區；最後，合併空閒區，修改空閒區表。假定作業歸還的分割槽起始位址為s，長度為l，則：
（1）歸還區有下鄰空閒區
如果s+l正好等於空閒區表中某個登記欄目（假定為第j欄）的起始位址，則表明歸還區有乙個下鄰空閒區。這時只要修改第j欄登記項的內容：
起始位址=s；
第j欄長度=第j欄長度+l；
則第j欄指示的空閒區是歸還區和下鄰空閒區合併後的大空閒區。
（2）歸還區有上鄰空閒區
如果空閒區表中某個登記欄目（假定為第k欄）的「起始位址+長度」正好等於s，則表明歸還區有乙個上鄰空閒區。這時要修改第k欄登記項的內容（起始位址不變）：
第k欄長度=第k欄長度+l；
於是第k欄指示的空閒區是歸還區和上鄰空閒區合併後的大空閒區。
（3）歸還區既有上鄰空閒區又有下鄰空閒區
如果s+l正好等於空閒區表中某個登記欄目（假定為第j欄）的起始位址，同時還有某個登記欄目（假定為第k欄）的「起始位址+長度」正好等於s，這表明歸還區既有乙個上鄰空閒區又有乙個下鄰空閒區。此時對空閒區表的修改如下：
第k欄長度=第k欄長度+第j欄長度+l；（第k欄起始位址不變）
第j欄狀態=「空」；（將第j欄登記項刪除）
這樣，第k欄指示的空閒區是歸還區和上、下鄰空閒區合併後的大空閒區；原來的下鄰空閒區登記項（第j欄）被刪除，置為「空」。
（4）歸還區既無上鄰空閒區又無下鄰空閒區
如果在檢查空閒區表時，無上述三種情況出現，則表明歸還區既無上鄰空閒區又無下鄰空閒區。這時，應該在空閒區表中查詢乙個狀態為「空」的欄目（假定查到的是第t欄），則第t欄的內容修改如下：
第t欄起始位址=s；
第t欄長度=l；
第t欄狀態=「未分配」
這樣，第t欄指示的空閒區是歸還區。
按上述方法歸還主存區域的流程如圖5所示。
由於是實驗，沒有真正的主存要分配，所以在實驗中，首先應建立一張空閒區表，初始狀態只有乙個空閒登記項（假定的主存空閒區）和一張所有狀態都為「空」的已分配區表，假定主存空間110kb，作業系統占用10kb，其餘為空閒區；然後，可以選擇進行主存分配或主存**，如果是分配，要求輸入作業名和所需主存空間大小，如果是**，輸入**作業的作業名，迴圈進行主存分配和**後，如果需要，則顯示兩張表的內容，以檢查主存的分配和**是否正確。
圖5 動態分割槽**流程圖
五、課外題
（1）程式設計實現頁式儲存管理的主存分配和**。
（2）用鍊錶方式表示主存空間分配情況，完成動態分割槽管理方式下的主存空間分配和**。
六、參考程式
#define n 10假定系統允許的最大作業數量為n
#define m 10假定系統允許的空閒區表最大為m
#define minisize 100
struct
used_table[n已分配區表
struct
free_table[m空閒區表
allocate(j,xk)
//採用最優分配演算法分配xk大小的空間
char j;
float xk;
//找到可用空閒區，開始分配：若空閒區大小與要求分配的空間差小於minisize大小，則空閒區全部分配；若空閒區大小與要求分配的空間差大於minisize大小，則從空閒區劃出一部分分配
if(free_table[k].length-xk<=minisize)
else
//修改已分配區表
i=0;
while(used_table[i].flag!=0&&i i++;
if(i>=n無表目填寫已分分割槽
{printf("無表目填寫已分分割槽，錯誤\n");
//修正空閒區表
if(free_table[k].flag==0前面找到的是整個空閒區
free_table[k].flag=1;
else前面找到的是某個空閒區的一部分
作業系統實驗可變分割槽儲存管理
學時 4學時 實驗內容 主儲存器空間分配實驗。實驗目的 通過首次適應演算法 最佳適應演算法和最壞適應演算法實現主存空間的分配，可以使讀者可好地理解儲存分配演算法。實驗題目 編寫一段程式來模擬可變分割槽管理方法。要求能通過檔案形式定義空閒區表 能隨意輸入作業及需要分配的空間 能分別使用首次適應演算法 ...
第四章 分頁式儲存管理方式
1.某系統採用頁式儲存管理策略，擁有邏輯空間32頁，每頁2k，擁有物理空間1m。1 寫出邏輯位址的格式。因為擁有邏輯空間32頁，所以頁號需要5位，每頁2k，所以頁內位址需要11位，所以邏輯位址的格式如下 2 若不考慮訪問許可權等，程序的頁表有多少項？每項至少有多少位？每個程序最多32個頁面，因此程序...
全新的成本管理方式
全新的成本管理方式 精益成本管理 乙個企業所具有的優勢或劣勢的顯著性最終取決於企業在多大程度上能夠對相對成本和歧異性有所作為，低成本成為衡量企業是否具有競爭優勢的兩個重要標準之一。加強成本管理更有效地降低成本，在企業經營戰略中已處於極其重要的核心地位，它從根本上決定著企業競爭力的強弱。現代經濟的發展...