灵巧指针与内存回收

1、 灵巧指针与内存回收 在JAVA 和 C# 中都有垃圾回收功能，程序员在分配一段内存后可以不再理会，而由垃圾回收自动回收，从而使程序员从复杂的内存管理中解脱出来。这是JAVA 和 C#的一大优点。而C+程序员在用 new 分配了一段内存后，还必须用 delete 释放，否则将造成资源泄漏。因此，一些C+ 书上经常告诫程序员：要养成好的习惯，new 与 delete 要成对出现，时刻记住将内存释放回系统。但是，事情只是这么简单吗？ 经常地，在使用C+的过程中，我们会遇到下面的情形： class A public： A（）； A（）； SetNextPtr（A* Ptr） pNext=Ptr； p

2、rivate： A * pNext； 一般地，为了不引起内存泄漏，我们会在析构函数中释放pNext，象下面这样： A：A（） if（pNext） delete pNext； pNext=NULL; 对于一般情况，这样就够了，但在某些情形下，这样也会出问题的，象下面这样： A *ptrB = new A;； A *ptrA = new A； ptrB->SetNextPtr(ptrA); ptrA->SetNextPtr(ptrB); delete ptrB; 这样会出问题,因为这些指针连成了一个回环,无论从那一个点开始删除,都会造成一个指针被删除两次以上,这将使得程序抛出异常。当然

3、，也有一些方法可以用来解决这个问题，但是我要说明的是：对于C+程序员来说，养成一个好的习惯并不难，难就难在有时候这样将把你带入一种逻辑的混乱当中 ，增加一些不必要的麻烦，有时甚至不知所措。 可是如何解决这个问题呢？如果C+也具有垃圾回收的功能，那么，这个问题当然就迎刃而解了。但是C+属于编译型语言，不会具备这个功能。长期以来，我也一直在思考这个问题，想找出一种方法来使自己从这种麻烦中解脱出来。直到最近开始学习泛型编程，看到灵巧指针的介绍以后，我灵光一闪，终于找到了办法来解决这个问题。 大家知道，灵巧指针具有一些灵巧特性，如在构造时可以自动初始化，析构时可以自动释放所指的指针。我们就利用它的这些

4、特性来实现我们的垃圾回收。 首先，我们要想办法来对我们用 new 分配的每一段内存增加引用记数，即记录下当前指向它的灵巧指针个数，当最后一个指向它的指针被释放时，我们就可以释放这段内存了。由此，我们进行了new 和 delete 的全局重载，并引入了CPtrManager 类。void operator delete(void * p) int mark=thePtrManager.GetMarkFromPtr(p);if(mark>0) thePtrManager.UserDelete(mark);free(p);void * operator new(size_t size) ret

5、urn thePtrManager.MallocPtr(size);class CPtrManager public:int GetCount(int mark,void * p); /得到当前的引用记数static CPtrManager* GetPtrManager(); /得到全局唯一的CPtrManager 指针void UserDelete(int mark); /删除 mark 标志的指针，并对指针和标志复位void * MallocPtr(size_t size); /new（）调用它分配内存；BOOL AddCount(int mark,void * Ptr); /增加引用记数

6、BOOL Release(int mark,void * Ptr); /减少引用记数int GetMarkFromPtr(void * Ptr); /通过指针得到标志CPtrManager();virtual CPtrManager();private:static CPtrManager * p_this; /指向全局唯一的CPtrManager 指针void AddPtr(void * Ptr); /增加一个新分配的内存 CPtrArray m_ptr; /存放分配的指针的可变数组CUIntArray m_count; /存放指针的引用记数void* pCurrent; /最近刚分配的指针

7、unsigned int m_mark; /最近刚分配的指针的标志CUIntArray m_removed;/存放m_ptr中指针被删除后所空留的位置; 顾名思义，CPtrManager 就是用来管理指针的，对于我们用new 分配的每一个指针，都存放在m_ptrindex中，并在m_countindex中存放它的引用记数。同时，我们对每一个指针都增加了一个标志（mark >0,<=0为无效），这个标志同时存在于灵巧指针中（后面将看到），这是为了一种双重保险，并且在这里，这个标志就等于指针在m_ptr中的索引，这也为快速查找提供了方便。 总的思路是这样的：当我们用new分配一个指针时

