感谢R大精彩深入的回复，我想我对G1算法本身现在应该算是搞清楚了。但可能是因为我对CMS的理解还比较肤浅，所以对R大的回复中很多关于G1和CMS的对比反而没有搞明白。具体有如下问题：
1.
为什么还要“外加根集合”啊。
2.CMS的“incremental update”到底是如何工作的，与SATB的区别在什么地方。SATB就是gc开始时的snapshot加上gc开始后新分配的对象，而incremental update难道不也是这样吗？

关于G1算法本身，还有两个问题：
1.为什么每个region需要prevTAMS和nextTAMS两个TAMS。
2.为什么分代G1可以“skip dirtying cards for young gen regions”

最后一个小问题：
R大的post_write_barrier代码中，dirty_region这个变量名是否是因为已经存在dirty_card这个常量名所以不得已才用的。card表示的就是内存中的一片区域吧，其在card table中的对应是所谓的card entry。不知对概念的理解是否有误！

楼主终于来回复了啊～


关于CMS、incremental update等的问题不如另外开一帖讨论？
这些知识在《The Garbage Collection Handbook》中讲解得非常透彻，买本来读读这些问题就全解决了。

简单说，SATB与incremental update是用不同的方式保证concurrent marking不漏扫描活对象。
回到扫描对象图的基本模型——三色扫描。黑色是自己已标记且字段也全部标记了的对象（collector就不会再访问到它了），灰色是自己已标记但尚有字段未标记的对象（collector正在访问的对象），白色是尚未标记的对象。
黑色和灰色对象都是确定存活的对象。灰色对象的集合构成了当前collector正在扫描的分界面（wavefront）。从分界面的角度看，灰色是正在分界面上，白色是在分界面之前，黑色是在分界面之后。

要不漏扫活对象，最最重要的就是下述两种情况不同时发生：
1、mutator把一个白对象的引用存到黑对象的字段里
2、某个白对象失去所有能从灰对象到达它的引用路径（直接或间接）

黑对象持有了指向白对象的引用。根据定义，collector已经不会再去遍历黑对象的字段，所以发现不了这里还有一个活引用指向这个白对象。如果还有某个灰对象持有直接或间接引用能到达这个白对象，那就没关系；如果从灰对象出发的所有引用到这个白对象的路径都不幸被切断了，那这个白对象就要被漏扫描了。

Incremental update的做法是：只要在write barrier里发现要有一个白对象的引用被赋值到一个黑对象的字段里，那就把这个白对象变成灰色的（例如说标记并压到marking stack上，或者是记录在类似mod-union table里）。这样就强力杜绝了上述第一种情况的发生。

SATB的做法是：把marking开始时的逻辑快照里所有的活对象都看作时活的。具体做法是在write barrier里把所有旧的引用所指向的对象都变成非白的（已经黑灰就不用管，还是白的就变成灰的）。
这样做的实际效果是：如果一个灰对象的字段原本指向一个白对象，但在concurrent marker能扫描到这个字段之前，这个字段被赋上了别的值（例如说null），那么这个字段跟白对象之间的关联就被切断了。SATB write barrier保证在这种切断发生之前就把字段原本引用的对象变灰，从而杜绝了上述第二种情况的发生。

很明显，incremental update write barrier和SATB write barrier都“过于强力”，不丹足以保证所有应该活的对象都被扫描到，还可能把一些可以死掉的对象也给扫描上了。这就是它们的精确度问题，结果就是floating garbage。Yuasa式的SATB write barrier的精度应该是比CMS用的incremental update write barrier低——前者比后者导致的floating garbage更多。

如果把mutator看作一个抽象的对象（里面包含root set），那么mutator也可以用三色抽象来描述：有使用黑色mutator的算法，也有使用灰色mutator的算法。关键在于是否允许mutator在concurrent marking的过程中持有白对象的引用，允许则为灰色mutator，不允许则为黑色mutator。

SATB write barrier是一种黑色mutator做法，而incremental update write barrier是一种灰色mutator做法。

