雖然是自己轉(zhuǎn)載的但是是真的好的一篇圖文并茂的對垃圾回收機制的講解!!!
先來個概述，第二部分的畫述才是厲害的袁辈。
Garbage collection(GC)
現(xiàn)在的高級語言如java恢口，c#等隙弛，都采用了垃圾收集機制拂到，而不再是c归榕，c++里用戶自己管理維護內(nèi)存的方式叁征。自己管理內(nèi)存極其自由纳账，可以任意申請內(nèi)存，但如同一把雙刃劍捺疼，為大量內(nèi)存泄露疏虫，懸空指針等bug埋下隱患。
對于一個字符串啤呼、列表卧秘、類甚至數(shù)值都是對象，且定位簡單易用的語言官扣，自然不會讓用戶去處理如何分配回收內(nèi)存的問題翅敌。
python里也同java一樣采用了垃圾收集機制，不過不一樣的是:
python采用的是引用計數(shù)機制為主惕蹄，標記-清除和分代收集兩種機制為輔的策略
引用計數(shù)機制：
python里每一個東西都是對象蚯涮，它們的核心就是一個結(jié)構(gòu)體：PyObject
typedef struct_object {
int ob_refcnt;
struct_typeobject *ob_type;
} PyObject;
PyObject是每個對象必有的內(nèi)容，其中ob_refcnt就是做為引用計數(shù)卖陵。當一個對象有新的引用時遭顶，它的ob_refcnt就會增加，當引用它的對象被刪除泪蔫，它的ob_refcnt就會減少
#define Py_INCREF(op) ((op)->ob_refcnt++) //增加計數(shù)
#define Py_DECREF(op) \ //減少計數(shù)
if (--(op)->ob_refcnt != 0) \
; \
else \
__Py_Dealloc((PyObject *)(op))
當引用計數(shù)為0時棒旗，該對象生命就結(jié)束了。
引用計數(shù)機制的優(yōu)點：
- 簡單
- 實時性：一旦沒有引用鸥滨，內(nèi)存就直接釋放了嗦哆。不用像其他機制等到特定時機谤祖。實時性還帶來一個好處：處理回收內(nèi)存的時間分攤到了平時。
引用計數(shù)機制的缺點：
- 維護引用計數(shù)消耗資源
- 循環(huán)引用
list1 = []
list2 = []
list1.append(list2)
list2.append(list1)
list1與list2相互引用老速，如果不存在其他對象對它們的引用粥喜，list1與list2的引用計數(shù)也仍然為1，所占用的內(nèi)存永遠無法被回收橘券，這將是致命的额湘。
對于如今的強大硬件，缺點1尚可接受旁舰，但是循環(huán)引用導致內(nèi)存泄露锋华，注定python還將引入新的回收機制。(標記清除和分代收集)
轉(zhuǎn)載地址:http://my.oschina.net/hebianxizao/blog/57367?fromerr=KJozamtm
畫說 Ruby 與 Python 垃圾回收
英文原文: visualizing garbage collection in ruby and python
中文:畫說 Ruby 與 Python 垃圾回收
本文基于我在剛剛過去的在布達佩斯舉行的RuPy上的演講箭窜。我覺得趁熱打鐵寫成帖子應該會比只留在幻燈片上更有意義毯焕。你也可以看看演講錄像。再跟你說件事磺樱，我在Ruby大會也會做一個相似的演講纳猫，但是我不會去說Python的事兒，相反我會對比一下MRI,JRuby和Rubinius的垃圾回收機制竹捉。
想了解Ruby垃圾回收機制和Ruby內(nèi)部實現(xiàn)更詳盡的闡述芜辕，請關注即將問世的拙作
《Ruby Under a Microscope》击狮。
既然是"Ruby Python"大會喻鳄，我覺得對比一下Ruby和Python的垃圾回收機制應該會很有趣憨闰。在此之前状蜗，到底為什么要計較垃圾回收呢？畢竟鹉动，這不是什么光鮮亮麗激動人心的主題诗舰，對吧。你們大家有多少人對垃圾回收感冒训裆？(竟然有不少RuPyde與會者舉手了!)
最近Ruby社區(qū)發(fā)表了一篇博文,是關于如何通過更改Ruby GC設置來為單元測試提速的。我認為這篇文章是極好的蜀铲。對于想讓單元測試跑得更快和讓程序GC暫停更少的人來說很有裨益边琉，但是GC并沒能引起我的興趣。第一瞥GC就像是一個讓人昏昏欲睡的记劝、干巴巴的技術主題变姨。
但是實際上垃圾回收是一個迷人的主題：GC算法不僅是計算機科學史的重要組成部分，也是一個前沿課題厌丑。舉例來說定欧，MRI Ruby使用的標記-清除算法已經(jīng)年逾五旬了渔呵，而Ruby的替代語言Rubinius使用的GC算法在不久前的2008年才被發(fā)明出來。
然而, "垃圾回收"這個詞其實有些用詞不當砍鸠。
應用程序那顆躍動的心
GC系統(tǒng)所承擔的工作遠比"垃圾回收"多得多扩氢。實際上，它們負責三個重要任務爷辱。它們
- 為新生成的對象分配內(nèi)存
- 識別那些垃圾對象录豺，并且
- 從垃圾對象那回收內(nèi)存。
如果將應用程序比作人的身體：所有你所寫的那些優(yōu)雅的代碼饭弓，業(yè)務邏輯双饥，算法，應該就是大腦弟断。以此類推咏花，垃圾回收機制應該是那個身體器官呢？（我從RuPy聽眾那聽到了不少有趣的答案：腰子阀趴、白血球 :) ）
我認為垃圾回收就是應用程序那顆躍動的心昏翰。像心臟為身體其他器官提供血液和營養(yǎng)物那樣，垃圾回收器為你的應該程序提供內(nèi)存和對象舍咖。如果心臟停跳矩父，過不了幾秒鐘人就完了。如果垃圾回收器停止工作或運行遲緩,像動脈阻塞,你的應用程序效率也會下降排霉，直至最終死掉窍株。
一個簡單的例子
運用實例一貫有助于理論的理解。下面是一個簡單類攻柠，分別用Python和Ruby寫成球订，我們今天就以此為例：
順便提一句，兩種語言的代碼竟能如此相像：Ruby 和 Python 在表達同一事物上真的只是略有不同瑰钮。但是在這兩種語言的內(nèi)部實現(xiàn)上是否也如此相似呢冒滩？
可用列表
當我們執(zhí)行上面的Node.new(1)時，Ruby到底做了什么浪谴？Ruby是如何為我們創(chuàng)建新的對象的呢开睡？
出乎意料的是它做的非常少。實際上苟耻，早在代碼開始執(zhí)行前篇恒，Ruby就提前創(chuàng)建了成百上千個對象，并把它們串在鏈表上凶杖，名曰：可用列表胁艰。下圖所示為可用列表的概念圖：
想象一下每個白色方格上都標著一個"未使用預創(chuàng)建對象"。當我們調(diào)用 Node.new ,Ruby只需取一個預創(chuàng)建對象給我們使用即可：
上圖中左側(cè)灰格表示我們代碼中使用的當前對象，同時其他白格是未使用對象腾么。(請注意：無疑我的示意圖是對實際的簡化奈梳。實際上，Ruby會用另一個對象來裝載字符串"ABC",另一個對象裝載Node類定義解虱，還有一個對象裝載了代碼中分析出的抽象語法樹攘须，等等)
如果我們再次調(diào)用 Node.new，Ruby將遞給我們另一個對象：
這個簡單的用鏈表來預分配對象的算法已經(jīng)發(fā)明了超過50年饭寺，而發(fā)明人這是赫赫有名的計算機科學家John McCarthy阻课，一開始是用Lisp實現(xiàn)的。Lisp不僅是最早的函數(shù)式編程語言艰匙，在計算機科學領域也有許多創(chuàng)舉限煞。其一就是利用垃圾回收機制自動化進行程序內(nèi)存管理的概念。
標準版的Ruby员凝，也就是眾所周知的"Matz's Ruby Interpreter"(MRI),所使用的GC算法與McCarthy在1960年的實現(xiàn)方式很類似署驻。無論好壞，Ruby的垃圾回收機制已經(jīng)53歲高齡了健霹。像Lisp一樣旺上，Ruby預先創(chuàng)建一些對象，然后在你分配新對象或者變量的時候供你使用糖埋。
Python 的對象分配
我們已經(jīng)了解了Ruby預先創(chuàng)建對象并將它們存放在可用列表中宣吱。那Python又怎么樣呢？
盡管由于許多原因Python也使用可用列表(用來回收一些特定對象比如 list)瞳别，但在為新對象和變量分配內(nèi)存的方面Python和Ruby是不同的征候。
例如我們用Pyhon來創(chuàng)建一個Node對象：
與Ruby不同，當創(chuàng)建對象時Python立即向操作系統(tǒng)請求內(nèi)存祟敛。(Python實際上實現(xiàn)了一套自己的內(nèi)存分配系統(tǒng)疤坝，在操作系統(tǒng)堆之上提供了一個抽象層。但是我今天不展開說了馆铁。)
當我們創(chuàng)建第二個對象的時候跑揉，再次像OS請求內(nèi)存：
看起來夠簡單吧，在我們創(chuàng)建對象的時候埠巨，Python會花些時間為我們找到并分配內(nèi)存历谍。
Ruby 開發(fā)者住在凌亂的房間里
回過來看Ruby辣垒。隨著我們創(chuàng)建越來越多的對象扮饶，Ruby會持續(xù)尋可用列表里取預創(chuàng)建對象給我們。因此乍构，可用列表會逐漸變短:
...然后更短：
請注意我一直在為變量n1賦新值，Ruby把舊值留在原處。"ABC","JKL"和"MNO"三個Node實例還滯留在內(nèi)存中哥遮。Ruby不會立即清除代碼中不再使用的舊對象岂丘！Ruby開發(fā)者們就像是住在一間凌亂的房間，地板上摞著衣服眠饮，要么洗碗池里都是臟盤子奥帘。作為一個Ruby程序員，無用的垃圾對象會一直環(huán)繞著你仪召。
Python 開發(fā)者住在衛(wèi)生之家庭
Python與Ruby的垃圾回收機制頗為不同寨蹋。讓我們回到前面提到的三個Python Node對象：
在內(nèi)部，創(chuàng)建一個對象時扔茅，Python總是在對象的C結(jié)構(gòu)體里保存一個整數(shù)已旧，稱為 引用數(shù)。期初召娜，Python將這個值設置為1：
值為1說明分別有個一個指針指向或是引用這三個對象运褪。假如我們現(xiàn)在創(chuàng)建一個新的Node實例，JKL：
與之前一樣玖瘸，Python設置JKL的引用數(shù)為1秸讹。然而，請注意由于我們改變了n1指向了JKL雅倒，不再指向ABC璃诀，Python就把ABC的引用數(shù)置為0了。
此刻蔑匣，Python垃圾回收器立刻挺身而出劣欢！每當對象的引用數(shù)減為0，Python立即將其釋放殖演，把內(nèi)存還給操作系統(tǒng)：
上面Python回收了ABC Node實例使用的內(nèi)存氧秘。記住，Ruby棄舊對象原地于不顧趴久，也不釋放它們的內(nèi)存丸相。
Python的這種垃圾回收算法被稱為引用計數(shù)。是George-Collins在1960年發(fā)明的彼棍，恰巧與John McCarthy發(fā)明的可用列表算法在同一年出現(xiàn)灭忠。就像Mike-Bernstein在6月份哥譚市Ruby大會杰出的垃圾回收機制演講中說的: "1960年是垃圾收集器的黃金年代..."
Python開發(fā)者工作在衛(wèi)生之家，你可以想象座硕，有個患有輕度OCD(一種強迫癥)的室友一刻不停地跟在你身后打掃弛作，你一放下臟碟子或杯子，有個家伙已經(jīng)準備好把它放進洗碗機了华匾！
現(xiàn)在來看第二例子映琳。加入我們讓n2引用n1：
上圖中左邊的DEF的引用數(shù)已經(jīng)被Python減少了，垃圾回收器會立即回收DEF實例。同時JKL的引用數(shù)已經(jīng)變?yōu)榱? 萨西，因為n1和n2都指向它有鹿。
標記-清除
最終那間凌亂的房間充斥著垃圾，再不能歲月靜好了谎脯。在Ruby程序運行了一陣子以后葱跋，可用列表最終被用光光了:
此刻所有Ruby預創(chuàng)建對象都被程序用過了(它們都變灰了)，可用列表里空空如也（沒有白格子了）源梭。
此刻Ruby祭出另一McCarthy發(fā)明的算法娱俺，名曰：標記-清除。首先Ruby把程序停下來废麻，Ruby用"地球停轉(zhuǎn)垃圾回收大法"荠卷。之后Ruby輪詢所有指針，變量和代碼產(chǎn)生別的引用對象和其他值脑溢。同時Ruby通過自身的虛擬機便利內(nèi)部指針僵朗。標記出這些指針引用的每個對象。我在圖中使用M表示屑彻。
上圖中那三個被標M的對象是程序還在使用的验庙。在內(nèi)部，Ruby實際上使用一串位值社牲，被稱為:可用位圖(譯注：還記得《編程珠璣》里的為突發(fā)排序嗎粪薛，這對離散度不高的有限整數(shù)集合具有很強的壓縮效果，用以節(jié)約機器的資源搏恤。)违寿，來跟蹤對象是否被標記了。
Ruby將這個可用位圖存放在獨立的內(nèi)存區(qū)域中熟空，以便充分利用Unix的寫時拷貝化藤巢。有關此事的更多內(nèi)容請關注我另一博文《Why You Should Be Excited About Garbage Collection in Ruby 2.0》
如果說被標記的對象是存活的，剩下的未被標記的對象只能是垃圾息罗，這意味著我們的代碼不再會使用它了掂咒。我會在下圖中用白格子表示垃圾對象：
接下來Ruby清除這些無用的垃圾對象，把它們送回到可用列表中：
在內(nèi)部這一切發(fā)生得迅雷不及掩耳迈喉，因為Ruby實際上不會吧對象從這拷貝到那绍刮。而是通過調(diào)整內(nèi)部指針，將其指向一個新鏈表的方式挨摸，來將垃圾對象歸位到可用列表中的孩革。
現(xiàn)在等到下回再創(chuàng)建對象的時候Ruby又可以把這些垃圾對象分給我們使用了。在Ruby里得运，對象們六道輪回膝蜈，轉(zhuǎn)世投胎锅移，享受多次人生。
標記-刪除 vs. 引用計數(shù)
乍一看彬檀，Python的GC算法貌似遠勝于Ruby的：寧舍潔宇而居穢室乎帆啃？為什么Ruby寧愿定期強制程序停止運行，也不使用Python的算法呢窍帝？
然而，引用計數(shù)并不像第一眼看上去那樣簡單诽偷。有許多原因使得不許多語言不像Python這樣使用引用計數(shù)GC算法：
首先坤学，它不好實現(xiàn)。Python不得不在每個對象內(nèi)部留一些空間來處理引用數(shù)报慕。這樣付出了一小點兒空間上的代價深浮。但更糟糕的是，每個簡單的操作（像修改變量或引用）都會變成一個更復雜的操作眠冈，因為Python需要增加一個計數(shù)飞苇，減少另一個，還可能釋放對象蜗顽。
第二點布卡，它相對較慢。雖然Python隨著程序執(zhí)行GC很穩(wěn)焦透恰（一把臟碟子放在洗碗盆里就開始洗啦）忿等，但這并不一定更快。Python不停地更新著眾多引用數(shù)值崔挖。特別是當你不再使用一個大數(shù)據(jù)結(jié)構(gòu)的時候贸街，比如一個包含很多元素的列表，Python可能必須一次性釋放大量對象狸相。減少引用數(shù)就成了一項復雜的遞歸過程了薛匪。
最后，它不是總奏效的脓鹃。在我的下一篇包含了我這個演講剩余部分筆記的文章中逸尖，我們會看到，引用計數(shù)不能處理環(huán)形數(shù)據(jù)結(jié)構(gòu)--也就是含有循環(huán)引用的數(shù)據(jù)結(jié)構(gòu)将谊。
下回分解
下周我會分解演講的剩余部分冷溶。我會討論一下Python如何擺平環(huán)形數(shù)據(jù)類型及GC在即將出爐的Ruby2.1發(fā)行版中是如何工作的。
對比Ruby和Python的垃圾回收（2）
英文原文地址: Generational GC in Python and Ruby
中文原文: 對比Ruby和Python的垃圾回收（2）：代式垃圾回收機制
上周尊浓，我根據(jù)之前在RuPy上做的一個名為“Visualizing Garbage Collection in Ruby and Python.”的報告寫了這篇文章的上半部分逞频。在上篇中，我解釋了標準Ruby(也被稱為Matz的Ruby解釋器或是MRI)是如何使用名為標記回收(Mark and Sweep)的垃圾回收算法栋齿，這個算法是為1960年原版本的Lisp所開發(fā)苗胀。同樣襟诸，我也介紹了Python使用一種有53年歷史的GC算法，這種算法的思路非常不同基协，稱之為引用計數(shù)歌亲。
事實證明，Python在引用計數(shù)之外澜驮，還用了另一個名為Generational Garbage Collection的算法陷揪。這意味著Python的垃圾回收器用不同的方式對待新創(chuàng)建的以及舊有的對象。并且在即將到來的2.1版本的MRI Ruby中也首次引入了Generational Garbage Collection 的垃圾回收機制(在另兩個Ruby的實現(xiàn)：JRuby和Rubinius中杂穷，已經(jīng)使用這種GC機制很多年了悍缠，我將在下周的RubyConf大會上將它是如何在這兩種Ruby實現(xiàn)中工作的)。
當然耐量，這句話“用不同的方式對待新創(chuàng)建的以及舊有的對象”是有點模糊不清飞蚓，比如如何定義新、舊對象廊蜒？又比如對于Ruby和Python來說具體是如何采取不同的對待方式趴拧？今天，我們就來談談這兩種語言GC機制的運行原理山叮，回答上邊那些疑問著榴。但是在我們開始談論Generational GC之前，我們先要花點時間談論下Python的引用計數(shù)算法的一個嚴重的理論問題聘芜。
Python中的循環(huán)數(shù)據(jù)結(jié)構(gòu)以及引用計數(shù)
通過上篇兄渺，我們知道在Python中，每個對象都保存了一個稱為引用計數(shù)的整數(shù)值汰现，來追蹤到底有多少引用指向了這個對象挂谍。無論何時，如果我們程序中的一個變量或其他對象引用了目標對象瞎饲，Python將會增加這個計數(shù)值口叙，而當程序停止使用這個對象，則Python會減少這個計數(shù)值嗅战。一旦計數(shù)值被減到零妄田，Python將會釋放這個對象以及回收相關內(nèi)存空間。
從六十年代開始驮捍，計算機科學界就面臨了一個嚴重的理論問題疟呐，那就是針對引用計數(shù)這種算法來說，如果一個數(shù)據(jù)結(jié)構(gòu)引用了它自身东且，即如果這個數(shù)據(jù)結(jié)構(gòu)是一個循環(huán)數(shù)據(jù)結(jié)構(gòu)启具，那么某些引用計數(shù)值是肯定無法變成零的。為了更好地理解這個問題珊泳，讓我們舉個例子鲁冯。下面的代碼展示了一些上周我們所用到的節(jié)點類：
我們有一個構(gòu)造器(在Python中叫做 init )拷沸，在一個實例變量中存儲一個單獨的屬性。在類定義之后我們創(chuàng)建兩個節(jié)點薯演，ABC以及DEF撞芍，在圖中為左邊的矩形框。兩個節(jié)點的引用計數(shù)都被初始化為1跨扮，因為各有兩個引用指向各個節(jié)點(n1和n2)序无。
現(xiàn)在，讓我們在節(jié)點中定義兩個附加的屬性衡创，next以及prev：
跟Ruby不同的是愉镰，Python中你可以在代碼運行的時候動態(tài)定義實例變量或?qū)ο髮傩浴＿@看起來似乎有點像Ruby缺失了某些有趣的魔法钧汹。(聲明下我不是一個Python程序員，所以可能會存在一些命名方面的錯誤)录择。我們設置 n1.next 指向 n2拔莱，同時設置 n2.prev 指回 n1。現(xiàn)在隘竭，我們的兩個節(jié)點使用循環(huán)引用的方式構(gòu)成了一個雙端鏈表塘秦。同時請注意到 ABC 以及 DEF 的引用計數(shù)值已經(jīng)增加到了2。這里有兩個指針指向了每個節(jié)點：首先是 n1 以及 n2动看，其次就是 next 以及 prev尊剔。
現(xiàn)在，假定我們的程序不再使用這兩個節(jié)點了菱皆，我們將 n1 和 n2 都設置為null(Python中是None)须误。
好了，Python會像往常一樣將每個節(jié)點的引用計數(shù)減少到1仇轻。
在Python中的零代(Generation Zero)
請注意在以上剛剛說到的例子中京痢，我們以一個不是很常見的情況結(jié)尾：我們有一個“孤島”或是一組未使用的、互相指向的對象篷店，但是誰都沒有外部引用祭椰。換句話說，我們的程序不再使用這些節(jié)點對象了疲陕，所以我們希望Python的垃圾回收機制能夠足夠智能去釋放這些對象并回收它們占用的內(nèi)存空間方淤。但是這不可能，因為所有的引用計數(shù)都是1而不是0蹄殃。Python的引用計數(shù)算法不能夠處理互相指向自己的對象携茂。
當然，上邊舉的是一個故意設計的例子窃爷，但是你的代碼也許會在不經(jīng)意間包含循環(huán)引用并且你并未意識到邑蒋。事實上姓蜂，當你的Python程序運行的時候它將會建立一定數(shù)量的“浮點數(shù)垃圾”，Python的GC不能夠處理未使用的對象因為應用計數(shù)值不會到零医吊。
這就是為什么Python要引入Generational GC算法的原因钱慢！正如Ruby使用一個鏈表(free list)來持續(xù)追蹤未使用的、自由的對象一樣卿堂，Python使用一種不同的鏈表來持續(xù)追蹤活躍的對象束莫。而不將其稱之為“活躍列表”，Python的內(nèi)部C代碼將其稱為零代(Generation Zero)草描。每次當你創(chuàng)建一個對象或其他什么值的時候览绿，Python會將其加入零代鏈表：
從上邊可以看到當我們創(chuàng)建ABC節(jié)點的時候，Python將其加入零代鏈表穗慕。請注意到這并不是一個真正的列表饿敲，并不能直接在你的代碼中訪問，事實上這個鏈表是一個完全內(nèi)部的Python運行時逛绵。
相似的怀各，當我們創(chuàng)建DEF節(jié)點的時候，Python將其加入同樣的鏈表：
現(xiàn)在零代包含了兩個節(jié)點對象术浪。(他還將包含Python創(chuàng)建的每個其他值瓢对，與一些Python自己使用的內(nèi)部值。)
檢測循環(huán)引用
隨后胰苏，Python會循環(huán)遍歷零代列表上的每個對象硕蛹，檢查列表中每個互相引用的對象，根據(jù)規(guī)則減掉其引用計數(shù)硕并。在這個過程中法焰，Python會一個接一個的統(tǒng)計內(nèi)部引用的數(shù)量以防過早地釋放對象。
為了便于理解鲤孵，來看一個例子：
從上面可以看到 ABC 和 DEF 節(jié)點包含的引用數(shù)為1.有三個其他的對象同時存在于零代鏈表中壶栋，藍色的箭頭指示了有一些對象正在被零代鏈表之外的其他對象所引用。(接下來我們會看到普监，Python中同時存在另外兩個分別被稱為一代和二代的鏈表)贵试。這些對象有著更高的引用計數(shù)因為它們正在被其他指針所指向著。
接下來你會看到Python的GC是如何處理零代鏈表的凯正。
通過識別內(nèi)部引用毙玻，Python能夠減少許多零代鏈表對象的引用計數(shù)。在上圖的第一行中你能夠看見ABC和DEF的引用計數(shù)已經(jīng)變?yōu)榱懔死壬ⅲ@意味著收集器可以釋放它們并回收內(nèi)存空間了桑滩。剩下的活躍的對象則被移動到一個新的鏈表：一代鏈表。
從某種意義上說允睹，Python的GC算法類似于Ruby所用的標記回收算法运准。周期性地從一個對象到另一個對象追蹤引用以確定對象是否還是活躍的幌氮，正在被程序所使用的，這正類似于Ruby的標記過程胁澳。
Python中的GC閾值
Python什么時候會進行這個標記過程该互？隨著你的程序運行，Python解釋器保持對新創(chuàng)建的對象韭畸，以及因為引用計數(shù)為零而被釋放掉的對象的追蹤宇智。從理論上說，這兩個值應該保持一致胰丁，因為程序新建的每個對象都應該最終被釋放掉随橘。
當然，事實并非如此锦庸。因為循環(huán)引用的原因机蔗，并且因為你的程序使用了一些比其他對象存在時間更長的對象，從而被分配對象的計數(shù)值與被釋放對象的計數(shù)值之間的差異在逐漸增長甘萧。一旦這個差異累計超過某個閾值蜒车，則Python的收集機制就啟動了，并且觸發(fā)上邊所說到的零代算法幔嗦，釋放“浮動的垃圾”，并且將剩下的對象移動到一代列表沥潭。
隨著時間的推移邀泉，程序所使用的對象逐漸從零代列表移動到一代列表。而Python對于一代列表中對象的處理遵循同樣的方法钝鸽，一旦被分配計數(shù)值與被釋放計數(shù)值累計到達一定閾值汇恤，Python會將剩下的活躍對象移動到二代列表。
通過這種方法拔恰，你的代碼所長期使用的對象因谎，那些你的代碼持續(xù)訪問的活躍對象，會從零代鏈表轉(zhuǎn)移到一代再轉(zhuǎn)移到二代颜懊。通過不同的閾值設置财岔，Python可以在不同的時間間隔處理這些對象臂聋。Python處理零代最為頻繁敌卓，其次是一代然后才是二代深寥。
弱代假說
來看看代垃圾回收算法的核心行為：垃圾回收器會更頻繁的處理新對象阳液。一個新的對象即是你的程序剛剛創(chuàng)建的虹茶，而一個來的對象則是經(jīng)過了幾個時間周期之后仍然存在的對象焰枢。Python會在當一個對象從零代移動到一代童擎，或是從一代移動到二代的過程中提升(promote)這個對象棉安。
為什么要這么做媳维？這種算法的根源來自于弱代假說(weak generational hypothesis)酿雪。這個假說由兩個觀點構(gòu)成：首先是年親的對象通常死得也快遏暴，而老對象則很有可能存活更長的時間。
假定現(xiàn)在我用Python或是Ruby創(chuàng)建一個新對象：
根據(jù)假說指黎，我的代碼很可能僅僅會使用ABC很短的時間朋凉。這個對象也許僅僅只是一個方法中的中間結(jié)果，并且隨著方法的返回這個對象就將變成垃圾了袋励。大部分的新對象都是如此般地很快變成垃圾侥啤。然而，偶爾程序會創(chuàng)建一些很重要的茬故，存活時間比較長的對象-例如web應用中的session變量或是配置項盖灸。
通過頻繁的處理零代鏈表中的新對象，Python的垃圾收集器將把時間花在更有意義的地方：它處理那些很快就可能變成垃圾的新對象磺芭。同時只在很少的時候赁炎，當滿足閾值的條件，收集器才回去處理那些老變量钾腺。
回到Ruby的自由鏈
即將到來的Ruby 2.1版本將會首次使用基于代的垃圾回收算法徙垫！(請注意的是，其他的Ruby實現(xiàn)放棒，例如JRuby和Rubinius已經(jīng)使用這個算法許多年了)姻报。讓我們回到上篇博文中提到的自由鏈的圖來看看它到底是怎么工作的。
請回憶當自由鏈使用完之后间螟，Ruby會標記你的程序仍然在使用的對象吴旋。
從這張圖上我們可以看到有三個活躍的對象，因為指針n1厢破、n2荣瑟、n3仍然指向著它們。剩下的用白色矩形表示的對象即是垃圾摩泪。(當然笆焰，實際情況會復雜得多，自由鏈可能會包含上千個對象见坑，并且有復雜的引用指向關系嚷掠，這里的簡圖只是幫助我們了解Ruby的GC機制背后的簡單原理，而不會將我們陷入細節(jié)之中)
同樣荞驴，我們說過Ruby會將垃圾對象移動回自由鏈中叠国，這樣的話它們就能在程序申請新對象的時候被循環(huán)使用了。
Ruby2.1基于代的GC機制
從2.1版本開始戴尸，Ruby的GC代碼增加了一些附加步驟：它將留下來的活躍對象晉升(promote)到成熟代(mature generation)中粟焊。(在MRI的C源碼中使用了old這個詞而不是mature)，接下來的圖展示了兩個Ruby2.1對象代的概念圖：
在左邊是一個跟自由鏈不相同的場景，我們可以看到垃圾對象是用白色表示的项棠，剩下的是灰色的活躍對象悲雳。灰色的對象剛剛被標記香追。
一旦“標記清除”過程結(jié)束合瓢，Ruby2.1將剩下的標記對象移動到成熟區(qū)：
跟Python中使用三代來劃分不同，Ruby2.1只用了兩代透典，左邊是年輕的新一代對象晴楔，而右邊是成熟代的老對象。一旦Ruby2.1標記了對象一次峭咒，它就會被認為是成熟的税弃。Ruby會打賭剩下的活躍對象在相當長的一段時間內(nèi)不會很快變成垃圾對象。
重要提醒：Ruby2.1并不會真的在內(nèi)存中拷貝對象凑队，這些代表不同代的區(qū)域并不是由不同的物理內(nèi)存區(qū)域構(gòu)成则果。(有一些別的編程語言的GC實現(xiàn)或是Ruby的其他實現(xiàn)，可能會在對象晉升的時候采取拷貝的操作)漩氨。Ruby2.1的內(nèi)部實現(xiàn)不會將在標記&清除過程中預先標記的對象包含在內(nèi)西壮。一旦一個對象已經(jīng)被標記過一次了，那么那將不會被包含在接下來的標記清除過程中叫惊。
現(xiàn)在款青，假定你的Ruby程序接著運行著，創(chuàng)造了更多新的霍狰，更年輕的對象可都。則GC的過程將會在新的一代中出現(xiàn)，如圖：
如同Python那樣蚓耽，Ruby的垃圾收集器將大部分精力都放在新一代的對象之上。它僅僅會將自上一次GC過程發(fā)生后創(chuàng)建的新的旋炒、年輕的對象包含在接下來的標記清除過程中步悠。這是因為很多新對象很可能馬上就會變成垃圾(白色標記)。Ruby不會重復標記右邊的成熟對象瘫镇。因為他們已經(jīng)在一次GC過程中存活下來了鼎兽，在相當長的一段時間內(nèi)不會很快變成垃圾。因為只需要標記新對象铣除，所以Ruby 的GC能夠運行得更快谚咬。它完全跳過了成熟對象，減少了代碼等待GC完成的時間尚粘。
偶然的Ruby會運行一次“全局回收”择卦，重標記(re-marking)并重清除(re-sweeping)，這次包括所有的成熟對象。Ruby通過監(jiān)控成熟對象的數(shù)目來確定何時運行全局回收秉继。當成熟對象的數(shù)目雙倍于上次全局回收的數(shù)目時祈噪，Ruby會清理所有的標記并且將所有的對象都視為新對象。
白障
這個算法的一個重要挑戰(zhàn)是值得深入解釋的：假定你的代碼創(chuàng)建了一個新的年輕的對象尚辑，并且將其作為一個已存在的成熟對象的子嗣加入辑鲤。舉個例子，這種情況將會發(fā)生在杠茬，當你往一個已經(jīng)存在了很長時間的數(shù)組中增加了一個新值的時候：
讓我們來看看圖月褥，左邊的是新對象，而成熟的對象在右邊瓢喉。在左邊標記過程已經(jīng)識別出了5個新的對象目前仍然是活躍的(灰色)宁赤。但有兩個對象已經(jīng)變成垃圾了(白色)。但是如何處理正中間這個新建對象灯荧？這是剛剛那個問題提到的對象礁击，它是垃圾還是活躍對象呢？
當然它是活躍對象了逗载，因為有一個從右邊成熟對象的引用指向它哆窿。但是我們前面說過已經(jīng)被標記的成熟對象是不會被包含在標記清除過程中的(一直到全局回收)。這意味著類似這種的新建對象會被錯誤的認為是垃圾而被釋放厉斟，從而造成數(shù)據(jù)丟失挚躯。
Ruby2.1 通過監(jiān)視成熟對象，觀察你的代碼是否會添加一個從它們到新建對象的引用來克服這個問題擦秽。Ruby2.1 使用了一個名為白障(white barriers)的老式GC技術來監(jiān)視成熟對象的變化 – 無論任意時刻當你添加了從一個對象指向另一個對象的引用時(無論是新建或是修改一個對象)码荔，白障就會被觸發(fā)。白障將會檢測是否源對象是一個成熟對象感挥，如果是的話則將這個成熟對象添加到一個特殊的列表中缩搅。隨后，Ruby2.1會將這些滿足條件的成熟對象包括到下一次標記清除的范圍內(nèi)触幼，以防止新建對象被錯誤的標記為垃圾而清除硼瓣。
Ruby2.1 的白障實現(xiàn)相當復雜，主要是因為已有的C擴展并未包含這部分功能置谦。Koichi Sasada以及Ruby的核心團隊使用了一個比較巧妙的方案來解決這個問題堂鲤。如果想了解更多的內(nèi)容，請閱讀這些相關材料：Koichi在EuRuKo 2013上的演講Koichi’s fascinating presentation媒峡。
站在巨人的肩膀上
乍眼一看瘟栖，Ruby和Python的GC實現(xiàn)是截然不同的，Ruby使用John-MaCarthy的原生“標記并清除”算法谅阿，而Python使用引用計數(shù)半哟。但是仔細看來酬滤，可以發(fā)現(xiàn)Python使用了些許標記清除的思想來處理循環(huán)引用，而兩者同時以相似的方式使用基于代的垃圾回收算法镜沽。Python劃分了三代敏晤，而Ruby只有兩代。
這種相似性應該不會讓人感到意外缅茉。兩種編程語言都使用了幾十年前的計算機科學研究成果來進行設計嘴脾，這些成果早在語言成型之前就已經(jīng)被做出來了。我比較驚異的是當你掀開不同編程語言的表面而深入底層蔬墩，你總能夠發(fā)現(xiàn)一些相似的基礎理念和算法∫氪颍現(xiàn)代編程語言應該感激那些六七十年代由麥卡錫等計算機先賢所作出的計算機科學開創(chuàng)性研究。
