睿豐德科技 專注RFID識別技術和條碼識別技術與管理軟件的集成項目。質量追溯系統、MES系統、金蝶與條碼系統對接、用友與條碼系統對接

1.引用計數算法

         引用計數（Reference Counting）算法是每個對象計算指向它的指針的數量，當有一個指針指向自己時計數值加1；當刪除一個指向自己的指針時，計數值減1，如果計數值減為0，說明已經不存在指向該對象的指針了，所以它可以被安全的銷毀了。可以很直觀的用下面的圖表示：

 

 

      引用計數算法的優點在于內存管理的開銷分布于整個應用程序運行期間，非常的“平滑”，無需掛起應用程序的運行來做垃圾回收；而它的另外一個優勢在于空間上的引用局部性比較好，當某個對象的引用計數值變為0時，系統無需訪問位于堆中其他頁面的單元，而后面我們將要看到的幾種垃圾回收算法在回收前都回遍歷所有的存活單元，這可能會引起換頁（Paging）操作；最后引用計數算法提供了一種類似于棧分配的方式，廢棄即回收，后面我們將要看到的幾種垃圾回收算法在對象廢棄后，都會存活一段時間，才會被回收。

     引用計數算法有著諸多的優點，但它的缺點也是很明顯的。首先能看到的一點是時間上的開銷，每次在對象創建或者釋放時，都要計算引用計數值，這會引起一些額外的開銷；第二是空間上的開銷，由于每個對象要保持自己被引用的數量，必須付出額外的空間來存放引用計數值；引用計數算法最大的缺點就在于它無法處理環形引用，如下圖所示：

       此 處藍色的這兩個對象既不可達也無法回收，因為彼此之間互相引用，它們各自的計數值都不為0，這種情況對引用計數算法來說是無能為力的，而其他的垃圾回收算法卻能很好的處理環形引用。

引用計數算法最著名的運用，莫過于微軟的COM技術，大名鼎鼎的IUnknown接口：

[cpp] view plaincopy

1. interface IUnknown  
2. {  
3.     virtual HRESULT _stdcall QueryInterface  
4.         (const IID& iid, void* * ppv) = 0;  
5.     virtual ULONG _stdcall AddRef() = 0;  
6.     virtual ULONG _stdcall Release() = 0;  
7. }  

 

其中的AddRef和Release就是用來讓組件自己管理其生命周期，而客戶程序只關心接口，而無須再去關心組件的生命周期，一個簡單的使用示例如下：

[cpp] view plaincopy

1. int main()  
2. {  
3.     IUnknown* pi = CreateInstance();  
4.   
5.     IX* pix = NULL;  
6.     HRESULT hr = pi->QueryInterface(IID_IX, (void*)&pix);  
7.     if(SUCCEEDED(hr))  
8.     {  
9.         pix->DoSomething();  
10.         pix->Release();  
11.     }  
12.   
13.     pi->Release();  
14. }  

上面的客戶程序在CreateInstance中已經調用過AddRef，所以無需再次調用，而在使用完接口后調用Release，這樣組件自己維護的計數值將會改變。下面代碼給出一個簡單的實現AddRef和Release示例：

[cpp] view plaincopy

1. ULONG _stdcall AddRef()  
2. {  
3.     return ++ m_cRef;  
4. }  
5.   
6. ULONG _stdcall Release()  
7. {  
8.     if(--m_cRef == 0)  
9.     {  
10.         delete this;  
11.         return 0;  
12.     }  
13.     return m_cRef;  
14. }  

 

     在編程語言Python中，使用也是引用計數算法，當對象的引用計數值為0時，將會調用__del__函數，至于為什么Python要選用引用計數算法，據我看過的一篇文章里面說，由于Python作為腳本語言，經常要與C/C++這些語言交互，而使用引用計數算法可以避免改變對象在內存中的位置，而Python為了解決環形引用問題，也引入gc模塊，所以本質上Python的GC的方案是混合引用計數和跟蹤（后面要講的三個算法）兩種垃圾回收機制。

2.標記-清除算法

標記-清除（Mark-Sweep）算法依賴于對所有存活對象進行一次全局遍歷來確定哪些對象可以回收，遍歷的過程從根出發，找到所有可達對象，除此之外，其它不可達的對象就是垃圾對象，可被回收。整個過程分為兩個階段：標記階段找到所有存活對象；清除階段清除所有垃圾對象。

標記階段

 

清除階段

 

      相比較引用計數算法，標記-清除算法可以非常自然的處理環形引用問題，另外在創建對象和銷毀對象時時少了操作引用計數值的開銷。它的缺點在于標記-清除算法是一種“停止-啟動”算法，在垃圾回收器運行過程中，應用程序必須暫時停止，所以對于標記-清除算法的研究如何減少它的停頓時間，而分代式垃圾收集器就是為了減少它的停頓時間，后面會說到。另外，標記-清除算法在標記階段需要遍歷所有的存活對象，會造成一定的開銷，在清除階段，清除垃圾對象后會造成大量的內存碎片。

3.標記-縮并算法

     標記-縮并算法是為了解決內存碎片問題而產生的一種算法。它的整個過程可以描述為：標記所有的存活對象；通過重新調整存活對象位置來縮并對象圖；更新指向被移動了位置的對象的指針。

標記階段：

 

清除階段：

 

標記-壓縮算法最大的難點在于如何選擇所使用的壓縮算法，如果壓縮算法選擇不好，將會導致極大的程序性能問題，如導致Cache命中率低等。一般來說，根據壓縮后對象的位置不同，壓縮算法可以分為以下三種：

1. 任意：移動對象時不考慮它們原來的次序，也不考慮它們之間是否有互相引用的關系。 
2. 線性：盡可能的將原來的對象和它所指向的對象放在相鄰位置上，這樣可以達到更好的空間局部性。 
3. 滑動：將對象“滑動”到堆的一端，把存活對象之間的自由單元“擠出去”，從而維持了分配時的原始次序。

4.節點拷貝算法

節點拷貝算法是把整個堆分成兩個半區（From，To）， GC的過程其實就是把存活對象從一個半區From拷貝到另外一個半區To的過程，而在下一次回收時，兩個半區再互換角色。在移動結束后，再更新對象的指針引用，GC開始前的情形：

GC結束后的情形：

      節點拷貝算法由于在拷貝過程中，就可以進行內存整理，所以不會再有內存碎片的問題，同時也不需要再專門做一次內存壓縮。，而它最大的缺點在于需要雙倍的空間。

5.總結

      本文總共介紹了四種經典的垃圾回收算法，其中后三種經常稱之為跟蹤垃圾回收，因為引用計數算法能夠平滑的進行垃圾回收，而不會出現“停止”現象，經常出現于一些實時系統中，但它無法解決環形問題；而基于跟蹤的垃圾回收機制，在每一次垃圾回收過程中，要遍歷或者復制所有的存活對象，這是一個非常耗時的工作，一種好的解決方案就是對堆上的對象進行分區，對不同區域的對象使用不同的垃圾回收算法，分代式垃圾回收器正是其中一種，CLR和JVM中都采用了分代式垃圾回收機制，但它們在處理上又有些不同，后面的文章再詳細介紹這兩種垃圾回收器的區別。

 更加詳細請參見于：http://www.cnblogs.com/Terrylee/

RFID管理系統集成商 RFID中間件 條碼系統中間層 物聯網軟件集成