物理和虛擬循址

較老的系統使用物理循址(physical addressing)，直接用物理地址訪問主存取得資料。

現代處理器則使用虛擬循址(virtual addressing)。CPU生成虛擬地址(Virtual Address, VA)，通過內存管理單元(Memory Management Unit, MMU) 訪問在主存中的查詢表動態翻譯VA成物理地址。查詢表由操作系統管理。

地址空間

地址空間(address space) 是非負整數地址的有序集合，若地址空間是連續的 我們稱它為線性地址空間(linear address space)。為簡化討論，我們假設使用線性地址空間。

在帶虛擬內存的系統中，CPU在有$N=2^{n}$個地址的地址空間中生成虛擬地址，則該地址空間稱虛擬地址空間(Virtual Address Space, VAS)。

地址空間的大小由表示最大地址所需的位數表明，例如一個$N=2^{n}$個地址的虛擬地址空間就稱$n$位虛擬地址空間。

練習題

9.1

虛擬地址位數($n$) 虛擬地址數($N$) 最大可能的虛擬地址
8 $2^{8}$ $2^{8}-1$
16 $2^{16}=64K=2^{6}\times 2^{10}$ $2^{16}-1=64K-1$
32 $2^{32}=4G$ $2^{32}-1=4G-1$
48 $2^{48}=256T=2^{8}\times 2^{40}$ $2^{48}-1=256T-1$
64 $2^{64}=4E$ $2^{64}-1=4E-1$

虛擬地址作為緩存的工具

將物理內存視作虛擬內存的緩存。VM系統將虛擬內存分割成稱作虛擬頁(Virtual Page, VP) 的大小固定的塊，每個虛擬頁的大小為$P=2^{p}$字節。物理內存被分割為大小為$P$字節的物理頁(Physical Page, PP，或稱頁幀, page frame)。

虛擬頁分為三個不相交的子集：

  • 未分配的：VM系統還未分配或創建的頁，沒有數據與它關聯，所以不占磁盤空間。
  • 緩存的：已緩存在物理內存中的已分配頁。
  • 未緩存的：未緩存在物理內存中的已分配頁。

1

DRAM緩存的組織結構

我們使用SRAM表示在CPU和主存之間的L1, L2, L3高速緩存，用DRAM表示虛擬內存系統的緩存，它在主存中緩存虛擬頁。

因為DRAM不命中處罰較大和訪問第一個字節的開銷，虛擬頁通常很大，4KB~2MB。因為不命中處罰大，DRAM緩存是全相聯的，即任何虛擬頁都可放置在任何物理頁中，不會因為映射限制導致額外的頁面置換。

因為對磁盤的訪問時間長，所以DRAM使用寫回而不是直寫。

頁表

頁表(page table) 存放在物理內存中，是由頁表條目(Page Table Entry, PTE) 組成的數組，將虛擬頁映射到物理頁。每次地址翻譯硬件將虛擬地址轉換為物理地址時，都會讀取頁表。操作系統維護頁表的內容，並在磁盤與DRAM間傳送頁。

PTE由一個有效位(valid bit) 和一個$n$位地址字段組成。若設置有效位，則地址段指向DRAM中相應的物理頁起始地址。若沒設置有效位，且地址段為空，則表示該虛擬頁還未分配。否則，地址段指向該虛擬頁在磁盤上的起始地址。

練習題

9.2

$2^{16}=64K$

$2^{32}=4G=4 \times 2^{20}K$

$n$ $P=2^{p}$ PTE數量
16 4K 16
16 8K 8
32 4K $2^{20}$
32 8K $2^{19}$

缺頁

DRAM緩存不命中稱為缺頁(page fault)，此時會發生缺頁異常，調用內核缺頁異常處理程序。處理程序會選擇一個已緩存的犧牲頁(victim page)，使其不再被緩存。然後更新之前緩存犧牲頁的PP，使其緩存我們需要的頁。最後更新PTE使缺頁的條目有效位設置為有效，並更新地址段為之前緩存犧牲頁的PP的起始地址。

然後處理程序會返回，並重新啟動導致缺頁的指令。

在磁盤和內存間傳送頁稱交換(swapping) 或頁面調度(paging)。頁從磁盤換入(頁面調入)，頁從DRAM換出(頁面調出)磁盤。等待直到不命中才換入頁面的策略稱按需頁面調度(demand paging)。

