gcのモデル

作ってみました。勉強のため。マーク＆スイープgcというらしい。

• 再利用可能なオブジェクトのリストがあり、
• 新しくオブジェクトをつくるときはそこからとる。
• そのときにリストが空ならgcを起動
  • ルートオブジェクトから辿れるオブジェクトすべてにマークを入れる
  • オブジェクトを走査してマークのついていないものを再利用可能リストに連結する

わかりやすい。利点は必要な時にだけgcが動くのでgcが動いていないときに高速に動作できる事で、欠点は一度起動するとオブジェクトすべてを走査するので線形のオーダーでコストがかかる事。だそう。今回のプログラムでは、ルートからすべてのオブジェクトに到達可能なときはexit()しています。より洗練された実装だとオブジェクト構造体の配列をreallocかけて増やすとかするようです。

#include<stdio.h>
#include<stdlib.h> // exit
#define SIZE 10

typedef struct Object {
  int mark;
  struct Object *next;
} object;

object obj_array[SIZE];
object NIL;
object *free_list;
object *root;

void init(void);
void gc(void);
object* get_new(void);

void init(void)
{
  int i;
  // init important objects
  NIL.mark = 1;
  NIL.next = &NIL;

  free_list = &NIL;
  root = &NIL;

  for (i = 0; i < SIZE - 1; i++){
    obj_array[i].mark = 0;
    obj_array[i].next = &obj_array[i+1];
  }
  obj_array[i].mark = 0;
  obj_array[i].next = &NIL;
  free_list = obj_array;
}

void gc(void)
{
  int i;
  object *tmp;

  printf("launch gc...");
  // marking objects can be traced from root object
  for (tmp = root; tmp != &NIL; tmp = tmp->next)
    tmp->mark = 1;
  
  // if not marked, then link to free list.
  for (i = 0; i < SIZE; i++)
    if (obj_array[i].mark == 0){
      obj_array[i].next = free_list;
      free_list = &obj_array[i];
    }
  printf("done\n");
}

object* get_new()
{
  object *tmp;

  if (free_list == &NIL){
    gc(); // if free list is NIL, then execute gc
    if (free_list == &NIL){ // still NIL
      printf("memory starvation\n");
      exit(0);
    }
  }
  tmp = free_list;
  free_list = free_list->next;

  // init
  tmp->mark = 0;
  tmp->next = &NIL;
  return tmp;
}

int main(void)
{
  int i;
  object *x, *y;
  
  init();

  x = get_new();
  y = get_new();
  x->next = y;
  root = x;
  // current status:
  //  root -> x -> y -> NIL
  
  for (i = 0; i < 10; i++) // force gc
    x = get_new();

  return 0;
}