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实验