TAOCP|基本算法|垃圾回收

摘要

本文介绍了标记-清扫式算法，标记的重点在于指针反转。补充习题中的反碎片化清扫。复制、并发等习题待补充。但是算法有点老了，感觉第二卷半数值算法这种bit tricky可能更好一些。

数据结构

高德纳在TAOCP中使用树的数据结构表示表。（Tricky：我们可以把同时活跃的每个表建立为树，并以匿名的根节点作为所有树的根，那么整个程序的树就被建立出来了）。

表这个概念比较复杂，我们类似理解为结构体就行。

但是Knuth并没有使用多叉的数据结构，而是让每个节点都含有lhs，rhs两个指针。（主要问题是因为Knuth居然在写GC之后才引入多链结构！！！反人类）

此外，每个表的表头都是lhs为空的节点

节点的rhs指向下一个非原子节点。

节点的lhs分为三种情况：

节点是表(like sturct) -> 指向子表的表头

节点是值 (like int)-> 指向原子节点(Knuth修改前,直接数据+rhs)

节点是指针 (like struct*)-> 指向其他节点

原子节点中只有数据(Knuth修改前,直接数据+rhs)

这样一来，原本是图的GC变为了生成树+回边+前向边+横跨边这样的方式。不过有一点比较特殊，不同于普通的生成树，由于这里只有lhs和rhs可以指出，因此出度<=2。这也是这个数据结构的一点好处。

注意,knuth在后面做了修改,原子节点中不具有rhs,我吐了!!!!!!!!!!

标记清扫式GC

标记清扫式GC分为两个阶段：

从主程序可以访问的节点开始遍历，标记可达的节点

顺序遍历内存池，清除不可达的节点

第二个阶段存在着某些重要变化，我在EX部分有提及,主要是涉及反碎片化。

第一个阶段是Knuth的重点。

很明显，第一阶段就是个DFS算法。

Question 1：DFS递归深度过大

Ans 1：使用显式栈

Question 2： GC通常在空闲内存很少时才进行，内存仍然不够用

Ans 2：不使用辅助栈空间，在节点中记录栈信息（暂时破坏表结构）Deutsch

我们直接介绍Knuth最后推荐的一个比较优秀的算法，当然现代也有变种。

标记算法

一句话概括:在节点中存储栈信息,回溯时恢复

我们假设一个节点由四个字段组成，这也是GC的一个难点，因为GC需要尽可能最少的内存开销，只能使用少量存储。

• mark（标记）
• atom（如果不是原子节点,用于标记属于lhs或rhs的回溯过程）
• lhs
• rhs

原子节点没有lhs/rhs,这些字段处用于存放其他数据(大小不一定还是两个指针),可以认为原子节点就是叶子节点.

使用C风格改写作者的伪代码，结果如下。

INIT:
pre = nullptr, cur = p0;
MARK:
p->mark = true;
CHECK:
if(cur->atom)
 goto TRACEBACK;
LHS:
next = cur->lhs;
if(next && !next->mark){
  cur->atom = true;
  cur->lhs = pre;
  pre = cur;
  cur = next;
  goto MARK;
}
RHS:
next = cur->rhs;
if(next && !next->mark){
  cur->rhs = pre;
  pre = cur;
  cur = next;
  goto MARK;
}
TRACEBACK:
if(!pre) return;
next = pre;
if(next->atom){
  next->atom = false;
  pre = next-> lhs;
  next-> lhs = cur;
  cur = next;
  goto RHS;
}
else{
  pre = next-> rhs;
  next-> rhs = cur;
  cur = next;
  goto TRACEBACK;
}

剖析

INIT PHASE

INIT:
pre = nullptr, cur = p0;

这里的pre表示栈顶节点，cur表示当前节点。

MARK PHASE

MARK:
p->mark = true;

标记当前节点可达

CHECK PHASE

CHECK:
if(cur->atom)
 goto TRACEBACK;

如果原子节点，立即回溯到上一个节点。因为原子节点不具有lhs/rhs

这里不可能是lhs改变导致的atom，因为如果这样cur已经mark并且访问了lhs，是不会进入上面的MARK阶段的。只有可能是回溯之后，但是回溯时会重置atom，因此也不可能。

LHS PHASE

LHS:
next = cur->lhs;
if(next && !next->mark){
  cur->atom = true;
  cur->lhs = pre;
  pre = cur;
  cur = next;
  goto MARK;
}

