配置器的工作（把請求串流對應到位址範圍）

想像一場熱鬧活動的衣帽寄放櫃台。人們不斷走來遞給你各種大小的外套——一條小圍巾、一件厚羽絨衣——你必須收好每一件並給一張票券。之後他們會以任意順序拿著票回來要回自己的外套。你的儲藏室是一塊固定且有限的空間，每件外套放哪裡由你決定。記憶體配置器（memory allocator）對一個執行中的程式做的正是這件事：一連串請求進來索取各種大小的記憶體區塊，程式之後把區塊歸還，配置器必須把它們全部塞進程式定址空間中的一塊大區域裡。

精確地說：配置器就是 malloc() 與 free() 背後的程式碼。它拿到一塊大而連續的虛擬位址範圍（它透過像 sbrk() 或 mmap() 這樣的呼叫向作業系統擴大這塊範圍），並且必須服務一串無法預測、交錯而來的請求：malloc(size) 的意思是幫我找一塊至少 size 個位元組的閒置區塊並回傳其位址，而 free(p) 的意思是位址 p 處的區塊又閒置了，把它收回。配置器永遠看不到未來——它不知道接下來會有什麼請求，而且一旦發出指標就不能再搬動該區塊，因為程式正在使用那個確切的位址。所以它必須在當下就把每個區塊放好，並在自己的記帳資料（自由串列、標頭、size class）中記住區域裡哪些部分在用、哪些是空的。

這是個真正困難的設計問題，因為各個目標互相衝突。你希望配置與釋放都很快（理想上只要幾條指令），希望浪費的記憶體很少（不要讓區域裡塞滿無法使用的小縫隙），又希望在許多執行緒同時呼叫 malloc() 時仍能擴展。沒有任何單一策略能在這三點上全勝。每個真實的配置器——系統 malloc、jemalloc、tcmalloc、一個 arena、一個 pool——都是對下列問題的一組具體回答：這個區塊我放哪裡、我怎麼追蹤空閒空間、我怎麼讓執行緒不必互相等待。這個領域接下來談的就是這些答案。