[科普中國]-外部碎片

碎片

在數(shù)據(jù)存儲領(lǐng)域中，碎片(fragmentation）是指存儲空間使用效率低下，結(jié)果導致功能、運行效率變低或二者兼而有之的現(xiàn)象。碎片化所造成的影響取決于具體的存儲系統(tǒng)以及碎片化的種類。大部分情況下，碎片化都會導致都會導致存儲空間的浪費，此時“碎片”一詞亦可指代閑置的空間本身。對于其他的一些系統(tǒng)來說（比如FAT文件系統(tǒng)），數(shù)據(jù)量一定的前提下，用于存儲數(shù)據(jù)所占的存儲空間是一定的，和碎片化的程度無關(guān)。

內(nèi)存碎片是指采用分區(qū)式存儲管理的系統(tǒng)，在儲存分配過程中產(chǎn)生的、不能供用戶作業(yè)使用的主存里的小分區(qū)稱成“內(nèi)存碎片”。內(nèi)存碎片分為內(nèi)部碎片和外部碎片。

內(nèi)部碎片當一個進程裝入到固定大小的分區(qū)塊（比如頁）時，假如進程所需空間小于分區(qū)塊，則分區(qū)塊的剩余的空間將無法被系統(tǒng)使用，稱為內(nèi)部碎片（internal fragmentation）。

外部碎片當空閑內(nèi)存被分成小區(qū)塊，分別為不同的進程所使用時，便會出現(xiàn)外部碎片（external fragmentation）。這種情況下，雖然空閑空間足夠大，但是程序沒法使用，因為剩余空間被分成了大大小小的區(qū)塊，沒有一塊能夠大到程序可以使用。

內(nèi)存分配內(nèi)存分配是指在程序執(zhí)行的過程中分配或者回收存儲空間的分配內(nèi)存的方法。內(nèi)存分配方法有靜態(tài)內(nèi)存分配和動態(tài)內(nèi)存分配兩種。

靜態(tài)內(nèi)存分配靜態(tài)內(nèi)存分配，也可以稱之為固定分區(qū)式分配是最簡單的一種可運行多道程序的存儲管理方式。這是將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)，這樣，把用戶空間劃分為幾個分區(qū)，便允許有幾道作業(yè)并發(fā)運行。當有一空閑分區(qū)時，便可以再從外存的后備作業(yè)隊列中選擇一個適當大小的作業(yè)裝入該分區(qū)，當該作業(yè)結(jié)束時，又可再從后備作業(yè)隊列中找出另一作業(yè)調(diào)入該分區(qū)。

可用下述兩種方法將內(nèi)存的用戶空間劃分為若干個固定大小的分區(qū)：

(1) 分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。其缺點是缺乏靈活性，即當程序太小時，會造成內(nèi)存空間的浪費；當程序太大時，一個分區(qū)又不足以裝入該程序，致使該程序無法運行。盡管如此，這種劃分方式仍被用于利用一臺計算機去控制多個相同對象的場合，因為這些對象所需的內(nèi)存空間是大小相等的。例如，爐溫群控系統(tǒng)，就是利用一臺計算機去控制多臺相同的冶煉爐。

(2) 分區(qū)大小不等。為了克服分區(qū)大小相等而缺乏靈活性的這個缺點，可把內(nèi)存區(qū)劃分成含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，便可根據(jù)程序的大小為之分配適當?shù)姆謪^(qū)。1

動態(tài)內(nèi)存分配動態(tài)內(nèi)存分配（Dynamic memory allocation）又稱為堆內(nèi)存分配，是指計算機程序在運行期中分配使用內(nèi)存。它可以當成是一種分配有限內(nèi)存資源所有權(quán)的方法。

動態(tài)分配的內(nèi)存在被程序員明確釋放或被垃圾回收之前一直有效。與靜態(tài)內(nèi)存分配的區(qū)別在于沒有一個固定的生存期。這樣被分配的對象稱之為有一個“動態(tài)生存期”。

分配過程包括尋找一塊足夠大未被使用的內(nèi)存。分配過程當中的問題：內(nèi)部和外部碎片。減少碎片需要特別處理，從而導致更復雜的實現(xiàn)。分配器的元數(shù)據(jù)需要占用額外的空間。嘗試組塊來減輕這個效應(yīng)。

通常，內(nèi)存是從一個被稱為堆的內(nèi)存池中分配出來的。高級語言封裝了內(nèi)存地址的概念，內(nèi)存通常是通過指針來間接訪問的。分配算法經(jīng)常將組織分配釋放組塊等操作封裝成抽象的接口供上層函數(shù)調(diào)用。

可重定位分區(qū)分配動態(tài)重定位的引入在連續(xù)分配方式中，必須把一個系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。如果在系統(tǒng)中只有若干個小的分區(qū)，即使它們?nèi)萘康目偤痛笥谝b入的程序，但由于這些分區(qū)不相鄰接，也無法把該程序裝入內(nèi)存。例如，圖中示出了在內(nèi)存中現(xiàn)有四個互不鄰接的小分區(qū)，它們的容量分別為 10 KB、30 KB、14 KB 和 26 KB，其總?cè)萘渴?80 KB。但如果現(xiàn)在有一作業(yè)到達，要求獲得 40 KB 的內(nèi)存空間，由于必須為它分配一連續(xù)空間，故此作業(yè)無法裝入。這種不能被利用的小分區(qū)稱為“零頭”或“碎片” 。

若想把作業(yè)裝入，可采用的一種方法是：將內(nèi)存中的所有作業(yè)進行移動，使它們?nèi)枷噜徑?，這樣，即可把原來分散的多個小分區(qū)拼接成一個大分區(qū)，這時就可把作業(yè)裝入該區(qū)。這種通過移動內(nèi)存中作業(yè)的位置，以把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法，稱為“拼接”或“緊湊” ，見圖 。由于經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)生了變化， 此時若不對程序和數(shù)據(jù)的地址加以修改(變換)， 則程序必將無法執(zhí)行。 為此，在每次“緊湊”后，都必須對移動了的程序或數(shù)據(jù)進行重定位。

動態(tài)重定位的實現(xiàn)在動態(tài)運行時裝入的方式中，作業(yè)裝入內(nèi)存后的所有地址都仍然是相對地址，將相對地址轉(zhuǎn)換為物理地址的工作，被推遲到程序指令要真正執(zhí)行時進行。為使地址的轉(zhuǎn)換不會影響到指令的執(zhí)行速度，必須有硬件地址變換機構(gòu)的支持，即須在系統(tǒng)中增設(shè)一個重定位寄存器，用它來存放程序(數(shù)據(jù))在內(nèi)存中的起始地址。程序在執(zhí)行時，真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的。 圖示出了動態(tài)重定位的實現(xiàn)原理。地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進行的，故稱為動態(tài)重定位。當系統(tǒng)對內(nèi)存進行了“緊湊”而使若干程序從內(nèi)存的某處移至另一處時，不需對程序做任何修改，只要用該程序在內(nèi)存的新起始地址，去置換原來的起始地址即可。

動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上相同，差別僅在于：在這種分配算法中，增加了緊湊的功能，通常，在找不到足夠大的空閑分區(qū)來滿足用戶需求時進行緊湊。