标記清除算法
政策
标記清除（Mark-Sweep），目前在 JavaScript引擎 裡這種算法是最常用的，到目前為止的大多數浏覽器的 JavaScript引擎 都在采用标記清除算法，隻是各大浏覽器廠商還對此算法進行了優化加工，且不同浏覽器的 JavaScript引擎 在運作垃圾回收的頻率上有所差異
就像它的名字一樣，此算法分為 标記 和 清除 兩個階段，标記階段即為所有活動對象做上标記，清除階段則把沒有标記（也就是非活動對象）銷毀
你可能會疑惑怎麼給變量加标記？其實有很多種辦法，比如當變量進入執行環境時，反轉某一位（通過一個二進制字元來表示标記），又或者可以維護進入環境變量和離開環境變量這樣兩個清單，可以自由的把變量從一個清單轉移到另一個清單，目前還有很多其他辦法。其實，怎樣标記對我們來說并不重要，重要的是其政策
引擎在執行 GC（使用标記清除算法）時，需要從出發點去周遊記憶體中所有的對象去打标記，而這個出發點有很多，我們稱之為一組 根 對象，而所謂的根對象，其實在浏覽器環境中包括又不止于 全局Window對象、文檔DOM樹 等
整個标記清除算法大緻過程就像下面這樣
- 垃圾收集器在運作時會給記憶體中的所有變量都加上一個标記，假設記憶體中所有對象都是垃圾，全标記為0
- 然後從各個根對象開始周遊，把不是垃圾的節點改成1
- 清理所有标記為0的垃圾，銷毀并回收它們所占用的記憶體空間
- 最後，把所有記憶體中對象标記修改為0，等待下一輪垃圾回收
優點
标記清除算法的優點隻有一個，那就是實作比較簡單，打标記也無非打與不打兩種情況，這使得一位二進制位（0和1）就可以為其标記，非常簡單
缺點
标記清除算法有一個很大的缺點，就是在清除之後，剩餘的對象記憶體位置是不變的，也會導緻空閑記憶體空間是不連續的，出現了 記憶體碎片（如下圖），并且由于剩餘空閑記憶體不是一整塊，它是由不同大小記憶體組成的記憶體清單，這就牽扯出了記憶體配置設定的問題
假設我們建立對象配置設定記憶體時需要大小為 size，由于空閑記憶體是間斷的、不連續的，則需要對空閑記憶體清單進行一次單向周遊找出大于等于 size 的塊才能為其配置設定（如下圖）
那如何找到合适的塊呢？我們可以采取下面三種配置設定政策
- First-fit，找到大于等于 size 的塊立即傳回
- Best-fit，周遊整個空閑清單，傳回大于等于 size 的最小分塊
- Worst-fit，周遊整個空閑清單，找到最大的分塊，然後切成兩部分，一部分 size 大小，并将該部分傳回
這三種政策裡面 Worst-fit 的空間使用率看起來是最合理，但實際上切分之後會造成更多的小塊，形成記憶體碎片，是以不推薦使用，對于 First-fit 和 Best-fit 來說，考慮到配置設定的速度和效率 First-fit 是更為明智的選擇
綜上所述，标記清除算法或者說政策就有兩個很明顯的缺點
- 記憶體碎片化，空閑記憶體塊是不連續的，容易出現很多空閑記憶體塊，還可能會出現配置設定所需記憶體過大的對象時找不到合适的塊
- 配置設定速度慢，因為即便是使用 First-fit 政策，其操作仍是一個 O(n) 的操作，最壞情況是每次都要周遊到最後，同時因為碎片化，大對象的配置設定效率會更慢
PS：标記清除算法的缺點補充
歸根結底，标記清除算法的缺點在于清除之後剩餘的對象位置不變而導緻的空閑記憶體不連續，是以隻要解決這一點，兩個缺點都可以完美解決了
而 标記整理（Mark-Compact）算法 就可以有效地解決，它的标記階段和标記清除算法沒有什麼不同，隻是标記結束後，标記整理算法會将活着的對象（即不需要清理的對象）向記憶體的一端移動，最後清理掉邊界的記憶體（如下圖）