[컴파일러 이론] 13. Memory Allocation

메모리의 구조를 다시 간단히 정리해보자.

 

메모리 안에 code와 data가 같이 저장되어있다.

data의 stack부분을 자세히 보면 이전에 알아봤던 AR을 단위로 저장된다.

stack과 code 사이에는 static data를 저장하는 공간도 있다.

프로그램 동작 중에 동적으로 생성되는 것들은 heap에 저장된다.

 

C, C++ 코딩 시에 메모리 free 등을 안해서 에러가 났던 경험이 한번씩 있을 것이다.

java,python 같은 언어는 garbage collection이라는 기능이 있어 알아서 이런 부분을 처리해준다.

이렇게 자동으로 메모리를 관리해주는 법을 알아보자.

---

Object Reachability

유저가 free를 명시적으로 하지 않았을 때, 언제부터 이게 정말로 필요하지 않을지 판단해야한다.

아래 그림에서 A는 더이상 reachable 하지 않다는 것을 알 수 있다.

reachable한지를 파악하려면, 메모리 안의 모든 포인터를 순회하면서 이 포인터들이 가리키고 있는 것들을 확인하면 된다.

그 애들에서 또 검사를 수행한다.

아래 그림에서 B에 의해 A는 reachable하게 된다.

D,F는 unreachable하다.

이런 대상들이 garbage collection의 대상이 된다.

 

 

---

Garbage Collection

garbage collection을 하는 몇가지 방법이 있다.

 

1. Mark and Sweep

이는 두 단계로 나눠진다.

 

mark phase : reachable한 것을 찾고 표시

sweep phase : garbage를 처리

 

각 객체에 대해 reachable한지 아닌지를 나타내는 1비트가 붙어있다고 가정하자.

mark phase에서 DFS, BFS같은 방법을 사용해 이 비트의 값을 정할 수 있다.

sudo코드

sweep phase에서는 heap을 스캔하면서 마킹이 안된 애들을 free list에 넣어놓는다.

바로 할당을 해제하지 않고 free list에 넣어놓는 이유는 나중에 사용되기 때문이다.

 

아래 예시를 보면 이해하기 수월하다.

 

이 방법의 구현에는 약간 생각할 것이 있다.

이 garbage collection을 하는 이유는 메모리에 여유 공간이 없어서 필요없는 것을 없애서 공간을 확보하기 위해서인데,

따라서 이 과정에 추가적인 메모리 소모가 없어야한다.

 

그래서 아래의 방법으로 최소한의 메모리만 사용하여 mark를 할 수 있다.

 

여기서 네모 하나하나는 각각 오브젝트이다.

 

루트에서 100번지로 포인터를 따라 왔다고 가정한다.

reachable하기 때문에 mark bit을 의미하는 앞의 숫자는 1이 된다.

 

이제 포인터를 따라 200번지로 가고 mark bit을 1로 바꾼 후, 다시 돌아갈 수 있도록 100을 prev ptr에 저장한다.

 

300번대로 또 이동을 하는데 위와 똑같이 prev ptr에 200을 저장하면 200에서 100으로 돌아갈 방법이 없어진다.

그래서 임시로 원래 300을 가리켰던 200의 포인터를 100을 향하게 바꾼다.

 

300번대를 전부 확인하고 prev ptr을 통해 200번대로 돌아가고,

여기서 임시로 바뀐 포인터를 통해 100번대로 다시 돌아가면서 포인터도 원래대로 돌려놓는다.

이런 방식으로 마킹을 할 수 있다.

 

위에서 잠깐 얘기한 free list는 linked list 형태인데 새롭게 저장할 내용이 있다면 이 리스트 안에서 적당한 공간을 찾아 저장된다.

 

하지만 위의 방법을 사용해 mark and sweep을 하는 것은 오래 걸린다.

그래서 두 번째 방법이 있다.

 

 

---

2. Stop and Copy Organization

애초에 메모리 공간을 나눠서 사용하는 것이다.

old  space : 기존의 메모리의 용도로 사용

New space : Garbage Collection을 위해 남겨두는 빈 공간

 

heap pointer라는 것을 사용해 stack처럼 데이터를 쌓아간다.