分配頁面

調用malloc的過程，在磁盤創建空間並更新PTE，使其指向磁盤上新創建的頁面。

又是局部性救了我們

局部性保證了程序將趨向一個較小的活動頁面(active page) 集合上工作，該集合稱工作集(working set) 或常駐集合(resident set)。當工作集頁面調度到內存中後，對該工作集的引用將導致命中，而不會訪問磁盤。

若工作集大小超過物理內存大小，頁面將不斷換入換出。此現象稱抖動(thrashing)。

虛擬內存作為內存管理工具

操作系統為每個進程提供獨立的頁表，代表獨立的虛擬地址空間。

多個虛擬頁面可以映射到同個共享頁面上。

2

VM簡化了鏈接和加載、代碼和數據共享，以及內存分配。

  • 簡化鏈接
    獨立地址空間允許每個進程的內存映像使用相同的基本格式，簡化鏈接器的設計實現。
  • 簡化加載
    要把目標文件的.text和.data加載到進程中，Linux加載器為代碼和數據段分配虛擬頁，把它們標示為無效的(未緩存的)，然後把頁表條目指向目標文件中適當的位置。
    注意，加載器不會從磁盤實際複製數據到內存。只有當每個頁初次被引用時，VM系統按需調度頁。
  • 簡化共享
    一般而言，每個進程有自己的私有代碼、數據、堆棧。此時，操作系統創建頁表，將相應的虛擬頁映射到不連續的物理頁面。
    某些情況下，多個進程間需要共享代碼和數據。此時，操作系統將不同進程選定的虛擬頁面映射到相同物理頁面來共享代碼。
  • 簡化內存分配
    當用戶進程要求額外堆空間，操作系統分配$k$個連續的 虛擬內存頁面，並將它們映射到物理內存中任意位置的$k$個物理頁面。因為頁表的工作方式，物理頁面不需要是連續的，可以隨機分散在物理內存中。

虛擬內存作為內存保護的工具

通過在PTE上添加額外的許可位來控制虛擬頁面內容的訪問。

3

其中，SUP位表示必須運行在內核(超級用戶)模式下才能訪問該頁。

若指令違反許可條件，則觸發一般保護故障。Linux shell 通常將這種異常報告為段錯誤(segmentation fault)。

地址翻譯

1

地址翻譯是一個$N$元素的虛擬地址空間(VAS)中的元素與一個$M$元素的物理地址空間(PAS)中的元素映射。

1

下圖展示了頁命中時，CPU執行的步驟：

  1. CPU生成虛擬地址，並傳給MMU。
  2. MMU生成PTE地址，向主存請求PTE。
  3. 主存返回PTE給MMU。
  4. MMU構造物理地址，並將其傳送給主存。
  5. 主存返回請求的數據字給CPU。

1

頁面命中時完全由硬件處理，但缺頁時要求操作系統與硬件協作，如下圖所示：
1~3步與頁命中時。
4.PTE中的有效位是零，MMU觸發異常。
5.缺頁程序確定出犧牲頁，若此頁面已修改則換出道磁盤。
6.缺頁處理程序頁面調入新的頁面，更新PTE。
7.缺頁程序返回，重新運行導致缺頁的指令。

1

練習題

9.3

32位 -> 4GB地址空間

24位 -> 16M地址空間

$P$ VPN位數 VPO位數 PPN位數 PPO位數
1KB 22 10 14 10
2KB 21 11 13 11
4KB 20 12 12 12
8KB 19 13 11 13

結合高速緩存和虛擬內存

若系統同時使用虛擬內存和SRAM，我們選擇使用物理地址來訪問SRAM。無須處理保護問題，因為訪問權限檢查在地址翻譯時就檢查過了。

注意，PTE可以緩存，就像其他數據字一樣。

1

利用TLB加速地址翻譯

MMU中包含一個存儲PTE的小緩存，稱翻譯後備緩衝器(Translation Lookaside Buffer, TLB)，專門用來虛擬尋址的緩存。

TLB的每一行都保存由單個PTE組成的塊。虛擬頁號被劃分成TLB標記和TLB索引。如果TLB有$T=2^{t}$個組，則TLBI由VPN的$t$個最低位組成。

1

