Garbage Collection 알고리즘 - 1

참고 자료

http://www.cs.technion.ac.il/~erez/courses/gc/

https://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795

 

# 마크-스윕 ( mark-sweep )

http://www.cs.technion.ac.il/~erez/courses/gc/lectures/01-Basics.pdf

 

우선 마크-스윕은 Reachable한 오브젝트를 마킹한다음 마킹이 안된 object를 Free시키는 방법이다.

 

Free 상태인 메모리는 반드시 Free상태인 Chunk를 list로 관리한다( glibc malloc 의 메모리 관리 방법이랑 비슷하게 ). 중간 중간에 위치하는 사용가능한 메모리 청크를 바로바로 사용하려면 List로 관리해야 한다. 

 

앞으로의 내용은 다음과 같은 1. markFromRoots,  2. sweep  을 행하는 collect 함수를 garbage collecting시 실행한다고 가정하자.

def collect():
    # 1. mark
    markFromRoots()
    # 2. sweep
    sweep(start, end)

 

1. mark :

object를 marking하면서 reference를 BFS로 타고 들어가 마킹한다.  markFromRoots함수를 보면 일단 Root object들 부터 marking을 시작하는데  Root Object들은 무조건 마크한 다음 그 이후 BFS로 마킹을 시작한다.

def markFromRoots():
    initialise(worklist)
    for each fid in Roots:
        ref <- *fld
        if ref ^ null && not isMarked(ref):
            setMarked(ref)
            add(worklist, ref)
            mark()

def initialise(worklist):
    worklist <- empty

def mark():
    while not isEmpty(worklist):
        ref <- remove(worklist)
        for each fid in Pointers(ref):
            child <- *fld
            if child != null and not isMarked(child):
                setMarked(child)
                add(worklist, child)

2. sweep : 

sweep은 marking이 안된 친구들을 모두 sweep하는 과정이다. 

위 그림처럼  중간 중간에 존재하는 reachable한 object는 그 존재를 알 수 있지만 unreachable한 친구들은 접근을 못하기에 free를 시킬려면 unreachable한 친구들에게 도달할 다른 방법이 필요하다.

 

이런 방법은 2가지가 있다.

 

- 1. sweep용도의 list를 따로 유지하는 방법. 

jerryscript에서 처럼 모든 object를 list로 연결시키는 방법이다. 그럼 list를 따라다니면서 unmarked인 object를 free list로 회수할 수 있다.

 

- 2. 메모리 공간을 처음부터 끝까지 쭉 훑는방법

오브젝트 헤더에 size필드를 저장해놓으면 다음 object의 위치를 알 수 있다. 이 object가 unmarked인지 혹은 free되어 있는 상태인지를 확인해 free list에 회수되지 않은 unreachable한 object라면 다시 회수한다.

def nextObject(scan):
  return scan + scan->size

def sweep(start, end):
  scan <- start
  while scan < end:
      if isMarked(scan):
          unsetMarked(scan)
      else:
          free(scan):
      scan <- nextObject(scan)

# 마크-컴팩트 ( Mark-Compact ) 

http://www.cs.technion.ac.il/~erez/courses/gc/lectures/02-compaction.pdf

 

앞으로의 내용은 gc가 가비지 컬렉팅시 다음과 같은 collect 함수를 실행한다고 가정하고 보자. mark-compact는 marking 과정은 mark-sweep에서와 같이 reachable한 object들을 marking한다. 하지만 단순히 sweep만 한다는 것과  compact를 하는 점이 차이가 난다.

def collect():
    # 1. mark
    markFromRoots()
    # 2. compact 
    compact()

 

Two Finger

모든 Object가 똑같은 size의 공간을 차지하는 구조에서만 사용하능하다.

 

Lisp2 알고리즘

Two Finger와는 달리 오브젝트 사이즈가 다양해도 사용할 수 있다. ( 물론 object 헤더에 size 필드가 있거나 object의 type으로 object의 사이즈를 유추할 수 있어야 한다. ). 또한 오브젝트들의 heap에서의 주소상 순서가 지켜진다. (비록 쓸데 없어 보이기는 하지만 )

하지만 forwarding address를 위한 필드 하나가 오브젝트 헤더에 필요하다.  또한 3번이나 메모리를 훑어야 한다. 

Lisp의 compact는 다음과 같은 3개의 phase로 이루어진다.

 

1. Address Computation : start -> end까지 scan 하면서 forwarding address를 forwarding address 필드에 기록한다.

* 이 과정을 marking 과정에서 함께 진행할 수도 있다. 하지만 start -> end scan하면서 forwarding하면 주소상 순서가 그대로 유지되지만 마킹 과정에서 진행하면 아래와 같이 주소상 순서가 뒤죽 박죽이 된다.

 

2. Update Reference : 이제 다시 start->end 까지 scan하면서 각 필드가 참조하는 object의 address를 수정한다. 

