Garbage Collection ~mark & sweep法~

本稿では, ガベージコレクションのアルゴリズムの一つであるmark & sweep法のアルゴリズムを解説します.

初めに

ヒープ領域のメモリ管理を自動的に行うソフトウェアであるGarbage Collection(ガベコレ)は現在広く用いられています.

ガベコレを取り入れている代表例に, golangやJavaがあります. 他にも様々なプログラミング言語がガベコレを採用しています.

ガベコレと聞くと難しそうという印象を覚えがちですが, mark & sweep法の考え方は非常にシンプルです. 実際, Rustで簡単なガベコレを実装したところ, 100行程度で書くことができました.

https://github.com/speed1313/gomicollector

そんなガベコレの仕組みを見ていきましょう!

ガベコレが必要になる背景

初めに, ガベコレがなぜ必要になるかを知っておきましょう.

プログラムを実行する際には,

メモリ

が必要になります.

そして, プログラム実行時, プログラムが使うことのできるメモリ領域は基本的に以下のような構成になっています.

テキスト領域
データ領域
ヒープ領域
 
 
スタック領域

今回注目すべき点は, ヒープ領域とスタック領域です. スタック領域とヒープ領域は実行時に動的に伸びたり縮んだりします.

使用できるメモリは有限であるため, どのように効率的に使うかがポイントになってきます.

スタック領域

現代のプログラムは, 基本的にスタックマシンという, スタックを用いて計算を行う計算モデルに従って動作します.

例えばスタックマシンで5+3を計算する場合, 以下のようにスタックに引数(5, 3)をpushし, その後スタックの上から引数をpopしてそれらを用いて加算演算をして, 計算結果をpushするという処理をします.

時間の方向→

       
    +  
    3  
  5 5 8
スタックの底 スタックの底 スタックの底 スタックの底

なぜこんな回りくどいことをするのかと思われるかもしれませんが, このようにスタックを用いることで, (5+3)(32)といった加減乗除が組み合わさった式や, 論理演算など, いわゆる式(Expression)をpushとpopと種々の演算(add, sub, cmp)で行うことができるのです.

さらに, 関数や再帰, ifなどもスタックマシンによって行うことができます.

このように, 基本的にプログラムの実行はスタックマシンのモデルに従って行われています.

プログラムの動作のより詳細な仕組みについてはOSやコンパイラ等の本を参照ください.

以下におすすめの本を載せておきます.

コンパイラ 第2版, 辻野, オーム社

低レイヤを知りたい人のためのCコンパイラ作成入門, Rui Ueyama

このようにプログラム実行時にはスタックというデータ構造を用いており, その際に使用するメモリ領域が先ほど述べたスタック領域になります.

ヒープ領域

前節でスタック領域が必要なことを述べました. では, ヒープ領域はなぜ必要なのでしょうか.

それは, プログラムにおいて動的にメモリを確保したいことがあるからです. そしてそれはコンパイル時に割り付け順序やサイズが決まっているスタック領域ではできません.

スタック領域はスタックのために使うのでした.

しかし, スタック領域に割り当てられるメモリの制約として, メモリ領域の確保及び解放のタイミングはスタックのpushとpopの時であり, メモリのサイズも静的に決まっている必要があります.

それに対し, ヒープ領域を用いる場合, メモリの確保及び解放のタイミングやサイズはピープ領域の範囲内において自由です.

例えば動的にサイズが決まる木やString等のデータ構造はヒープ領域にメモリを確保する必要がとあります.

このように便利なヒープ領域ですが, ハープ領域のメモリを使用する際には, メモリの確保と解放を”正しく”行う必要があります.

“正しく”とは, 例えば以下のようなことを守らなければなりません.

このようなことを守らないと, 想定と異なる挙動をしてしまいます.

ピープ領域のメモリの解放は非常に厄介で, 歴史的に長い間プログラマを悩ませてきました. 実際, バグの多くがメモリに起因すると言われます.

莫大な行数の複雑なプログラムにおいて, どこでメモリを確保して, どこでメモリを解放すべきか正確に把握するのは難しいのです.

そこでガベージコレクションが生まれました.

ガベコレは自動でメモリの確保・解放を行ってくれます.