标记atom为true，目的是告诉TRACEBACK当前的栈信息存储在左节点。

lhs存储之前的栈顶，将当前的cur入栈（实际上栈就一个元素），然后访问下一个节点。和DFS类似，不同的是，之前的栈顶放在lhs里存储。

goto MARK； 深度优先

RHS PHASE

RHS:
next = cur->rhs;
if(next && !next->mark){
  cur->rhs = pre;
  pre = cur;
  cur = next;
  goto MARK;
}

区别在于，这里没有标记atom为true。因为上述条件只有当前节点的左节点已经遍历之后才能成立。

在之前的回溯过程中，我们将回退的节点的atom全部置为false，恢复其lhs。因此这里保持atom为false，以让TRACEBACK知道，接下来是从右节点回溯。

TRACEBACK:
...
next->atom = false;

TRACEBACK PHASE

TRACEBACK:
if(!pre) return;
next = pre;
if(next->atom){
  next->atom = false;
  pre = next-> lhs;
  next-> lhs = cur;
  cur = next;
  goto RHS;
}
else{
  pre = next-> rhs;
  next-> rhs = cur;
  cur = next;
  goto TRACEBACK;
}

if(!pre) 说明回退到了起始节点。显然DFS结束。

next = pre 相当于pop栈顶。

如果上一节点atom（lhs被修改），恢复其lhs，并goto RHS，遍历上个节点的右节点。

如果上一节点!atom,则恢复其rhs，并goto TRACEBACK继续回溯（因为上个节点的左节点必然已经先遍历完毕）

Extension

Ex 5【Schorr and Waite】CACM 10(1967),501-506

同时使用辅助栈，仅当栈满时才使用节点存储栈信息。高德纳写第一卷时，这种算法是当时最好的算法。

Ex 9 【Daniel Edwards】

反碎片化算法

一句话概括:清扫时将活跃内存全部换到前面,并在原址留下信息,以供指向活跃内存的指针能够正确切换到新的内存处

原内存池中存在内存块

[公式]

。重新组织被标记的节点，使得所有被标记的节点为

[公式]

。必要时改变非原子字段的lhs和rhs以维护表结构。

上文中的指针都指向一个node，所以这里我们使用. 而不是->

INIT:
i=0； k=m+1;
FIRSTUSE:
while(node[++i].mark);
LASTFREE:
while(!node[--k].mark);
SWAP:
if(i>k)
goto MAINTAIN;
else
node[i]=node[k]
node[k].lhs = node+i;
node[k].mark = false;
goto FIRSTUSE;
MAINTAIN:
for i from 1 to k
node[k].mark=false;
if(!node[i].atom && node[k].lhs > node+k)
node[i].lhs = node[i].lhs->lhs;
if(!node[i].atom && node[k].rhs > node+k)
node[i].lhs = node[i].rhs->lhs;

剖析

INIT PHASE

INIT:
i=0； k=m+1;

初始化首尾索引

FISRTUSE/LASTFREE PHASE

FIRSTUSE:
while(node[++i].mark);
LASTFREE:
while(!node[--k].mark);

i处为第一个free内存块

k处为最后一个active内存块

SWAP PHASE

SWAP:
if(i>k)
goto MAINTAIN;
else
node[i]=node[k]
node[k].lhs = node+i;
node[k].mark = false;
goto FIRSTUSE;

将active的内存覆盖到free的内存上，并且恢复mark，以备下次GC。

现在原本active的内存可以free了，但是，因为之前有指针指向这块active的区域，因此我们必须留下信息，让之前的指针能正确指向改变后的区域。(MOST TRICKY!!!!)

因此我们设置lhs为node+i,也就是改变之后的地址.

如果i>k,说明所有的free的block都被交换到最后的active block了.此时无论是free或者active的block都是连续的.

MAINTAIN PHASE

MAINTAIN:
for i from 1 to k
node[i].mark=false;
if(!node[i].atom && node[i].lhs > node+k)
node[i].lhs = node[i].lhs->lhs;
if(!node[i].atom && node[i].rhs > node+k)
node[i].rhs = node[i].rhs->lhs;

将所有active的block的mark恢复.

如果是原子节点,那么不需要恢复lhs rhs,因为lhs/rhs不是指针字段.

如果指针指向了node+k之后(也就是free区域),说明指向的区块发生过swap

那么根据之前我们在lhs中保存的改变后的地址,我们恢复指针到它该指向的active block.