.NET內存分配淺析
我知道這是一個富有神話色彩的主題，同樣也是個深奧的主題，說它神話是因為.NET程序員幾乎看不到它，但是它一直在保護著.NET程序的運行，說它深奧可能涉及一些底層的東西在這個高級的編程語言裡顯得有點與眾不同。我希望通過本文能和大家一起分享.NET關於內存分配上的一些經驗，正如題目所描述這裡只是淺析，因為我的知識也大部分來自MSDN和一些觀察的結果。
一個有趣的假設
.NET很霸道，.NET程序基於這樣一個假設，用戶的內存是無限的（這怎麼可能呢），為了管理這個“無限”的內存.NET需要一個管理器來在有限的內存上模擬出來一個無限的內存空間，對於.NET應用程序來說這些都是透明的（應用程序是看不到的），.Net程序只管貪婪的申請內存，其他事情就有這個管理器來處理，這個管理器微軟叫它垃圾收集器（這個概念在JAVA裡面早就有了）。基於這個“無限”內存的假設.NET的內存分配是線性的，線性分配內存是最高效的，在分配內存的時候首先計算需要分配的地址空間然後再將頭指針偏移即可，這時候頭指針指向下一次要分配的內存的起始位置。如果內存真的是無限的，可以想象這種程序的運行將會多麼高效，可惜的是內存是有限的，神話結束了。
內存分類
說到內存要簡單提一下現代計算機中普遍存在的兩種類型的內存 --- 棧和堆。
棧是一種數據結構，這種數據結構是計算機的核心數據結構所以該結構在CPU本身已經支持，什麼是棧？棧是一種後進先出的數據結構，它只能在末端進行插入和刪除元素的操作，所有的函數調用都是通過棧完成的，由於程序員不需要自己來維護棧上面的內存分配任務，所以棧內存又叫自動內存，所謂自動內存就是它的分配和釋放完全由系統自動管理。不幸的是棧的空間是有限的，所以容納的對象也是有限的，Windows操作系統上默認棧的大小是1M。
堆內存是操作系統實現的一種動態內存管理方法，在Windows中有Win32堆、CRT堆、托管堆等，在.NET應用程序裡面使用的就是托管堆。這裡簡單的描述一下Window堆管理器的概念以及工作方法，Windows有一個堆管理器專門處理對內存的分配，堆管理器是虛擬內存管理器的消費者，堆管理器始終從虛擬內存管理器中獲得新的內存區域，堆管理器將這片內存初始化為堆內存供應用程序使用。堆管理器分兩部分：前端分配和後端分配。申請內存總是從前端分配開始，如果前端分配不能滿足需求則會啟用後端分配，前端分配會將內存分成若干大小不同的塊（內存頁面字節倍數），這些塊被按照大小散列到一個包含128個項的鏈表中（Windows中稱之為Look Aside List），眾所周知散列表是查找最快的一種數據結構，這是快速分配內存的基礎，假如應用程序要分配18個字節的內存，則堆管理器首先將18+8（這8個字節是堆管理器用來管理內存的元數據描述）=26字節，那麼堆管理器會按照此方法來找26/8-1=2。堆管理器會在第二個槽中查找是否有可用的內存，如果有則將該內存返回給應用程序，並且堆管理器會將這個槽標示為已被使用（會有一個數據結構專門處理這個標記，這裡從略）如果沒有則在第三個槽上（臨近的二倍的內存槽）查找是否有空閒的內存，如果找到了空閒的內存則將該空閒內存一分為二，將其中一個返回給應用程序，將另一個放入第二個槽中備用，如果還沒有則向Windows虛擬內存管理器提出申請，申請新的堆段。為了提高效率，操作系統還提供一個內存已經分配的快照列表，該列表有0或1組成，如果是0則說明對應的槽上沒有內存可用，如果為1則說明該槽上有內存可用，這個內部的存儲結構有操作系統維護，開發人員不用關心。
上面簡單的描述了操作系統中的兩種內存結構以及操作系統如何管理這些內存，其中有關堆管理的描述不完整，只是大概的描述，有興趣的朋友可以參看MSDN相關文檔的描述。
托管堆
托管堆是由Windows的堆管理器分配的一塊內存。這部分堆實際上可以理解為自動內存的衍生，在C++時代，內存的管理完全由程序員自己控制，這種完全控制導致粗心的程序員總是會分配了內存而忘記釋放內存，導致各種各樣的異常（OOM只是其中的一個表現形式）。在.NET時代微軟為了將開發人員從內存管理中解脫出來專心處理業務，微軟實現了托管堆，托管堆顧名思義是由另外一個管理器來管理的內存。
分配內存必然需要釋放內存，否則內存總是會被耗盡，那麼托管堆是如何分配和釋放內存的？.NET應用程序開始運行CLR會為該應用程序創建一個默認的托管堆，應用程序的所有的內存分配都在該堆上進行，如果堆段被耗盡，則CLR向操作系統申請一個較大的堆段，一般為兩倍，如果沒有兩倍的堆段可以分配，則將申請減半，如果還不行則再減半，直到申請被減小到堆段的最小的閥值，就會出現OOM。
如何分配內存？托管堆上的內存被分為3代：0代、1代、2代。用戶的內存分配永遠在0代上。1代，2代可以理解為系統維護的一個緩沖區，老對象總是慢慢升級到高一級的代上，那麼2代中的對象是在程序生命周期中最老的對象集合。另外為了提高效率托管堆上有一個獨立的堆叫：大對象堆。大對象堆用來放置尺寸超過85K的對象，大對象堆也是由多個堆段組成，大對象堆的垃圾回收策略和2代一樣，當2代發生垃圾會收時，大對象堆上也需要進行垃圾回收。高一級的代被回收時會觸發低一級代的回收，也就是說當發生2代回收時0，1代也會被回收，大對象堆也會被回收。前面說了托管堆的分配是線性的，這一點和Win32堆不同，線性意味著O(1)的時間復雜度，效率是最高的，這也是為什麼會說.NET程序運行起來會比較快的原因（別拍磚，請往下看）。
如何回收內存？要說清楚這個問題需要知道一個概念，什麼是垃圾，垃圾就是在地址空間中不再被任何對象引用的對象（孤立的對象？），要判斷什麼是垃圾就要知道什麼是根，根是判斷對象是否是垃圾的唯一標准，常見的根有靜態變量、全局變量、寄存器變量、函數調用棧上的變量。寄存器變量和函數調用棧上的變量從函數調用的角度來說本質是相同的，當函數發生調用時，參數被壓入棧，有些參數被分配給寄存器（依賴於編譯器），寄存器中的對象（引用）是當前線程正在使用的對象所以視為根。全局和靜態的變量伴隨應用程序的整個生命周期所以它們也是根。知道什麼是根了以後就需要如何判斷對象和這些根有引用關系，首先GC會建立一個根列表，這個根列表表示當前有多少根，垃圾收集器首先會將所有的對象都看作是垃圾，然後開始逐個遍歷這些對象的引用，如果最終能找到這個對象和根之間的引用關系則標記這個對象不是垃圾，否則是垃圾，當遍歷完所有的根之後，所有的對象都只有兩個狀態：1、是垃圾。2、不是垃圾。此時GC開始回收所有垃圾對象所占用的內存空間，前面說到內存分配是線性的，所以垃圾對象被清除之後必然會在這個線性的結構上產生很多空的“洞”。這些“洞”顯然是可以再次利用的內存，並且這些洞會造成大量的內存碎片，為了解決這個問題GC啟動一個叫做“壓縮”的機制，該機制將移動托管堆上的所有對象讓他們靠攏到一起，填充這些空“洞”，此時GC還需要調整每個對象的引用（這些對象的地址都發生了變化）。到此為止垃圾回收結束。需要說明的一點是：垃圾回收開始時所有的工作線程都處於掛起狀態，直到垃圾回收結束。這裡只描述了一個普通的過程，GC是一個復雜的管理器，其中有很多其他的內容，比如用來調用析構函數的對象列表。這些內容本文不作詳細描述，有興趣的可以參考MSDN的相關文檔。正是由於這個GC的回收機制可能會導致系統性能下降，這也就是為什麼.NET程序運行起來會比較慢的原因。但是需要說明的是垃圾回收的時間是不可預期的，當它觸發某些條件時才會觸發垃圾回收，觸發這些條件的時刻是不固定的。