ガベコレによりプログラマはメモリ管理に頭を悩ませる必要がなくなったのです. (ガベコレでもオーバーヘッドによる速度低下などの問題はあります. 情報科学ではトレードオフが至る所で存在します.)

Garbage Collectionのアルゴリズム

ガベコレを実現するためのアルゴリズムは現在に至るまでに数多く発明されてきました.

代表例に参照カウント法とmark & sweep法があります.

オブジェクトを参照するポインタの数を数え、参照するポインタの数がゼロになったら解放する方法。循環参照の問題がある。解放が集中したときに、単純な実装だと停止時間が長くなる。 (https://ja.wikipedia.org/wiki/ガベージコレクションより引用)

mark & sweep法

オブジェクトから別のオブジェクトへの参照をたどり、到達できないオブジェクトを破棄する方法。(https://ja.wikipedia.org/wiki/ガベージコレクションより引用)

ここではmark & sweep法について具体例を添えて解説します.

mark & sweep法

mark & sweep法の考え方は, ヒープ領域のオブジェクトのうち, ルートからオブジェクトを再帰的にたどり, その過程でmarkをつけ, 再帰が終了した時点でmarkがついていないものは不要とみなして破棄および回収するというものです.

アルゴリズムは以下の流れで行われます.

  1. ヒープ領域のうち現在使用できる領域のindexを保存するリスト(free_list)を見る. リストにindexが存在していればその中から一つpopしてメモリを割り当てる. なければ以下を行いゴミを回収して再利用する.
  2. 初期化: ヒープ領域のオブジェクトを全てmarked=falseにする.
  3. markフェーズ: rootからオブジェクトを再帰的にたどっていき, 辿る過程でmarked=trueにしていく
  4. sweepフェーズ: ヒープ領域の先頭からオブジェクトを見ていき, marked=falseのindexをfree_listに登録
  5. free_listからindexを一つpopして返す. なければ割り当てられる領域はないためエラーを返す.

なお, 今回提示したアルゴリズムはmark & sweep法の実装の一例にすぎません. 実際, ピープ領域は伸びるにも関わらず固定長のvectorのようにしています.

一概にmark & sweep法といってもやり方はいろいろあります. ただどれも本質となるロジックは共通しています.

具体例

以下のように5つの領域が存在するヒープ領域があるとしましょう.

以下のテーブルは固定長ですが, これを生のメモリを指すindexテーブルと解釈すれば実際のメモリは可変長にできます. または固定長のメモリ領域しか割り当てられないとしても良いです.

root      
index marked: bool object名 points to
0      
1      
2      
3      

最初はヒープ領域が使用されていないため, Noneで初期化されています(Noneは省略).

rootはガベコレ時にマークをつける際のスタート地点であり, スタック領域にある変数です. C言語であればピープ領域を指すポインタに当たります.

rootはC言語のポインタがいくらでも定義できるようにいくつあっても良いのですが, 今回は簡単のため一つにします.

rootが指すオブジェクトは現在使用されている領域であり, ガベコレにおいて回収されません.

ヒープ領域のうち使用できるindexが保存されたfree_listも用意しておきます. はじめは使用できる領域がわからないため空になっています.

free_list []
   

この状態で, 以下のようにobj1のメモリが確保されました.

obj1_id = gc.allocate()

すると, gcは

  1. free_listに空き領域がないかチェックします.
free_list []
   

今回はfree_listが空なので, heap領域からゴミを回収するフェーズに入ります.

  1. まずは全てmarked=falseにします.
root      
index marked object名 points to
0 false    
1 false    
2 false    
3 false    
  1. 続いてmark処理を行います.

mark処理では現在使用中のオブジェクトを全て見つけてmarkして行きます.

rootから再帰的に辿っていくのですが, 今回rootが指しているindexは存在しないため, mark処理は1つもオブジェクトを見つけず終了です.

  1. 続いてsweep処理を行います.

sweep処理ではピープ領域のうち未到達つまり不要な領域を回収してfree_listに保存します.

今回はindexを0から辿り, どれもmarked=falseなので

free_list [0, 1, 2, 3]
   

となります.

  1. 最後にfree_listの後ろから一つindexをpopします.

今回はobj1に3を割り当てられます.

root      
index marked object名 points to
0 false    
1 false    
2 false    
3 false obj1  

これでobj1にメモリが割り当てられました.

ただ残念ながら今のところobj1は誰からもポイントされていません. このままではメモリがいっぱいになったら回収されるでしょうから覚えておいてください.

続いてこの状態で

obj2_id = gc.allocate()

をすると, free_listに以下のようにまだ空きがあるので

free_list [0, 1, 2]
   

ゴミの回収は行わずobj2に2が割り当てられます.

その結果ヒープは以下のようになります.

root      
index marked object名 points to
0 false    
1 false    
2 false obj2  
3 false obj1  

allocate()をさらに二回繰り返すと, 以下のようにheap領域が全て割り当てられた状態になります.

root      
index marked object名 points to
0 false obj4  
1 false obj3  
2 false obj2  
3 false obj1  
free_list []
   

この状態でallocate()すると, 現在free_listが空になっているためメモリを回収する必要があり, ガベコレはmark & sweep法に従って, ゴミを回収します.

またしてもrootは何も指していないためmark()後にmarkedはどれもfalseになり, スイープ後のfree_listは

free_list [0, 1, 2, 3]
   

になります.

これはすなわち, obj1, … , obj4といった誰からもポイントされていない到達不可能なオブジェクトは不要であるためガベコレにより自動的に解放されるということを意味します.

その後free_listからindexがポップされobj5には3番目の領域が割り当てられます.

root      
index marked object名 points to
0 false    
1 false    
2 false    
3 false obj5  

確かにガベコレが不要な領域を回収して新たにメモリを割り付けていますね.

では次にobj5を割り当てる直前の状態に戻りましょう. 以下のヒープ領域が全て割り当てられた状態です.

root      
index marked object名 points to
0 false obj4  
1 false obj3  
2 false obj2  
3 false obj1  

この状態で,

root = *heap[obj1_id]

とrootがobj1を指してみることにします.

root     obj1
index marked object名 points to
0 false obj4  
1 false obj3  
2 false obj2  
3 false obj1  

この状態でobj5にallocate()をすると, mark()終了時点で以下のようになります.

root     obj1
index marked object名 points to
0 false obj4  
1 false obj3  
2 false obj2  
3 true obj1  

root→obj1

となっているため, mark(root)を呼ぶと, obj1だけmarked=trueされるのです.

そのため, sweep()後にはfree_listは以下のようになります.

free_list [0, 1, 2]
   

これは, 到達可能なオブジェクトは回収しないことを意味します.

ガベコレはまだ到達可能, 即ち必要なものを回収しないのです.

そしてobj5割り付け後ヒープ領域およびfree_listは以下のような構成になっています.

root     obj1
index marked object名 points to
0 false    
1 false    
2 false obj5  
3 true obj1  
free_list [0, 1]
   

以上の例から, ガベコレは到達可能なオブジェクトと到達不可能なオブジェクトをmarked=true, falseで判断し, ゴミを回収してヒープ領域を最大限使用できるようにしていることがわかりました.

今回はヒープの構造をベクターに置き換えるなどかなり単純化しています.

実際のallocationの仕方については以下の動画等を参照ください.

以下の動画ではmalloc()の内部動作を非常に丁寧に説明されている動画です.

The 67th Yokohama kernel reading party

まとめ

本稿ではガベージコレクションの代表的なアルゴリズムであるmark & sweep法を解説しました.

名前だけ聞くと難しそうなガベコレですが, mark & sweep法は

オブジェクトをたどりながら到達できるものにmarkをつけ, markされていないものは不要と判断してメモリ解放する

という単純なアルゴリズムであることがわかりました.

より詳細な仕組みについては, mark & sweep GCをRustで100行程度で実装してみたので読んでみてください. よければStarもお願いします🤲

今回紹介したものはガベコレの触りです.

実用的なものにするためには, ゴミ回収のタイミングを工夫したり, ヒープ領域のコンパクションをしたり, 並行処理化したりなど, より複雑なトピックがたくさんあります(私は主なトピックの名前以外まだ何も知りません).

ぜひdeep diveしてみてください.

Ref.