原地内存整理算法
Table of Contents
内存碎片化是内存回收器需要解决的问题之一。尽管堆中仍有可用空间，但是内存管理器却无法分配找到一块连续内存块来满足较大对象的分配需求，或者需要花费较长时间才能找到合适的空闲内存，这就是内存碎片化的问题。
要整理内存，以解决碎片问题，就要移动内存中的对象。对象移动后，原来指向对象的指针也要修改，指向对象新的内存位置。内存整理算法主要解决的问题就是保持指向对象的指针继续指向它这个约束，改变对象的位置以整理出大块空闲内存块。
1 双指针算法
双指针算法是最简单的整理算法。算法假设所有内存分配都是固定大小的，所以适用场景为只包含固定大小对象的区域。算法包括两次堆遍历。我不知道双指针整理算法的意义是什么，既然要求对象大小固定，还有什么整理的必要呢？
(1.1) 第一次遍历初始化时，指针 free 指向区域初始位置，scan 指向区域末端。
(1.2) 随后不断向前移动指针 free， 直到遇到一个空闲位置 (没有"-"的位置)；同时不断向后移动指针 scan，直到遇到一个存活对象。
(1.3) 如果 free 和 scan 发生交错，第一次遍历结束，否则
(1.4) 将 scan 指向的对象移动到 free 的位置，scan 指向的位置记录下原对象移动到了哪里，并将这块内存标记为空闲。随后执行 (1.2)。
(2.1) 第二次遍历初始化时，scan 指向区域初始位置。
(2.2) 如果 scan 指向的位置为空闲内存，第二次遍历结束，否则
(2.3) 如果 scan 指向的对象中包含指向空闲位置的指针 p，则 p 指向的内存块必定包含 (1.4) 中记录的对象移动后的地址，将 p 指向这个地址，随后将 scan 向前移动。执行 (2.2)。
Figure 1: 双指针算法示意图
用上图的流程举例，(a) 初始化； (b) free 找到第一个空闲位置， scan 找到第一个存活对象； (c) 将 scan 指向的对象转移到 free 指向的空闲位置； (d) free 和 scan 继续前几， 两者交叉，第一次扫描结束。第二次扫描将所有指向 6 的指针改为指向 2。
2 Lisp 2 整理算法
Lisp 2 回收算法可以说是历史悠久，同时也得到了广泛应用。尽管需要三次遍历，但每次遍历要做的工作都不多。虽然标记-整理回收算法的吞吐量都比较低，但一些研究发现 Lisp 2 在整理式回收算法中算是最快的。它的缺陷在于，需要每个对象头部都额外增加一个完整的域(forwardingAddress)来记录转发地址。
Lisp 2 需要三次遍历。
(1) 第一次遍历将所有存活对象的 forwardingAddress 域指向最后要移动到的地址。
(2) 第二次遍历将所有指向存活对象的引用都修改为相应对象的 forwardingAddress。
(3) 第三次遍历将所有存活对象转移到 forwardingAddress 中。
compact(): computeLocations(HeapStart, HeapEnd, HeapStart) updateReferences(HeapStart, HeapEnd) relocate(HeapStart, HeapEnd) computeLocations(start, end, to) scan <- start free <- to while scan < end if isMarcked(scan) /* marcked 过的对象是存活的 */ forwardingAddress(scan) <- free scan <- scan + size(scan) updateReferences(start, end): for each fld in Roots ref <- *fld if ref != null *fld <- forwardingAddress(ref) scan <- start while scan < end if isMarked(scan) for each fld in Pointers(scan) if *fld != null *fld <- forwardingAddress(*fld) scan <- scan + size(scan) relocate(start, end): scan <- start while scan < end if isMarked(scan) dest <- forwardingAddress(scan) move(scan, dest) unsetMarked(dest) scan <- scan + size(scan)
3 引线整理算法
引线整理算法通过一种策略解决指针更新的问题，并且不需要额外的域来保存转发地址。一次引线操作是将指向某对象的指针反转，将指向它的指针连接成链表，当转移这个对象时，可以通过这个链表找到所有指向他的指针。由于算法会破坏域信息，所以并不适合并发回收器。引线过程如下图所示：
Figure 2: 引线示意图
引线前，A, B, C 都有一个指针域指向 N, 引线后， N 中的一个域作为链表的头指向 C 中指向 N 的指针， C 中指向 N 的指针指向 B 中指向 N 的指针， B 中指向 N 的指针指向 A 中指向 N 的指针。因为 A 是链表的尾部，所以 A 中原来存放指针的位置可以保存 N 处已经指向 C 的指针的位置的信息。
引线整理算法需要两次遍历，第一次实现引线，以及前向指针的逆引线；第二次实现后向指针的逆引线。
compact(): updateForwardReferences() updateBackwordReferences() thread(ref): // 引线，即反转一个指针 ... update(ref, addr): // 逆引线， ref 为链表头的下一个位置，addr 为链表头 ... updateForwardreferences(): for each fld in Roots thread(*fld) free <- HeapStart scan <- HeapStart while scan <= HeapEnd if isMarked(scan) update(scan, free) // 将所有指向 scan 的前向指针改为 free for each fld in Pointers(scan) thread(fld) free <- free + size(scan) scan <- scan + size(scan) updateBackwordreferences(): free <- HeapStart scan <- HeapStart while scan <= HeapEnd if isMarked(scan) update(scan, free) // 将所有指向 scan 的后向指针改为 free move(scan, free) free <- free + size(scan) scan <- scan + size(scan)
4 单次遍历算法
单次遍历算法用一个位图标记存活的内存对象，并将内存分成大小相等的块，每个块第一个存活对象的转发地址将记录在偏移向量中，块中其它对象的偏移地址通过块大小和块中存活对象的数量与大小实时计算。
compate(): computeLocations(HeapStart, HeapEnd, HeapStart) updateReferencesRelocate(HeapStart, HeapEnd) // 计算每个内存块第一个存活对象的偏移地址 computeLocations(start, end, toRegion): loc <- toRegion block <- getBlockNum(start) for b <- 0 to numBits(start, end) - 1 if b % BITS_IN_BLOCK = 0 offset[block] <- loc // 块中第一个对象的偏移地址 block <- block + 1 if bitmap[b] == MARKED loc <- loc + BYTES_PER_BIT // 根据存活对象大小增加 // 计算对象的偏移地址 newAddress(old): block <- getBlockNum(old) return offset[block] + offsetInBlock(old) // offsetInBlock 通过位图计算 updateReferencesRelocate(start, end): for each fld in Roots ref <- *fld if ref != null *fld <- newAddress(ref) scan <- start while scan < end scan <- nextMarkedObject(sccan) for each fld in Pointers(scan) ref <- *fld if ref != null *fld <- newAddress(ref) move(scan, newAddress(scan))