灵巧指针与内存回收.DOC

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

2、ext=Ptr； private： 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(mark0) thePtrManager.UserDelete(mark); free(p); void * operator new(

5、size_t size) return 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 ma

6、rk,void * Ptr); /增加引用记数 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; /存放

7、指针的引用记数 void* pCurrent; /最近刚分配的指针 unsigned int m_mark; /最近刚分配的指针的标志 CUIntArray m_removed;/存放 m_ptr 中指针被删除后所空留的位置 ; 顾名思义， CPtrManager 就是用来管理指针的，对于我们用 new 分配的每一个指针，都存放在 m_ptrindex中，并在 m_countindex中存放它的引用记数。同时，我们对每一个指针都增加了一个标志（ mark 0, class auto_ptr public: auto_ptr() mark=0;pointee=0; auto_ptr(auto_p

8、tr auto_ptr(T*ptr); auto_ptr()Remove(); T*operator-() const; operator T*(); T auto_ptr auto_ptr private: void Remove(); /释放所指指针的拥有权 T*pointee; /所拥有的指针 int mark;/所拥有的指针的标志 ; template void auto_ptr:Remove() CPtrManager * pMana=CPtrManager:GetPtrManager(); if(pointee /如果引用记数为 0， delete 指针 else /所拥有的指针不

9、在 CPtrManager 中，有可能在栈中 /User decide to do pointee=NULL; /复位 mark=0; template auto_ptr:auto_ptr(auto_ptr mark=rhs.mark; CPtrManager * pMana=CPtrManager:GetPtrManager(); if(pMana) pMana-AddCount(mark,pointee); /增加引用记数 template auto_ptr:auto_ptr(T*ptr) mark=0; pointee=ptr; CPtrManager * pMana=CPtrManag

10、er:GetPtrManager(); if(pMana) mark=pMana-GetMarkFromPtr(ptr); /得到指针的标志 if(mark0) pMana-AddCount(mark,pointee); /如果标志不为 0，增加引用记数 templateauto_ptr /释放当前指针的拥有权 pointee=rhs.pointee; mark=rhs.mark; CPtrManager * pMana=CPtrManager:GetPtrManager(); if(pMana) pMana-AddCount(mark,pointee); return *this; temp

11、late auto_ptr pointee=ptr; CPtrManager * pMana=CPtrManager:GetPtrManager(); if(pMana) mark=pMana-GetMarkFromPtr(ptr); if(mark0) pMana-AddCount(mark,pointee); 当到了这里时，我便以为大功告成，忍不住摸拳搽掌，很想试一试。结果发现对于一般的情况，效果确实不错，达到了垃圾回收的效果。如下面的应用： auto_ptr p1=new test; auto_ptrp2 = p1; auto_ptrp3 = new test; 但是，很快地，我在测试前

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

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

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

15、eleteAutoPtr(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; /指针指向内存的大小 CPt

16、rArray 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); BOO

17、L bCanWrite(); void DeletePtr(int mark,void * Ptr); void AddPtr(void *Ptr,int PtrSize); static CPtrManager * GetPtrManager(); CPtr * GetCPtr(void * Ptr,int mark);/通过指针和指针标志得到存放该指针的 CPtr private: CPtrArray m_ptr; /存放 CPtr 的指针数组 void* pCurrent; unsigned int m_mark; CUIntArray m_removed; BOOL bWrite; /

18、在解决互锁现象的过程中，谢绝其它线程的处理 static CPtrManager * p_this; CMutex mutex;/用于线程同步 CMarkTable myMarkTable; void RemoveLockRes(); /处理互锁内存 void CopyAllMark(); /处理互锁现象前，先对所有的 CPtr 进行拷贝 static UINT myThreadProc(LPVOID lparm); /处理互锁现象的线程函数 CWinThread* myThread; void BeginThread() myThread=AfxBeginThread(myThreadPro

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

20、er:GetAutoMark(void *ptr) CSingleLock singleLock( singleLock.Lock(); /线程同步 int size =m_ptr.GetSize(); for(int i=1;iGetPtr();/得到内存的首指针 int ptrEnd=ptrFirst+theCPtr-GetPtrSize();/得到内存的尾指针 int p=(int)ptr; /灵巧指针的指针 if(p=ptrFirst public: CMark() virtual CMark() void operator delete(void * p) free(p); void

21、 * 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;/拥有该指针的所有灵巧指针的标志 ; class CMarkTa

22、ble public: 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(); /得到所有可能被互锁的内存的 CMark，结果

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

24、拷贝信息，也就是说，它等同于 CPtr 。 为了处理互锁问题，先要把可能被互锁的内存指针找出来， 看下面函数的实现： void CMarkTable:GetLockMark() CLockMarkArray.SetSize(0); int size=CMarkArray.GetSize(); for(int i=0;ibIsNoneInStack() CLockMarkArray.SetAtGrow(i,theMark); 把这些内存找出来之后，就需要把那些假锁的内存找出来，什么是假锁呢？看下面的例子： 对于指针 ptrA ，如果它的灵巧指针 autoA 存在于指针 ptrB 中，而 ptrB

25、 的灵巧指针 autoB 又存在于 ptrA 中，那么 ptrA 和 ptrB 是真锁，但是如果 ptrB 的灵巧指针 autoB 存在于指针 ptrC 中，而 ptrC 的灵巧指针 autoC 存在于栈中，那么， ptrA 和 ptrB 属于假锁。怎么找出假锁的内存呢？看下面函数的实现： void CMarkTable:RemoveUnlockMark() CUIntArray UnlockMarkArray; BOOL bNoneRemoveed; do bNoneRemoveed=TRUE; UnlockMarkArray.SetSize(0); int size=CLockMarkAr

26、ray.GetSize(); for(int i=0;iautomarkArray).GetSize(); for(int j=0;jautomarkArray)j; if(!FindLockMark(mark) /判断灵巧指针是否存在于CLockMarkArray所包含的指针中 UnlockMarkArray.InsertAt(0,i); /record to remove bNoneRemoveed=FALSE; break; else UnlockMarkArray.InsertAt(0,i); bNoneRemoveed=FALSE; int size2=UnlockMarkArray

27、.GetSize(); for(int k=0;k class auto_ptr :public parent_autoptr public: virtual void Release()Remove(); auto_ptr() mark=0;pointee=0;thisAutoMark=GetAutoMark(); auto_ptr(auto_ptr auto_ptr(T*ptr); auto_ptr()Remove(); T*operator-() const; operator T*(); T auto_ptr auto_ptr private: void Remove(); int G

28、etAutoMark(); CMutex *GetCMutex(); void ReadyWrite(); T*pointee; int mark; ; 在 CMarkTable 和 CMark 中对互锁内存进行了释放，如下： void CMarkTable:DoLockMark() GetLockMark(); RemoveUnlockMark(); int size=CLockMarkArray.GetSize(); while(size) CMark* theMark=(CMark*)CLockMarkArray0; CLockMarkArray.RemoveAt(0); if(theM

29、ark) int size2=(theMark-automarkArray).GetSize(); for(int i=0;iautomarkArray)i; RemoveGroup(automark); theMark-Release(); size=CLockMarkArray.GetSize(); Init(); void CMark:Release() int size=autoptrArray.GetSize(); for(int i=0;iRelease(); 到了现在，终于算是大功告成了，我马上把它投入测试当中，发现工作得非常好，即使开辟 20至 30个线程，程序也工作得很好，并

30、没有抛出异常，而且垃圾回收的功能也非常好 。但是，如果线程太多，那么在 CPtrManager 中为了保证线程同步，将会造成瓶颈效应，严重者将会严重影响执行效率。同时，如果每个线程都不停地产生死锁内存，那么，垃圾回收将应接不暇，时间长了，也会造成系统的资源耗尽。 代码的使用很简单，你只需要将我所附的两个文件加入到工程中，然后，在你的 C*App 中加入如下一段代码就行了： CPtrManager thePtrManager; 这将保证 thePtrManager 在进程最后结束的时候才被析构。 如果你是在一个新的工 程中使用，这就够了，但是，如果你还要使用原来的代码，特别是有指针参数的传递时，那么，你必须注意了。 如果需要从老代码中接收一个指针，而且这个指针需要你自己释放，那么可以使用灵巧指针，如果不需要释放，那么只能使用一般指针； 如果需要传递一个指针给老代码，而且这个指针需要你自己释放，那么可以使用灵巧指针，否则，只能使用一般指针。 我将随后附上所有源代码，由于没有经过严格测试，所以大家在使用前最好再测试一遍，最好能将发现的问题公布或写信告之于我，本人表示感谢。 欢迎大家 下载测试，批评指正和改进， Email: