已经讲述过垃圾收集器的工作机制和总体实现了，这篇文章主要针对标记和内存缩并进行具体阐述。
1. 标记
我们知道，标记存活对象是为了识别出垃圾，依靠对所有存活对象进行一次全局遍历来确定哪些内存可以回收。这个遍历从根出发，利用相互引用关系，标记所有存活对象，除此之外，其他内存就是垃圾。这里强调下，标记并不会沿着已经被标记的单元追踪下去，这确保了标记能够终止。
对于对象间的相互引用关系，这针对不同的对象类型又有所不同。对象类型指的是ObjectHandle可被解释为整型、布尔型、字符串、数组等等。显然，基本数据类型比如整型，只需要看看自己是否被标记就可以了，但是对于复合数据类型，比如数组，必须再继续跟踪每个数组元素到底有没有被标记。于是我们发现，针对不同的对象类型，遍历方法是不一样的，所以想办法把不同对象类型的遍历方法分开来写，万一需求增加了，想再增加别的对象类型，比如结构体，只需要增加代码，就没有必要因此大幅度地修改代码了。
上文提到，我们会为每个对象类型写自己的遍历方法，这里我们将这件事封装在Walker里。Walker提供接口，具体的对象类型可以继承并实现之，这里用整型对象类型，即IntWalker举例。
class Walker
{
public:
virtual void WalkObject(ObjectHandle* handle)const=0;
};
class IntWalker : public Walker
{
public:
virtual void WalkObject(ObjectHandle* handle)const
{
handle->Marked=true;
}
};
自然地，我们还需要根据ObjectHandle的对象类型来选择不同的Walker，这里把它封装在WalkerSelector里。
enum ObjectType //对象类型
{
objectINT,
objectBOOL,
objectSTRING,
objectARRAY,
objectSTRUCT
};
class WalkerSelector
{
private:
static IntWalker* intWalker;
public:
static Walker* GetWalker(ObjectHandle* handle)
};
Walker* WalkerSelector::GetWalker(ObjectHandle* handle)
{
ObjectType type=Describer::GetType(handle);
switch(type)
{
case objectINT:
return intWalker;
default:
throw "handle类型出错";
}
}
GC里Mark的实现就显得非常容易了。
void GC::Mark(ObjectHandle* handle)
{
WalkerSelector::GetWalker(handle)->WalkObject(handle);
}
2. 内存缩并
内存缩并可以解决内存碎片的问题，垃圾收集器的工作机制中已经提过。本文主要针对其具体算法和实现。这里我们先明确一下，如果是对第n代进行垃圾收集，那么意味着第0-n代都会进行操作。假设我们只有3代，如果是对第2代进行垃圾收集，那么存活对象就不需要进行提升；反之，如果是第0代或第1代的存活对象，则需要对其进行提升。所以我们的讨论分两种情况。（下图红色区域表示存活对象，蓝色区域表示非存活对象，绿色区域表示已清扫到一起的空闲内存）
对第0代或第1代进行垃圾收集：只需把存活对象提升到更高一代的空闲内存即可。
对第2代进行垃圾收集：我们需要记录FreeIndex和FreeCount，分别表示空闲内存的起始位置和大小。在扫描过程中，我们需要把存活对象往前移，把空闲内存往后移，具体如下图：
代码实现如下：
void SmallObjectHeap::Collect(const int generationIndex)
{
for (int i=generationIndex; i>=0; i--)
{
int count=ObjectHandles.ObjectHandleCount[i];
ObjectHandles.Clear(i);
if (i==GenerationCount-1) //对第2代进行收集
{
int FreeIndex=Generations[i].Start; //空闲内存起始位置
int FreeCount=0; //空闲内存大小
for (int j=0; j<count; j++)
{
ObjectHandle* handle=ObjectHandles.Data[i][j];
if (handle->Marked || handle->Type==handlePINNED)
{
if (FreeCount) handle->Move(FreeIndex);
FreeIndex+=handle->Size;
ObjectHandles.Add(handle, i);
}
else FreeCount+=handle->Size;
}
}
else //对第0代或第1代进行收集
{
int FreeIndex=Generations[i+1].Start;
for (int j=0; j<count; j++)
{
ObjectHandle* handle=ObjectHandles.Data[i][j];
if (handle->Marked || handle->Type==handlePINNED)
{
handle->Move(FreeIndex);
FreeIndex+=handle->Size;
ObjectHandles.Add(handle, i);
}
}
}
}
}
posted on 2010-05-14 16:30
Lyt 阅读(1584)
评论(2) 编辑 收藏 引用 所属分类:
垃圾收集器