이 과정을 Address Computation 과정에서 같이 하지 않는 이유는 reference하는 object의 forwarding address는 Address Computation이 지나야 알 수 있기 때문이다. Address Computation이 끝나면 reference하는 object의 헤더에 forwarding address값이 저장되어 있다.

 

3. Relocate : 이제 다시 start -> end scan을 진행하면서 새로운 주소로 object를 복사한다.

이 과정을 Update Reference 에서 같이 수행하지 않는 이유는 필드가 Reference하는 object의 forwarding address를 알아 내기 위해 해당 위치로 찾아 갔는데 이미 해당 address에 이상한 Relocate 된 object에 의해 이상한 값이 들어가 버릴 수 있기 때문이다.

def compact():
    addressComputation(HeapStart, HeapEnd, HeapStart)
    updateReferences(HeapStart, HeapEnd)
    relocate(HeapStart, HeapEnd)

def addressComputation(start, end, toRegion):
    scan <- start
    free <- toRegion
    while scan < end:
        if isMarked(scan):
            forwardingAddress(scan) <- free
            free <- free + size(scan)
        scan <- scan + size(scan)

def updateReferences(start, end):
    for fld in Roots:
        if *fld != null:
            *fld = forwardingAddress(ref)

    scan <- start
    while scan < end:
        if isMarked(scan):
            for fld in Pointers(scan);
                if *fld != null:
                    *fld = forwardingAddress(ref)
        scan <- scan + size(scan)

def relocate(start, end):
    scan <- start
    while scan < end:
        if isMarked(scan):
            dest <- forwardingAddress(scan)
            move(scan, dest)
            unsetMarked(dest)
        scan <- scan + size(scan)

Threaded Compaction. ( Concurrent 하게 한다는 뜻이 아니다! 그냥 Linked List로 연결하는 방식을 Threaded 라고 부르고 있다. )

# lecture pdf-02 34쪽부터 보면 이해하기 쉽다.

 

여기서 스레디드 압축이라고 하면 Concurrent한 방식인걸로 보이기 쉽지만 그거랑 관계없다. 그냥 Linked List를 사용하는 방식을 쓰레디드라고 부를 뿐이다.

 

우선 이 방법의 핵심은 특정 자료를 저장하는 헤더 필드를 gc 때는 thread 용으로 쓴다는 것이다. 그게 garbage collecting 과정에서 필요한 필드가 아니라면 gc가 끝난 이후에는 다시 원상태로 돌아오기 때문에 gc때 잠깐만 다른용도로 사용해도 괜찮다.

 

해당 필드는 꼭 가장 앞에 존재하는 필드일 필요는 없지만 고정된 오프셋의 어떤 필드여야 한다.

 

Threading은 자신을 가리키는 reference를 역으로 Linked List로 연결시켜서 나중에 field의 reference를 새 주소라 rewrite할 때 그 Linked List를  활용하는 방법을 말한다. Threading을 이용한 compact작업은 

Update Forward Reference, Update Backward Reference 2 단계로 이루어진다.

1. Update Forward Reference

슬라이딩 하면서 (scan 을 start 주소부터 end 까지 증가시키면서) object 를 발견할 때 마다 다음을 수행한다.

- 1.1 update

scan을 진행하면서 이전에 발견했던 각 오브젝트마다 1.2 작업을 수행했음으로 thread linked list ( chain)가 형성되어 있다.  이 chain에 있는 필드들의 값을 지금 오브젝트 ( 그림에서 P 오브젝트)의 new location으로 바꿔준다.

 

 

- 1.2 thread

오브젝트를 가리키는 필드들을 따라가서 threading field의 값을 자신의 ref로 고쳐 놓고, 원래 있던 threading 값을 자신의 필드에 채워 놓는다.

 

아래와 같은 Object들이 있다고 하자. 주소값 순서 상  A, B, C, D 순서로 있고 따라서 Scan할 때 A, B, C, D 순서로 Scan 된다.

이제 순서대로 Scan을 한다. A부터 Scan이 시작된다.

A의 모든 필드를 돌면서 값을 바꿔치기 한다.

 

 

다음 Scan 순서인 B 역시 똑같이 한다.

 

 

이제  C 의 차례가 되었다. C는 value field에 있는 Linked List를 따라가면서 각 필드마다 새로운 C의 Address값을 써 넣는다.

나중에 Scan되는 D 역시 Threading 작업을 해준다. 이때 새로운 C의 Address를 Threading된 Field에 써넣는 작업은 Update Backward Reference Phase에서 진행한다.

 

2. Update Backward Reference 

1과 똑같이 슬라이딩 하면서 (scan 을 start 주소부터 end 까지 증가시키면서) object 를 발견할 때 마다 다음을 수행

 

- 2.1 update

Update Forward Reference의 Update 작업에서  thread chain을 업데이트 한 이후 나중에 Scan된 오브젝트의 필드가 다시 이전에 Scan된 오브젝트를 참조하고 있다면  아래 그림처럼 다시 thread chain 이 형성되는걸 볼 수 있었다. 이런 reference를 backward reference 라 한다.

 