下圖展示TLB運行的步驟，命中時因為所有地址翻譯步驟都在MMU中運行，所以很快。

1

多級頁表

1

假設32位虛擬地址空間被分為4KB的頁，每個頁表條目4字節。

我們還假設虛擬地址空間中前2K個頁被分配給代碼和數據，接下來6K個頁面還未分配，再接下來1023個頁面也還未分配，接下來1個頁面分配給用戶棧。

一級頁表中每個PTE映射虛擬地址空間中4MB的片(chunk)，每個片由1024個連續的頁組成。假設地址空間4GB，則只需1024個一級PTE就足夠覆蓋所有空間。

若片$i$所有頁面皆未分配，則一級PTE $i$ 為空。若片$i$至少有一個頁面分配了，那一級PTE $i$ 就指向一個二級頁表的基址。

下圖展示了多級頁表的示意圖。

1

練習題

9.4

A.

0 0 0 1 1 1 1 0 1 0 1 1 1

B.

參數 值
VPN 0xf
TLB索引 0x3
TLB標記 0x3
TLB命中? 是
缺頁? 否
PPN 0xd

C.

0 0 1 1 0 1 0 1 0 1 1 1

D.

參數 值
字節偏移 0x3
緩存索引 0x5
緩存標記 0xd
緩存命中? 是
返回的緩存字節 1D

Linux 虛擬內存系統

1

上圖標示了一些之前沒填寫的細節，即內核虛擬內存。

內核虛擬內存的某些區域被映射到所有進程共享的物理頁面。比如進程共享的代碼和數據結構。

Linux 還將一組連續的虛擬頁面(大小等於DRAM總量)映射到一組連續的物理頁面，方便內核訪問物理內存中特定位置。例如，訪問頁表。

Linux 虛擬內存區域

Linux將虛擬內存組織成區域(area，或稱段, segment) 的集合。區域就是已分配的連續虛擬內存片(chunk)，同個區域內的頁必定互相關聯。比如，代碼段、數據段、用戶棧，都屬於不同區域。

每個已分配的頁必定屬於某個區域，否則該頁未分配(不存在)，不能被進程引用，亦不占任何空間。

內核為進程維護一個任務結構(task_struct)，保存運行該進程所需的所有信息。

任務結構中有個條目指向mm_struct，其描述虛擬內存中的狀態。

其中兩個字段pgd和mmap我們較關心。pgd指向第一級頁表(頁全局目錄)的基址，當進程運行時CR3控制寄存器就會存放pgd。mmap指向vm_area_structs鏈表。

每個vm_area_structs節點描述一個區域：

  • vm_start：指向該區域起始地址。
  • vm_end：指向該區域末地址。
  • vm_prot：區域內頁的讀寫權限。
  • vm_flags：區域內頁是與其他進程共享還是私有。(以及一些其他信息)
  • vm_next：指向下一個vm_area_structs。

1

Linux 缺頁異常處理

缺頁處理程序是這樣處裡異常的：

  1. 虛擬地址A是否合法？A是否在一個區域內？不在的話觸發段錯誤並終止進程。
  2. 內存訪問是否合法？進程是否有讀寫、執行該區域內頁面的權限？若不合法則觸發保護異常並終止進程。
  3. 該缺頁由於合法的地址與操作造成。選擇一個犧牲頁，換入新頁並更新頁表。

內存映射

Linux 將虛擬內存區域與磁盤上的對象關聯，以初始化該虛擬內存區域的內容。此過程稱內存映射(memory mapping)。

虛擬內存區域可以映射到下列兩種類型對象：

  1. 普通文件：例如可執行目標文件。文件區(section)被分成頁大小的片，每一片包含虛擬頁面的初始內容。因為按需頁面調度，虛擬頁並沒有進入物理內存中，直到CPU第一次引用該虛擬頁。若區域比文件區大，剩下部分填充零。
  2. 匿名文件：匿名文件由內核創建，由二進制的零填充。CPU第一次引用虛擬頁，內核在物理內存中尋找犧牲頁並用二進制零覆蓋頁面，最後更新頁表。注意磁盤和內存間沒有實際的數據傳送。映射到匿名文件區域的頁亦稱請求二進制零的頁(demand-zero page)

虛擬頁被初始化後，它就在由內核維護的交換文件(swap，或稱交換空間, swap space，或稱交換區域, swap area) 中調度。交換空間的大小限制了一個進程可分配的頁數量。