灰色mutator做法要完成marking就需要重新扫描根集合。这就是为什么使用incremental update的CMS在remark的时候要重新扫描整个根集合。


因为G1是并发的嘛。论文里其实已经说清楚了。
G1的concurrent marking用了两个bitmap：
一个prevBitmap记录第n-1轮concurrent marking所得的对象存活状态。由于第n－1轮concurrent marking已经完成，这个bitmap的信息可以直接使用。
一个nextBitmap记录第n轮concurrent marking的结果。这个bitmap是当前将要或正在进行的concurrent marking的结果，尚未完成，所以还不能使用。

对应的，每个region都有这么几个指针：

|<-- (1) -->|<-- (2) -->|<-- (3) -->|<-- (4) -->|
bottom      prevTAMS    nextTAMS    top         end

其中top是该region的当前分配指针，[bottom, top)是当前该region已用（used）的部分，[top, end)是尚未使用的可分配空间（unused）。
(1): [bottom, prevTAMS): 这部分里的对象存活信息可以通过prevBitmap来得知
(2): [prevTAMS, nextTAMS): 这部分里的对象在第n-1轮concurrent marking是隐式存活的
(3): [nextTAMS, top): 这部分里的对象在第n轮concurrent marking是隐式存活的
这样清楚了？


之前的回复里已经多次提到了嘛：因为young gen region总是在CSet里，它们总是会被收集，所以不需要记录从它们出发的跨region引用。
还记得前面说remembered set是用来干嘛的不？是在只收集部分区域的GC中用来记录“不收集区域”指向“收集区域”的数据结构。这里不需要记录从young gen region到别的region的引用，就跟一般的分代式GC不需要记录从young gen到old gen的引用一样。


其实card、card table这些概念在实际使用中略模糊。Card到底是card table里那个byte，还是那个byte所覆盖的内存区域？

我所理解的，还有书上啊论文上通常说的是被覆盖的内存区域是card，在card table里的byte是card table entry。
而在HotSpot VM的代码里多数是用前者，card就是card table里的byte，而它所覆盖的内存区域则另外找词来描述。有时候也把两种用法混在一起用。是有点混乱嗯。

HotSpot里dirty_card、clean_card、g1_young_gen这些都是一个card可以有的值的枚举常量。
我把我的伪代码里的dirty_region改为dirty_mem_region了，免得跟G1的HeapRegion概念冲突。

非常感谢R大的回复，由于最近比较忙，加上基础有点薄弱，看了好几遍你得回复才明白了个大概。对于RSet部分基本明白了，不过对于G1的gc过程还是有许多不解

这两个部分和young gc和 mixed gc有什么关系？是说这两部分组成了young gc和mixed gc么？为什么说


我之前写得“而又有一些说法是minor gc是 STW的，显然并发收集不能适用于YGC”
前半句很多地方都看到过，比如：
http://www.oracle.com/technetwork/tutorials/tutorials-1876574.html
Young generation garbage collections, or young GCs, are stop the world events. All application threads are stopped for the operation.
和
http://www.infoq.com/articles/G1-One-Garbage-Collector-To-Rule-Them-All
When eden reaches capacity, a “young garbage collection”, also known as an “evacuation pause”, will occur. This is a STW pause that copies (evacuates) the live objects from the regions that make up the eden, to the 'to-space' survivor regions.
后半句是我推测的，因为global concurrent marking是有并发的，所以我推测它不是YGC的一部分

关于global concurrent marking的表格，也是我看到相关的blog写出的，来源暂时没找到，回头找到后补上，不过cleanup阶段的确是没有拷贝操作的，我写的时候也是把global concurrent marking当成一个完成的gc过程了。

我更新的回复里在这后面紧接着就说了：

就是为了解答您对young GC与mixed GC的疑惑。


逻辑上global concurrent marking与evacuation是相对独立的。但是global concurrent marking之中initial marking要做的事情正好跟young GC要做的事情有重叠——遍历根集合，所以在实现上把它们安排在一起做。

