已經(jīng)講述過垃圾收集器的工作機(jī)制和總體實(shí)現(xiàn)了，這篇文章主要針對(duì)標(biāo)記和內(nèi)存縮并進(jìn)行具體闡述。
1. 標(biāo)記
我們知道，標(biāo)記存活對(duì)象是為了識(shí)別出垃圾，依靠對(duì)所有存活對(duì)象進(jìn)行一次全局遍歷來確定哪些內(nèi)存可以回收。這個(gè)遍歷從根出發(fā)，利用相互引用關(guān)系，標(biāo)記所有存活對(duì)象，除此之外，其他內(nèi)存就是垃圾。這里強(qiáng)調(diào)下，標(biāo)記并不會(huì)沿著已經(jīng)被標(biāo)記的單元追蹤下去，這確保了標(biāo)記能夠終止。
對(duì)于對(duì)象間的相互引用關(guān)系，這針對(duì)不同的對(duì)象類型又有所不同。對(duì)象類型指的是ObjectHandle可被解釋為整型、布爾型、字符串、數(shù)組等等。顯然，基本數(shù)據(jù)類型比如整型，只需要看看自己是否被標(biāo)記就可以了，但是對(duì)于復(fù)合數(shù)據(jù)類型，比如數(shù)組，必須再繼續(xù)跟蹤每個(gè)數(shù)組元素到底有沒有被標(biāo)記。于是我們發(fā)現(xiàn)，針對(duì)不同的對(duì)象類型，遍歷方法是不一樣的，所以想辦法把不同對(duì)象類型的遍歷方法分開來寫，萬一需求增加了，想再增加別的對(duì)象類型，比如結(jié)構(gòu)體，只需要增加代碼，就沒有必要因此大幅度地修改代碼了。
上文提到，我們會(huì)為每個(gè)對(duì)象類型寫自己的遍歷方法，這里我們將這件事封裝在Walker里。Walker提供接口，具體的對(duì)象類型可以繼承并實(shí)現(xiàn)之，這里用整型對(duì)象類型，即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;
}
};
自然地，我們還需要根據(jù)ObjectHandle的對(duì)象類型來選擇不同的Walker，這里把它封裝在WalkerSelector里。
enum ObjectType //對(duì)象類型
{
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類型出錯(cuò)";
}
}
GC里Mark的實(shí)現(xiàn)就顯得非常容易了。
void GC::Mark(ObjectHandle* handle)
{
WalkerSelector::GetWalker(handle)->WalkObject(handle);
}
2. 內(nèi)存縮并
內(nèi)存縮并可以解決內(nèi)存碎片的問題，垃圾收集器的工作機(jī)制中已經(jīng)提過。本文主要針對(duì)其具體算法和實(shí)現(xiàn)。這里我們先明確一下，如果是對(duì)第n代進(jìn)行垃圾收集，那么意味著第0-n代都會(huì)進(jìn)行操作。假設(shè)我們只有3代，如果是對(duì)第2代進(jìn)行垃圾收集，那么存活對(duì)象就不需要進(jìn)行提升；反之，如果是第0代或第1代的存活對(duì)象，則需要對(duì)其進(jìn)行提升。所以我們的討論分兩種情況。（下圖紅色區(qū)域表示存活對(duì)象，藍(lán)色區(qū)域表示非存活對(duì)象，綠色區(qū)域表示已清掃到一起的空閑內(nèi)存）
對(duì)第0代或第1代進(jìn)行垃圾收集：只需把存活對(duì)象提升到更高一代的空閑內(nèi)存即可。
對(duì)第2代進(jìn)行垃圾收集：我們需要記錄FreeIndex和FreeCount，分別表示空閑內(nèi)存的起始位置和大小。在掃描過程中，我們需要把存活對(duì)象往前移，把空閑內(nèi)存往后移，具體如下圖：
代碼實(shí)現(xiàn)如下：
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) //對(duì)第2代進(jìn)行收集
{
int FreeIndex=Generations[i].Start; //空閑內(nèi)存起始位置
int FreeCount=0; //空閑內(nèi)存大小
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 //對(duì)第0代或第1代進(jìn)行收集
{
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 閱讀(1631)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
垃圾收集器