再看共享對象

若一個對象被作為共享對象映射到虛擬內存中的一個區域中，那麼該進程對該區域做的所有操作，對所有把該共享對象映射到虛擬內存中的進程都是可見的。這些變化也會反映在磁盤上的原始對象中。若兩個進程共享同一個對象，則物理內存中只需要存放一個副本

若兩個進程將同一個私有對象映射到虛擬內存中，起始時物理內存中只存放一個副本。對每個映射私有對象的進程，相應私有區域應標示為只讀，並且區域結構被標記為私有的寫時複製(copy-on-write)。當一個進程寫私有區域內的頁時，觸發保護故障。此時，處理程序會在物理內存中創建這個頁的副本，更新PTE然後恢復這個頁的可寫權限。

1

如上圖所示，延遲私有對象的副本創建，寫時複製充分利用稀有的物理內存。

再看fork函數

當fork被當前進程調用，內核為新進成創建數據結構，並分配唯一的PID。

為了給新進成創建虛擬內存，內核創建當前進程mm_struct、區域結構和PT的副本。它將兩個進程中每個頁都標為只讀，並將區域結構標記為私有的寫時複製。

再看execve函數

執行execve函數需要幾個步驟：

  1. 刪除已存在的用戶區域：刪除當前進程虛擬地址用戶部分區域結構。
  2. 映射私有區域。
  3. 映射共享區域。
  4. 設置PC。

1

使用mmap函數的用戶級內存映射

1
2
3
4
5
#include <unistd.h>
#include <sys/mman.h>

/* 返回：成功則為指向映射區域的指針，否則為MAP_FAILED(-1) */
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
  • start：請求內核最好從此處開始分配區域，僅作為請求通常為NULL。
  • prot：描述區域的訪問權限(即vm_prot位)
    • PROT_EXEC
    • PROT_READ
    • PROT_WRITE
    • PROT_NONE：該區域內的頁不能被訪問。
  • flags：描述被映射對象類型
    • MAP_ANON：匿名對象。
    • MAP_PRIVATE：私有、寫時複製對象。
    • MAP_SHARED：共享對象。
  • fd：文件描述符，將指定的對象中連續的片映射到此區域。
  • offset：文件讀取的偏移。

例如：

1
buf = mmap(NULL, size, PROT_READ, MAP_PRIVATE | MAP_ANON, 0, 0);

可以使用munmap刪除區域：

1
2
/* 返回：成功0，否則-1 */
int munmap(void *start, size_t length);

此函數刪除由start開始長length的區域。刪除後對該區域的引用會出錯。

練習題

9.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

int main(int argc, char *argv[])
{
    if (argc != 2) {
        printf("[-] argument error! \n");
        return -1;
    }

    int target = open(argv[1], O_RDONLY);

    if (target == -1) {
        printf("[-] cannot find file: %s\n", argv[1]);
        return -2;
    }

    struct stat s_target;
    if (fstat(target, &s_target) == -1) {
        printf("[-] get file %s state error\n", argv[1]);
        close(target);
        return -3;
    }

    char *buf = mmap(NULL, s_target.st_size, PROT_READ, MAP_PRIVATE, target, 0);

    if (buf != MAP_FAILED) {
        printf("[+] file %s mapped! \n", argv[1]);
    }
    else {
        printf("[-] cannot map file %s\n", argv[1]);
        close(target);
        return -4;
    }

    close(target);

    if (!write(STDOUT_FILENO, buf, s_target.st_size)) {
        printf("[-] failed to write stdout with buf\n");
        return -5;
    }

    return 0;
}

動態內存分配

動態內存分配器(dynamic memory allocator) 維護一個稱為堆的區域。堆是一個向高地址增長的請求二進制零區域，緊接著未初始化數據(.bss)區域後開始。變量brk(讀break)指向堆的頂部。分配器將堆視為一組不同大小的塊(block)，每個塊都是連續的虛擬內存片(chunk)。

分配器有兩種基本風格：

  • 顯式分配器(explicit allocator)：要求顯式地釋放已分配的塊。如malloc, free或new delete。
  • 隱式分配器(implicit allocator)：或稱垃圾收集器(garbage collector)，自動釋放已分配的塊(垃圾收集, garbage collection)。

malloc和free函數

1
2
3
4
#include <stdlib.h>

/* 返回：成功為指向分配塊的指針，否則NULL */
void *malloc(size_t size);

若編譯在32位模式(gcc -m32)，malloc返回塊的地址總是8的倍數，64位則總是16的倍數。

若想取得以初始化的動態內存，可以使用calloc，它是malloc的瘦包裝函數，會將分配的內存初始化為零。若想改變已分配塊的大小，可以使用realloc。

動態內存分配器，除了通過mmap和munmap函數，還可以使用sbrk函數：

1
2
3
4
#include <unistd.h>

/* 返回：若成功則為舊brk指針，否則-1並令errno為ENOMEM */
void *sbrk(intptr_t incr);

sbrk修改brk來拓展或收縮堆。若incr為零，則返回當前brk值。incr可以為負，而且返回值會在新堆頂向上abs(incr)個字節。

讓我們模擬一些malloc和free對堆的操作：

  1. 程序請求4個字。
  2. 程序請求5個字，因為數據對齊所以分配6個字。
  3. 程序請求6個字。
  4. 釋放第二步分配的6個字。注意，p2仍指向被釋放的塊，在重新初始化前不可使用。
  5. 程序請求2個字。

1

碎片

碎片(fragmentation) 指雖有未使用的內存，但不能滿足分配請求的現象。

有效載荷(payload)：指分配器分配後，用戶實際可用的部分。(不包括 chunck header 和 pedding)

碎片分為兩種：

  • 內部碎片：已分配塊比有效載荷大時發生。比如上圖 (b) 中的內存對齊使得分配塊比有效載荷大。內部碎片的大小，即已分配塊大小與有效載荷差的和。
  • 外部碎片：當空閒內存合計起來足以滿足分配請求，但沒有單獨的空閒空間可以處理此請求時發生。比如，若在上圖 (e) 的情況下請求8個字，雖然堆中仍有8個字空閒空間，但這8個字分在兩個空閒塊中。量化外部碎片比量化碎片難，因為它不只取決於先前請求模式和分配器實現方式，還取決於將來請求的模式。

實現問題

想實現一個分配器，必須考慮以下問題：

  • 空閒塊組織：如何記錄空閒塊？
  • 放置：如何選擇合適的空閒塊來分配？
  • 分割：當空閒塊被分配後，如何處理該空閒塊的剩餘部分？
  • 合併：如何處理剛被釋放的塊？

我們在一種稱為隱式空閒鏈表的數據結構中解釋上述問題。

隱式空閒鏈表

1

上圖展示了一個簡易的堆塊結構。

若我們強加一個對8的對齊要求，則塊大小的最低3位必是0，所以存儲塊大小只需要29個高位。在這種情況下，低3位就可以拿來編碼其他信息(特別妙的一種想法)。此時，我們利用低3位標記此塊是否已分配。

例如，我們有一個已分配的塊，大小為24(0x18)字節。則他的頭部將是：

1
0x00000018 | 0x1 = 0x00000019

由上述的塊結構，我們可以將堆看做連續的已分配塊和空閒塊交錯出現的序列：

1

我們稱這種結構隱式空閒鏈表(implicit free list)，因為空閒塊間由頭部的塊大小字段隱式連接著。在結構的最後，我們需要一種特殊標記的結束塊，此例中是一個設置已分配位且大小為零的終止頭部(terminating header)。

此結構的優點是簡單，缺點則是操作的開銷大。比如，要為新分配的塊選擇空閒塊放置。此時要對空閒鏈表進行搜索，且時間與堆中已分配塊和空閒塊總數呈線性關係。

注意，系統對齊要求和分配器塊數據結構格式會限制最小塊大小，沒有任何已分配塊可以比這個最小值小。例如，上述的塊格式邀導致最小的塊佔8字節。4字節作為 header，4字節用來維持對齊。

練習題

9.6

請求 塊大小(十進制字節) 塊頭部(十六進制)
malloc(1) 8 0x00000009
malloc(5) 16 0x00000011
malloc(12) 16 0x00000011
malloc(13) 24 0x00000019

放置已分配的塊

當應用請求塊，分配器搜索空閒鏈表，查找足夠放置所求塊的空閒塊。分配器執行搜索的方式由放置策略(placement policy) 確定。

以下是常見的策略：

  • 首次匹配：從頭開始搜索，選擇第一個適合的空閒塊。
    • 優點：傾向於將大空閒塊留在鏈表後面。
    • 缺點：前面留下太多小空閒塊碎片，導致搜索較大塊的時間增加。
  • 下一次匹配：從上一次查詢結束的地方開始搜索，選擇第一個適合的塊。
  • 最佳匹配：檢查每個空閒塊，找到最適合的。

分割空閒塊

一旦找到合適的空閒塊，就必須做出另一個策略決定，分配這個塊中多少空間。

  • 若匹配佳，選擇使用整個空閒塊。缺點：造成內部碎片。
  • 若匹配不佳，分割空閒塊。

合併空閒塊

當分配器釋放已分配塊時，可能有其他空閒塊與新釋放的空閒塊相鄰。相鄰的空閒塊可能導致假碎片(fault fragmentation)。

為了解決此問題，分配器必須合併相鄰的空閒塊，此過程稱合併(coalescing)。合併分為立即合併與推遲合併(deferred coalescing)，延遲合併會等某個分配請求失敗，才會掃描整個堆進行合併。

快速的分配器應使用推遲合併，但我們這裡的假設使用立即合併。

帶邊界標記的合併

我們稱想要釋放的塊為當前塊。想要合併處於當前塊的下一個空閒塊很簡單，只要檢查下一塊的頭部，並將它的大小加到當前塊的頭部即可。

但是若想合併處於當前塊之前的空閒塊，則必須整個重新遍歷一次鏈表。釋放的時間與堆的大小成線性關係。

Knuth提出邊界標記(boundary tag) 的技術，允許常數時間的合併。邊界標記通過往每個塊的結尾添加一個腳部(footer，亦稱邊界標記) 實現，腳部存放的是頭部的副本。當前塊可以通過訪問腳部來判斷當前塊之前的塊是否空閒。

對每個塊添加腳部貌似有點奢侈，其實，只有未分配塊才需要腳部。已分配塊只需要將已分配/空閒位存儲在當前塊的頭部低位(當前塊腳部仍保持當前塊的已分配/空閒位)，就可以被當前塊識別，從而略過合併。但是，空閒塊仍需要腳部，因為當前塊需要從腳部取得塊大小。

練習題

9.7

對齊要求 已分配的塊 空閒塊 最小塊大小(字節)
4 頭部、腳部 頭部、腳部 12
4 頭部 頭部、腳部 8
8 頭部、腳部 頭部、腳部 16
8 頭部 頭部、腳部 8

9.8

1
2
3
4
5
6
7
8
9
10
11
12
static void *find_fit(size_t asize)
{
	char *cur = heap_listp;

	/* we can also use GET_SIZE(HDRP(cur)) > 0 as condition (touched epilogue? ) */
	while (cur < mem_brk) {
		if (GET_SIZE(HDRP(cur)) >= asize && !GET_ALLOC(HDRP(cur)))
			return cur;
		cur = NEXT_BLKP(cur);
	}
	return NULL;
}

9.9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void place(void *bp, size_t asize)
{
	size_t prev_size = GET_SIZE(HDRP(bp));
	
	/* in this case, minimum block size equals to 16 bytes */
	if ( (prev_size - asize) >= 2 * DSIZE) {    /* split */
		PUT(HDRP(bp), PACK(asize, 1));
		PUT(FTRP(bp), PACK(asize, 1));
		PUT(HDRP(NEXT_BLKP(bp)), PACK(prev_size - asize, 0));
		PUT(FTRP(NEXT_BLKP(bp)), PACK(prev_size - asize, 0));
	}
	else {                                      /* use entire free block */
		PUT(HDRP(bp), PACK(prev_size, 1));
		PUT(FTRP(bp), PACK(prev_size, 1));
	}
}

顯式空閒鏈表

由於隱式空閒鏈表的塊分配與堆塊數量呈線性關係，所以不適合用於通用分配器。這時，顯式空閒鏈表較適用。

因為空閒塊不需要主體，我們可以將指針數據放在此處。例如，可以組織成一個雙向鏈表，並存儲在空閒塊中。這樣可以使分配時間從總塊數的線性時間減少到總空閒塊數的線性時間。

