ガベージコレクションのアルゴリズムと実装

bianchi 2023/06/28に更新

マークフェーズ

割愛

2.1.3 スイープフェーズ


sweep(){
  sweeping = $heap_start
  while(sweeping < $heap_end)
    if(sweeping.mark == TRUE)
      sweeping.mark = FALSE
    else
      sweeping.next = $free_list
      $free_list = sweeping
    sweeping += sweeping.size
}

sizeはオブジェクトのバイト数
オブジェクトを回収するという意味で、free_listと呼ばれる片方向リンクリストにチャンクとして連結する。
後でアロケーションの際に、このフリーリストをたどり、チャンクを見つける

7行目のnextフィールドはフリーリストを生成する際、およびそのフリーリストからチャンクを取り出す際に使用する。ここではnextと書いているが、任意のフィールドを上書きして使用する。既に死んでいるオブジェクトなのでフィールドの書き換えを行っても良い。

2.1.4 アロケーション


new_obj(size){
  chunk = pickup_chunk(size, $free_list)
  if(chunk != NULL)
    return chunk
  else 
    allocation_fail()
}

free_listをたどり、size以上のサイズをもつチャンクを探す
もし大きい場合、sizeと残りに分割され、残りチャンクをフリーリストに再度戻す

疑問

死んでいるオブジェクトを見つけた時点でfree()をせず、自分のアプリケーションで保持し続けるのか。
つまりフリーリストの意義がわかっていない。

bianchi 2023/06/28に更新

なぜフリーリストという概念があるのか

参考にさせていただきました。以下引用です

関数 free(p) が行なうべき仕事は、指定されたオブジェクト p を空き領域 (=将来の allocate のために利
用できる領域) にすることである。プログラムは飛び飛びに存在するオブジェクトを free するかもしれない
ため、一般に空き領域はヒープ上に通常は散らばってしまっている。

これらを将来再利用するために、リス
トにつないで管理 (フリーリスト) するのが一般的である。結局、free が行なう仕事は、p から始まる領域
をフリーリストへつなぐということである。

一方 allocate(n) が行なうべき仕事は、様々な空き領域がつまったフリーリストから、要求された大きさ
以上の箇所を見つける、ということになる。

ちょっとまだわかっていない。具体的に空き領域というのは誰がどう管理しているのかが不明。
cでmallocとfreeするものを別言語上から呼び出すという認識なのだが、違っているのだろうか
個人的予想では普通にos管理下に戻すべきで、フリーリストに繋いで自分が書いたアプリが常にヒープの保持をするべきではないのでは？と思ってしまう。普通言語作る時ってcとかで書くでしょう？

https://samwho.dev/memory-allocation/

In order to free memory, we need to keep better track of memory. We can do this by saving the address and size of all allocations, and the address and size of blocks of free memory. We'll call these an "allocation list" and a "free list" respectively.

あーなるほどと思った。このフリーリストとは違う概念だが、若干なるほど感はある

非常によくわかった。これに悩んでいた。OK

bianchi 2023/06/28に更新

3 Reference Counting

Reference CountingではミューテータがGCを明示的に呼び出すことはない。
ミューテータの実行に密接に関わっており、処理を進めていく中でカウンタの増減を行い、メモリ管理をする

new_obj(size){
  obj = pickup_chunk(size, $free_list)
  if (obj == NULL)
    allocation_fail()
  else
    obj.ref_cnt = 1
    return obj
}

pickup_chunkがNULLの場合アロケーション失敗となることに注意-> ヒープ中に適切なサイズのチャンクがない
参照カウントでは、フリーリストに連結されているオブジェクト以外は全て生きている

update_ptr(ptr, obj){
  inc_ref_cnt(obj)
  dec_ref_cnt(*ptr)
  *ptr = obj
}
inc_ref_cnt(obj){ obj.ref_cnt++ }
dec_ref_cnt(ojb){
  obj.ref_cnt--
  if(obj.ref_cnt == 0)
    for(child: children(obj))
      dec_ref_cnt(*child)
    reclaim(obj) # フリーリストに連結
}

inc_ref_cnt(obj)がdec_ref_cnt(*ptr)の前にあるのは、「*ptrとobjが同じオブジェクトの場合に対処するため」
dec_ref_cntした後に、inc_ref_cntをすると、dec_ref_cntした瞬間にカウントが0になって回収されてしまう可能性がある

update_ptrは例えば配列の要素の変更時等に行われる。これによって生じた不要なオブジェクトはすぐに回収される。つまりアロケーション時にチャンクがないということは、ヒープ中のオブジェクトは全て生きていて、新しいオブジェクトを割り当てることができないという意味になる

メリット

不要オブジェクトがすぐに回収可能
- 他のGCアルゴリズムだと、チャンクが無くなってからGCが走るので、不要なメモリ領域を抱えたままになる
- 最大停止時間が短い
- ポインタを辿る必要がない
  - 分散環境等ポインタの走査のコストが高い場合、ReferenceCountingは良い