9.11
A.
00001001 111100
B.
C.
010111 111100
D.
9.12
00001110 101001
010001 101001
9.13
更新：計算VPN時0x4寫成0010，本錯誤由孫月晴指出，已更正。
000000001 000000
Page fault
9.14
這個題要注意将<code>open</code>的flag設定為<code>O_RDWR</code> ，因為我們要從這個檔案進行讀寫操作，同時<code>mmap</code>的prot也要設定為<code>PROT_WRITE</code> （否則會出現Segmentation fault），最後一點是要将<code>mmap</code>的flags設定為<code>MAP_SHARED</code> ，因為我們需要将更新直接更改于實體記憶體/磁盤上，如果設定為<code>MAP_PRIVATE</code> 更改将不會最終改寫磁盤上的資料（copy-on-write）。參見<code>man 2 mmap</code> ：
運作輸出：
9.15
9.16
更新：這個題我之前是按照Min(Min(Allocated block), Min(Free block))來做的，但是由于allocate操作後剩餘的空間要大于一個Min(Free block)才會有split發生——産生一個比原來的Free block更小的兩個塊。是以最小的塊應該是Max(Min(Allocated block), Min(Free block))，本錯誤由孫月晴指出，已更正。
9.17
本題要求将9.9.12節的“first-fit”政策改為“next-fit”政策，主要改動的函數是<code>find_fit</code> ，同時注意以下兩點：
用一個靜态存儲的指針“rover”儲存上一次搜尋的結果位址（第一次是堆的起始位址），作為下一次搜尋的起點。
釋放（free）節點并且有合并（coalesce）的時候，如果rover正好指向的就是合并的節點中那個高位址的部分，需要将其指向合并後的節點的起始位置。
**下面的代碼改編自CS:APP3e官網的Code examples 的mm.c（完整代碼），如需使用請聯系Randy Bryant and Dave O'Hallaron ** 。
隻需要改變<code>mm_init</code> <code>find_fit</code> <code>coalesce</code> 這三個子產品，注釋寫的非常清楚，就不細說了，宏定義請參考上面連結中的完整代碼。
9.18
由于存在記憶體對齊，Header的最低三位将是000，其中的最低位已經被用來判斷這個塊是否是空塊（free or allocated），我們将倒數第二個位用來判斷前一個塊是否是空塊，例如010代表這個空塊的前一個塊已經被占用了。
我這裡隻利用了Header的倒數第二位，Free block的Boundary tag沒有發生改變。要注意的是，由于allocated塊不需要Boundary tag，是以最小的塊是一個DWORD（一個Header和一個四位元組的資料），最小的存儲機關還是WORD。 最小的free塊1D：
每一個free塊的Boundary tag被申請後可以存資料（與優化前相比多存一個WORD），是以一個1D的free塊可以存1W，2D的塊可以存23W，3D的塊可以存45W，4D的塊可以存6~7W，根據這個對應關系更改<code>mm_malloc</code>函數。
另外要注意的是申請和釋放一個塊以後記得儲存Header中關于前一個塊free or allocated的資料，同時要更新下一個塊Header中free or allocated的資料。
**下面的代碼改編自CS:APP3e官網的Code examples 的mm.c（完整代碼），并去掉了一些檢查子產品，改變的地方用“! CHANGED !”注釋标出，如需使用請聯系Randy Bryant and Dave O'Hallaron ** 。
用這一章實驗的工具檢測正确性：
9.19
答案：adb
下面是錯誤陳述的錯誤原因：
1
(b) "best fit" 可能（看free list是怎麼安排的，例如第二問的d項）更慢，因為可能每一次都需要周遊一遍free list
(c) 如果free block是按照位址高低連結的，那麼每次插入都需要線性的時間（掃描恰當的位址）
(d) 不一定，例如2^m次方這個連結清單上的free block都不能合并（位址不連續），但是現在需要申請一個2m+1的塊，即使2m次方這個連結清單上的空間夠，我們也可能需要向堆申請新的空間，構成了“external fragmentation”
2
(a) 這話看着想打人，空間浪費得有多大。。。這并不能避免“external fragmentation”，因為連結清單上的free block并沒有合并
(b) 應該按照從小到大的順序排列，因為這樣能夠線上性時間内擷取到對應的塊（d選項）
(c) 應該是選擇能夠放下的最小塊
3
書上9.10.3節原話：
The fundamental reason that Mark&Sweep collectors for C programs must be conservative is that the C language does not tag memory locations with type information. Thus, scalars like ints or floats can masquerade as pointers. For example, suppose that some reachable allocated block contains an int in its payload whose value happens to correspond to an address in the payload of some other allocated block b. There is no way for the collector to infer that the data is really an int and not a pointer. Therefore, the allocator must conservatively mark block b as reachable, when in fact it might not be.
9.20
這個題包含在本章對應的Malloc Lab （Self-Study Handout ）實驗中，我做完後會放上來的。
更新：參見 CS:APP3e 深入了解計算機系統_3e MallocLab實驗