Java的指針與垃圾回收

在JAVA 和 C# 中都有垃圾回收功能，程序員在分配一段內存後可以不再理會，而由垃圾回收自動回收，從而使程序員從復雜的內存管理中解脫出來。這是Java 和 C#的一大優點。而C++程序員在用 new 分配了一段內存後，還必須用 delete 釋放，否則將造成資源洩漏。因此，一些C++ 書上經常告誡程序員：要養成好的習慣，new 與 delete 要成對出現，時刻記住將內存釋放回系統。但是，事情只是這麼簡單嗎？
    經常地，在使用C++的過程中，我們會遇到下面的情形：

以下為引用的內容：
        class  A
             {
                public：
              A（）；
              ~A（）；
              SetNextPtr（A* Ptr）
                   {pNext=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;   

    這樣會出問題,因為這些指針連成了一個回環,無論從那一個點開始刪除,都會造成一個指針被刪除兩次以上,這將使得程序拋出異常。當然，也有一些方法可以用來解決這個問題，但是我要說明的是：對於C++程序員來說，養成一個好的習慣並不難，難就難在有時候這樣將把你帶入一種邏輯的混亂當中，增加一些不必要的麻煩，有時甚至不知所措。
    可是如何解決這個問題呢？如果C++也具有垃圾回收的功能，那麼，這個問題當然就迎刃而解了。但是C++屬於編譯型語言，不會具備這個功能。長期以來，我也一直在思考這個問題，想找出一種方法來使自己從這種麻煩中解脫出來。直到最近開始學習泛型編程，看到靈巧指針的介紹以後，我靈光一閃，終於找到了辦法來解決這個問題。
    大家知道，靈巧指針具有一些靈巧特性，如在構造時可以自動初始化，析構時可以自動釋放所指的指針。我們就利用它的這些特性來實現我們的垃圾回收。
    首先，我們要想辦法來對我們用 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)
{

   
  return thePtrManager.MallocPtr(size);

}
class CPtrManager  
{
public:
 int GetCount(int mark,void * p);  file://得到當前的引用記數
 static CPtrManager* GetPtrManager(); file://得到全局唯一的CPtrManager 指針
 void UserDelete(int mark);  file://刪除 mark 標志的指針，並對指針和標志復位
 void * MallocPtr(size_t size); file://new（）調用它分配內存；
 BOOL AddCount(int mark,void * Ptr); file://增加引用記數
 BOOL Release(int mark,void * Ptr); file://減少引用記數
 int GetMarkFromPtr(void * Ptr);  file://通過指針得到標志
 CPtrManager();
 virtual ~CPtrManager();
private:
 static CPtrManager * p_this;  file://指向全局唯一的CPtrManager 指針
 void AddPtr(void * Ptr);  file://增加一個新分配的內存
           CPtrArray  m_ptr;   file://存放分配的指針的可變數組
 CUIntArray m_count; file://存放指針的引用記數 
 void*  pCurrent;   file://最近剛分配的指針
 unsigned int m_mark; file://最近剛分配的指針的標志
 CUIntArray m_removed;//存放m_ptr中指針被刪除後所空留的位置
};

    顧名思義，CPtrManager 就是用來管理指針的，對於我們用new 分配的每一個指針，都存放在m_ptr[index]中，並在m_count[index]中存放它的引用記數。同時，我們對每一個指針都增加了一個標志（mark >0,<=0為無效），這個標志同時存在於靈巧指針中（後面將看到），這是為了一種雙重保險，並且在這裡，這個標志就等於指針在m_ptr中的索引，這也為快速查找提供了方便。
    總的思路是這樣的：當我們用new分配一個指針時，這個指針將被存入CPtrManager中，當一個靈巧指針開始擁有這個指針時， CPtrManager將負責對這個指針的引用記數加 1 ，反之亦然，即一個靈巧指針開始釋放該指針的擁有權時，CPtrManager將負責對這個指針的引用記數減 1 ，如果引用記數為 0 ，那麼這個靈巧指針將負責對該指針 delete。
    下面是靈巧指針的部分介紹：

以下為引用的內容：
template
class auto_ptr
{
   public:
    auto_ptr()
    {mark=0;pointee=0;}
    auto_ptr(auto_ptr&rhs);
    auto_ptr(T*ptr);
    ~auto_ptr(){Remove();}
    T*Operator->() const;
    Operator T*(); 
    T&Operator*()const;
    auto_ptr&Operator=(auto_ptr&rhs); 
       auto_ptr&Operator=(T*ptr);
   private:
              void Remove(); file://釋放所指指針的擁有權 
    T*pointee;  file://所擁有的指針
    int mark;//所擁有的指針的標志
};
template void auto_ptr< T>::Remove()
{
       CPtrManager * pMana=CPtrManager::GetPtrManager();
 if(pointee&&pMana)
 {
   if(pMana->Release(mark,pointee))   file://減少引用記數
   {
        if(pMana->GetCount(mark,pointee) ==0)
         delete pointee;    file://如果引用記數為0，delete 指針
   }      
   else  file://所擁有的指針不在CPtrManager 中，有可能在棧中
   {
    file://User decide to do
   }

 }
 pointee=NULL;  file://復位
 mark=0;
}
template auto_ptr< T>::auto_ptr(auto_ptr&rhs) 
{
 pointee=rhs.pointee;
 mark=rhs.mark;
 CPtrManager * pMana=CPtrManager::GetPtrManager();
 if(pMana)
    pMana->AddCount(mark,pointee); file://增加引用記數
  
}
template auto_ptr< T>::auto_ptr(T*ptr)
{
       mark=0;
       pointee=ptr;
       CPtrManager * pMana=CPtrManager::GetPtrManager();
       if(pMana)
    {
       mark=pMana->GetMarkFromPtr(ptr); file://得到指針的標志
       if(mark>0)
           pMana->AddCount(mark,pointee);  file://如果標志不為0，增加引用記數
    }
}
templateauto_ptr& auto_ptr< T>::Operator=(auto_ptr&rhs)
{
 if(pointee!=rhs.pointee) 
 {
     Remove();  file://釋放當前指針的擁有權
     pointee=rhs.pointee;
     mark=rhs.mark;
     CPtrManager * pMana=CPtrManager::GetPtrManager();
     if(pMana)
        pMana->AddCount(mark,pointee);

 }
 return *this;

}
template auto_ptr&auto_ptr< T>::Operator = (T* ptr)
{
   if(pointee!=ptr)
   {
       Remove();
       pointee=ptr;
       CPtrManager * pMana=CPtrManager::GetPtrManager();
       if(pMana)
       {
          mark=pMana->GetMarkFromPtr(ptr);
          if(mark>0)
    pMana->AddCount(mark,pointee);
       }
   }

}

   當到了這裡時，我便以為大功告成，忍不住摸拳搽掌，很想試一試。結果發現對於一般的情況，效果確實不錯，達到了垃圾回收的效果。如下面的應用：
    auto_ptr p1=new  test;
       auto_ptrp2 = p1;
       auto_ptrp3 = new test;
    但是，很快地，我在測試前面提到的回環時，就發現了問題，我是這樣測試的：

以下為引用的內容：
    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 。當程序執行離開作用域後，p1，p2被析構，使它們的引用記數都為1，此後再沒有靈巧指針被析構而使它們的引用記數變為 0 ，因此它們將長期保留在堆中。這就象兩個被鎖住的箱子，其中每個箱子中都裝著對方的鑰匙，但卻無法把彼此打開，這就是互鎖現象。
      可是如何解決呢？看來必須對它進行改進。同時，我也發現上面的方法不支持多線程。所以，我們改進後的方法不僅要解決互鎖現象，而且還要支持多線程。下面是我改進後的方法：
   首先是如何發現這種互鎖現象。我們知道，互鎖現象產生的根源在於擁有堆中內存的靈巧指針本身也存在於已分配的堆內存中，那麼，如何發現靈巧指針是存在於堆中還是棧中就成了問題的關鍵。由此，我引入了一個新的類 CPtr，由它來管理用 new 分配的指針，而 CPtrManager 專門用來管理 CPtr。如下所示：

以下為引用的內容：
class CPtr
{
 frIEnd class CMark;
public:
 int GetPtrSize();  file://得到用 new 分配指針的內存的大小
 CMutex * GetCMutex(); file://用於線程同步
 void * GetPtr(); file://得到用 new 分配的指針
 CPtr();
 virtual ~CPtr();
 int GetCount(); file://得到引用記數
           void AddAutoPtr(void * autoPtr,int AutoMark);//加入一個擁有該指針的靈巧指針
 BOOL DeleteAutoPtr(void * autoPtr); file://釋放一個靈巧指針的擁有權
 void SetPtr(void * thePtr,int Size,          int mark,int count=0);  file://設置一個新的指針

 
    void Operator delete(void * p)
 {
   free(p);
 }
    void * Operator new(size_t size)
 {   
      return malloc(size);
 }

private:
 int m_mark;  file://指針標志
 int m_count; file://引用記數
 void * m_ptr; file://分配的指針
 int m_size; file://指針指向內存的大小
 CPtrArray AutoPtrArray; file://存放擁有該指針的所有靈巧指針的指針數組
 CUIntArray m_AutoMark; file://靈巧指針標志：0 in the stack; >0 =mark 
 CMutex mutex; file://用於線程同步
};
class CPtrManager  
{
public:
 int GetAutoMark(void * ptr); file://通過靈巧指針的指針，得到靈巧指針標志
 CPtrManager();
 virtual ~CPtrManager();
 int GetMarkFromPtr(void * Ptr);
 void *MallocPtr(size_t size);
           BOOL 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; file://存放 CPtr 的指針數組
 void*  pCurrent;
 unsigned int m_mark;
 CUIntArray m_removed;
 BOOL bWrite; file://在解決互鎖現象的過程中，謝絕其它線程的處理
 static CPtrManager * p_this;
 CMutex mutex;//用於線程同步
 CMarkTable myMarkTable;
 void RemoveLockRes(); file://處理互鎖內存
 void CopyAllMark(); file://處理互鎖現象前，先對所有的CPtr進行拷貝
 static UINT myThreadProc(LPVOID lparm); file://處理互鎖現象的線程函數
 CWinThread* myThread;
 void BeginThread()
 { myThread=AfxBeginThread(myThreadProc,this,THREAD_PRIORITY_ABOVE_NORMAL);}
};

   上面的應用中加入了靈巧指針的標志，其實，這個標志就等於該靈巧指針所存在的內存的指針的標志。例如：我們用 new 分配了一個 test 指針，假如這個指針的標志 mark=1，那麼，這個 test 中的靈巧指針 auto_ptr p 的標志 automark=1。如果一個靈巧指針存在於棧中，那麼它的 automark=0。反之亦然，如果一個靈巧指針的 automark 等於一個指針的 mark，那麼，該靈巧指針必存在於這個指針所指的內存中。可是，如何得到這個標志呢，請看下面這個函數的實現：

以下為引用的內容：
int CPtrManager::GetAutoMark(void *ptr)
{
    CSingleLock singleLock(&mutex);
    singleLock.Lock(); file://線程同步

  int size =m_ptr.GetSize();
  for(int i=1;i  {
      CPtr* theCPtr=(CPtr*)m_ptr[i];
      if(theCPtr)
      {
   int ptrFirst=(int)theCPtr->GetPtr();//得到內存的首指針
   int ptrEnd=ptrFirst+theCPtr->GetPtrSize();//得到內存的尾指針
   int p=(int)ptr; file://靈巧指針的指針
   if(p>=ptrFirst&&p<=ptrEnd)//比較靈巧指針的指針是否在首尾之間

                   return  i;
      }
  }
  return 0;
}

    這個函數的原理就在於：如果一個靈巧指針存在於一塊內存中，那麼該靈巧指針的指針必在這塊內存的首尾指針之間。
    解決了靈巧指針的位置問題，下一步就是要找出所有被互鎖的內存的指針。這個好實現，只要所有擁有這個指針的靈巧指針的 automark > 0 ，那麼，這塊內存就可能被互鎖了(注意只是可能)，接著看下面的實現：

以下為引用的內容：
class CMark
{
 frIEnd class CMarkTable;
public:
 CMark(){}
 virtual ~CMark(){}

    void Operator delete(void * p)
 {
   free(p);
 }
    void * Operator new(size_t size)
 {   
            return malloc(size);
 }
 void CopyFromCPtr(CPtr* theCPtr); file://從 CPtr 中拷貝相關信息
 BOOL bIsNoneInStack(); file://判斷擁有該指針的所有靈巧指針是否都不在棧中
 void Release(); file://解除該指針的互鎖 
private:
 int m_mark; file://指針的標志
 CPtrArray autoptrArray; file://擁有該指針的所有靈巧指針的指針數組
 CUIntArray automarkArray;//擁有該指針的所有靈巧指針的標志

};
class CMarkTable
{
public:
 CMarkTable(){Init();}
 virtual ~CMarkTable(){}
 
 void AddCMark(CMark * theCMark);
 BOOL FindMark(int mark);
 void Init();
 void DoLockMark(); file://處理互鎖問題
private:
 CPtrArray CMarkArray; file://暫存從CPtrManager 中拷貝過來的指針信息的 CMark 指針數組
 CPtrArray CLockMarkArray; file://存放互鎖的內存
 void GetLockMark(); file://得到所有可能被互鎖的內存的 CMark，結果存放於CLockMarkArray
 BOOL FindLockMark(int mark); file://判斷一個靈巧指針是否存在於CLockMarkArray所包含的指針中
 void RemoveUnlockMark();//去除假的互鎖內存
 void RemoveGroup(int automark);//對互相有聯系的相互死鎖的內存進行分組

};

   這裡又引入了兩個類：CMark 和 CMarkTable ，這是為了在處理互鎖問題之前，對 CPtrManager 中的 CPtr 進行快速拷貝，以防止影響其它線程的正常運行。其實，這裡的 CMark 與 CPtr 沒有什麼區別，它只是簡單地從 CPtr 中拷貝信息，也就是說，它等同於 CPtr 。
   為了處理互鎖問題，先要把可能被互鎖的內存指針找出來，看下面函數的實現：

以下為引用的內容：

void CMarkTable::GetLockMark()
{
 CLockMarkArray.SetSize(0);
 int size=CMarkArray.GetSize();
 for(int i=0;i {
  CMark * theMark=(CMark*)CMarkArray[i];
  if(theMark)
  {
    if(theMark->bIsNoneInStack())
      CLockMarkArray.SetAtGrow(i,theMark);
  }
 }
}

   把這些內存找出來之後，就需要把那些假鎖的內存找出來，什麼是假鎖呢？看下面的例子：
   對於指針 ptrA ，如果它的靈巧指針 autoA 存在於指針 ptrB 中，而 ptrB 的靈巧指針 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=CLockMarkArray.GetSize();
 for(int i=0;i {
    CMark * theMark=(CMark*)CLockMarkArray[i];
    if(theMark)
    {
       int size1=(theMark->automarkArray).GetSize();
                 for(int j=0;j       { 
         int mark=(theMark->automarkArray)[j];
         if(!FindLockMark(mark)) file://判斷靈巧指針是否存在於CLockMarkArray所包含的指針中
         {
  UnlockMarkArray.InsertAt(0,i); file://record to remove
  bNoneRemoveed=FALSE;
  break;
          }
        }
     }
    else
    {         UnlockMarkArray.InsertAt(0,i);
       bNoneRemoveed=FALSE;
     }
 }
 int size2=UnlockMarkArray.GetSize();
 for(int k=0;k {
    int m=UnlockMarkArray[k];
    CLockMarkArray.RemoveAt(m);
 }
}while(!bNoneRemoveed);

}

    上面函數的原理就是：不停地刪除那些靈巧指針不在CLockMarkArray所包含的指針中的指針，直到所有的指針的靈巧指針都存在於CLockMarkArray所包含的指針中。
    所有被互鎖的內存被找出來了，那麼，下一步就是如何解鎖的問題了。由此，我對靈巧指針引入了一個父類parent_autoptr 如下：

以下為引用的內容：

class parent_autoptr
{
public:
 parent_autoptr()
 {thisAutoMark=0;}
 virtual ~parent_autoptr(){}
 virtual void Release(){} file://釋放指針的擁有權
protected:
 int thisAutoMark; file://存放靈巧指針標志
};

    在靈巧指針中，對函數 Release() 進行了重載。

以下為引用的內容：
template
class auto_ptr :public parent_autoptr
{
   public:
    virtual void Release(){Remove();}
    auto_ptr()
    {mark=0;pointee=0;thisAutoMark=GetAutoMark();}
    auto_ptr(auto_ptr&rhs);
    auto_ptr(T*ptr);
    ~auto_ptr(){Remove();}
    T*Operator->() const;
    Operator T*(); 
    T&Operator*()const;
    auto_ptr&Operator=(auto_ptr&rhs); 
              auto_ptr&Operator=(T*ptr); 
   private:
              void Remove();
    int GetAutoMark();
    CMutex *GetCMutex();
    void ReadyWrite();
    T*pointee;
    int mark;
    
};

    在 CMarkTable 和 CMark 中對互鎖內存進行了釋放，如下：

以下為引用的內容：

void CMarkTable::DoLockMark()
{
GetLockMark();
RemoveUnlockMark();

int size=CLockMarkArray.GetSize();
while(size)
{
 CMark* theMark=(CMark*)CLockMarkArray[0];
 CLockMarkArray.RemoveAt(0);
 if(theMark)
 {
    int size2=(theMark->automarkArray).GetSize();
    for(int i=0;i    {
       int automark=（theMark->automarkArray)[i];
       RemoveGroup(automark);
     }
    theMark->Release();
 
 }
 size=CLockMarkArray.GetSize();
}

Init();
}

void CMark::Release()
{
    int size=autoptrArray.GetSize();
    for(int i=0;i   {
 parent_autoptr * thePtr=(parent_autoptr *)autoptrArray[i];
 thePtr->Release();
   }
}

       到了現在，終於算是大功告成了，我馬上把它投入測試當中，發現工作得非常好，即使開辟20至30個線程，程序也工作得很好，並沒有拋出異常，而且垃圾回收的功能也非常好。但是，如果線程太多，那麼在 CPtrManager 中為了保證線程同步，將會造成瓶頸效應，嚴重者將會嚴重影響執行效率。同時，如果每個線程都不停地產生死鎖內存，那麼，垃圾回收將應接不暇，時間長了，也會造成系統的資源耗盡。

    代碼的使用很簡單，你只需要將我所附的兩個文件加入到工程中，然後，在你的 C*App 中加入如下一段代碼就行了：

     CPtrManager thePtrManager;

    這將保證 thePtrManager 在進程最後結束的時候才被析構。

    如果你是在一個新的工程中使用，這就夠了，但是，如果你還要使用原來的代碼，特別是有指針參數的傳遞時，那麼，你必須注意了。

    如果需要從老代碼中接收一個指針，而且這個指針需要你自己釋放，那麼可以使用靈巧指針，如果不需要釋放，那麼只能使用一般指針；
    如果需要傳遞一個指針給老代碼，而且這個指針需要你自己釋放，那麼可以使用靈巧指針，否則，只能使用一般指針。