《靈巧指針與垃圾回收》由會員分享，可在線閱讀，更多相關(guān)《靈巧指針與垃圾回收（10頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、 靈巧指針與內(nèi)存回收
在JAVA 和 C# 中都有垃圾回收功能，程序員在分配一段內(nèi)存后可以不再理會，而由垃圾回收自動回收，從而使程序員從復(fù)雜的內(nèi)存管理中解脫出來。這是JAVA 和 C#的一大優(yōu)點(diǎn)。而C++程序員在用 new 分配了一段內(nèi)存后，還必須用 delete 釋放，否則將造成資源泄漏。因此，一些C++ 書上經(jīng)常告誡程序員：要養(yǎng)成好的習(xí)慣，new 與 delete 要成對出現(xiàn)，時(shí)刻記住將內(nèi)存釋放回系統(tǒng)。但是，事情只是這么簡單嗎？
經(jīng)常地，在使用C++的過程中，我們會遇到下面的情形：
class A
2、 {
public：
A（）；
~A（）；
SetNextPtr（A* Ptr）
{pNext=Ptr；}
private：
A * pNext；
}
一般地，為了不引起內(nèi)存泄漏，我們會在析構(gòu)函數(shù)中釋放pNext，象下面這樣：
A：：~A（）
3、 {
if（pNext）
delete pNext；
pNext=NULL;
}
對于一般情況，這樣就夠了，但在某些情形下，這樣也會出問題的，象下面這樣：
A *ptrB = new A;；
A *ptrA = new A；
ptrB->SetNextPtr(ptrA);
ptrA->SetNextPtr(ptrB);
delete
4、 ptrB;
這樣會出問題,因?yàn)檫@些指針連成了一個(gè)回環(huán),無論從那一個(gè)點(diǎn)開始刪除,都會造成一個(gè)指針被刪除兩次以上,這將使得程序拋出異常。當(dāng)然，也有一些方法可以用來解決這個(gè)問題，但是我要說明的是：對于C++程序員來說，養(yǎng)成一個(gè)好的習(xí)慣并不難，難就難在有時(shí)候這樣將把你帶入一種邏輯的混亂當(dāng)中 ，增加一些不必要的麻煩，有時(shí)甚至不知所措。
可是如何解決這個(gè)問題呢？如果C++也具有垃圾回收的功能，那么，這個(gè)問題當(dāng)然就迎刃而解了。但是C++屬于編譯型語言，不會具備這個(gè)功能。長期以來，我也一直在思考這個(gè)問題，想找出一種方法來使自己從這種麻煩中解脫出來。直到最近開始學(xué)習(xí)泛型編程，看到
5、靈巧指針的介紹以后，我靈光一閃，終于找到了辦法來解決這個(gè)問題。
大家知道，靈巧指針具有一些靈巧特性，如在構(gòu)造時(shí)可以自動初始化，析構(gòu)時(shí)可以自動釋放所指的指針。我們就利用它的這些特性來實(shí)現(xiàn)我們的垃圾回收。
首先，我們要想辦法來對我們用 new 分配的每一段內(nèi)存增加引用記數(shù)，即記錄下當(dāng)前指向它的靈巧指針個(gè)數(shù)，當(dāng)最后一個(gè)指向它的指針被釋放時(shí)，我們就可以釋放這段內(nèi)存了。由此，我們進(jìn)行了new 和 delete 的全局重載，并引入了CPtrManager 類。
void operator delete(void * p)
{
int mark=thePtrManage
6、r.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); //得到當(dāng)前的引用記數(shù)
static CPtrManager* GetPtrManager(); /
7、/得到全局唯一的CPtrManager 指針
void UserDelete(int mark); //刪除 mark 標(biāo)志的指針，并對指針和標(biāo)志復(fù)位
void * MallocPtr(size_t size); //new（）調(diào)用它分配內(nèi)存；
BOOL AddCount(int mark,void * Ptr); //增加引用記數(shù)
BOOL Release(int mark,void * Ptr); //減少引用記數(shù)
int GetMarkFromPtr(void * Ptr); //通過指針得到標(biāo)志
CPtrManager();
virtual ~CPtrM
8、anager();
private:
static CPtrManager * p_this; //指向全局唯一的CPtrManager 指針
void AddPtr(void * Ptr); //增加一個(gè)新分配的內(nèi)存
CPtrArray m_ptr; //存放分配的指針的可變數(shù)組
CUIntArray m_count; //存放指針的引用記數(shù)
void* pCurrent; //最近剛分配的指針
unsigned int m_mark; //最近剛分配的指針的標(biāo)志
CUIntArray m_removed;//存放m_ptr中
9、指針被刪除后所空留的位置
};
顧名思義，CPtrManager 就是用來管理指針的，對于我們用new 分配的每一個(gè)指針，都存放在m_ptr[index]中，并在m_count[index]中存放它的引用記數(shù)。同時(shí)，我們對每一個(gè)指針都增加了一個(gè)標(biāo)志（mark >0,<=0為無效），這個(gè)標(biāo)志同時(shí)存在于靈巧指針中（后面將看到），這是為了一種雙重保險(xiǎn)，并且在這里，這個(gè)標(biāo)志就等于指針在m_ptr中的索引，這也為快速查找提供了方便。
總的思路是這樣的：當(dāng)我們用new分配一個(gè)指針時(shí)，這個(gè)指針將被存入CPtrManager中，當(dāng)一個(gè)靈巧指針開始擁有這個(gè)指針時(shí)，CPtrMan
10、ager將負(fù)責(zé)對這個(gè)指針的引用記數(shù)加 1 ，反之亦然，即一個(gè)靈巧指針開始釋放該指針的擁有權(quán)時(shí)，CPtrManager將負(fù)責(zé)對這個(gè)指針的引用記數(shù)減 1 ，如果引用記數(shù)為 0 ，那么這個(gè)靈巧指針將負(fù)責(zé)對該指針 delete。
下面是靈巧指針的部分介紹：
template<class T>
class auto_ptr
{
public:
auto_ptr()
{mark=0;pointee=0;}
auto_ptr(auto_ptr<T>&rhs);
auto_ptr(T*ptr);
~aut
11、o_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(); //釋放所指指針的擁有權(quán)
T*pointee; //所擁有的指針
12、int mark;//所擁有的指針的標(biāo)志
};
template<class T> void auto_ptr< T>::Remove()
{
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pointee&&pMana)
{
if(pMana->Release(mark,pointee)) //減少引用記數(shù)
{
if(pMana->GetCount(mark,pointee) ==0)
delet
13、e pointee; //如果引用記數(shù)為0，delete 指針
}
else //所擁有的指針不在CPtrManager 中，有可能在棧中
{
//User decide to do
}
}
pointee=NULL; //復(fù)位
mark=0;
}
template<class T> auto_ptr< T>::auto_ptr(auto_ptr<T>&rhs)
{
pointee=rhs.pointee;
mark=rhs.mark;
CPtrMa
14、nager * pMana=CPtrManager::GetPtrManager();
if(pMana)
pMana->AddCount(mark,pointee); //增加引用記數(shù)
}
template<class T> auto_ptr< T>::auto_ptr(T*ptr)
{
mark=0;
pointee=ptr;
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pMana)
{
15、 mark=pMana->GetMarkFromPtr(ptr); //得到指針的標(biāo)志
if(mark>0)
pMana->AddCount(mark,pointee); //如果標(biāo)志不為0，增加引用記數(shù)
}
}
template<class T>auto_ptr<T>& auto_ptr< T>::operator=(auto_ptr<T>&rhs)
{
if(pointee!=rhs.pointee)
{
Remove();
16、//釋放當(dāng)前指針的擁有權(quán)
pointee=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(
17、pointee!=ptr)
{
Remove();
pointee=ptr;
CPtrManager * pMana=CPtrManager::GetPtrManager();
if(pMana)
{
mark=pMana->GetMarkFromPtr(ptr);
if(mark>0)
pMana->AddCount(mark,pointee);
}
}
}
當(dāng)?shù)搅诉@里時(shí)，我便以為大功告成，忍不住
18、摸拳搽掌，很想試一試。結(jié)果發(fā)現(xiàn)對于一般的情況，效果確實(shí)不錯(cuò)，達(dá)到了垃圾回收的效果。如下面的應(yīng)用：
auto_ptr<test> p1=new test;
auto_ptr<test>p2 = p1;
auto_ptr<test>p3 = new test;
但是，很快地，我在測試前面提到的回環(huán)時(shí)，就發(fā)現(xiàn)了問題，我是這樣測試的：
class test
{
auto_ptr<test> p;
};
auto_p
19、tr<test> p1=new test;
auto_ptr<test>p2 =new test;
p1->p=p2;
p2->p=p1;
當(dāng)程序執(zhí)行離開作用域后，這兩塊內(nèi)存并沒有象我想象的那樣被釋放，而是一直保留在堆中，直到程序結(jié)束。我仔細(xì)分析造成這種現(xiàn)象的原因，發(fā)現(xiàn)了一個(gè)非常有趣的問題，我把它稱之為互鎖現(xiàn)象。
上面p1 所擁有的指針被兩個(gè)靈巧指針?biāo)鶕碛?，除p1外，還有p2所擁有的 test 類中的靈巧指針p，p2亦然。也就是說，這兩塊內(nèi)存的指針的引用記數(shù)都為 2 。當(dāng)程序執(zhí)行離開作用域
20、后，p1，p2被析構(gòu)，使它們的引用記數(shù)都為1，此后再沒有靈巧指針被析構(gòu)而使它們的引用記數(shù)變?yōu)?0 ，因此它們將長期保留在堆中。這就象兩個(gè)被鎖住的箱子，其中每個(gè)箱子中都裝著對方的鑰匙，但卻無法把彼此打開，這就是互鎖現(xiàn)象。
可是如何解決呢？看來必須對它進(jìn)行改進(jìn)。同時(shí)，我也發(fā)現(xiàn)上面的方法不支持多線程。所以，我們改進(jìn)后的方法不僅要解決互鎖現(xiàn)象，而且還要支持多線程。下面是我改進(jìn)后的方法：
首先是如何發(fā)現(xiàn)這種互鎖現(xiàn)象。我們知道，互鎖現(xiàn)象產(chǎn)生的根源在于擁有堆中內(nèi)存的靈巧指針本身也存在于已分配的堆內(nèi)存中，那么，如何發(fā)現(xiàn)靈巧指針是存在于堆中還是棧中就成了問題的關(guān)鍵。由此，我引入了一個(gè)新的類
21、 CPtr，由它來管理用 new 分配的指針，而 CPtrManager 專門用來管理 CPtr。如下所示：
class CPtr
{
friend class CMark;
public:
int GetPtrSize(); //得到用 new 分配指針的內(nèi)存的大小
CMutex * GetCMutex(); //用于線程同步
void * GetPtr(); //得到用 new 分配的指針
CPtr();
virtual ~CPtr();
int GetCount(); //得到引用記數(shù)
void AddAutoPtr(void
22、* autoPtr,int AutoMark);//加入一個(gè)擁有該指針的靈巧指針
BOOL DeleteAutoPtr(void * autoPtr); //釋放一個(gè)靈巧指針的擁有權(quán)
void SetPtr(void * thePtr,int Size, int mark,int count=0); //設(shè)置一個(gè)新的指針
void operator delete(void * p)
{
free(p);
}
void * operator new(size_t size)
{
return mallo
23、c(size);
}
private:
int m_mark; //指針標(biāo)志
int m_count; //引用記數(shù)
void * m_ptr; //分配的指針
int m_size; //指針指向內(nèi)存的大小
CPtrArray AutoPtrArray; //存放擁有該指針的所有靈巧指針的指針數(shù)組
CUIntArray m_AutoMark; //靈巧指針標(biāo)志：0 in the stack; >0 =mark
CMutex mutex; //用于線程同步
};
class CPtrManager
{
public:
int Ge
24、tAutoMark(void * ptr); //通過靈巧指針的指針，得到靈巧指針標(biāo)志
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();
25、
CPtr * GetCPtr(void * Ptr,int mark);//通過指針和指針標(biāo)志得到存放該指針的 CPtr
private:
CPtrArray m_ptr; //存放 CPtr 的指針數(shù)組
void* pCurrent;
unsigned int m_mark;
CUIntArray m_removed;
BOOL bWrite; //在解決互鎖現(xiàn)象的過程中，謝絕其它線程的處理
static CPtrManager * p_this;
CMutex mutex;//用于線程同步
CMarkTable myMarkT
26、able;
void RemoveLockRes(); //處理互鎖內(nèi)存
void CopyAllMark(); //處理互鎖現(xiàn)象前，先對所有的CPtr進(jìn)行拷貝
static UINT myThreadProc(LPVOID lparm); //處理互鎖現(xiàn)象的線程函數(shù)
CWinThread* myThread;
void BeginThread()
{ myThread=AfxBeginThread(myThreadProc,this,THREAD_PRIORITY_ABOVE_NORMAL);}
};
上面的應(yīng)用中加入了靈巧指針的標(biāo)志，其實(shí)，這個(gè)標(biāo)志就等于該
27、靈巧指針?biāo)嬖诘膬?nèi)存的指針的標(biāo)志。例如：我們用 new 分配了一個(gè) test 指針，假如這個(gè)指針的標(biāo)志 mark=1，那么，這個(gè) test 中的靈巧指針 auto_ptr<test> p 的標(biāo)志 automark=1。如果一個(gè)靈巧指針存在于棧中，那么它的 automark=0。反之亦然，如果一個(gè)靈巧指針的 automark 等于一個(gè)指針的 mark，那么，該靈巧指針必存在于這個(gè)指針?biāo)傅膬?nèi)存中?？墒?，如何得到這個(gè)標(biāo)志呢，請看下面這個(gè)函數(shù)的實(shí)現(xiàn)：
int CPtrManager::GetAutoMark(void *ptr)
{
CSingleLock singleLo
28、ck(&mutex);
singleLock.Lock(); //線程同步
int size =m_ptr.GetSize();
for(int i=1;i<size;i++)
{
CPtr* theCPtr=(CPtr*)m_ptr[i];
if(theCPtr)
{
int ptrFirst=(int)theCPtr->GetPtr();//得到內(nèi)存的首指針
int ptrEnd=ptrFirst+theCPtr->GetPtrSize();//得到內(nèi)存的尾指針
in
29、t p=(int)ptr; //靈巧指針的指針
if(p>=ptrFirst&&p<=ptrEnd)//比較靈巧指針的指針是否在首尾之間
return i;
}
}
return 0;
}
這個(gè)函數(shù)的原理就在于：如果一個(gè)靈巧指針存在于一塊內(nèi)存中，那么該靈巧指針的指針必在這塊內(nèi)存的首尾指針之間。
解決了靈巧指針的位置問題，下一步就是要找出所有被互鎖的內(nèi)存的指針。這個(gè)好實(shí)現(xiàn)，只要所有擁有這個(gè)指針的靈巧指針的 automark > 0 ，那么，這塊內(nèi)存就可能被互鎖了(注
30、意只是可能)，接著看下面的實(shí)現(xiàn)：
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); //從 CPtr 中拷貝相關(guān)信息
31、 BOOL bIsNoneInStack(); //判斷擁有該指針的所有靈巧指針是否都不在棧中
void Release(); //解除該指針的互鎖
private:
int m_mark; //指針的標(biāo)志
CPtrArray autoptrArray; //擁有該指針的所有靈巧指針的指針數(shù)組
CUIntArray automarkArray;//擁有該指針的所有靈巧指針的標(biāo)志
};
class CMarkTable
{
public:
CMarkTable(){Init();}
virtual ~CMarkTable(){}
void AddC
32、Mark(CMark * theCMark);
BOOL FindMark(int mark);
void Init();
void DoLockMark(); //處理互鎖問題
private:
CPtrArray CMarkArray; //暫存從CPtrManager 中拷貝過來的指針信息的 CMark 指針數(shù)組
CPtrArray CLockMarkArray; //存放互鎖的內(nèi)存
void GetLockMark(); //得到所有可能被互鎖的內(nèi)存的 CMark，結(jié)果存放于CLockMarkArray
BOOL FindLockMark(int mark
33、); //判斷一個(gè)靈巧指針是否存在于CLockMarkArray所包含的指針中
void RemoveUnlockMark();//去除假的互鎖內(nèi)存
void RemoveGroup(int automark);//對互相有聯(lián)系的相互死鎖的內(nèi)存進(jìn)行分組
};
這里又引入了兩個(gè)類：CMark 和 CMarkTable ，這是為了在處理互鎖問題之前，對 CPtrManager 中的 CPtr 進(jìn)行快速拷貝，以防止影響其它線程的正常運(yùn)行。其實(shí)，這里的 CMark 與 CPtr 沒有什么區(qū)別，它只是簡單地從 CPtr 中拷貝信息，也就是說，它等同于 CPtr 。
為了處理
34、互鎖問題，先要把可能被互鎖的內(nèi)存指針找出來，看下面函數(shù)的實(shí)現(xiàn)：
void CMarkTable::GetLockMark()
{
CLockMarkArray.SetSize(0);
int size=CMarkArray.GetSize();
for(int i=0;i<size;i++)
{
CMark * theMark=(CMark*)CMarkArray[i];
if(theMark)
{
if(theMark->bIsNoneInStack())
CLockMarkArray.SetAtGrow(i,theM
35、ark);
}
}
}
把這些內(nèi)存找出來之后，就需要把那些假鎖的內(nèi)存找出來，什么是假鎖呢？看下面的例子：
對于指針 ptrA ，如果它的靈巧指針 autoA 存在于指針 ptrB 中，而 ptrB 的靈巧指針 autoB 又存在于 ptrA 中，那么 ptrA 和 ptrB 是真鎖，但是如果ptrB 的靈巧指針 autoB 存在于指針 ptrC 中，而 ptrC的靈巧指針 autoC 存在于棧中，那么， ptrA 和 ptrB 屬于假鎖。怎么找出假鎖的內(nèi)存呢？看下面函數(shù)的實(shí)現(xiàn)：
void CMarkTable::RemoveUnlockMark()
{
CUI
36、ntArray UnlockMarkArray;
BOOL bNoneRemoveed;
do
{
bNoneRemoveed=TRUE;
UnlockMarkArray.SetSize(0);
int size=CLockMarkArray.GetSize();
for(int i=0;i<size;i++)
{
CMark * theMark=(CMark*)CLockMarkArray[i];
if(theMark)
{
int size1=(theMark->automarkArray).GetSiz
37、e();
for(int j=0;j<size1;j++)
{
int mark=(theMark->automarkArray)[j];
if(!FindLockMark(mark)) //判斷靈巧指針是否存在于CLockMarkArray所包含的指針中
{
UnlockMarkArray.InsertAt(0,i); //record to remove
bNoneRemoveed=FALSE;
break;
}
38、 }
}
else
{ UnlockMarkArray.InsertAt(0,i);
bNoneRemoveed=FALSE;
}
}
int size2=UnlockMarkArray.GetSize();
for(int k=0;k<size2;k++)
{
int m=UnlockMarkArray[k];
CLockMarkArray.RemoveAt(m);
}
}while(!bNoneRemoveed);
}
上面函數(shù)的原理就是：不停地刪除
39、那些靈巧指針不在CLockMarkArray所包含的指針中的指針，直到所有的指針的靈巧指針都存在于CLockMarkArray所包含的指針中。
所有被互鎖的內(nèi)存被找出來了，那么，下一步就是如何解鎖的問題了。由此，我對靈巧指針引入了一個(gè)父類parent_autoptr 如下：
class parent_autoptr
{
public:
parent_autoptr()
{thisAutoMark=0;}
virtual ~parent_autoptr(){}
virtual void Release(){} //釋放指針的擁有權(quán)
protected:
in
40、t thisAutoMark; //存放靈巧指針標(biāo)志
};
在靈巧指針中，對函數(shù) Release() 進(jìn)行了重載。
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);
aut
41、o_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 GetAu
42、toMark();
CMutex *GetCMutex();
void ReadyWrite();
T*pointee;
int mark;
};
在 CMarkTable 和 CMark 中對互鎖內(nèi)存進(jìn)行了釋放，如下：
void CMarkTable::DoLockMark()
{
GetLockMark();
RemoveUnlockMark();
int size=CLockMarkArray.GetSize();
while(size)
{
CMark* theMark=(CMark*)CLockMa
43、rkArray[0];
CLockMarkArray.RemoveAt(0);
if(theMark)
{
int size2=(theMark->automarkArray).GetSize();
for(int i=0;i<size2;i++)
{
int automark=（theMark->automarkArray)[i];
RemoveGroup(automark);
}
theMark->Release();
}
size=CLockMarkArr
44、ay.GetSize();
}
Init();
}
void CMark::Release()
{
int size=autoptrArray.GetSize();
for(int i=0;i<size;i++)
{
parent_autoptr * thePtr=(parent_autoptr *)autoptrArray[i];
thePtr->Release();
}
}
到了現(xiàn)在，終于算是大功告成了，我馬上把它投入測試當(dāng)中，發(fā)現(xiàn)工作得非常好，即使開辟20至30個(gè)線程，程序也工作得很好，并沒有
45、拋出異常，而且垃圾回收的功能也非常好。但是，如果線程太多，那么在 CPtrManager 中為了保證線程同步，將會造成瓶頸效應(yīng)，嚴(yán)重者將會嚴(yán)重影響執(zhí)行效率。同時(shí)，如果每個(gè)線程都不停地產(chǎn)生死鎖內(nèi)存，那么，垃圾回收將應(yīng)接不暇，時(shí)間長了，也會造成系統(tǒng)的資源耗盡。
代碼的使用很簡單，你只需要將我所附的兩個(gè)文件加入到工程中，然后，在你的 C*App 中加入如下一段代碼就行了：
CPtrManager thePtrManager;
這將保證 thePtrManager 在進(jìn)程最后結(jié)束的時(shí)候才被析構(gòu)。
如果你是在一個(gè)新的工程中使用，這就夠了，但是，如果你還要使用原來的代碼，特別是有指針參數(shù)的傳遞時(shí)，那么，你必須注意了。
如果需要從老代碼中接收一個(gè)指針，而且這個(gè)指針需要你自己釋放，那么可以使用靈巧指針，如果不需要釋放，那么只能使用一般指針；
如果需要傳遞一個(gè)指針給老代碼，而且這個(gè)指針需要你自己釋放，那么可以使用靈巧指針，否則，只能使用一般指針。
我將隨后附上所有源代碼，由于沒有經(jīng)過嚴(yán)格測試，所以大家在使用前最好再測試一遍，最好能將發(fā)現(xiàn)的問題公布或?qū)懶鸥嬷谖?，本人表示感謝。
歡迎大家下載測試，批評指正和改進(jìn)，
Email: ydshzhy@
靈巧指針與垃圾回收
