[sp] Dynamic Memory Allocation : Advanced (2)

1. Segregated List (Seglist) Allocators

(1) 블럭의 각 크기별 클래스는 각자의 free list를 가짐

malloc(6)을 했을 때 알맞는 클래스를 찾아서 6만큼 할당하고,

나머지 남은 블럭은 이 블럭의 사이즈에 맞는 클래스에 연결해줌

 

(2) 종종 각각의 작은 사이즈에 대한 분리된 클래스를 가짐

(3) 큰 사이즈 : 각 2의 지수 크기의 블럭 클래스

 

(4) 크기가 n인 블럭을 할당하기 위해

 - n보다 큰 사이즈의 블럭에 대한 적절한 free list를 찾음

 - 만약 적절한 크기의 블럭을 찾았다면 -> 블럭을 분리하고, 이 분리된 블럭 중 할당되지 않은 블럭은 적절한 클래스를 찾아 이어줌 (선택)

 - 만약 블럭이 없으면, 다음의 큰 클래스에 이 과정을 반복

 

(5) 블럭이 없으면

 - OS로부터 추가적인 힙 메모리를 요청 (sbrk() 사용)

 - 이 새로운 메모리로부터 n 바이트의 블럭을 할당

 - 나머지는 더 큰 사이즈에 클래스에 단일 free block으로 둠

 

기존의 heap 공간에서 원하는 크기만큼 할당할 블럭이 없으면 sbrk()를 사용하여 brk를 증가시키면서 힙 공간을 늘려줌

거기서 원하는 만큼 할당을 해주고, 남은 힙 공간은 하나의 free block으로 만들어서

이렇게 9-info와 같은 적절한 크기의 클래스를 찾아서 이어줌

 

 

(6) 블럭 할당해제

 - 적절한 리스트에 합치고 넣어줌

 

(7) seglist allocator의 장점

 - 높은 throughput : 2의 지수 크기의 클래스에 대한 log 시간

 - 더 좋은 메모리 이용량 : fragmentation이 적음, segregated free list의 first-fit 서치는 전체 힙의 best-fit에 가까움

                                 : 극단적인 경우 - 각 블럭에 각 사이즈 클래스를 주는 것은 best-fit과 동일

 

 

 

 

2. Garbage collection

(1) Implicit memory management : Garbage collection

 - Garbage collection : 할당된 저장소인 힙의 자동 회수는 free할 필요 없음

void foo() {
    int *p = malloc(128);
    return; /* p block is now garbage */
}

int형의 포인트 p는 스택 안에서 힙의 32 x 4 = 128만큼의 int 배열을 포인트하고 있음

만약 foo가 종료되면 스택이 포인트하고 있는 것이 해제되면서 힙 안에 메모리 누수가 발생할 수 있는데 이를 garbage

 

(2) 어떻게 메모리 매니저는 메모리가 free된 것을 알까

- 일반적으로 조건에 따라 다르기 때문에 알 수 없음

- 하지만 특정 블럭에 대한 포인터가 없으면, 특정 블럭을 사용할 수 없음

 

(3) 포인터에 대한 가정

- 메모리 매니저는 non-pointer로부터 포인터를 구분

- 모든 포인터는 블럭의 시작 지점을 가리킴

- 포인터를 숨길 수 없음

(ex. int에 대한 포인터를 합치고 돌아옴)

 

 

 

 

3. Memory as graph

(1) 메모리는 방향 그래프로 봄

- 각 블럭은 그래프의 노드

- 각 포인터는 그래프의 엣지

- 힙에 없는 위치에서 힙에 대한 포인터를 포함하는 위치: root node

(ex. 레지스터, 스택의 위치, 글로벌 변수)

루트에서부터 노트까지의 path가 있으면 노드(블럭)은 reachable

non-reachable 노드는 garbage

 

리턴하면서 스택에서 힙 안의 노드를 가리키고 있던 포인터가 해제했을 경우,

힙 안의 노드들은 non-reachable이 됨

 

배열로 나타내면, 배열 안에는 reachable한 블럭과 non-reachable한 블럭이 섞여 있는데

non-reachable한 블럭은 free해줌

 

 

 

4. Mark and sweep collecting

(1) malloc / free package의 top에 빌드 가능

- 공간이 부족할 때까지, malloc을 사용하여 할당

 

(2) 공간 부족할 때

- 각 블럭의 헤드에서 추가적인 mark bit를 사용

- Mark : root에서 시작하며 각각의 reachable한 블럭에 mark bit를 세팅

- Sweep : 모든 블럭을 스캔하고 mark가 없는 블럭을 free

빨간 색 블럭들은 reachable

sweep에서 모든 블럭을 돌면서 mark bit가 없는 블럭은 free

 

(3) 간단한 구현을 위한 가정

- Application

 : new(n) - 모든 위치가 지워진 새로운 블럭에 포인터를 리턴

 : reab(b, i) - 블럭 b의 위치 i을 레지스터로 읽음

 : write(b, i, v) - 블럭 b의 위치 i로 v를 씀

 

- 각 블럭은 header word를 가짐

 : 블럭 b에 대해 b[-1]로 주소 지정

 : 다른 collector에서 다른 목적으로 사용

 

- GC에 의해 사용되는 명령어

 : is_ptr(p) - p가 포인터인지를 결정

 : length(b) - 블럭 b의 길이를 리턴 (헤더 포함하지 않음)

 : get_roots() - 모든 루트를 리턴

 

 

(4) Mark and sweep

- Mark

메모리 그래프의 깊이 우선 탐색을 사용하여 Mark

ptr mark(ptr p) {
    if (!is_ptr(p)) return; // do nothing if not pointer
    if (markBitSet(p)) return; // check if already marked
    setMarkBit(p); // set the mark bit
    for (i=0; i < length(p); i++) // call mark on all words
    	mark(p[i]); // in the block
    return;
}

포인터가 아니면 리턴하고 포인터이면 밑으로

mark bit가 세팅되어 있으면 리턴 그렇지 않으면,

포인터 p에 mark bit을 세팅하고

p의 길이만큼 블럭을 돌면서 깊이 우선 탐색을 하면서 위 과정 반복

 

 

- Sweep

다음 블럭을 찾기 위해 길이를 사용하여 sweep

ptr sweep(ptr p, ptr end) {
    while (p < end) {
    	if markBitSet(p)
    		clearMarkBit();
    	else if (allocateBitSet(p)) //non-reachable
    		free(p);
    	p += length(p);
}

모든 블럭을 스캔하면서,

p에 mark bit가 세팅되어있으면 mark bit를 지움

p에 비트가 세팅되어 있지 않고 비트가 할당되어 있으면 free

p에 p의 길이만큼 더해주면서 다음 블럭에서 위 과정 반복

 

 

 

(5) Conservative Mark & Sweep in C

- C 프로그램에서의 conservative garbage collector

 : is_ptr()은 포인터가 메모리의 할당된 블럭을 가리키는지 확인함으로써 워드가 포인터인지를 결정

 : C 포인터에선 블럭의 중앙을 포인트

 

- 그럼 어떻게 블럭의 시작을 찾음?

 : 균형 이진트리를 사용하여 할당된 모든 블럭을 추적

 (key : start-of-block)

 : 균형 트리 포인터는 헤더에 저장될 수 있음 (추가적인 2 word 사용)

 

left가 allocated돼 있다고 가정

-> mark 수행

-> sweep 시 할당돼 있으므로 free하지 않음 => conservative