已經講述過垃圾收集器的工作機制和總體實現了，這篇文章主要針對標記和內存縮并進行具體闡述。
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 閱讀(1625)
評論(2) 編輯 收藏 引用 所屬分類:
垃圾收集器