old space가 가득차면 garbage collection을 하고, 그 결과인 살아있는(사용되는) 오브젝트들만 new space에 다시 넣는다.

이렇게 되면 두 space가 역할이 바뀌게 된다.

여기서 new space로 옮길때마다 연관된 포인터들도 다 바꿔주는 것은 시간이 오래 걸린다.

그래서 laze update라는 방법을 사용한다.

 

예시를 통하는 것이 훨씬 더 쉽게 동작을 이해할 수 있다.

Scan/Alloc라는 화살표를 기준으로 왼쪽이 old, 오른쪽이 new이다.

old가 가득찼으므로 이제 new로 옮겨야한다.

 

먼저 root에서 시작해 A를 보자.

root에서 직접 포인터를 따라온것이므로 reachable하다.

따라서 A를 new space에 넣는다.

다만 원래 B→A, F→A의 포인터관계도 있는데, 이런 것을 모두 탐지해서 포인터를 new space의 A를 가리키게 바꾸는 것은 너무 시간이 오래 걸린다.

대신 원래 A자리에 새로운 A를 가리키는 포인터(forwarding pointer)를 만든다.

이렇게 되면 B,F의 포인터를 바꾸지 않아도 새로운 A를 가리킬 수 있게 된다.

대신 A에서 나오는 포인터(A→C)는 수정해줘야한다.

이제 A가 가리키는 대상인 C에 대해 비슷하게 작업을 수행한다.

당연히 reachable한 A에서 도달한 C이므로 C도 reachable하고 new space로 이동된다.

기존 C자리에는 forwarding pointer를 넣어주고, 새로운C→F 처럼 포인터도 만들어준다.

New space의 A에서 C를 가리킨 것이므로 새로운 A → 새로운 C 의 포인터도 추가한다.

 

alloc은 현재 new space에 추가된 오브젝트의 끝을 가리킨다.

scan은 아래처럼 A에서 이어지는 다른 오브젝트들을 모두 처리완료 했을 때 이를 표현하기 위해 사용한다.

이를 끝까지 반복하면 된다.

laze update는 new space에 추가할 때 바로 포인터를 처리하는게 아니고 scan이 지나갈 때 처리하는 것이다.

아래 그림에서 scan/alloc이 잘못 표시되어 있는데, scan은 C/F 사이에 있어야 한다는 것을 알고 설명을 봐야한다.

 

어쨋든 C/F사이의 Scan이 F를 거쳐가면서 laze update가 일어난다.

F는 예전A로 포인터가 가있는데, 포인터를 따라가보니 이미 forward pointer가 있다. 그럼 새로운F는 이 forward pointer가 가리키는 새로운A를 향하게 바꾸는 것이 laze update이다.

 

이 stop and copy는 과정에서 봤듯이 아예 B같은 garbage를 건드리지 않는다. 

sweep 방식은 전체를 보기 때문에 garbage가 많으면 stop and copy가 유리하다.

 

이 stop and copy는 garbage collection 기법 중 일반적으로 가장 빠르다.

allocation도 heap pointer를 하나씩 늘리면서 가능하다.

반면 mark and sweep은 linked list를 순차적으로 돌면서 공간을 찾아야한다.

 

---

3. Reference Counting

이전 방법까지는 메모리가 가득찼을 때만 garbage collection이 실행된다.

그래서 메모리가 다 차기 전까지는 좋지만 가득 찬 이후 collection이 실행되면 너무 오래 걸린다.

그래서 그때그때 collection이 가능해지면 바로 수행하는 방법이 이 방법이다.

 

각 오브젝트는 reference count라는 값을 가지고 있다.

자신이 참조되는 횟수를 나타낸다.

즉 이 값이 0이 되면 더이상 필요없는 오브젝트이므로 바로바로 garbage collection을 한다.

다만 아래 같이 서로 포인터가 있을 경우, x가 할당이 해제되더라도 두 오브젝트의 reference count는 0이 아닌 1이되어서 collection이 이루어지지 않는다. 이런 경우는 별도의 조치가 있어야한다.

어쨋든 이 방식은 항상 조금씩 느린 대신 한번에 극단적으로 느려지는 경우를 막을 수 있다.