Lyt
posts - 16,comments - 61,trackbacks - 0

      已经讲述过垃圾收集器的工作机制总体实现了,这篇文章主要针对标记和内存缩并进行具体阐述。

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)  编辑 收藏 引用 所属分类: 垃圾收集器

FeedBack:
# re: 稚嫩版垃圾收集器 之 具体实现(二)
2010-05-14 16:47 | Any
文中图用什么画的? 可否相告?  回复  更多评论
  
# re: 稚嫩版垃圾收集器 之 具体实现(二)
2010-05-14 16:49 | Lyt
@Any
Microsoft Office Word 2007  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理