硬实时系统算法介绍及探讨
最近涉及到一套硬实时系统的设计相关工作，这里简要分享3种生产环境可用的并发算法，分别是并发标记-清除、并发标记-整理和一套并发复制算法，欢迎深入探讨。
一、 可移植性强、稳定的多核心系统并发标记清理算法
算法特点是在尽可能不妨碍Mutator工作的情况下以单线程和增量方式逐步完成整个堆的标记清理。算法的高效性之一体现在当Mutator进行对象初始化、读写对象、加载到寄存器计算操作时几乎不会有额外的屏障触发和同步开销。这也体现在Collector和mutator并发执行时Collector几乎不会阻塞Mutator的正常工作。虽然在回收过程中Collector工作需要mutator配合，但其所承担的额外工作量相比其正常工作来说也微乎其微，要进一步说明的是当Mutator尝试更新一个字段或者创建、清扫堆中的对象时，很少调用系统互斥函数。
可移植性表现在对比大多数并发算法存在的两个问题：1.在Mutator中加入几乎不可忍受的屏障开销，2.需要特定的硬件指令支持。该算法则几乎没有。
算法的应用场景：
1. 寄存器是本地化的线程私有空间、当一根线程正在占用CPU时间进行运算时，如果没有特定的触发条件，认为寄存器中的值永远也不会同步回主存（虽然譬如说线程主动让出CPU时间、强制刷新寄存器、新变量计算导致缓存刷新等因素可能会触发主存同步，但时间点不能确定，更何况算法的初衷是尽量不给Mutator更多压力，所以扩展这种情况到一般，算法认为包括本地缓冲区（CPU缓冲区）在内的非工作内存区都是不可追踪的）。
2. 同步的开销很大：很多系统都提供了信号量或其他同步设备支持，但这些操作的系统调用操作代价往往很大，算法会尽可能避免。
3. 资源是无限性的：资源本身认为是无界的，也就是说堆的大小不会因为算法本身的局限性被限制在某个范围内，相反它可能会无限增长，所以算法必须能够在这种情况下正常工作且工作良好，保证正确性和效率。
基于以上前提条件，算法把Mutator的工作细分为如下几种：
1. move：把基本数据类型变量或指针从主存/寄存器中移动到寄存器/主存中。
2. load：直接从寄存器/本地内存中读取一个变量而不经过堆。
3. reserve：在主存中申请一块内存空间。
4. create：直接在申请的独享内存空间中创建一个对象，在合适的时候同步回主存。
5. fill：填充对象或非对象的一个域，并在合适的时候同步回主存中。
6. update：更新主存中的一个字段值（位置未知）
7. cooperate：和Collector进行必要的合作。
8. mark：标记一个对象，对这个对象的引用可能在主存或和寄存器中。
算法把“在堆中分配一个对象”操作看成是由（reserve、create和fill）共同组成的，reserve操作的性能可能很低，因为主存是多线程共享单位，要划分出一块空间需要使用同步（假设不使用线程私有内存），而fill和create操作则可根据需要在不定时间刷新缓存或批量同步回主存。
而fill和update行为发生的前提条件不同，发生的频率也不相同。但他们的本质都差不多，即最终更新主存的一个字或多个字。设update更新的值依然是该Mutator私有的，则发生fill时可能会发生主存同步-多线程可见，所以相比之下fill更难于实现。
这里cooperate和mark操作是回收过程中不可避免的动作，若回收行为发生，则意味着mutator必须配合完成前期的三色不变式维护，后期的同步更新等等。算法的高效和合理性也表现在它不会让mutator做更多与之本职工作不相关的工作。如：
1. 在Mutator的经常行为中（move、load、reserve、fill）均不会有额外工作。
2. 只有在reserve操作中会有一些额外的工作来维护三色不变式。
3. 只有在mutator空闲时才执行cooperate和mark。
4. cooperate和mark操作会在一次回收过程中仅执行固定数量，而这一轮回收工作的上限标志则是标记工作完事。
5. 回收工作的展开和进行和堆的增长不存在必然联系，但当前堆的大小和游离垃圾的多少确实决定了Collector（以后用C表示，Mutator用M）的工作量，呵呵。
总结一下，上面提到的情况中，条件1是很高效的，条件2的同步条件决定了它对mutator的影响比较缓和，几乎没有额外的开销。条件3说明M要在合适的条件下帮助C完成一部分工作，条件4同时限制了C和M的工作量。算法中C是单线程方式执行，所以它的性能和以STW方式执行的单线程算法具有一定的可比性。但话说回来，现在机器的内存都比较大，CPU核心数量很多，C若仅利用单核心虽然有好的一方面，但大堆情况下它可能也力不从心，所以算法也需根据实际情况进行改进。C的具体工作包括：标记、反标记和回收。
简单的三色不变式回顾：
白色：对象没有被标记过，它的可达性未知。
黑色：对象和他的所有儿子都已经完成标记。
灰色：自己被标记完成，但是儿子们还没有被标记完成。
全局性的空闲列表：由于是标记清除算法，所以堆中的可用区域块必须使用合理数据结构管理，这里堆的可用空间按虚拟地址由低到高，空间由小到大以数组+红黑树方式挂在M共享空间中，空间的回收、分配都遵循伙伴算法等，关于此数据结构，这里不做具体说明，但需要说明的是，空闲列表总是以常数对数时间复杂度完成工作。
回收阶段说明：回收器的回收周期被划分成4个阶段，他们分别是：
1. 标记：把堆中的对象拓扑做可达性分析。
2. 扫描：把灰色对象取出对其子代进行递归再标记，保证所有存活对象均被记录在案。
3. 回收全部白色对象。
4. 翻转全局旗标，为下一轮回收做好准备。
算法要遵循的不变式有：
1. 在标记阶段，白色对象能且只能从白色或灰色对象可达。
2. 在回收阶段，不存在指向白色对象的黑色或灰色对象。
算法的垃圾回收率会受制于浮动垃圾，在第N轮回收工作完成后，一部分浮动垃圾由于并发维护三色式的代价将不会被甄别回收，而他们只有在N+1轮才能完成回收，而这一轮同时也存在相同问题。
具体的回收过程概要说明：
1. 标记阶段：标记阶段由于本地内存和寄存器的不可追踪性，必须要求Mutator配合一定的工作才能完成。而强制Mutator使用重量级屏障在算法中不允许。这里采用软握手机制完成M和C的同步过程。具体为C发起新一轮标记，设置全局旗标，当M在某次执行时观察到旗标的变化，它开始标记自己调用栈中的所有直接引用对象，标记完成后它将回复C自己完成标记及状态变迁。但描述中存在两个不能忽略的问题：
1) 单M下的对象丢失问题：假设堆中的对象拓扑为：
in T1’s register
a) C发起根标记请求，随后等待M状态回复
b) T1把自己的唯一根A着为灰色
T1回复C的请求
T1把B加载到Register中，打断指针A->B
T1随后释放CPU资源
c) C发现全部M都回复了它的请求
C把对象B挂在回空闲链表。
这一轮回收过程结束。
d) T2申请内存，B所在空间随即被分配给T2并由它更改。
e) T1重新得到CPU时间开始操作B，但其内部数据结构已经被T2更改，出错。
同理在分配新对象过程中也存在这个问题，这里不在赘述。解决这个标记丢失问题的方式是在对指针更新时或在创建新对象时马上标记对象是可达的从而维护三色式的不变性。但是在基础算法中，标记旧对象是不必要的，若标记它，则意味着更多的浮动垃圾在本轮中得以幸存，但不标记吧，也不应该有同步策略导致其最终丢失，而且大部分情况下大多数不会逃逸出方法的对象会很快死亡也不会再这个区间分配（都是栈直接引用对象）。
2. 多Mutator情况下的对象丢失问题：
该问题表现在旧对象在多线程情况下一直都不能确定自己的“旧对象”到底是谁，因为它的旧对象随时可能被其他线程重写。
a) C发起根标记请求。
b) T1把根A涂成灰色
T1回复了C的请求
T1把B加载到寄存器中，同时打断A->B。由于B是旧对象，B被涂成灰色。
T1失去CPU时间。
c) T2把A涂成灰色，T2回复C的请求。T2增加A->C的指针，同时把B（已经是灰色）涂成灰色，把C涂成灰色，清空自己的寄存器。
d) C发现全部M都回复了它的软握手请求，它扫描并回收垃圾，这一轮回收完成。
e) C发起新一轮的标记工作。
f) T2开始运行，把A涂成灰色。T2回复C的请求，T2把C放入自己的寄存器中。T2失去CPU。
g) T1恢复执行，T1设置A->null，（旧对象在上一轮回收中已经被着色）。T1把A涂成灰色，T1回复C。
h) C回收了C节点，但C现在依然在T2的寄存器中，程序出错。
问题产生的原因是跨越两轮回收寄存器中还存有旧对象的引用引起T1不能判定自己的旧对象究竟是谁导致的对象丢失。为了避免这个问题应该在一轮回收完成后马上加一次软握手强制M刷新自己的寄存器。若正确完成了以上两点，并发扫描配以合适的写屏障可保证标记阶段不出现标记遗漏。
扫描阶段：
结合标记阶段提供的写屏障保障，扫描阶段会不断的找到灰色对象并继续向下标记直到再也找不到灰色对象为止。此过程依赖于M的写屏障引入的三色不变式保证（这里特别说一下关于屏障的选择：算法是逐步由Dijikastra屏障衍化而来，而算法本身注重效率，所以相比那些通过波面回退维护三色式的算法来说，它的效率更高，但精确性难以保证）。
关于结束扫描的过程：
基本算法会有一个很明显的效率问题：C可能要来回不停的扫描很多次堆才能最终确定灰色对象没有遗漏。最坏的情况下一个灰色对象诞生就会引来一次完整的堆扫描，假设堆的大小为N，则最坏情况要扫描N^2次。这里算法使用一个数据缓冲区结构缓存灰色对象，只要缓冲区不空，则C不需要在堆中继续寻找灰色对象。这里使用一个全局旗标dirty表示堆中是否还存在灰色对象，该变量总是被Mutator设置外true而被C更改为false，该变量具有严格的读写顺序性和一致性，大多数情况下，算法只要扫描堆1~2次可确定没有标记遗漏。下面一个问题引起灰色对象没有继续扫描就发生回收导致对象丢失：
初始状态下dirty = false，缓冲区此时也是空，以下流程发生：
A把圆圈加载到缓冲区中并把圆圈涂成灰色
C把方块涂成黑色，扫描工作完成。
A把dirty设置为true（但是太晚了）
A把方块指向圆圈的指针打断，
C得到三角，而三角则错误的被回收。
上面问题具体看代码如何避免。
回收阶段：回收是swept指针从头部向后顺序移动找到空闲空间并把他们挂回空闲链表的过程。为了不在此过程中产生过多的竞争，对已经是白色对象的对象将着以新的颜色来区分这次回收的和上次回收的对象集合。而最终两个空闲链表会发生合并操作完成区域整合。上面简单介绍了各阶段及所完成的工作，下面结合伪代码具体说明每个过程的细节。
1. 状态变量说明：
sync1：C和M之间发生第一次同步。
sync2：C和M之间发生第二次同步。
swept：已经扫描完的区域指针。
scanned：扫描完成的区域指针。
async：表示C和M之间已经不需要相互同步，他们的行为互不干扰（但可能屏障依然有效）。
2. 行为说明：初始情况下swept = -无穷，scanned=-无穷，dirty=false，state=async。此时C发现内存占用率不小于回收阈值，发起回收。
C发起软握手请求：
handshake(sync1) {
statusC = sync1;//C的状态变迁为sync1
for(Mutator in AllMutatorCollections) { //迭代所有M等待其状态变迁为sync1
wait while mutator.status != statusC
}
curPhase = sync1;//全部变迁完成后整个状态机状态变迁为sync1
…
mutator行为：
create(node) { //创建新对象方法
if(statusM!=asnyc || pos(node) < swept) { //若当前M的状态不是async，或者清理
color(node) = white; //工作已经完成，则直接分配白色对象
return node;
}
…
cooperate() { //该屏障加载在创建，修改指针和访问对象之前
if(statusM != statusC) { //如果M和C的状态不一致，则M发生状态转换
statusM = statusC; //该指令将导致M下所有本地内存和寄存器被刷回主存
} //从而保证了上面提到的标记陷阱被提前触发
…
当C收集到了足够的M响应之后（在特定位置上挂起（安全点）的线程的本地缓冲区和寄存器被认为已经刷新），将进入到下一个阶段。注意第一阶段的存在意义仅仅是为了握手刷新缓存，M依然分配白色对象。
C发起标记阶段的初始化，首先把swept变量设置为负无穷标志着这一阶段的开始，然后开启sync2阶段握手：
M合作代码：
cooperate() {
if(statusM != statusC) {
if(statusM == Sync2) { //async2阶段M要开启根标记，标记完成后才发生状
for(x in Stack) { //态变迁。
if(isPointer(x) == true) {
markGray(x) //把自己的直接引用对象涂成灰色。
}
}
}
statusM = statusC //自己的状态发生变迁
…
create(node) { //M创建对象的过程没有变化，这可以最大限度的减少浮动垃圾
…
update(x, i, y) { //更新指针，前面分析过寄存器导致的缓存对象丢失，而解决办法是
if(statusM != Async) { //在新旧对象中分别着色，而屏障则是以Dijkastra方式运行
markGray(heapObj[x, i]); //屏障的粒度虽大，但是扫描的压力减小
markGray(y);
}
heapObj[x, i] = y;
…
由于cooperate总是先发生，而且刷新寄存器，所以更新屏障操作会无缝生效。
当C收到了足够的反馈，回收进入下一个阶段：
handshake(async)，此阶段意味着C和M之间的同步工作已经结束，M只保留很小的屏障开销维护三色式的正确性和C配合完成标记和回收工作就行。
M的行为：
cooperate() {
statusM = statusC; //状态直接发生变化，刷新寄存器中的值
…
create(node) {
color(node) = BLACK //新对象无论在哪分配的（栈中，静态全局变量中指向等等）
//都不可能再被回收，从这一刻起，赋值器变成黑色
…
update(x, i, y) {
if(swept == 负无穷) { //若清扫阶段还未开始
markAndWarn(heapObj[x, i]); //标记旧对象并设置dirty标志位给C提示
}
heapObj[x , i] = y; //y对象已经不需要再标记了，因为C一定会扫描到它，如果
//这个阶段分配的新对象，则它一定是黑色的
…
markAndWarn(x) { //这里若是扫描阶段发生ditry = true，那么旧对象一定是scan之前
if(color(x) != BLACK) { //被从父节点解除指向，然后进行一系列后续操作前必然
markGray(x); //把dirty=true同步回主存，这些操作都发生在dirty=true之后，
if(x <= scanned) { //所以要么旧对象已被C发现，要么dirty=true对于C是可
dirty = true; //见的且扫描阶段一定尚未结束。因为打断指针操作总是发
} //生在dirty=true之后，而markGray又发生在他们俩操作之前。
}
…
C的标记工作：C的标记工作按深度优先顺序完成（不移动对象搜索主要看额外数据结构开销）：
trace(node) { //标记过程起源于顺序扫描遇到的第一个灰色节点，算法总是以深度优先
markBlack(node); //的顺序对子节点进行迭代并标记，若一个节点被扫描完成，
while(isEmpty(cache) == false) { //意味着所有这个节点的可达树被分析完毕，之后
child = removeHead(cache); //scan指针+1既可继续扫描下一个节点。
markBlack(child);
}
…
markBlack(node) { //把该节点标记为黑色
if(color(node) != BLACK) { //若它不是黑色，则有必要标记它和它的儿子们
if(size(cache) < MAX_CACHE) { //若缓存没有溢出
color(node) = BLACK; //则标记它并把它加入标记队列，意味着儿子们灰
cache.addTail(node);
}else { //如果缓存已经溢出，则必须清空缓存后在扫描
color(node)=GRAY; //这里标记为灰色为下一轮扫描做准备
if(pos(node) < scanned) {
dirty = true;
}
}
}
…
清扫阶段：这是算法的最后一个阶段，设置swept=0标志这一阶段的开始，由于清扫阶段开始，赋值器对象不可能再被回收，而新对象只能分配在已标记的堆的后面，所以这个阶段赋值器屏障全面失效，是真正的async阶段。
C的工作流程：
swept = 0;
while(swept < heapEnd) { //顺序扫描堆
if(color(heapObj[swept]) == BLACK or GRAY) { //若标记发生在本轮，则它在单独的
color(heapObj[swept]) = WHITE; //空闲链表中单独记录，为的是不影响现有对
}else if(color(heapObj[swept] == WHITE) { //象分配效率
color(heapObj[swept]) = BLUE; //对于已经是旧对象来说，为加以区分，它被
} //着为蓝色
addWhiteToFreeList(heapObj[swept]);
swept += 1word;
}
swept = 正无穷; //标记位被重置为正无穷，标志着这一轮回收工作完成
…
由于篇幅限制，不对空闲链表的具体数据结构和合并过程进一步说明，下面直接给出M和C的工作完整代码：
Mutator：下面是两个Mutator的标记行为，markGray在扫描阶段之前被使用，另外一个作用是保证并发扫描过程中不会发生对象丢失。
markGray(node) {
if(color(node) == WHITE) {
color(node) = GRAY;
}
}
markAndWarn(node) {
if(color(node) != BLACK) {
markGray(node);
if(pos(node) <= scanned) {
dirty = true;
}
}
}
下面是mutator要执行的合作行为合并代码
cooperate() { //当前Mutator线程
if(curMut.statusM != statusC) {
if(statucC == sync2) {
for(stackElement : Stacks) {
markGray(stackElement);
}
}
}
curMut.statusM = statusC;
}
下面是分配对象可用空间的代码：
reserve(space) { //lock protection
while(freeList.hasEnoughSpace(space) == false) {
await;
}
return freeList.allocate(space); //lock released
}
下面是创建对象的屏障代码：
create(node) {
color(node) = BLACK;
if(curMut.statusM != async || pos(node) < swept) {
color(node) = WHITE;
}else if(pos(node) == swept) {
color(node) = GRAY;
}
return node;
}
更新对象指针的屏障代码：
update(node , i, newNode) {
if(curMut.statusM != async) {
markGray(heapObj[node, i]);
markGray(newNode);
}else if(swept == 负无穷) {
markAndWarn(heap[node, i]);
}
heap[node,i]=newNode;
}
标记灰色对象：
trace(node) {
markBlack(node);
while(isEmpty(cache) == false) {
node = cache.removeHead();
for(pointer : node.pointers) {
markBlack(pointer);
}
}
}
软握手等待过程：
handshake(state) {
statusC=s;
for(mutator : mutaturCollection) {
outer:
if(mutator.StatusM != statusC) {
await outer;
}
}
curPhase = s;
}
把对象标记为黑色：
markBlack(node) {
if(color(node) != BLACK) {
color(node) = BLACK;
addToCache(node);
}else{
color(node) = GRAY;
if(pos(node) < scanned) {
dirty = true;
}
}
}
collector在整个回收阶段的总体工作流程：
Clear阶段：handShake(sync1);
mark阶段：swept = 负无穷;
开启软握手流程：
handshake(sync2);
handshake(async);
软握手过程结束：
for(rootDirect : globalVariables) {
trace(rootDirect);
}
Scan阶段：
do{
dirty = false;
scanned = 0;
while(scanned < HEAP_END) {
if(color(obj(scanned)) == GRAY) {
trace(scanned);
}
scanned+=1;
}
scanned = 负无穷;
} while(dirty == true);
swept阶段：
swept = 0;
while(swept < HEAPEND) {
if(color(obj(swept)) == BLACK || GRAY) {
color(obj(swept)) = WHITE;
}else if(color(obj(swept)) == WHITE) {
color(obj(swept)) = BLUE;
}
freeList.addWhiteObj(obj(swept));
swept += 1;
}
swept = 正无穷;
下面给出变量statusM、statusC、swept、scanned和dirty变量的阶段变迁时序图：
由于Mutator和collector的感知延时性，每个阶段和三个状态（async，sync1，sync2）并不是完全对应的，但实际状态已变更，在整个回收过程中，算法只在对象头部设置能容纳四个状态的（白色、灰色、黑色、蓝色）标志位即可（2个bit），不需要额外的空间（比如说位图等）辅佐完成回收过程，所以堆的利用率比较高，若程序符合分代假说，则算法可作为old区的回收算法存在，那么若碎片率过高则必须辅以合适的整理算法，另外其单CPU使用的特性虽然整体对Mutator的工作冲击不大，但是效率也不很高，还有提高的空间。
并发、增量、并行堆压缩算法
前面介绍的算法对mutator影响很小，但是它以单线程执行所有工作且不能移动对象，适合于对象总量不太大的情况，当堆太大，算法显得有些力不从心。要维护堆的结构同时需要维护额外的数据结构来描述堆中存活对象之间的可用空间。并且当遇到大对象分配这样的问题，在堆中碎片非常多的情况下甚至无法完成。该压缩算法是一个基本没有入侵的并行、并发整理算法，能够解决此类问题。算法的最终目标是把堆中分散对象整理成为一个空间紧凑的连续对象集合，而且能够尽量保证对象之间的局部性，而且对mutator的影响整体不大，在遇到大内存多CPU核心的环境时，它的性能比较好。它的压缩过程仅需要一次堆遍历即可完成，高效。算法能够在一个要不断对用户输入进行响应，不断产生新垃圾的巨大堆系统中运行良好。算法的非入侵性是指回收工作运行在单独的回收线程中，它们和Mutator并发运行，虽然它们会占用一些系统资源，但大部分资源依然由mutator掌控管理。
首先算法是以增量方式工作的（压缩工作逐步向前推进，由mutator在特定的操作中织入屏障完成一部分回收工作），并行的（数据压缩过程可以由多个Collector线程以很小的同步代价并行完成），并发的（mutator和collector线程们一起运行）。算法把堆压缩成一个连续空间的同时能尽量保证一部分对象的空间局部性不发生改变，这个局部性取决于物理内存和虚拟内存映射关系。算法使用额外的数据结构保证仅对堆进行单次遍历就能完成压缩（减少随机寻址的性能消耗）。
应用的技术：
为达到并发整理的目的，算法需要应用到操作系统的页保护机制，每次访问对象时mutator都假设对象已经发生移动，若实际情况对象还没有移动，则会触发一个陷阱来先进行对象移动，这个不变性贯穿算法始终。
术语、数据结构及虚拟内存操作：
系统首先会初始化两套大小相同的虚拟地址空间，每一组空间的大小都和堆能达到的最大值保持一致。这两组虚拟地址并不总是和物理地址保持映射关系，同一时刻，可能只有真正容纳对象的虚拟地址空间和物理地址保持映射关系而其他虚拟地址则处于unmap状态。每次进行整理时，算法都会把对象从一个空间复制到另外一个。此时两个空间分别叫做原空间和目标空间。当完成一轮移动之后，原空间和目标空间的角色发生互换，为下一次回收做准备。
在复制过程中需要用到4种数据结构。在标记阶段，一个以字为对象对齐方式的位图被用来记录存活对象。向量中每个对象都至少占用2个字的空间，所以向量中使用一个字表示对象的内存起始位置，另外一个表示对象的尾部位置。偏移向量：算法把原空间分割成块，块的大小固定为512字节（小于一般的虚拟内存分页大小：4KB）。对于每一个原空间块，在偏移向量中都有唯一的槽位与之对应表示该块中第一个存活对象（地址从小到大排布）在目标空间中的位置。最后，算法使用两个小一点的表，一个叫做首对象向量，另外一个叫状态向量。首对象向量以操作系统的虚拟页为单位记录移动到该页面的第一个原空间对象地址。状态向量也以页为单位记录了目标空间虚拟页状态，该向量的元素是线程能够独立操作的最小数据结构，它需要能够表示4种状态且内存空间连续。以上几种数据结构的例子如下图：
算法借助于操作系统的页映射机制完成对象压缩，具体可以分为如下几种操作：
Map：把一个物理页和虚拟页进行连接。
Unamp：把物理页和虚拟页解除连接。物理页还给操作系统。
PortN：对特定N个虚拟页面进行写保护。防止其被其他线程占用。
Unport：把一个虚拟页解除写保护。
Trap：在一个已经被保护的虚拟页中执行一系列操作。
DoubleMap：把一个物理页面同时映射给多个虚拟页面（这里是俩）
当mutator触发陷阱时，DoubleMap功能被启用。当mutator还在使用被保护页面时，压缩程序会直接使用一个二级虚拟视图完成该页对象操作。
具体操作的伪代码说明：
1. 获取一个原空间内存地址的目标空间地址：
getTargetSpaceAddress(oldAddress) {
blockNumber = getOrgBlockNumber(oldAddress);//使用位运算利用起始地址和每块
//长度计算块的逻辑编号。
blockAddress = getOrgBlockAddress(oldAddress);//根据位运行（抹掉后几位）得到块
//起始地址
offsetInBlock = getTotcalLiveData(blockAddress,oldAddress);//根据此块中该对象前所
//有对象压缩完成后的长度偏移量计算出该对象的相对位置
newAddress = toVirSpaceAddr + offsetVector[blockNumber]+offsetInBlock;//根据偏移
//量向量和to空间首地址和该对象块内相对偏移位置得到压缩后的目标空间地址
}
上面方法通过简单的数学计算和向量查找完成对象的目标空间计算，由于位图向量和偏移量向量在标记阶段就计算完成，所以该方法实际不需要再次访问堆，仅遍历各向量即可，而向量由于结构紧凑对于CPU缓冲区极具友好性，所以计算速度非常快，没有竞争发生，所以对于合理划分了工作区间的C线程可以高效并行计算。
2. 把旧对象移动到新页中：
handleMoveToPage(pageNumber) {
pageAddr = getPageAddr(pageNumber);//首地址+pageNumber*4KB
map(pageAddress,PAGE_SIZE);//发生物理虚拟地址映射，借助操作系统函数完成
firstObjAddr=firstObject[pageNumber];//应该移动到此页面的第一个对象
lastObjAddr=firstObject[pageNumber+1];//应移动到此页面的最后一个对象
org=firstObjAddr;
to=getTargetSpaceAddress(org);//得到该对象的新地址
while(org<lastObjAddr){
fixReference(org); //先更新指针，目标空间指针的计算根据上面方法得到
copy(org,to); //把对象拷贝到目标空间
to=to+sizeof(org);
org=getNextObject(org);
}
unmap(firstObj, Addr, lastObjAddr - firstObjAddr);//释放一个页映射还给操作系统
}
更新指针的过程是找到引用对象目标空间地址的过程和getNewAddr过程一致。算法可以以STW方式运行，也可以以增量并发方式运行，这里分别介绍两个版本：
1. 并行的STW方式运行的压缩过程
移动的过程中对象在原空间的顺序被保留（以目标空间页为单位），所以要移动到目标空间对象的新地址是前面已经移动的对象大小的总和+To空间起始地址。如前图所描述，每一个目标空间地址都能通过计算前面对象的地址总和的方式得到，而偏移向量的作用仅仅是加快这个进程，否则越后面的对象的计算压力越大。而偏移向量的作用仅仅是加快这个进程而已。另外由于向量本质上是数组，它的CPU缓冲区友好性决定了在扫描位图并计算对象相对位置时效率非常高（位图也不会变化），同时定位数组元素操作的时间复杂度可近似认为是常数，所以计算速度非常快也没有多线程竞争问题，最重要的是，随机寻址问题被解决，因为计算根本不需要触碰堆本身。
计算的第二步是以目标空间虚拟页为单位界定源空间要移动的对象范围的过程。此过程借助于首对象向量完成，首对象向量两个槽位内存地址之差正好就是原空间内存的移动范围，所以计算常亮时间就完成了。
压缩过程的开始是先进行可达性分析根扫描确定存活对象范围，根节点的范围包括了线程栈、JNI区域、方法区引用（若分代了的话还包括已经完成扫描的年轻代指向老年代对象的指针集合）。而这些部分则可以合理划分移动粒度使用多线程以负载均衡的方式（竞争得到待扫描区间）并发完成。扫描工作结束意味着位图向量构建完毕，但需要注意的是位图以多C方式构建，所以对于每一个byte都存在并发修改的可能，所以必须加锁保证完整性，若要避免加锁则需要使用以空间换时间方式把位图扩展为字节图，这样空间将是原来8倍。之后的工作是以单页或多页为单位把目标空间（首对象向量）合理划分给线程完成并行移动，若以单位页为粒度划分工作，可能带来比较激烈的竞争（单页实在太小了），若以多页为单位则不利于负载均衡，而这又是和堆中对象分布情况相关的，所以比较麻烦。若要知道一个页面内的对象是否都移动完成，状态表可以以原子更新方式被更新反映当前页的状态并作为线程选取下一个待移动目标空间页指示器。状态表状态：
UNHANLED：页面没有发生对象移动。
BUSY：页面正在被线程操作。
HANDLED：页面已经完成对象移动。
除了CPU核心数量会影响线程数量之外，另外一个要考虑的问题是当前剩余物理内存的多少也同样影响着性能，若物理内存不足导致不得不使用磁盘作为交换空间的话，性能自然下降。
一个多C下STW版算法的伪代码：
parallelSTWCompact1() {
stopAllMutatorThreads(); //在安全点挂起所有mutator
calculateWholeVectors(); //标记并计算所有向量
for(root:rootCollection) {
getTargetSpaceAddress(root); //逐一翻转根节点指向
}
}
parallelSTWCompact2() {
pageC = getNextUnhandledPageChunk(); //扫描首对象向量（多线程同步竞争）
while(pageC != null) {
handleMoveToPage(pageC); //根据向量计算目标地址并fix指针
pageC = getNextUnhandledPageChunk();
}
}
2. 并发的、增量式、并行回收器
并发标记过程这里略去不表（后面算法中会具体说明一种可行方案），偏移向量和首对象向量是可以在mutator保持运行太下C计算得到的。第二，移动对象和更新指针两步操作也可以并发完成。在移动根节点到目标空间之前，两个向量必须先被计算出来，计算过程是每当有新对象发生分配，mutator都会承担一部分计算工作，同时运行的多个C也会以并发方式对每个块进行计算，计算过程仅仅是根据偏移向量做纯数学计算而不需要触碰堆本身。因为标记阶段已经结束，为了维护三色不变式，新对象在标记结束后只能在目标虚拟地址中分配。换句话说赋值器只能分配黑色对象。一个问题是新分配在目标空间中的对象指针还一定指向原空间，所以这部分区间中的对象必须统一进行指针翻转。当所有向量都已经计算完成，标记阶段就已经完事了，移动工作开始。由于移动工作的主体是没有发生映射关系的目标空间页，所以必须在多线程获取工作页或页组之前调用系统函数把这些虚拟地址加以保护以防其他进程抢占。同时为了保证一致性，写屏障也会同步加入进来让mutator参与到移动工作中去。C首先会在全局安全点上挂起全部mutator来完成根指针的翻转。当前部指针都已经得到翻转，此时意味着mutator只能访问目标空间对象，而原空间此时还处在和物理内存的映射状态中，假设每一个mutator都在访问不同的目标空间虚拟页，数量为M，而同时有N个C在尝试在其他目标空间移动对象，则必须存在未使用的物理内存页面数量>=(N +M)，否则被映射到磁盘不能避免，这会影响算法效率。但之后随着有更多的From空间页被释放出来，可用物理内存也可能会随之增多，这是因为压缩后的内存占用率一般小于之前（这里不考虑其他进程竞争的情况）。
陷阱的触发：当mutator被唤醒，意味着它的根翻转已经完成，此时必须给它无缝织入一个读屏障，当它读取一个原空间对象时，屏障会检查该指针的指向空间，若原空间，则通过向量计算得到该指针的目标空间所在目标页，该线程必须完成该页的所有对象移动工作后屏障才能结束。若发现此页面处于BUSY状态，则它必须等待该页状态改变为HANLDED才能继续工作。热点对象的移动通常会导致大量mutator一直轮询检查状态向量的某一个页标志位，而最坏情况下所有个mutator等待一个页的移动页是有可能的，从这一点看算法的性能不稳定，而且若移动的粒度过大，也意味着给mutator加入了一个很重的负担，这必然影响mutator的执行效率。另外一点是在标记期后分配的新对象陷阱的工作是更新他们指针，因为他们就是在to空间分配，在执行陷阱过程中，mutator只能通过双重映射方式的内存函数访问受保护页，而第二个虚拟页面被陷阱使用读写目标空间受保护页。
一个mutator触发陷阱的例子：
图中对象3由于空间限制没有办法在单个页中完成分配，这种情况下只复制对象的前半部分，而后半部分在另外一个页中复制来完成一个整体复制过程。
两种陷阱整合后的伪代码：
trapRoutine(address) {
page = getPageNumber(address); //得到对象的目标空间所属页
oldStatus = compareAndSwap(statusTable[page], UNHANLDED, BUSY);
if(oldStatus == UNHANLDED) {
if(isUpdatePointer(page)) {
fixPointer(page);
}else {
moveToVirtualPage(page);
}
unprotect(page);
set(statusTable[page], HANDLED); //安全状态更新
}else if(oldStatus == BUSY) {
while(test(statusTable[page]) != HANLDED) {
wait and loop again;
}
}
}
并发压缩伪代码：
void concurrentCompact() {
1. M和C以并发方式共同计算偏移向量和首对象向量
2. 把全部目标空间虚拟页保护起来
3. 在全局安全点挂起所有mutator，更新其栈指针（还包括JNI、常量区等）
4. 在mutator中织入读屏障
5. 恢复所有mutator的执行
pageC = getNextUnhandledPageChunk();
while(pageC != null) {
handleMoveToPage(pageC);
pageC =getNextUnhandledPageChunk();
}
翻转两个区间，回收工作结束
}
密集存活对象块的处理
算法以块作为计算对象移动后位置的向量最小单位，这样既不会使向量占用空间过大，又能很好的平衡计算的工作量。当某一个块中存在密集的或单一大长寿对象时，它/它们通常是经历了很多次移动但一直存活然后最终会聚集到逻辑相连的区域中。对于此类块最好的做法是像MC2那样把他们当做一个整体并在做偏移向量计算时通过位图向量识别出他们然后向槽中写入特殊值来标识它/它们可以被整体移动，这样可以减少计算量加快移动效率。当它们聚集量达到一个Page时，则仅改变它们的虚拟页映射并更新指针就完了，根本不需要再移动。
算法在翻转根指针时还需要STW来停止所有mutator避免在移动原空间页时其他mutator对其中对象做的修改，而这个STW时间取决于不同线程栈深度总和。而且在移动过程中，划分线程工作的最小单元的粒度决定了屏障的负担，若太大或者其中存活对象太多，也同样会影响mutator运行，而且热点对象会阻塞多个mutator同时访问相同的目标页对象。所以在最坏情况下算法的效率会很低，因为竞争太多。在大内存中若以4KB作为线程移动对象的最小单元确实太小了，而加大这个值也同时能减少状态向量和首对象向量的空间需求。算法用8倍于pageSize的大小作为线程移动的基本单元。
Shapphire
该算法是一种并行并发半区复制算法，算法适用于大量线程，多CPU核心，中等或小内存环境中。每轮回收过程中mutator要同时更新新旧两个区间的对象（一个对象本身，另外一个是它的副本），然后每次以增量方式仅翻转一根线程（让线程指针指向新半区对象），算法完全避免了使用读屏障。由于是半区复制算法，所以它比较适合于分代回收系统中的年轻代。
内存区域定义：
内存根据功能性的不同被划分成很多区域，有些区域仅包含指向其他对象的槽位和基本类型数据，有些仅包含对象。算法首先定义若一个内存地址是指针，那么它能够被准确无误的判断出，也就是说算法工作在准确型GC中。具体分区：
U：该区域分布在堆中，其由所有mutator线程共享，此区域中的对象不在回收的范围内。主要包含Class对象和常量池引用等。
C：该区域分布在堆中，其由所有mutator线程共享，此区域中的内容是回收的主体，具体把它细分为两个区间：
O：旧区间，当回收工作开始后，待回收对象都分布在此区间中。
N：新区间，回收开始后存活对象的目标区间。
S：指的是栈，是线程方法调用链的追溯，它是线程独享区域，私有于线程。其中存在的全部都是槽位，没有对象。这些槽位中或者存储的是数据，或者是指向U或O空间的指针（回收之前），S具体包括了：线程栈，寄存器和JNI部分。
需要注意的是，若堆中做了分区并且算法工作在年轻代，那么老年代指向年轻代的引用（可能是卡表）也作为扫描但不回收的一部分，这部分区间若存在则应该归属为U中。一个例子：
算法分步说明：
算法主要分成两个部分，第一部分markAndCopy，目的是把从U和S空间中存活对象进行可达性标记，这个过程mutator只负责更新O区间的对象。标记完成后在N区间建立存活对象副本。若过程中mutator修改了O区间对象属性，N区副本和O区对象之间会保持一个弱同步状态，在两次同步点之间发生的O区属性更新都会在第二次同步之前穿插到N副本中。关于这一点是利用了java虚拟机中的内存同步规则。具体来说，在更新两个副本的过程中并不要求原子和同步完成。如果所有的mutator都处于同步点之中，在回收阶段若mutator感知到O和N两个副本时，同步会由mutator中织入的屏障完成。其他情况算法提供了特殊处理方式，后面具体说明。
第二个过程是翻转：把U和S区间中的指针槽位翻转为仅指向N空间。这个过程中算法在mutator中追加写入屏障完成。由于翻转过程mutator被逐一挂起，所以算法允许还没有发生翻转的线程同时更新O区对象和N区副本。另外有副本存在的对象在判断是否同一对象时（==）必须能够区分O区对象和N区，在java语意中若是同一对象则它们必须相等，尽管在算法回收的过程中它们分别指向不同区间的原体和副本。判断两个对象是否相等的情况有：
A) 和null相比，该操作不需要外的工作。
B) 它们指向不同的副本，地址相同或不同或任意一个是null。
pointer-equal(p, q) {
if(p == q) return true;
if(q == 0) return false;
if(p == 0) return false;
return flip-pointer-equal(p , q); //方法会调用一个屏障，把p和q指针翻转到一个空间
}
标记和复制过程：一个动态平衡的过程
这个过程细分为3个阶段：标记、分配和复制。这些过程最终可以被合并在一起完成，但是为了方便说明这里把它们拆开，最后在合并。
标记过程算法严格遵循三色不变式。算法规定完成对象本身及它的所有指针扫描后应当把它着为黑色（从标记队列中移除并设置标志位或向量）。灰色对象是完成标记但尚未完成扫描的对象。白色是未被标记的对象。而违反三色式的情况是黑色对象直接指向白色对象。算法规定S区中的槽位均为灰色，所以他们指向的对象颜色可以是任意的。这也暗示了S区指向对象在回收的前期阶段中不会产生游离垃圾（因为没有刻意标记），同时也意味着屏障不需要安装在S区直接指向的对象的操作方法中。但其他更新共享内存的操作（U区和C区对象）需要写屏障维护三色不变式。
标记过程的起点是所有对象都为白色，随着标记过程的深入，对象的颜色逐步转换成灰色，最后堆中仅剩下白色和黑色组成的对象集合，过程中可能由于指针更新导致以维护三色不变式的屏障被触发来对指针目标或源对象进行着色或褪色。但算法不允许黑色对象褪色成灰色，这就使得屏障粒度变粗。
标记阶段：
mark-phase-write(p , q) { //p和q属于U或O区
*p = q;
mark-write-barrier(q);
}
mark-write-barrier(q) { //当指针发生更新为了避免并发扫描下的标记对象丢失，mutator
if(old(q) && !marked(q)) { //将对指针指向的新对象进行更新，
enqueue-object(q); //把新对象加入到自己私有标记队列中
}
}
标记阶段可以进一步被细分成3个阶段：
1. preMark：在mutator中激活写屏障。
2.rootMark：标记非Stack区间的根集合。
2. Heap/Stack Mark：对全部存活对象进行再标记，完成最后的标记工作。
PreMark：激活mutator的写屏障，这一步当全部mutator都回复了C自己已经完成了写入屏障激活后阶段完成，标记进入下一个阶段，由于回复会触发一个线程缓冲区刷新，所以完成回复的线程此时不存在私有‘脏数据’。完成这一阶段之后的内存状态如图所示。
Mutator着色对象的方式时把它们直接放入自己的私有标记队列中，这暗示了它们的颜色是灰色，因为尚未完成子节点扫描。采用这种非直接标记方式的好处有：
1. Mutator没有把旧对象复制到目标区域的同步开销。
2. 本地队列将不会和全局队列产生竞争。
3. 当Collector需要此队列中的元素，只需要挂起这个mutator然后翻转一个旗标把私有队列挂在全局队列上即可，然后恢复mutator执行。
根标记阶段：该阶段将迭代所有U区间对象槽位，U区间直接指向的O区间对象C都会调用mark-write-barrier方法把它们加入到自己的私有标记队列中去。由于前一个阶段屏障已经织入到mutator中，所以虽然对U区间存在被M并发修改的可能，但也不会出现标记遗漏现象，因为若在C扫描到之前U -> O指针发生了改变，则虽然C没有能把它加入到自己的私有标记队列，但它一定存在于Mutator的队列中，待下一个队列迁移阶段该对象会正确得到扫描，同理若发生在之后，则它必然存在于C的私有标记队列中。一个问题是对于同一个可达对象来说，它的引用会同时出现在多个私有标记队列中，但它不会影响正确性。而这个过程中C工作的负载均衡可以通过多线程竞争固定大小的待扫描区间方式完成，也可以使用预先划分好的静态区间以无竞争方式完成。静态划分方式例子如下图所示：
堆/栈的标记过程：
过程中C工作在它自己的私有标记队列中（初始情况下是一组U中的灰色对象集合）和S区指针集合。C首先会根据自己队列中的灰色对象指针按逐步向下标记，而一旦完成某一个全部儿子们节点的入队，这个对象马上从灰色转换成黑色（转换方式可以通过位图向量反应出来也可以通过对象头部特定bit位）。这样当其他线程（指M和C）看到该对象的标志位后就不再重复扫描它和它的子孙。由于C完成这个工作也是通过mark-write-barrier完成的，此步骤完成的标志是所有C线程的私有标记队列中都为空。这种可以通过多C维护一个全局性的计数器反应当前完成自己标记工作的线程总数方式实现同步。每个线程完成自己工作后都更新这个计数器并不断轮询查看计数器的值直到全部线程都完成，回收工作进入下一个阶段。堆/栈的扫描工作首先需要完成线程栈的扫描，然后向下标记直到整个过程完成，但如果寄存器中存有还未同步的脏数据则标记过程将不准确，这里的做法是C会在特定的安全点上逐步挂起Mutator（脏数据会刷回主存），然后对其栈进行一次扫描，把指针都加入到C的私有标记队列中，然后把它的私有标记队列挂载到自己的私有标记队列中，然后恢复该线程的执行。Mutator恢复后，C会完成这部分数据树的扫描而工作。而在这个过程中，C依然有可能向其私有队列中添加新元素，而C则不得不周期性的挂起mutator继续对其栈和队列进行扫描直到某一次挂起后发现它的标记队列为空，为空标志着此时的mutator状态和C状态统一，C唯一要做的工作就是再次扫描它的栈找到指针，而加快这个过程的方法是在栈中也加入一个屏障，但当这个栈被释放，这些元素可能要从栈屏障队列中移除掉。当C再次仅扫描mutator栈完成后，一个写入屏障在mutator恢复执行前被织入，目的是此时此刻开始，mutator只能在目标空间分配新对象，换句话说，mutator在之后只能分配黑色对象，这样算法就完全维护了三色式的不变性。
在标记的3个阶段中，1、2阶段产生的S区直接引用对象由于栈帧的弹出（方法执行完毕）所带来的垃圾都不会被再次标记，而他们往往是垃圾的主要来源（理论上每次垃圾回收对象的存活率不到10%），只有第三个阶段完成之后Mutator才要求仅能分配黑色对象。而且使用本地队列的标记方式最大层度的减少了多线程之间的竞争的同步开销。而且根据CPU核心数量来确定并行C线程数量可以使用静态分派方式完成扫描区间的划分从而避免多线程进一步竞争，而对于M来说，每次挂起并不要求以STW方式完成且即便挂起，队列的移动，栈指针扫描工作都是可接受的。问题是采用静态分派的方式可能难以避免负载不均衡的情况，而采用类似Dijkastra的粗粒度屏障确实带来游离垃圾问题，而三阶段后的黑色赋值器也意味着从这一时间点开始到回收结束产生的垃圾均不能被回收。
分配和复制工作
标记工作的完成意味着这一轮存活对象的总数量已经确定，此时C的工作是在目标空间或晋升空间分配存活对象的副本。如果使用的是位图标记，那么它也可以使用前面所述的静态任务分派法进行多C负载均衡。但是分配内存肯定是要竞争的（不考虑线程本地堆）。
分配过程：C会遍历位图来确定存活对象的物理地址并把它们复制到目标空间中。当这个过程完成，一个转发指针会被写入到原空间对象头部。注意由于原空间中的对象依然在被使用，转发指针不能覆盖对象的原有域，它应该是一块新的独享区域，虽然给每个对象都分配一个这样的空间会降低堆的利用率。由于在复制过程中会遇到通过O区对象寻找N区副本或相反操作，一个反向HashMap用来做N空间指针查找。当整个回收过程完成之后，HashMap和位图都被释放。分配过程完成的标志是所有C都完成了属于自己那块内存区域的存活对象目标空间申请。
复制阶段：该阶段需要一个新的写入屏障，目的是为了维护两个空间对象的一致性。其实新屏障和C之间也有一个软握手的过程标志着阶段的开始。Pre-copy阶段将加入这个屏障，具体的代码为：
copy-write(p, f, q) {
p -> f = q; //普通的指针赋值操作
copy-write-barrier(p , f, q);
}
copy-write-barrier(p, f, q) {
if(forwarded(p)) { //如果p已经被转发，也就是p不在u空间，头部转发指针有值
pp = forward(p); //通过转发指针得到N区副本
qq = forward(q); //如果q是指针且在U区qq = q，如果q在O区则是它的转发地
//址，如果不是指针则qq = q
pp -> f = qq;
}
}
forward(p) {
return (forwarded(p) ? forwarding-address(p) : p);
}
该方法若在多线程情况下运行，则可能有如下问题发生：
线程T1和T2均修改对象O的字段f，T1：O -> f = A, T2：O -> f = B，则多线程的不确定性带来的结果可能有：
情况1：f=B，ff=B。情况2：f=A，ff=B。情况3：f=A，ff=B，情况4和情况3类似略去。注意只有情况1和2是原本和副本保持一致，3和4结果则不能确定，多个线程下可能还有意想不到的结果。但仔细分析后得出结论是问题的根源并不在于复制算法本身，由于多线程下原值本身就具有不确定性，而为了避免这种不确定性，一般来说需要给赋值部分加入同步块保护，而如果加了锁，那原体和副本都能保持一致。这本身没有什么问题，但是对于volatile字段来说，算法需要特别处理才能保证一致性，关于这一点后面会有细致的说明。C们会根据上一步操作中预分配的内存划分区间堆N区新对象进行以字为单位的数据复制，而新对象找到旧对象的过程就是访问hashMap的过程。因为此时旧对象和新对象都已经被mutator感知，而新的写入屏障会同时更新两个副本，所以C在复制过程中会和M发生写入竞争，而由于C应该总是以M的最后更新值为准，所以字的复制是以尝试方式完成，具体代码为：
copy-word(p, q) { //p指向原空间，q指向目标空间副本
i = max-cycles; //单子复制的最大尝试次数
do {
wo = *p; //原空间的值赋给wo
wn = forward(wo); //查找它的目标空间值，先的定位到转发指针上
*q = wn; //让指针q指向目标空间这个值的地址
if(*p == wo) //若两个区间的值相等，说明M已经执行了屏障且过程中无更改
return; //不需要C在进行复制它直接返回
}while(--i > 0) //若失败则说明更新行为发生，尝试的意义是为了在过程合并后（过程合并这里没提，后面会说明）保证正
//确性，也就是转发指针未感知时旧对象落后于新对象的情况
//因为第一次比较不一致可能意味着mutator没有感知到，而为了保证一致性，C必须完成一次值的同步，否则可能在复制接近尾声时两个值都不一样而mutator再也没有更新它
wn = *q; //新空间值的快照
wo = *p;
wn2 = forward(wo);
compare-and-swap(q, wn, wn2); //若失败说明mutator修改了这个值，没问题
}
算法假设多mutator更新非volatile修饰的值已经由程序使用锁保护，否则最后得到的值是什么天知道，关于这个代码片段的正确性讨论：
假设mutator赋值原空间和目标空间的行为写成mp和mq，
假设collector读取原值操作是rp，写目标空间值wq，再次读原空间值rp，那么当mutator和collector并发执行时（collector可能只有一个，而mutator可能有多个），可能的赋值排列组合如下表所示（一共10种）：
第一种：C先尝试设置新值成功，M完成新值设置成功，结果正确
第二种：C写入旧值，比较新旧2值不同，重试，而重试过程会变为10种情况之一
第三种：C写入旧值，M覆盖为新值，此时两个副本值统一，而在C最后一步比较失败，重试
第四种：C写入新值，旧值比较后无变化，最后退出，之后又被M更新，正确。
第五种：C写入旧值，m更新两个值，C发现失败，原子尝试
第六种：C写入旧值，比较后发现一致，然后M更新为正确的新值
第七种：C直接写入成功
第八种：C把副本更新为旧值，但之后比较失败，会重新尝试
第九种：和第八种一样的。
第十种：C就是返回但被M更新为新值，结果正确
以上10种情况中，为了避免C一直发现两个区间中的值不一致而一直在while循环中尝试，这里设置最大尝试次数来避免这样情况，但尝试依然是有必要的，这时为避免过程合并后C已经开始了单字拷贝而M还未感知到的情况发生。
区域翻转：
当全部存活对象都完成复制，一致性的维护依靠屏障，程序本身的同步机制，算法对volatile字段的一致性处理和锁复制（后面说明）。使O区和N区一直处于同步状态之后，就可以开始翻转所有指针到N区，需要翻转的指针分布在U和S区中，完成翻转后整个回收过程结束。翻转分为4个阶段：预翻转、堆翻转、线程翻转和翻转后处理。指针翻转过程的不变式遵循N区对象不会指向O区对象。预翻转过程是织入新的屏障过程，堆翻转翻转U区对象指针，线程翻转会翻转S区，翻转后处理是最后阶段。
预翻转：为了避免M和C并发修改U区指针导致已经翻转指针失效，这里织入新写屏障来统一规定mutator行为，屏障代码：
flip-write(p ,f , q) { //p对象可能分布在U，O，N，若q是指针，那么它也分布在U，O，N
p -> f = q; //原指针赋值
if(forwarded(p)) { //若p在U区，那后一步会翻转它，但写屏障必须保证它指向N区
//若HashMap中存在p，则它是N区对象，那为了维护不变式必须
//保证它指向也是N区对象。
//若它有转发指针，则它是O区对象，它也指向N区
pp = forward(p);
qq = q;
if(old(qq))
qq=forward(qq);
pp -> f = qq;
}
}
此时由于已经在没有反转的mutator中暴露出了N区对象，所以equals屏障也必须加进来（两个对象必须在一个空间）。
堆翻转：有了前一步屏障的保护，这一步过程其实就是C们分治不同U区域这导致多M和单C产生竞争，C顺序扫描U区中指针，找到指向O区的进行翻转，失败则意味着屏障成功翻转了这个对象，一轮扫描后整个U区翻转过程结束。
flip-heap-pointer(p) {
q=*p;
if(old(q))
compare-and-swap(p, q, forward(q));
}
线程翻转：C以增量方式逐一翻转mutator栈，每根线程会挂起在安全点中，然后把他们的栈指针翻转到新区，由于上面不变式的制约，翻转后的线程不可能在访问到O区对象。具体就是使用flip-heap-pointer方法完成整个流程。
翻转后处理：首先C会重置全局旗标，这样所有屏障失效，当所有线程都回复了注销请求（参考上面算法的软握手流程），C可以安全的释放掉反向HashMap、位图向量，然后C把两个区间的指针对调，整个过程完毕。
过程合并：
对mutator来说，上面所有过程有一些并不需要全局方式统一进行状态变迁，这样一部分过程可以合并减少同步握手开销，也就是说一部分屏障可以整合到一起加快回收速度。这里把根标记、堆/栈标记、空间分配和复制这些过程的mutator写屏障合并到一起简单整合为一个单独的屏障，具体如下：
replicate-phase-write(p , q) {
*p = q;
replicate-write-barrier(p, f, q);
}
replicate-write-barrier(p ,f , q) {
copy-write-barrier(p ,f , q); //这里q可以是指针也可以不是
mark-write-barrier(q); //这里q必须是指针
}
对collector来说，它的工作大体总结为如下4点：
1. C扫描全部根节点，之后是堆中的槽位（U区指向了O区的指针），然后是M的栈，对每一个对象都调用mark-write-barrier方法把引用对象加入到标记队列中，元素的标记顺序不影响整体的正确性。
2. 对于任何在输入队列中的引用，如果它引用的对象还没有转发地址，它会先在目标区域分配一个对象空间，然后在原对象头部加入一个转发指针，此过程叫forward-object。
3. 在方法forward-object中，C会以递归方式逐层向下扫描刚刚完成转发的对象指针集合然后进一步完成其子对象的转发，在这个过程中同时完成N区副本中的指针指向它的N区副本引用的过程，这个过程叫scan-slot。
4. 整个过程的完成的标志为：
a) 全部存活对象的根集合和U区槽位都完成扫描。
b) 所有N区副本都已经完成扫描。
c) 所有线程栈槽位都完成扫描，已经不存在任何灰色-白色指针，同时C队列都空。
scan-slot(p ,f) {
pp = unforward(p);
copy-word(&(pp -> f), &(p -> f));
forward-object(p->f); //如果f不是指针，则这一步不成立
if(forwarded(p->f)) { //只有f是指针才返回true
v=p->f;
vv=forward(v);
compare-and-swap(&(p->f), v, vv);
}
}
volatile字段在复制过程中的顺序性保证
在java中，如果一个字段被声明为volatile，则意味着任何发生在其身上的读写操作都必须严格有序。它区别于普通变量的地方是若普通变量发生写入，只需要在时机成熟时才同步回主存，而读操作也不用每次都从主存中获取。其实对于普通变量来说，copy-word方法能够成功的关键依赖了它们“同步时机”的不确定性。这里假设volatile变量上发生的读写具有严格的顺序性，那么同时更新O区和N区两个副本在没有同步块保证的情况下（前面分析copy-word时候说过，不再赘述）会出现不一致的情况，那么为了避免同时修改两个值，必须有一种方式避免，具体做法如下：
1. 在O区对象发生转发之前，对它的volatile变量读写只能发生在O区。
2. 若O区对象已经完成复制，那么对其访问只能发生在N区。
3. 若要以原子方式完成O区对象到N区对象的复制，C必须先得到O区对象锁，在持有锁情况下完成复制。
4. 若要保证volatile写和collector拷贝之间的顺序性，算法要求在复制过程中拿到锁的线程必须仅对O区对象进行写入
5. 在复制过程中，volatile必须检查锁定标志来首先判定对象的迁移状态，若发生了迁移，那直接读取迁移后对象值，若还没有迁移，则以线程观察到的这个点为准进行读取。
总结来说未迁移和迁移后的顺序性分别以O区和N区对象的volatile字段做保证，而迁移过程中的灰色地带则依靠对象锁保证。下面给出读写volatile的一致性代码：
repl-vol-write(p, f, v) {
if(forwarded(p)) { //如果已经完成了复制，直接写入新值，而过程前的得到转发地址代码不影响最终的正确性
A) p = forward(p);
B) v = forward(v);
vol-write(p->f, v);
return;
}
q = acquire-metalock(p -> lock); //若p此时没有被转发，p指向O区，否则指向N区
C) if(p is in N) v = forward(v); //锁定的是新区对象，则v也在N区
vol-write(p->f, v);
release-metalock(p->lock);
}
假设初始情况下复制未发生，则多线程拿到的全是O区对象锁，更新顺序按锁的获取顺序进行。若过程中对象完成了复制，则后来的线程可能看到了O区对象转发地址，也可能在获取锁的时候看到（p在N空间），那么它获取到的是N区锁。则它们之间的顺序若忽略ABC三步，则完全交由N区的volatile变量控制，而之前得到O区锁的对象直接更新O区旧对象而没有覆盖新值，也是正确的。
repl-vol-read(p , f) {
top:
l = p -> lock;
if(metalocked(1)) goto top; //没有锁定意味着完成或未完成复制
if(not forwarded(p)) //若复制没开始，以线程看到的点为准
return vol-read(p->f); //读写同步交给O区volatile本身控制
p=forward(p);
v=vol-read(p->f); //复制完成靠N区volatile本身控制
return unforward(v);
}
Java锁的复制
随着对象移动，要保证锁能够在正确对象中生成，也需要额外的逻辑控制。java中的锁根据不同的使用场景分为偏向锁，轻量级锁和重量级锁三种。程序对三种锁的处理方式相同，当已经确切知道堆中存活对象时，当全部线程已经执行到安全点（此时没有线程在执行字节码），若发现锁为偏向状态，则需要判断全局等待队列中是否有等待线程，如果有，则修改偏向所有者栈，把N区对应对象的markWord修改为指向该mutator栈指针，更新O区对象markWord为FORWARD旗标，同时遍历所有全局等待队列中的线程，改变EE中的对象指针，然后唤醒他们结束全局安全点执行。若没有等待线程，说明锁不需要膨胀，此时只修改其epoch和对应Class的epoch即可。若锁处于轻量级锁定状态，修改线程栈指向N区对象，写入FORWARD旗标。若锁处于重量级锁定状态，则必须复制并修改对象monRec。复制O区对象monRec到N区对象markWord处，遍历monRec中阻塞队列中的节点，按顺序复制到新monRec中并修改每个节点（EE）中的targetObj，然后按顺序便利并赋值等待队列中所有节点，执行相同操作，最后在O区对象中写入FORWARD旗标。
算法在偏向、轻量级锁定、重量级锁定的基础上加入一个FORWARD状态标志着对象锁已经迁移，安全点恢复后，尝试获取对象锁的线程发现FORWARD指针后会在N区对象中获得。而在指针反转过程中，对象总是在N区获得锁。
总结：复制线程和mutator共同工作，写屏障给mutator带来了额外的开销来维护三色不变式，同时降低了游离垃圾的回收率。而STW类型算法只通过单次堆扫描（比如说使用cheney或层次分解算法）就能完成整个复制过程，但并发算法必须先对堆进行一次标记工作且此阶段还需要不断的与mutator进行同步才能继续进行增量复制。二次阶段的mutator还要承担额外的写屏障，并且锁和volatile类型变量的复制还需要额外的处理。这些工作的目的仅是让mutator能停顿更短的时间。
先写到这里吧。
网友评论