基本介紹
- 中文名：動態存儲分配
- 外文名：dynamic memory allocation
- 學科：計算機
- 定義：為源程式分配存儲空間
- 有關術語：分配方式、重定位
- 領域：作業系統
存儲分配方式,重定位,方法,
存儲分配方式
存儲分配所要解決的問題是多道程式之間如何共享主存的存儲空間。解決存儲分配問題有三種方式：直接存儲分配方式、靜態存儲分配方式、動態存儲分配方式。
直接存儲分配方式
直接存儲分配方式要求存儲器的可用空間已經確定，且確保各程式所用的地址之間互不重疊。缺點是用戶感到不方便，存儲器的利用率也不高。
靜態存儲分配方式
靜態存儲分配方式中。在程式被裝入、連線時，才確定它們在主存中的相應位置(物理地址)。系統必須分配其要求的全部存儲空間．否則不能裝入該用戶程式。程式將占據著分配給它的存儲空間直到程式結束。該存儲空間的位置固定不變，也不能動態地申請存儲空間。這種方式無法實現用戶對存儲空間的動態擴展，而且也不能有效地實現存儲器資源的共享。
動態存儲分配方式
動態存儲分配方式是不一次性將整個程式裝入到主存中。可根據執行的需要，部分地動態裝入。同時，在裝入主存的程式不執行時，系統可以收回該程式所占據的主存空間。再者，用戶程式裝入主存後的位置，在運行期間可根據系統需要而發生改變。此外，用戶程式在運行期間也可動態地申請存儲空間以滿足程式需求。由此可見，動態存儲分配方式在存儲空間的分配和釋放上，表現得十分靈活，現代的作業系統常採用這種存儲方式。
重定位
為了實現靜態、動態存儲分配方式．必須把邏輯地址和物理地址分開井將邏輯地址定位為物理地址。為此，首先耍弄清地址空間和存儲空間這兩個概念。編譯系統總是從零號地址單元開始，為目標程式指令順序分配地址。這些地址故稱為相對地址，相對地址的集合稱為邏輯地址空間，簡稱地址空間。存儲空間是指主存中一系列存儲信息的物理單元的集合，這些物理單元的編號稱為物理地址或絕對地址。由於用戶程式的裝入而引起地址空間中的相對地址轉化為存儲空間中的絕對地址的地址變換過程，稱為地址重定位。實現地址重定位的方法有兩種：靜態地址重定位和動態地址重定位。
靜態地址重定位
靜態地址重定位是指用戶程式在裝入時由裝配程式一次完成。即地址變換隻是在裝入時一次完成，以後不再改變。這種重定位方式實現起來比較簡單，在早期多道程式設計中大多採用這種方案：它的缺點是用戶程式必須分配一個連續的存儲空間，難以實現程式和數據的共享。
動態地址重定位
動態地址重定位是在程式執行的過程中，當CPU要對存儲器進行訪問時，通過硬體地址變換機構，將要訪問的程式和數據地址轉換成主存地址。
動態地址重定位的優點是：
(1)程式執行時可以在主存中浮動．有利於提高主存的利用率和存儲空間使用的靈活性。
(2)有利於程式段的共享實現。當系統提供多個重定位暫存器時，規定某些或某個重定位暫存器作為共享程式段使用，就可實現主存中的相應程式段為多個程式所共享。
(3)為實現虛擬存儲管理提供了基礎。有了動態地址重定位的概念和技術，程式中的信息塊可根據執行時的需要分配在主存中的任何區域，還可以覆蓋或交換不再使用的區域，使得程式的邏輯地址空間可比實際的物理存儲空間大．從而實現了虛擬存儲管理功能。
動態地址重定位的缺點是實現存儲器管理的軟體比較複雜以及需要附加更多的硬體支持。
方法
首次適應算法(first fit)
我們以空閒分區鏈為例來說明採用 首次適應算法(first fit)時的分配情況。FF 算法要求空閒分區鏈以地址遞增的次序連結。在分配記憶體時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閒分區為止；然後再按照作業的大小，從該分區中劃出一塊記憶體空間分配給請求者，餘下的空閒分區仍留在空閒鏈中。若從鏈首直至鏈尾都不能找到一個能滿足要求的分區，則此次記憶體分配失敗，返回。該算法傾向於優先利用記憶體中低址部分的空閒分區，從而保留了高址部分的大空閒區。這給為以後到達的大作業分配大的記憶體空間創造了條件。其缺點是低址部分不斷被劃分，會留下許多難以利用的、很小的空閒分區，而每次查找又都是從低址部分開始，這無疑會增加查找可用空閒分區時的開銷。
循環首次適應算法(next fit)
該算法是由首次適應算法演變而成的。在為進程分配記憶體空間時，不再是每次都從鏈首開始查找，而是從上次找到的空閒分區的下一個空閒分區開始查找，直至找到一個能滿足要求的空閒分區，從中劃出一塊與請求大小相等的記憶體空間分配給作業。為實現該算法，應設定一起始查尋指針，用於指示下一次起始查尋的空閒分區，並採用循環查找方式，即如果最後一個(鏈尾)空閒分區的大小仍不能滿足要求，則應返回到第一個空閒分區，比較其大小是否滿足要求。找到後，應調整起始查尋指針。該算法能使記憶體中的空閒分區分布得更均勻，從而減少了查找空閒分區時的開銷，但這樣會缺乏大的空閒分區。
最佳適應算法（Best Fit）
算法：將空閒分區鏈中的空閒分區按照空閒分區由小到大的順序排序，從而形成空閒分區鏈。每次從鏈首進行查找合適的空閒分區為作業分配記憶體，這樣每次找到的空閒分區是和作業大小最接近的，所謂“最佳”。
優點：第一次找到的空閒分區是大小最接近待分配記憶體作業大小的；
缺點:產生大量難以利用的外部碎片。
最壞適應算法（Worst Fit）
算法：與最佳適應算法剛好相反，將空閒分區鏈的分區按照從大到小的順序排序形成空閒分區鏈，每次查找時只要看第一個空閒分區是否滿足即可。
優點：效率高，分區查找方便；
缺點：當小作業把大空閒分區分小了，那么，大作業就找不到合適的空閒分區。
快速適應算法(quick fit)
該算法又稱為分類搜尋法，是將空閒分區根據其容量大小進行分類，對於每一類具有相同容量的所有空閒分區，單獨設立一個空閒分區鍊表，這樣，系統中存在多個空閒分區鍊表，同時在記憶體中設立一張管理索引表，該表的每一個表項對應了一種空閒分區類型，並記錄了該類型空閒分區鍊表表頭的指針。空閒分區的分類是根據進程常用的空間大小進行劃分，如 2 KB、4 KB、8 KB 等，對於其它大小的分區，如 7 KB 這樣的空閒區，既可以放在 8 KB 的鍊表中，也可以放在一個特殊的空閒區鍊表中。該算法的優點是查找效率高，僅需要根據進程的長度，尋找到能容納它的最小空閒區鍊表，並取下第一塊進行分配即可。另外該算法在進行空閒分區分配時，不會對任何分區產生分割，所以能保留大的分區，滿足對大空間的需求，也不會產生記憶體碎片。該算法的缺點是在分區歸還主存時算法複雜，系統開銷較大。此外，該算法在分配空閒分區時是以進程為單位，一個分區只屬於一個進程，因此在為進程所分配的一個分區中，或多或少地存在一定的浪費。空閒分區劃分越細，浪費則越嚴重，整體上會造成可觀的存儲空間浪費，這是典型的以空間換時間的作法。
