Garbage Collection: 힙공간에 할당된 공간을 자동적으로 반환해주는 것

• application이 free해줄 필요가 절대 없음
• Functional, scripting, 현대 Object oriented 언어에서 흔히 있음: Lisp, ML, Java, Perl, Mathematica...
• C와 C++에서는 보수적인 형태의 gc 존재 :모든 garbage collect(수집)불가:
• 언제 메모리 free시켜줄 지 memory manager가 알까?
  • 일반적으로 미래에 뭐가 어떻게 쓰일 지 알 수 있는 방법이 없음 (조건에 따라 다르므로)
  • 하지만 특정 블록들을 가르키는 포인터가 없다면 그 블록들을 사용(접근)할 수 없다는 건 알 수 있음.

1. 고전적인 GC 알고리즘

Mark & Sweep (McCarthy,1960)

• compact하지 않은 이상 블록을 옮기지 않음

Reference counting (Collins,1960)

CS에서 reference counting은 참조의 개수,포인터의 개수 등을 저장하는 프로그래밍 기술 또는 자원(object, 메모리 블록, 디스크 공간 등등)을 다루는 방식이다.
GC알고리즘에서 reference counting은 더이상 사용되지 않는 object들을 deallocate하기 위해 사용된다.

• 각 object에 관해 counting track를 참조하면서, 참조의 개수가 0이 되면 object가 접근 불가능하다고 판단하고 destroy(제거)할 수 있다고 판단.

• object를 제거하면 이 object에 의해 참조되고 있는 참조 카운트도 감소한다. 따라서 하나의 참조를 제거하면 free되는 object의 개수가 무지 커질 숟 있다.

• 이를 해결하기 위해 reference count가 0이 되면 바로 제거하기보다는 참조되지 않은 object리스트에 넣어 주기적으로 이 리스트에서 제거하는 방식을 취함.

• Simple reference count는 잦은 업데이트가 필요하다.

• 참조관계가 수정되거나 삭제되거나, object의 reference count가 감소하거나, object가 생성되거나 복사되어 reference count가 증가한다 등등의 경우.

• 쓰임

  • Reference counting은 파일시스템이나 distributed systems에서도 사용된다.
  • non-incremental tracing GC에서 object 그래프의 크기가 너무 크거나 접근 속도가 느려질 때

Copying collection(Minsky,1963)

• Mark-compact와 비슷하게 Copying collection은 garbage를 Collect하지는 않는다.
• 오히려 liveobject들을 한곳에 몰아주고, 나머지 힙 영역들은 오로지 garbage 밖에 없기 떄문에 사용가능하다는 걸 알 수 있다.
• 따라서 implicit(암시적)인 방식이다.

  Like markcompact but unlike marksweep copying
  garbage collection does not really collect garbage
  Rather it moves all of the live objects into one area
  and the rest of the heap is then known to be available
  because it contains only garbage Garbage collec
  tion in these systems is thus only implicit and some
  researchers avoid applying that term to the process
  Copying collectors like markingandcompacting
  collectors move the objects that are reached by the
  traversal to a contiguous area While markcompact
  collectors use a separate marking phase that traverses
  the live data copying collectors integrate the traversal
  of the data and the copying process so that most ob
  jects need only be traversed once Objects are moved
  to the contiguous destination area as they are reached
  by the traversal The work needed is proportional to
  the amount of live data all of which must be copied
  The term scavenging is applied to the copying
  traversal because it consists of picking out the worth
  while objects amid the garbage and taking them away.

그래프로 메모리 나타내기

메모리는 directed(방향이 있는) graph다.

• 각 블록들은 그래프의 node다.
• 각 포인터는 그래프의 edge다.
• 힙영역에 있지 않으면서 힙영역의 노드를 가르키고 있는 포인터들을 포함한 노드들은 root node들이다.
  • registers, stack영역에 있는 것, 전역 변수들 등등
    
• 위의 그림처럼 node(==블록)를 향한 edge(pointer)가 있다면 reachable(접근가능)하다.
• Non-reachable(접근불가능한) 노드들은 garbage다.
• 즉, 포인터(==edge)가 가르키지 않는(==이어져 있지 않는, 접근할 수 없는) 블록(==노드)들은 application에 의해 필요하지 않음

Mark & Sweep Collecting

전제

• Application
  – new(n): 모든 영역이 clear된 새로운 블록을 가르키는 포인터 return
  – read(b,i): register한테 b영역에 있는 i 위치 read
  – write(b,i,v): b 블록의 i 위치에 v write
• 각 블록은 header word를 가짐
  – addressed as b[-1], for a block b
  – collector에 따라 다르게 사용됨
• GC가 사용하는 Instructions
  – is_ptr(p): p가 포인터인지 아닌자 결정
  – length(b): header 불포함, b 블록 return
  – get_roots(): 모든 root returns

malloc/free 패키지 바탕으로 만들 수 있음

• 공간이 없어질 때까지 malloc을 활용해서 할당하기
• 공간이 없어지면
  • 각 블록에 있는 head의 추가적인 mark bit 를 사용하기
  • Mark(표시하기) : root에서 시작해서 접근가능한 모든 메모리에 bit set mark해주기
  • Sweep(빗자루로 쓸어주기): 모든 블록 스캔하기 ➡️ 할당은 됐지만 mark은 하지않은 블록들 free해주기
    
• Mark해주기 : 메모리 그래프에서 depth-first traversal
  
• Sweep해주기 : 포인터의 길이를 통해 다음 블록찾기

Conservative Mark & Sweep (보수적인)

• Is_ptr() : 할당된 메모리 블록을 가르키는 지에 따라 word가 포인터인지 결정
• C 포인터에서는 블록 중간을 가르킬 수도 있음!
  
• 블록 시작을 찾는 방법?
  • 균형트리를 활용해서 할당된 모든 블록 track ➡️ key 위치 파악
  • 균형트리 포인터는 header에 저장 될 수 있음 (word 2개 추가적으로 사용)

• 추가적으로 정리할 내용: Java Garbage Collection
• gc: reference counting에 관해
• Carnegie Mellon : Uniprocessor Garbage Collection Techniques
  

References

• Reference counting : wikipedia