作業系統課程設計報告

模擬單使用者作業系統

課程設計

班級組員

指導教師

2023年12月22日星期四

儲存管理

---動態分割槽分配演算法的模擬

摘要:分割槽分配演算法就是系統在尋找空閒的分割槽分配給某一使用者作業,具體可採用首次適應演算法,迴圈首次適應演算法和最佳適應演算法。下面將針對每個演算法的資料結構及演算法實現進行分析，在分析演算法前，先對此次課題進行了分析，再對一些基礎相關知識進行了整理。

關鍵字:分割槽分配演算法；首次適應；迴圈首次適應；最佳適應

概述動態分割槽分配是根據程序的實際需要，動態地為之分配記憶體空間。在實現可變分割槽分配時，將涉及到分割槽分配中所用的資料結構、分割槽分配演算法和分割槽的分配和**操作這樣三個問題。

1、設計目的及開發環境

(1)設計目的

分割槽管理是滿足多道程式執行的最簡單的儲存管理方式，為了實現對記憶體空間的有效管理，需要採取一些方法和策略，用以實現對記憶體空間的分配或**。

(2)開發環境

作業系統：windows xp

開發環境：dev-c++ 5

2資料結構設計

(1) 空閒區說明表結構：把空閒區定義為結構體變數，包括空閒區始址，空閒區大小和空閒區狀態，用0表示空表目，1為可用空閒塊。

struct freearea

freeblock[n]=,,,,};

(2) 為作業分配主存空間的函式alloc()，三個演算法分別對應三個分配主存空間的演算法。applyarea為作業申請量，tag為檢查是否有滿足作業需要的空閒區的標誌。

首次適應演算法:

檢查空閒區說明表是否有滿足作業要求的空閒區時,如果大於作業要求,則分配給作業,修改位址和空閒區大小,並將tag置「1」,表示有滿足作業要求的空閒區,返回為作業分配主存的位址.程式如下所示：

if(freeblock[i].state==1&&freeblock[i].size>applyarea)

如果空閒區等於作業要求，則分配給作業,修改位址和空閒區大小,並將tag置「1」,表示有滿足作業要求的空閒區,返回為作業分配主存的位址.

if(freeblock[i].state==1&&freeblock[i].size==applyarea)

freeblock[i].state=0;

tag=1

return freeblock[i].startaddress;

如果沒有滿足條件的空閒區，分配不成功，返回-1

if(tag==0)return -1;

迴圈首次適應演算法的alloc()函式與首次適應演算法的alloc()函式區別在於從**開始找是否有滿足作業要求的空閒區，它是從上次找到的空閒區的下乙個空閒分割槽開始找，只需要改變for迴圈的條件即可。

for(i=s;i最佳適應演算法：該演算法總是把滿足要求、又是最小的空閒區分配給作業。檢查空閒區說明表是否有滿足作業要求的空閒區，也分為三種情況：

大於，等於，小於。若檢查到有「等於」的情況，就可以直接分配，若沒有，則繼續檢查是否有「大於」的情況：

if(freeblock[i].state==1&&freeblock[i].size==applyarea)

freeblock[i].state=0;

tag=1;

return freeblock[i].startaddress;

檢查「大於」的情況：先把所有大於所要求的空閒區放入陣列,

for(i=0;i

再從陣列中挑出最小的那個：

如果陣列中的元素大於乙個，則需要乙個個比較過去，然後取出最小的那個分配給作業：

if(j>1)

如果陣列中只有乙個元素，則直接分配給作業：

if(j==1)

如果沒有滿足條件的空閒區，分配不成功，返回-1

if(tag==0)return -1;

(3) 主存**函式setfree()：tag1代表釋放區的高位址是否鄰接乙個空閒區，tag2代表釋放區的高低位址是否都鄰接乙個空閒區，tag3代表釋放區的低位址是否鄰接乙個空閒區。分為四種情況：

**分割槽的上鄰和下鄰分割槽都不是空閒的，則直接將**區的相關資訊記錄在空閒區表中。

if(tag3==0)

}**分割槽的上鄰分割槽是空閒的，需要將這兩個相鄰的空閒區合併成乙個較大的空閒區，然後修改空閒區表。

if(freeblock[i].startaddress==s+l&&freeblock[i].state==1)

**分割槽的下鄰分割槽是空閒區，需要將這兩個相鄰的空閒區合併成乙個空閒區，並修改空閒區表。

if(freeblock[i].startaddress+freeblock[i].size==s&&freeblock[i].state==1)

**分割槽的上鄰和下鄰都是空閒區，則需要將這三個空閒區合併成乙個更大的空閒區，然後修改空閒區表。先判斷有上鄰空閒區（如所示），再判斷有下鄰空閒區（如所示），若都有，則將tag2置1。

(4) 對空閒區表中的空閒區調整的函式adjust()：使空閒區按始位址從小到大排列，空表目放在最後面。

(5) 列印空閒區說明表函式：print()

(6) 首次適應演算法函式shouci():若有作業需要分配記憶體，則對空閒區表中的空閒區進行調整，呼叫調整函式adjust()，再將其列印出來；輸入作業申請量，呼叫alloc()函式為作業分配空間，分配結束後，要進行主存**，再次調整空閒區表後，列印出來。迴圈執行直到沒有作業為止。

(7) 迴圈首次適應演算法xunhuan():與首次適應演算法不同的是，迴圈首次適應演算法要記錄上次找到的空閒區位址，並在下次分配時從這個位址開始。

(8) 最佳時應演算法best():該演算法在分配記憶體時，把所有滿足要求的空閒區中最小的那個空閒區分配給請求程序。

3演算法的實現

（1）首次適應演算法首次適應演算法要求空閒區按其起始位址由小到大排列，當某一使用者作業要求裝入記憶體時，儲存分配程式從起始位址最小的空間區開始掃瞄，直到找到滿足該作業要求的空閒區為止。（2）迴圈首次適應演算法在查詢空閒區時，不再每次從鏈首開始查詢，而是從上一次找到的空閒區的下乙個空閒分割槽開始查詢，直到找到乙個能滿足要求的空閒區為止，並從中劃出一塊與請求大小相等的記憶體空間分給該作業。

（3）最佳適應演算法該演算法總是把滿足要求，又是最小的空閒區分配給請求程序，即在空閒區表中，按空閒區的大小由小到大排序，建立索引，當使用者程序請求分配記憶體時，從索引表中找到第乙個滿足該程序大小要求的空閒區分配給它。

（4）整體實現過程：系統利用某種分配演算法，從空閒分割槽鏈（表）中找到所需大小的分割槽，設請求分割槽的大小為r.size，其中空閒分割槽的大小可表示為f.

size，若 f.size-r.size≤size（size為事先規定的不再切割的剩餘分割槽的大小）成立，則說明多餘部分太小，不能滿足其它請求程序，故將整個分割槽分配給該請求者；否則，從該分割槽中按請求的大小劃分出一塊記憶體空間分配出去，餘下的部分留在空閒區表中，然後將分割槽首部返回給呼叫者。

作業系統課程設計報告

作業系統課程設計報告

作業系統課程設計報告

作業系統課程設計報告

相關推薦