本文介绍了标记-清扫式算法,标记的重点在于指针反转。补充习题中的反碎片化清扫。复制、并发等习题待补充。但是算法有点老了,感觉第二卷半数值算法这种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分为两个阶段:
从主程序可以访问的节点开始遍历,标记可达的节点
顺序遍历内存池,清除不可达的节点
第二个阶段存在着某些重要变化,我在EX部分有提及,主要是涉及反碎片化。
第一个阶段是Knuth的重点。
很明显,第一阶段就是个DFS算法。
Question 1:DFS递归深度过大
Ans 1:使用显式栈
Question 2: GC通常在空闲内存很少时才进行,内存仍然不够用
Ans 2:不使用辅助栈空间,在节点中记录栈信息(暂时破坏表结构)Deutsch
我们直接介绍Knuth最后推荐的一个比较优秀的算法,当然现代也有变种。
一句话概括:在节点中存储栈信息,回溯时恢复
我们假设一个节点由四个字段组成,这也是GC的一个难点,因为GC需要尽可能最少的内存开销,只能使用少量存储。
原子节点没有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继续回溯(因为上个节点的左节点必然已经先遍历完毕)
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.