동적 메모리 할당(2)

앞 포스트에 이어서 설명하도록 하겠다.

 

이전까지 할당기가 어떻게 사용가능한 공간을 찾아주는지 알아봤다. 이번에는 할당기가 할당된 공간을 해제(free) 했을 때 생겨나는 빈 공간을 어떻게 처리 할 지에 대해서 알아보자.

사용 가능한 공간 연결

위 그림에서 볼 수 있듯이, 할당기가 공간을 반환할 때 헤더에 있는 allocate bit를 0으로 바꿔주기만 한다. 즉, 자동으로 인접한 빈 공간에 붙혀주는것은 아니다. 만약 자동으로 연결해주었다면 위 그림은 16/0으로 바뀔것이 아니라, 32/0이 됐을 것이다.

 

다시 위 예시에서, 할당기가 첫번째 그림에서 빨간색으로 표시한 부분을 해제했다고 해보자. 그렇다면 16바이트의 새로운 사용 가능한 공간이 생기는 것이고, 총 32바이트의 사용 가능한 공간이 힙에 존재하게 된다. 그래서 24바이트의 새로운 공간을 요청하면 당연히 저 공간 안에 할당 할 수 있을 것이라 생각된다. 하지만 24바이트의 새로운 공간을 탐색하다보면 할당기는 빈 공간이 없다고 판단할 것이다. 그 이유는 할당기가 리스트를 돌아다니면서 헤더에 쓰여진 사이즈 정보를 보고 빈 공간을 찾는데, 그림에서 볼 수 있듯, 사이즈 16바이트 짜리 가용공간이 두개가 존재하므로 24바이트는 들어갈 수 없다고 판단하는 것이다. 때문에 두 빈공간을 합쳐주는 연산이 필요하다.

 

위 예시와 다르게 빈 공간이 할당 해제된 공간의 '이전에' 생길 수 도 있기에, 우리는 이전 블럭의 정보도 알고 있어야한다. 이는 Footer라는 경계 태그를 추가함으로써 해결 할 수 있다.

 

Footer는 Header의 정보를 똑같이 가지고 있다. 다만 Header가 현재 블럭 이전의 블럭을 찾는데 쓰이는 반면 Footer는 현재블럭 다음 블럭을 찾는데 사용된다.

 

힙은 블럭들이 연속적으로 존재하기 때문에 헤더에서 4바이트(한 블럭 사이즈)를 빼면 이전 블럭의 푸터의 위치이며, 푸터에서 4바이트 만큼 더하면 다음 블럭의 헤더를 찾을 수 있다.

 

할당기가 현재 블럭을 할당 해제 할 때 생길 수 있는 경우의 수는 4가지이다. 참고로 위에서 본 예시는 2번 경우이다. 

1. 이전 블럭과 다음 블럭이 모두 할당 돼 있는경우
2. 이전 블럭은 할당 돼 있고 다음 블럭만 사용 가능할 경우
3. 이전 블럭은 사용가능하고 다음 블럭이 할당 돼 있는 경우
4. 이전, 다음 블럭 모두 사용 가능한 경우

이전까진 힙을 가로로 배치해서 해당 그림이 햇갈릴 수 있을것이다. 이 그림은 아래위로 힙이 배치된 것이라고 생각하면 이해하기 쉬울 것이다. 그리고 가용블럭인지 할당된 블럭인지는 a(allocate), f(free)로 구분하고 있다.

이렇게 빈 공간들을 서로 연결해주고 할당기는 헤더와 푸터에 저장된 정보를 갱신 해주어야한다. 위 그림에서 볼 수 있듯, 할당기는 헤더와 푸터에 29비트 만큼의 영역에 기존의 가용공간과 할당 해제함으로써 생긴 공간의 사이즈를 더해 갱신해준다. 또한 기존에 할당됐던 공간의 allocate bit를 가용 공간임을 나타내는 0으로 바꿔줌으로써 힙을 관리한다.

 

Explicit free list

우리는 이전에 implicit free list에서 대해서 살펴봤었다. 할당기는 힙을 돌아다니면서 특정 사이즈의 빈 공간을 찾고(헤더, 푸터에 기록된 사이즈 정보) 그 공간이 사용할 수 있는 공간이라면 (allocate bit가 0인 공간) 할당 해주는 방식을 취했다. 하지만 이 방식은 free하지 않은 공간에 대해서도 살펴보아야한다.

 