一个young GC可以顺带做initial marking，也可以不做；
一个正常的initial marking（除非是System.gc()+ -XX:+ExplicitGCInvokesConcurrent）总是搭在young GC上做。

一个假想的混合的STW时间线：

启动程序
-> young GC
-> young GC
-> young GC
-> young GC + initial marking
(... concurrent marking ...)
-> young GC (... concurrent marking ...)
(... concurrent marking ...)
-> young GC (... concurrent marking ...)
-> final marking
-> cleanup
-> mixed GC
-> mixed GC
-> mixed GC
...
-> mixed GC
-> young GC + initial marking
(... concurrent marking ...)
...

其中可以看到young GC可以单独运行，也可以搭上initial marking在同一个STW中运行。
“young GC (... concurrent marking ...)”的行里面young GC还是单独运行的，跟后台正在进行的concurrent marking不冲突。


嗯，前半句跟事实吻合，但是后半句有点奇怪所以我才问的。因为用后半句的描述方式有可能引致微妙的误解。


OK～

谢谢R大的耐心讲解。总算理解global concurrent marking和evacuation的关系了，也就是说global concurrent marking对mixed gc中的old gen gc有帮助，与young gc没多大关系，young gc和mixed gc都是STW的，他们都是用了拷贝算法。
另外还有一点需要确认一下：

也就是说做YGC的时候，只需要选定young gen region的RSet（记录了old->young的跨代引用）作为根集，这样就避免了扫描old gen？
而mixed gc的时候，old gen中记录了old->old的RSet，young->old的引用由扫描全部young gen region得到，这样也不用扫描全部old gen region。在扫描young gen region的时候，还需要判断young-> old 中的old对象所在的region是否在CSet中。在的话，才标记为活的。

麻烦R大帮忙确认下上述表述是否有问题，谢谢

对的。


这个也对的。扫描任何region的时候如果碰到指向不在CSet里的region的引用都可以忽略，不只是扫描young gen region可以。
要记住的是，在一次收集中，从非收集区域到收集区域的incoming reference是重要的（需要作为根集合的一部分），而从收集区域到非收集区域的outgoing reference是可忽略的（非收集区域的对象反正不收集，可以当作还活着）。

还有个小细节：在有liveness bitmap指明对象生死情况的地方，G1可以借助liveness bitmap来减少card table引致的floating garbage。具体是：
假如region A的RSet记录着有来自region B的card 123有incoming reference，而这个card 123正好在第n-1轮global concurrent marking已经记录下了对象生死在prev liveness bitmap里，那么在扫描card 123的时候只有prev liveness bitmap说还活着的对象的字段会被扫描，bitmap说已经死掉的对象则不会被扫描。

感觉R大是24-hour on-call，我无论白天还是晚上提问，没多久就能收到回复，赞勤奋~

感觉我应该先看看《The Garbage Collection Handbook》这本书，您提到的一些基本概念（如liveness bitmap ）我都得现查。印象中R大貌似想翻译这本书的，后来是不是放弃了，很期待中文版啊。

抱歉…是放弃了。真的抱歉嗯。

liveness bitmap其实就是个外置的mark bit啦，没啥神奇的。
带有marking阶段的GC，要记录某个对象是否已经被mark，可以在对象头上借用一个bit，也可以在一个外部的bitmap里记录。G1的global concurrent marking用的是外部的bitmap方式，这在前面的某个回复里提到了。

关于incremental update和SATB的理解，开了一个新帖子，http://hllvm.group.iteye.com/group/topic/44529，请R大指点。

另外关于prevTAMS和nextTAMS还是没有搞懂，关键是R大所说的第n-1轮concurrent marking和第n轮concurrent marking到底是什么，G1的过程按照您最初的回复不就是初始标记、并发标记、最终标记和清理四个阶段吗，难道并发标记阶段本身还分成很多轮吗，那轮与轮之间的边界到底是什么，是一次STW的SATB buffer的处理吗？