이처럼 이후에 생성된 chain에 속한 필드들의 값을 new location 으로 변경해주는 작업을 Update Backward Reference Phase에서 해주어야 한다.

 

- 2.2 move

이제 마지막으로 오브젝트를 new location으로 옮겨주는 작업이다.

 

def compact():
    updateForwardReferences()
    updateBackwardRefeerences()


# make chain
def thread(ref):
    if isReference(*ref):
        *ref, ** ref <- ** ref, ref



def update(ref, addr):
    # tmp : field address
    # addr : new relocated address
    tmp <- *ref
    while isReference(tmp):
        *tmp, tmp <- addr, *tmp
    *ref <- tmp


def updateForwardReferences():
    for fld in Roots:
        thread(*fld)

    free <- HeapStart
    scan <- HeapStart
    while scan <- HeapEnd:
        if isMarked(scan):
            # first update : write new address to referencing field of other object with chain that has been created until now.
            update(scan, free)
            # make chain
            for fld in Pointers(scan):
                thread(fld)
            free <- free + size(scan)
    scan <- scan + size(scan)


def updateBackwardReferences():
    free <- HeapStart
    scan <- HeapStart
    while scan <= HeapEnd:
        if isMarked(scan):
            # second update : write new address to referencing field of other object with chain that has been created after first update.
            update(scan, free)
            # move to new space
            move(scan, free)
            free <- free + size(scan)
    scan <- scan + size(scan)

 

단일 패스 알고리즘 ( 비트맵  )

(이건 lecture.pdf는 참고해도 별 도움 안된다. 코드를 보던가 책을 보던가하자. )

 

힙을 블록 단위로 나눈 후 gc 하는 알고리즘이다. 핵심은 offset table 과 bitmap 이다.

 

offset 테이블은 각 블록의 base address를 저장하는 테이블이다. 

base address란 각 블록들이 garbage collection 이후 새로운 주소로 옮겨간다고 했을 때의 주소이다. 따라서 모든 블록의 가장 첫 번째 object의 새 주소( new address of first object ) 가 각 블록들의 offset table 값이 된다.

 

4096 바이트 크기의 힙이 있을 때 256 바이트 크기의 블록을 사용한다고 치면

256 * 16 = 4096   16개의 블록이 존재하므로 offset 테이블의 크기는 32비트에서는 포인트 크기가 4바이트 이므로 4*16 = 64 바이트이다.

 

Marking Phase

bitmap 은 1비트가 4바이트 혹은 8바이트 (혹은 임의의 object 최소 크기 혹은 object align 크기이면 됨 ) 를 나타내는 맵으로 특정 object 가 marked 된지를 나타내는 맵이다.

예를들어 1비트가 8바이트를 타나낸다고 할 때 4096 바이트 힙을 bitmap으로 관리할려면 4096/(8*8) = 64 바이트 크기의 bitmap이 필요하다.marking을 할때는 이 bitmap에 marking을 한다.

 

Compute Location Phase

각 블록들의 base address를 구하는 단계이다. bitmap의 bit를 하나하나 counting하면서 새 주소를 계산하다가 block의 첫 번째 object를 만나면 해당 object의 새 주소값을 offset table에 기록한다.

 

 

def computeLocations(start, end, toRegion):
    loc <- toRegion
    block <- getBlockNum(start)

    for b in range(0, numBits(start, end) - 1):
        if b % BITS_IN_BLOCK == 0:
            # base address(first object address) of new address for this block  <- loc
            offset[block] <- loc
            block <- block + 1
        if bitmap[b] == MARKED:
            loc <- loc + BYTES_PER_BIT

 

 

Update Reference Relocate Phase

Marking Phase 에서 마킹한 bitmap과 Compute Location Phase에서 구한 offset table을 이용해 오브젝트의 필드에 있는 Reference를 Update하고 오브젝트를 Relocate 하는 단계이다. 

 

새로운 주소값을 구하는 방법은 우선 object address값이나  field의 참조 address값이 속한  블록의 base address 를 offset 테이블에서 가져온다. 그 후 bitmap을 보면서 속한 블록내에서 앞에 몇 개의 bit가 있는지 계산해 base address 에서의 오프셋을 알 수가 있다.

따라서 base address +  (같은 블록 내 앞에 존재하는 bit 개수 *   bit당 주소 크기 [= 그림에서는 8 byte]) 주소값이 new address 가 된다. 

아래 그림을 보면 Scan 대상 object가 속한 3번째 블록의 base address는 0x4028이고 같은 블록 내에 3개의 비트가 존재하므로 1 * 0x8 = 8 이 offset이다. 따라서 0x4028 + 0x8 = 0x4030 이 새 주소값이다.

 

def updateReferencesRelocate(start, end):
    for fld in Roots:
        ref <- *fld
    if ret != null:
        *fld <- newAddress(ref)
    scan <- start
    while scan < end:
        scan <- nextMarketObject(scan)
    for fld in Pointers(scan):
        ref <- * fld
        if ref != null:
            *fld <- newAddress(ref)
    dest < - newAddress(scan)
    move(scan, dest)