垃圾回收 的基本演算法
GC 作為一個長久的話題，從誕生[1]至今也算是經歷了六七十年了，對於很多習慣於使用 Java/Python 的同學來說，對於內存的管理可能會稍微更陌生一些，因為這些語言在語言層面就屏蔽了內存的分配和管理，幫助我們減少了超多的麻煩。但是，在幫助我們減少麻煩的同時，也帶來了很多問題，其中一個就是內存爆掉，這個問題有可能是代碼寫得不好，有可能是設計不好，反正就是存在這個問題。
本文不準備細究這些問題，本文旨在介紹一些內存回收的基本演算法，通過這些基本演算法，從而介紹一下這些自動內存管理語言底層管理內存的一些套路，從而在平時使用它們的時候可以依照它們的尿性來編寫代碼，減少一些內存管理方面的 Bug。
反觀這麼多年來，GC 雖然發展了這麼久，從古老的 Lisp 到新一些的 Go 語言，垃圾回收的基本演算法都沒有太大的創新，一方面說明了這些演算法的強大，另外一方面也說明了這裡還有很大的挖掘空間給愛好者們/專家們去思考，挖掘出新的基本演算法。本文就對這些年一直被各種編程語言直接使用/配合使用的幾種垃圾回收演算法進行一個總結介紹，順便介紹一下他們的優缺點。
垃圾回收演算法的性能點
為什麼會存在那麼多的垃圾回收演算法呢？我想這個問題的答案可能是沒有任何一種內存回收演算法是完美的，所以在針對不同的情景需求下，不同的內存回收演算法有其獨特的優勢，所以最後就延續了多種回收演算法。那麼，在平時的大多數情況下，有哪些性能考慮點是我們關注的呢，下面就列舉一下常見的性能指標
雖然這不是所有的關注指標，但是這些卻是大部分情況下被關注的指標。而且，需要注意的是，這裡面有一些指標是互斥的，例如我們會發現，最大吞吐量和最大暫停時間往往無法得到雙贏，也就是說無法同時滿足這兩項的最優。所以，在選擇具體的回收演算法的時候，其實就是在這些指標之間進行權衡，然後根據自己的需求進行選擇。下面就對常見的三種基本回收演算法進行介紹。
基本 GC 演算法1. 標記-清除
標記-清除演算法是一個比較經典的演算法了，在標記-清除演算法中，一般都是有所謂的根對象，而且一般來說根對象都不止一個，有很多，以 C 語言來理解的話，我們可以理解成分配在棧中的對象和全局對象都是所謂的根對象。標記-清除演算法從這些所謂的根對象出發，進行第一個階段——標記階段，也就是將這些根對象能夠引用到的那些對象都作上標記，一般的做法是每個對象都有一個欄位用於標識是否被標記，當然還有很多其他的做法，例如專門弄一張表來表示對象的標記等，這些都是後話啦，反正這個階段就只做一件事情，那就是找出被使用的對象，作上標記，這樣沒有被標記的對象也就是不用的對象了。
在第一階段標記完之後，那麼進入標記-清除的第二個階段——清除階段，清除階段其實也就是所謂的釋放階段，無非就是把不使用的對象所佔用的內存釋放掉，然後回收起來這麼簡單。
看上去標記-清除演算法還是比較簡單的，但是，這個簡單背後也是有很多需要思考的問題：
這是兩個比較常見的問題。第一個問題，對象的內存分配問題，假設現在我們的語言需要創建一個對象，那麼自然需要分配一塊內存給它，怎麼分配這個內存呢？一個可能的做法就是從上次分配的位置往後直接分配一塊，這樣保證每次分配的內存都是往高位走，內存地址逐漸疊加。但是，這種方法帶來了一個問題，那就是釋放的時候就很尷尬了：
假設這裡有一段內存，按照剛才的策略分配了 A、B 和 C 三個對象，當程序運行一段時間之後，我們想回收掉對象 B，然後回收之後發現現在的內存是這樣的：
這個時候，我們想再分配一個對象 D，那麼不巧，D 的大小就比 B 大那麼一點，所以原來 B 的位置不足以容納 D，所以也就不能使用 B 原來的位置，那麼這樣的話，內存結構可能就成了這樣：
長此以往，我們會發現內存就會有一個一個的洞，碎片化會很嚴重，導致內存的利用率逐漸下降。同時，因為這裡的內存是一塊一塊的，所以我們用鏈表來保存它的時候，分配內存查找又是一個問題，所以就很麻煩。
此外，周期性得標記對象，從而會周期性得改變對象的微小數據，所以導致操作系統 COW 體系不能得到較好的運用，從而導致性能的缺失。這是一方面，前面還有一個問題，那就是我們標記對象的時候以怎麼樣的順序來查找活動對象，常見的查找方式有深度優先查找和廣度優先查找，這兩種查找在性能上可能沒有太大區別，但是，對於臨時空間的佔用卻是有較大的影響，所以一般來說，深度優先比廣度優先更能壓低內存使用量，所以經常使用的是深度優先搜索。
雖然有缺點，但是標記-清除的優點也是比較明顯的，例如實現起來還是比較簡單的，與保守式 GC 是兼容的，使得標記-清除演算法在實際應用中還是得到大家的青睞的。
2. 引用計數
除了標記-清除演算法外，引用計數也是一種不錯的方法，引用計數演算法顧名思義就是在對象中額外記錄自身被引用的次數，當次數減小到 0 的時候那麼就知道自己已經沒有用處了，可以被回收了。也是一種很簡單很直觀的方式，可以在對象不被使用的時候立刻回收掉內存，從而將垃圾回收的時間分散化，也不需要像標記-清除一樣需要進行遍歷查找。
但是這也帶來了一定程度的麻煩，例如，我們需要使用內存屏障管理引用計數，對象的生成、賦值和引用都涉及引用計數的變化，從而導致引用計數的增減處理頻繁；同時，因為引用計數的存在，我們還需要在對象的自身數據之外，為引用計數分配固定的空間來存放計數，這是固有損耗。還有一個致命的缺點就是，使用引用計數演算法，無法清除循環引用的問題，從而導致內存一直佔用，無法釋放。
3. GC 複製
前面介紹的兩種方法都是在對象本身上操作的，也就是說清除和釋放都是操作對象本身所在的位置，但是，GC 複製演算法就稍微複雜一些了，GC 複製演算法最原始的做法就是將內存一分為二，每次只使用其他一半，當要 GC 的時候就將使用著的一半中的活動對象複製到另外一半中，然後清理掉這一半中的所有對象，直接使用另外一半即可，重複這個操作。
這個我們一眼就可以看出問題，那就是空間的利用率不高，但是，好處也是非常明顯的，首先是速度快，沒有額外的標記-清理操作，就是直接的複製，高吞吐；分配對象直接分配，不需要考慮碎片化問題；還可以保持與 OS 的緩存兼容，優勢還是比較明顯的。然而，硬幣總有正反面，除了空間利用率不高之外，這種方法不兼容保守式的 GC 演算法，此外，對於遞歸調用還會有棧溢出的風險。
所以為了更好得完善了這個演算法，還有有很多改進思路被提出的，例如不是將空間劃分為兩部分，而是劃分為多個部分，從而提升空間的利用率就是其中的一個思路。
總結
本文就常見的三種垃圾回收基本演算法以及經常需要考慮的幾個性能指標進行介紹，從而為了解垃圾回收開一個頭。其實看各種編程語言的 GC 實現都會發現本文中基本演算法的身影，無非就是它們直接如何組合，所以，理解本文中的基本演算法對於理解其他編程語言的 GC 實現還是很有幫助的。
Reference
https://en.wikipedia.org/wiki/Garbage_collection_(computer_science
TAG:服務端開發 |