때문에 사용 가능한 공간을 이중 연결리스트로 저장한다면, 공간 할당이 필요한 경우 이 연결리스트를 순회하면서 사이즈만 비교하면 됫것이다. 이러한 방식을 Explicit free list라고 한다.

이렇게 하려면, 이중 연결리스트를 구현할 때 처럼 사용 블럭안에 앞 노드(여기서는 사용 가능한 블럭을 의미한다.)와 뒷 노드를 가르키고 있는 특정한 포인터를 필요로 한다. 그 모습은 아래 그림과 같다.

 

사용 가능한 공간에는 Payload(데이터를 저장하는 공간)에는 무엇이 들어있든 상관이 없다. 그저 할당이 필요하다면 allocate bit를 1로 바꿔주고 새로운 데이터를 덮어 써 버리면 되기 때문이다. 그래서 Free block에는 이전 가용공간과 다음 가용 공간의 주소를 가지는 특정한 변수를 넣어줄 수 있다. 이는 각 pred, succ로 해보자.

 

가용 블럭을 찾을 때 first fit을 쓴다고 가정하고, 할당을 위해서 사용 가능한 공간을 순회할 때, 우리는 Root(힙의 제일 첫부분)에 연결된 블럭부터 차례로 succ를 찾아보면서 사이즈를 비교, 할당 가능하다면 바로 할당해 주면 된다.

 

문제는 할당된 후에 생긴다. 새로운 공간을 할당하면, 아래 그림과 같이(흰 블럭이 사용가능한 공간을 의미한다.)새로운 빈 공간이 생기게 되는데, 기존에 있던 연결을 끊고 새로 생겨난 빈 공간을 기존의 빈 공간에 다시 연결해주는 작업이 필요 할 것이다. 이는 연결리스트에 노드를 삭제할 때 연산과 비슷하다.

 

 

설명을 간단히 하기위해서 새로 생긴 사용 가능한 블럭을 Root 뒤에 붙힌다고 가정하겠다. 이는 LIFO(last in first out) policy라고 불린다. 이는 간단할 뿐만 아니라 새로운 가용 공간을 연결 해줄 때 상수시간이 걸리게 해준다.

 

이런 연결작업은 할당 뿐만 아니라 할당 공간을 해제 할 때도 주의해야한다. 마치 연결리스트의 삽입 연산과 같이 노드가 삽입 될 때 앞 뒤 노드와 연결 해주는 것처럼 말이다. 하지만 연결리스트완 달리 이번 예시는 LIFO를 가정했기에 새 빈 공간이 생기면 그저 Root에 붙이기만 하면 된다.

다시, 할당된 블럭을 해제하고 나면 새 가용 공간이 생겨나는데, 이를 위해 적절히 가용 블럭끼리 연결해주는 작업이 필요하다.

 

Explicit free list는 Implicit free list와 달리 가용 공간을 탐색하는 시간이 가용 공간의 수에 비례한다. 반면에 Implicit 방식은 힙에 있는 블럭의 수에 비례하는 시간걸린다.

 

그러나 일반적으로 Explicit free list는 최소 블럭의 크기가 Implict 방식보다 커진다. Implict 방식은 Payload가 없다면 헤더와 푸터의 크기 즉, 8바이트만 있어도 충분하다. 그러나 Explicit free list는 pred와 succ을 포함하기에 최소 16바이트를 필요로 한다. 두 방식모두 장점과 단점이 존재하기 때문에 중요도에 따라서 적절히 방식을 선택하면 될 것이다.

정리

이제 동적 메모리 할당의 기본 개념들을 대부분 살펴본 것이라 할 수 있다. 이 개념으로 간단한 할당기를 만들 수 있을 것이다. 할당과 해제 이 너머에 있는 가용블럭의 연결, 탐색 등을 살펴보았다. 이번 공부를 통해 메서드의 인터페이스 너머에 있는 메모리라는 미지의 공간에 한발 내딪은듯 해서 뭔가 뿌듯하다!