8、，这个指针将被存入CPtrManager中，当一个灵巧指针开始拥有这个指针时，CPtrManager将负责对这个指针的引用记数加 1 ，反之亦然，即一个灵巧指针开始释放该指针的拥有权时，CPtrManager将负责对这个指针的引用记数减 1 ，如果引用记数为 0 ，那么这个灵巧指针将负责对该指针 delete。 下面是灵巧指针的部分介绍：template<class T>class auto_ptr public: auto_ptr() mark=0;pointee=0; auto_ptr(auto_ptr<T>&rhs); auto_ptr(T*ptr); a

9、uto_ptr()Remove(); T*operator->() const; operator T*(); T&operator*()const; auto_ptr<T>&operator=(auto_ptr<T>&rhs); auto_ptr<T>&operator=(T*ptr); private: void Remove(); /释放所指指针的拥有权 T*pointee; /所拥有的指针 int mark;/所拥有的指针的标志;template<class T> void auto_ptr<

10、T>:Remove() CPtrManager * pMana=CPtrManager:GetPtrManager();if(pointee&&pMana) if(pMana->Release(mark,pointee) /减少引用记数 if(pMana->GetCount(mark,pointee) =0) delete pointee; /如果引用记数为0，delete 指针 else /所拥有的指针不在CPtrManager 中，有可能在栈中 /User decide to do pointee=NULL; /复位mark=0;template<c

11、lass T> auto_ptr< T>:auto_ptr(auto_ptr<T>&rhs)pointee=rhs.pointee;mark=rhs.mark;CPtrManager * pMana=CPtrManager:GetPtrManager();if(pMana) pMana->AddCount(mark,pointee); /增加引用记数 template<class T> auto_ptr< T>:auto_ptr(T*ptr) mark=0; pointee=ptr; CPtrManager * pMana=C

12、PtrManager:GetPtrManager(); if(pMana) mark=pMana->GetMarkFromPtr(ptr); /得到指针的标志 if(mark>0) pMana->AddCount(mark,pointee); /如果标志不为0，增加引用记数 template<class T>auto_ptr<T>& auto_ptr< T>:operator=(auto_ptr<T>&rhs)if(pointee!=rhs.pointee) Remove(); /释放当前指针的拥有权 point

13、ee=rhs.pointee; mark=rhs.mark; CPtrManager * pMana=CPtrManager:GetPtrManager(); if(pMana) pMana->AddCount(mark,pointee);return *this;template<class T> auto_ptr<T>&auto_ptr< T>:operator = (T* ptr) if(pointee!=ptr) Remove(); pointee=ptr; CPtrManager * pMana=CPtrManager:GetPtrM

14、anager(); if(pMana) mark=pMana->GetMarkFromPtr(ptr); if(mark>0) pMana->AddCount(mark,pointee); 当到了这里时，我便以为大功告成，忍不住摸拳搽掌，很想试一试。结果发现对于一般的情况，效果确实不错，达到了垃圾回收的效果。如下面的应用： auto_ptr<test> p1=new test; auto_ptr<test>p2 = p1; auto_ptr<test>p3 = new test; 但是，很快地，我在测试前面提到的回环时，就发现了问题，我是这

15、样测试的： class test auto_ptr<test> p; ; auto_ptr<test> p1=new test; auto_ptr<test>p2 =new test; p1->p=p2; p2->p=p1; 当程序执行离开作用域后，这两块内存并没有象我想象的那样被释放，而是一直保留在堆中，直到程序结束。我仔细分析造成这种现象的原因，发现了一个非常有趣的问题，我把它称之为互锁现象。 上面p1 所拥有的指针被两个灵巧指针所拥有，除p1外，还有p2所拥有的 test 类中的灵巧指针p，p2亦然。也就是说，这两块内存的指针的引用记数都为

16、 2 。当程序执行离开作用域后，p1，p2被析构，使它们的引用记数都为1，此后再没有灵巧指针被析构而使它们的引用记数变为 0 ，因此它们将长期保留在堆中。这就象两个被锁住的箱子，其中每个箱子中都装着对方的钥匙，但却无法把彼此打开，这就是互锁现象。 可是如何解决呢？看来必须对它进行改进。同时，我也发现上面的方法不支持多线程。所以，我们改进后的方法不仅要解决互锁现象，而且还要支持多线程。下面是我改进后的方法： 首先是如何发现这种互锁现象。我们知道，互锁现象产生的根源在于拥有堆中内存的灵巧指针本身也存在于已分配的堆内存中，那么，如何发现灵巧指针是存在于堆中还是栈中就成了问题的关键。由此，我引入了一个

17、新的类 CPtr，由它来管理用 new 分配的指针，而 CPtrManager 专门用来管理 CPtr。如下所示：class CPtrfriend class CMark;public:int GetPtrSize(); /得到用 new 分配指针的内存的大小CMutex * GetCMutex(); /用于线程同步void * GetPtr(); /得到用 new 分配的指针CPtr();virtual CPtr();int GetCount(); /得到引用记数 void AddAutoPtr(void * autoPtr,int AutoMark);/加入一个拥有该指针的灵巧指针BOOL

18、 DeleteAutoPtr(void * autoPtr); /释放一个灵巧指针的拥有权void SetPtr(void * thePtr,int Size, int mark,int count=0); /设置一个新的指针 void operator delete(void * p) free(p); void * operator new(size_t size) return malloc(size);private:int m_mark; /指针标志int m_count; /引用记数void * m_ptr; /分配的指针int m_size; /指针指向内存的大小CPtrArra

19、y AutoPtrArray; /存放拥有该指针的所有灵巧指针的指针数组CUIntArray m_AutoMark; /灵巧指针标志：0 in the stack; >0 =mark CMutex mutex; /用于线程同步;class CPtrManager public:int GetAutoMark(void * ptr); /通过灵巧指针的指针，得到灵巧指针标志CPtrManager();virtual CPtrManager();int GetMarkFromPtr(void * Ptr);void *MallocPtr(size_t size); BOOL bCanWrit

20、e();void DeletePtr(int mark,void * Ptr);void AddPtr(void *Ptr,int PtrSize);static CPtrManager * GetPtrManager();CPtr * GetCPtr(void * Ptr,int mark);/通过指针和指针标志得到存放该指针的 CPtrprivate: CPtrArray m_ptr; /存放 CPtr 的指针数组void* pCurrent;unsigned int m_mark;CUIntArray m_removed;BOOL bWrite; /在解决互锁现象的过程中，谢绝其它线程的

21、处理static CPtrManager * p_this;CMutex mutex;/用于线程同步CMarkTable myMarkTable;void RemoveLockRes(); /处理互锁内存void CopyAllMark(); /处理互锁现象前，先对所有的CPtr进行拷贝static UINT myThreadProc(LPVOID lparm); /处理互锁现象的线程函数CWinThread* myThread;void BeginThread() myThread=AfxBeginThread(myThreadProc,this,THREAD_PRIORITY_ABOVE_

22、NORMAL); 上面的应用中加入了灵巧指针的标志，其实，这个标志就等于该灵巧指针所存在的内存的指针的标志。例如：我们用 new 分配了一个 test 指针，假如这个指针的标志 mark=1，那么，这个 test 中的灵巧指针 auto_ptr<test> p 的标志 automark=1。如果一个灵巧指针存在于栈中，那么它的 automark=0。反之亦然，如果一个灵巧指针的 automark 等于一个指针的 mark，那么，该灵巧指针必存在于这个指针所指的内存中。可是，如何得到这个标志呢，请看下面这个函数的实现：int CPtrManager:GetAutoMark(void

23、*ptr) CSingleLock singleLock(&mutex); singleLock.Lock(); /线程同步 int size =m_ptr.GetSize(); for(int i=1;i<size;i+) CPtr* theCPtr=(CPtr*)m_ptri; if(theCPtr) int ptrFirst=(int)theCPtr->GetPtr();/得到内存的首指针 int ptrEnd=ptrFirst+theCPtr->GetPtrSize();/得到内存的尾指针 int p=(int)ptr; /灵巧指针的指针 if(p>=p

24、trFirst&&p<=ptrEnd)/比较灵巧指针的指针是否在首尾之间 return i; return 0; 这个函数的原理就在于：如果一个灵巧指针存在于一块内存中，那么该灵巧指针的指针必在这块内存的首尾指针之间。 解决了灵巧指针的位置问题，下一步就是要找出所有被互锁的内存的指针。这个好实现，只要所有拥有这个指针的灵巧指针的 automark > 0 ，那么，这块内存就可能被互锁了(注意只是可能)，接着看下面的实现：class CMarkfriend class CMarkTable;public:CMark()virtual CMark() void oper

25、ator delete(void * p) free(p); void * operator new(size_t size) return malloc(size);void CopyFromCPtr(CPtr* theCPtr); /从 CPtr 中拷贝相关信息BOOL bIsNoneInStack(); /判断拥有该指针的所有灵巧指针是否都不在栈中void Release(); /解除该指针的互锁private:int m_mark; /指针的标志CPtrArray autoptrArray; /拥有该指针的所有灵巧指针的指针数组CUIntArray automarkArray;/拥有该

26、指针的所有灵巧指针的标志;class CMarkTablepublic:CMarkTable()Init();virtual CMarkTable()void AddCMark(CMark * theCMark);BOOL FindMark(int mark);void Init();void DoLockMark(); /处理互锁问题private:CPtrArray CMarkArray; /暂存从CPtrManager 中拷贝过来的指针信息的 CMark 指针数组CPtrArray CLockMarkArray; /存放互锁的内存void GetLockMark(); /得到所有可能被互

27、锁的内存的 CMark，结果存放于CLockMarkArrayBOOL FindLockMark(int mark); /判断一个灵巧指针是否存在于CLockMarkArray所包含的指针中void RemoveUnlockMark();/去除假的互锁内存void RemoveGroup(int automark);/对互相有联系的相互死锁的内存进行分组; 这里又引入了两个类：CMark 和 CMarkTable ，这是为了在处理互锁问题之前，对 CPtrManager 中的 CPtr 进行快速拷贝，以防止影响其它线程的正常运行。其实，这里的 CMark 与 CPtr 没有什么区别，它只是简单

28、地从 CPtr 中拷贝信息，也就是说，它等同于 CPtr 。 为了处理互锁问题，先要把可能被互锁的内存指针找出来，看下面函数的实现：void CMarkTable:GetLockMark()CLockMarkArray.SetSize(0);int size=CMarkArray.GetSize();for(int i=0;i<size;i+)CMark * theMark=(CMark*)CMarkArrayi;if(theMark) if(theMark->bIsNoneInStack() CLockMarkArray.SetAtGrow(i,theMark); 把这些内存找出

29、来之后，就需要把那些假锁的内存找出来，什么是假锁呢？看下面的例子： 对于指针 ptrA ，如果它的灵巧指针 autoA 存在于指针 ptrB 中，而 ptrB 的灵巧指针 autoB 又存在于 ptrA 中，那么 ptrA 和 ptrB 是真锁，但是如果ptrB 的灵巧指针 autoB 存在于指针 ptrC 中，而 ptrC的灵巧指针 autoC 存在于栈中，那么， ptrA 和 ptrB 属于假锁。怎么找出假锁的内存呢？看下面函数的实现：void CMarkTable:RemoveUnlockMark()CUIntArray UnlockMarkArray;BOOL bNoneRemovee

30、d;do bNoneRemoveed=TRUE;UnlockMarkArray.SetSize(0);int size=CLockMarkArray.GetSize();for(int i=0;i<size;i+) CMark * theMark=(CMark*)CLockMarkArrayi; if(theMark) int size1=(theMark->automarkArray).GetSize(); for(int j=0;j<size1;j+) int mark=(theMark->automarkArray)j; if(!FindLockMark(mark

31、) /判断灵巧指针是否存在于CLockMarkArray所包含的指针中 UnlockMarkArray.InsertAt(0,i); /record to removebNoneRemoveed=FALSE;break; else UnlockMarkArray.InsertAt(0,i); bNoneRemoveed=FALSE; int size2=UnlockMarkArray.GetSize();for(int k=0;k<size2;k+) int m=UnlockMarkArrayk; CLockMarkArray.RemoveAt(m);while(!bNoneRemove

32、ed); 上面函数的原理就是：不停地删除那些灵巧指针不在CLockMarkArray所包含的指针中的指针，直到所有的指针的灵巧指针都存在于CLockMarkArray所包含的指针中。 所有被互锁的内存被找出来了，那么，下一步就是如何解锁的问题了。由此，我对灵巧指针引入了一个父类parent_autoptr 如下：class parent_autoptrpublic:parent_autoptr()thisAutoMark=0;virtual parent_autoptr()virtual void Release() /释放指针的拥有权protected:int thisAutoMark; /

33、存放灵巧指针标志; 在灵巧指针中，对函数 Release() 进行了重载。template<class T>class auto_ptr :public parent_autoptr public: virtual void Release()Remove(); auto_ptr() mark=0;pointee=0;thisAutoMark=GetAutoMark(); auto_ptr(auto_ptr<T>&rhs); auto_ptr(T*ptr); auto_ptr()Remove(); T*operator->() const; operator T*(); T&operator*()const; auto_ptr<T>&operator=(auto_ptr<T>&rhs); auto_ptr<T>&operator=(T*ptr); private: void Remove(); int GetAutoMark(); CMutex *GetCMutex(); void ReadyWrite(); T*pointee; int mark; ; 在 CMarkTable 和 C