內存碎片
在沒有其他方式輔助的情況下，我們分配給一個進程的內存是連續的。在分配時候我們需要有動態分配與碎片處理。如何理解呢？就是每個進程需要一塊內存，我們要選取合適的位置的內存分配給它。當有的進程先結束了內存還給操作系統，此時可能就會產生內存碎片，要對碎片進行處理。首先對一些概念進行解釋。
- 連續內存分配：給進程分配一塊不小于指定大小的連續的物理內存區域。
- 內存碎片：不能被利用的空閑內存，內存碎片又分為外部碎片和內部碎片。
- 外部碎片：分配單元之間的未被利用的內存，比如兩個進程之間的進程結束后的空間，如果后續請求的大小都大于這一部分空間，這部分空間就不能被利用，也就形成了外部碎片。
- 內部碎片：分配單元內部的未被使用的內存，這是由于分配時可能只能分配2的冪次方大小內存比如512字節，而實際使用了510字節，那么就有2字節的內部碎片。
動態分配：
當程序加載執行時，需要分配給進程一個指定大小可變的分區，分區的地址是連續的。如圖中右側分給進程1到6內存空間。當進程3和進程5結束后它們所占有的位置重新變為空閑。操作系統要維護的數據結構就包含了內存中已分配區域與未分配區域。當有新的進程請求一定的內存空間時，則根據未分配空間進行一個動態分區分配。分配的策略是多種多樣的。比如：
- 最先分配，空閑分區列表按照地址順序排序，遍歷空閑分區，遇到的第一個大小滿足需求的區域分配給進程。釋放內存使，查看附近是否有臨近的空閑區，有的話進行合并。優點是找和合并開銷較小，算法簡單，并且由于每次從小地址開始查找，可以在大地址處留有大塊的空閑分區，可以分配給需要大內存的進程。缺點是會有外部碎片，因為切完剩下的可能有很多小塊內存，也因此分配大內存時需要遍歷到最后時間較長。
- 最佳匹配，空閑分區列表按照大小排序，尋找空閑區域中大小大于需求大小中最小的分配給進程，具體實現時可以對空閑分區按大小排序從最小開始尋找第一個大于需求的內存區即可，如果不排序則需要整個遍歷一遍。釋放時，也是與鄰近空閑區域合并。而合并時我們要找的是地址鄰近的而不是大小鄰近的，所以合并的開銷會大一些。優點大部分分配的內存尺寸較小時效果很好，因為可以避免較大的內存被拆分，同時減小外部碎片的大小，同時相對來說比較簡單。缺點是外部碎片還是較多，并且越小越無法被利用，容易產生很多無用的小碎片，此外如前所述釋放分區較慢，合并時算法復雜。
- 最差匹配，空閑分區列表按照大小排序，尋找空閑去榆中大小最大的區域從中劃分出需要大小的內存分配給進程。釋放時尋找鄰近空閑分區合并。因此也存在最佳匹配的問題，釋放內存時合并算法開銷較大。優點是中等尺度內存分配較多時效果最好，可以避免產生太多小碎片。缺點是釋放較慢，也會有外部碎片，容易破壞大的內存區域，因此后續無法分配大內存。
碎片整理
系統運行過程中，碎片越來越多，很可能無法獲取需要的較大的內存空間。我們需要解決這個問題，這就是碎片整理的意義，可以通過碎片整理獲得更大的連續內存空間，以便于滿足進程的應用空間需求。碎片整理是通過調整進程占用的分區位置來減少或避免分區碎片的。碎片整理有很多種方式，比如碎片緊湊、分區對換。
碎片緊湊
- 實現方式：通過移動分配給進程的內存分區，以合并外部碎片。
- 條件：所有的應用程序可以動態重定位。這是因為程序中可能有很多地址引用，如果引用了絕對地址，移動分配的內存位置可能就會出錯。因此需要動態重定位，執行到命令的時候才生成內存地址。
- 時機：進程處于等待狀態時搬動。
- 開銷：移動已分配的內存分區是有開銷的，因此不會為了一小塊碎片就進行緊湊。具體開銷暫且按下不講。
分區對換
分區對換是通過搶占并回收處于等待狀態進程的分區，以增大可用內存空間。即將等待狀態進程的數據存儲到外存中，也就是對換到對換區。可以結合下面的圖示理解：假設系統運行到某個時刻處于如下第一張圖片的狀態，圖中下側為內存與外存狀態，上側為操作系統維護的進程狀態數據結構示意圖，即有三個進程P1、P2、P3占滿了內存區，而P1處于等待狀態，P2處于運行狀態，P3處于就緒狀態。此時又有第四個進程要運行，而內存是不夠的。則進行分區對換，對換后如第二張圖所示，將處于等待狀態的進程P1移動到外存，此時就有足夠的內存空間。通過這種方式，我們可以讓更多的進程在系統中交替進行。
由于對換是在內存與外存之間，對換速度是非常慢的，開銷很大，因此需要解決一個問題，就是到底要交換哪些進程。
伙伴系統
伙伴系統是連續存儲分配的一種辦法。它比較好地折中了分配和回收過程中分配塊的位置碎片和合并的問題。伙伴系統地概念如下圖：整個可分配分區大小為2的冪次方，當需要的內存空間大于當前塊的一半的時候就將整個分區分配給進程，如果小于當前分區的一半，就將當前分區對半分開，將其中一半繼續與需要的內存大小進行比較，遞歸進行下去，直到滿足所需內存大小大于分區一半。可以看到這種分配方式內部碎片最大為分區大小的一半減一。知道了伙伴系統的思想，下面我們看下具體實現。
伙伴系統的實現
數據結構：
- 空閑塊按大小和起始位置組織稱二維數組；
- 初始狀態時，只有一個大小為
的空閑塊；
分配過程：
- 由小到大在空閑塊數組中找最小的可用空閑塊；
- 如果空閑塊過大，對可用空閑塊進行二等分，一個放入空閑塊列表，另一塊繼續比較，直到得到合適的可用空閑塊
分配示例：
釋放過程：
- 把釋放的塊放入空閑塊數組
- 合并滿足合并條件的空閑塊
合并條件：
- 大小相同
- 地址相鄰
- 起始地址小的塊的地址必須是
的倍數。看起來有點抽象，其實就是地址較小的塊的起始地址必須是要合并的塊的大小的兩倍的倍數。因此上圖中三個256只有后面兩個可以合并。
)
