原地内存整理算法

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)。

double_pointer_0.png

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 引线整理算法

引线整理算法通过一种策略解决指针更新的问题,并且不需要额外的域来保存转发地 址。一次引线操作是将指向某对象的指针反转,将指向它的指针连接成链表,当转移 这个对象时,可以通过这个链表找到所有指向他的指针。由于算法会破坏域信息,所 以并不适合并发回收器。引线过程如下图所示:

thread_1.png

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))

By .