釋放塊有兩種策略：

  • 後進先出(LIFO)：將新釋放的塊放在鏈表頭部。複雜度：$O(1)$。
  • 按地址順序：將新釋放的塊放在按地址大小排序的相應位置，因為必須遍歷找到新釋放塊的pred和succ，所以複雜度較高。複雜度：$O(n)$。

按地址排序的首次適配有較高內存利用率，這也是為何就算時間複雜度較高也有人選用的原因。

顯式鏈表的缺點是，最小塊大小增加，提高內部碎片的程度。

1

分離的空閒鏈表

空閒鏈表的核心想法是，把不同大小的塊分開管理，每種大小一條鏈表。我們稱這些大小為等價類或大小類(size class)。

  1. 簡單的分離存儲
    每個大小類的空閒鏈表都是大小相等的塊，每個塊的大小都是該大小類中最大元素的值。比如大小類定義為${ 17\sim 32 }$則每個快大小都為32。這個辦法缺點嚴重，我就不詳細介紹了。
  2. 分離適配
    對於不同大小類，分配器維護很多鏈表與之關聯。鏈表中，每個塊的大小都在相應大小類區間中。所以想要操作塊時，只要簡單的向對應鏈表搜索即可。

垃圾收集

垃圾收集器的基本知識

垃圾收集器將內存視為有向可達圖(reachability graph)，由根節點和堆節點組成。根節點不在堆，但保存指向堆的指針。堆節點則對應於堆中的一個已分配塊。

任何不可達節點都是垃圾，收集器釋放它並返回給空閒鏈表。

C/C++的收集器通常無法精確維持可達圖，即保守垃圾收集器(conservative garbage collector)。某些不可達節點可能被誤記為可達。

Mark & Sweep 垃圾收集器

Mark & Sweep 垃圾收集器由標記和清除兩階段組成，標記階段會標記出根結點與所有可達的已分配後繼，清除階段則會釋放未被標記的已分配塊。header 中，空閒低位的其中一位會被拿來標記用。

我們對 Mark & Sweep的描述使用以下函數，其中ptr定義為typedef void *prt：

1

標記階段會對所有根節點調用一次mark函數：

1
2
3
4
5
6
7
8
9
10
11
12
void mark(ptr p)
{
	if ( (b = isPtr(p)) == NULL)
		return;
	if (blockMarked(b))
		return;
	markBlock(b);
	len = length(b);
	for (i = 0; i < len; i++)
		mark(b[i]);
	return;
}

清除階段使用sweep函數在堆上每個塊上循環：

1
2
3
4
5
6
7
8
9
10
11
void sweep(ptr b, ptr end)
{
	while (b < end) {
		if (blockMarked(b))
			unmarkBlock(b);
		else if (blockAllocated(b))
			free(b);
		b = nextBlock(b);
	}
	return;
}

下圖是使用 Mark & Sweep 的一個例子：

1

可以看到在 Mark 階段，塊2和塊5沒有被標記，所以在 Sweep 階段被釋放。

C程序的保守 Mark & Sweep

想要在C語言中實現垃圾收集器，有兩大難點：

  1. isPtr無法判斷入參是否為指針。
  2. isPtr若入參是指針，如何判斷入參是否指向已分配塊有效載荷中的某個位置？

對於第一點，我們只能採用保守策略，若該值正好指向已分配塊有效載荷中的某個位置，則標記該塊為可達，就算實際不可達。

對於第二點，我們可以使用一個平衡二叉樹來實現。所有已分配的塊作為二叉樹的一個節點，節點中存放塊大小。而左子樹存放所有地址小於當前塊的已分配塊(的 header )，右子樹存放所有地址大於當前塊的已分配塊。

我們只需要二分查找AVL樹，利用 header 就可以判斷是否指向已分配塊有效載荷中的某個位置。

1

C程序中常見的內存有關錯誤

假設指針和指向的對象大小相同

考慮以下代碼：

1
2
3
4
5
6
7
8
int **makeArr(int n, int m)
{
	int i;
	int **A = (int **)malloc(n * sizeof(int));
	for (i = 0; i < n; i++)
		A[i] = (int *)malloc(m * sizeof(int));
	return A;
}

這段代碼只有在int的大小和int *的大小相同時可以產生正確結果。

如果int *在某系統佔8字節，則會產生錯誤結果，而且可能要運行很久才會發生錯誤。