主記憶體:配置、連結與分段

外部碎裂(external fragmentation)

想像一個停了一半的停車場,但空位是散落在停著的車子之間的單格縫隙——這裡一格、那裡兩格。一輛巴士到來,需要連續三格,卻無處可停,即使總空位充足。外部碎裂正是如此:總共有足夠的空閒記憶體,但它被打碎成小片,沒有一片大到足以容納請求。

具體來說,外部碎裂發生在連續配置中,因為行程在不同時間開始與結束。每當一個行程離開,它把它的區塊還回成一個空洞;每當一個行程被放置,它切出一個空洞並留下較小的餘額。久而久之,空閒記憶體變成一塊塊空洞構成的棋盤。一個新行程需要一整段連續空間,所以即使所有空洞的總和遠大於那個行程,它也可能塞不下,因為沒有單一空洞夠大。被浪費的空間位於已配置區塊的外面(之間)——故稱為外部。

為什麼重要:外部碎裂是連續配置的核心缺陷,而選用最先適配、最佳適配或最差適配都無法治癒它——它們只重塑剩餘。兩個真正的解藥是緊縮(把使用中的區塊挪在一起以合併空洞,代價高昂),以及更具決定性的分頁,它讓一個行程佔據許多不連續的頁框,所以它根本不需要一整段大的連續空間。請把這與內部碎裂對照,後者的浪費發生在已配置區塊的裡面。

空閒空洞總計 90 KB,但被切成 30 KB + 60 KB,中間夾著一個行程。一個 80 KB 的行程無法執行:總空閒(90 KB)超過它的需求,但沒有單一空洞夠大。這就是一張圖說明的外部碎裂。

總量充足卻無法使用,因為它分散各處。

一個有用的經驗法則(50% 法則):採用最先適配時,每配置 N 個區塊,約有 0.5N 因碎裂而流失。分頁徹底消除外部碎裂,但它做到這點時無法不引入少許內部碎裂。

又稱
external fragmentation of memory外部碎片