Malloc Lab | 동적 메모리 할당(2) - 묵시적 가용 리스트(Implicit free list)

 

Malloc Lab | 동적 메모리 할당(1) - 개념 정리

Malloc Lab | 동적 메모리 할당(1) - 개념 정리

 

 

이전 포스팅에서 동적 메모리에 대한 간단한 개념 소개와 명시적 할당기 중 묵시적 가용 리스트, 명시적 가용 리스트 두 가지 방법에 대해서 짧게 설명했었다. 이번에는 묵시적 가용리스트(Implicit free list, 줄여서 Implicit라고 부르겠음)에 대해 정리해보려고 한다.

 

 

묵시적 가용 리스트(Implicit free list)

실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당기는 이 정보를 블록 내에 내장한다.

 

힙 블록의 포맷

 

위의 그림은 Implicit 리스트의 한 블록의 구조이다. 이 경우에 한 블록은 1워드 헤더(header), 데이터, 추가적인 패딩(padding)으로 구성된다.

• 헤더(header) : 헤더는 블록 크기(헤더와 추가적인 패딩 포함)와 블록이 할당되었는지 가용 상태인지를 반환한다. 이전 글에서 설명했던 것 처럼 한 블록, 즉 1워드(4byte)이고 우리는 할당기가 8byte 더블 워드 정렬을 기준으로 구현할 것이다. 더블 워드 정렬 조건으로 할당되는 블록의 크기는 항상 8의 배수이고, 블록 크기의 하위 3비트는 항상 0이다(8의 2진수는 1000으로, 하위 세 비트는 항상 0!). 그래서 하위의 3개의 비트는 다른 정보를 담기 위해 남겨둔다. 다른 정보라고 하면, 블록이 할당 되었는지, 아니면 가용 상태인지를 나타내기 위해 필요하다는 의미다. 위의 그림에서 Header 부분의 a를 보면 a=1일 때는 할당 상태, a=0일 때는 가용 상태라는 것을 보여준다. 즉 우리는 블록을 선택하는 과정에서 블록의 할당, 가용 상태를 파악해야 하는데, 헤더를 통해 블록의 할당 상태를 알 수 있다.
  
  
• 데이터 : 헤더 다음에는 malloc을 불렀을 때 요구한 데이터가 따라온다.
  
  
• 패딩(padding) : 데이터 다음 남는 공간에는 패딩이 따라올 수 있는데, 패딩의 크기는 가변적이다. 패딩을 해야 하는 이유 1) 외부 단편화를 극복하기 위해서, 2) 정렬 요구사항을 만족하기 위해서

위와 같은 방법으로 블록 포맷이 주어졌을 때, 힙을 연속된 블록의 배열로 구성하면 아래와 같은 그림으로 구성된다.

 

Implicit list 사용하여 힙 구성하기

 

위 그림으 보면 두 번째 블록의 8/0은 가용한 상태의 블록이 8byte 있다는 뜻이고, 그 다음 16/1은 할당된 블록 16byte가 있다는 뜻이다. 16/1 바이트의 마지막 의 진한 색의 블록은 패딩을 나타낸다. 

 

이러한 구조를 묵시적 리스트(Implicit list)라고 부르고, 가용 블록이 헤더 내 필드에 의해 묵시적으로 연결되어 있다는 의미이다.

 

 

할당한 블록의 배치

어플리케이션이 메모리 할당을 요청할 때, 할당기는 요청한 메모리를 저장하기에 충분히 큰 가용 블록을 검색한다. 검색을 수행하는 방법에는 first fit, next fit, best fit이 주로 사용된다.

 

| First fit

First fit은 가용 리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용 블록을 선택

| Next fit

Next fit은 fisrt fit과 비슷하지만 검색을 리스트의 처음에서 시작하는 것 대신 이전 검색이 종료된 지점에서 검색 시작

| Best fit

Best fit은 모든 가용블록을 검사하여 크기가 맞는 가장 작은 블록을 선택

 

 

가용 블록의 분할

교재를 읽으면서 글이 잘 읽히지 않아서 그냥 대충 그림을 그려봤다.

 

만약 24바이트 짜리 가용 블록에 a라는 블록을 할당한다면 문제될 것이 없다. 그러나 8바이트 크기의 b 블록을 할당하게 된다면 6칸의 가용 블록 중 4칸의 내부 단편화가 발생하게 된다. 이런 메모리 낭비를 해결하기 위해 b 블록의 두 칸은 할당하고, 나머지 4칸은 분할해서 새로운 가용 블록을 만들면 메모리를 효율적으로 사용할 수 있다.

 

 

추가적인 힙 메모리 획득

우리가 요청한 만큼의 가용 블록이 없다면 추가적인 힙 메모리를 요청해야 한다. 이 때 sbrk함수를 호출하여 추가 메모리를 획득할 수 있고, sbrk함수에 대해서는 구현할 때 다시 설명하겠다.

 

 

가용 블록 연결

아래의 그림을 보면,

 

 

중간에 가용 가능한 블록(16/0)이 두 개로 나뉘어져 있다. 이를 오류 단편화라고 한다. 이를 극복하기 위해서는 연결이라는 과정으로 인접한 가용 블록들을 통합해야 한다. 

 

요렇게!

 

 

경계 태그로 연결

할당기는 어떻게 연결을 구현할까? 반환하려고 하는 블록을 '현재 블록'이라고 할 때, 다음 가용 블록을 연결하는 것은 쉽고 효율적이다. 현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용 가능한지 판단할 수 있는 근거가 된다.

 

그러나 현재 블록 이전의 블록은 어떻게 연결할 수 있을까? 현재 블록에 도달할 때까지 전체 리스트를 검색해서 이전 블록의 위치를 찾아내야 할 것이고 이는 시간 소모가 크다.

 

이런 문제를 해결하기 위해 경계 태그, 즉 풋터(footer)라는 기법이 생겼다. footer는 헤더를 복사한 것으로, 헤더와 마찬가지로 4byte를 차지하게 된다.

 

footer가 필요한 이유를 다시 강조하자면 가용 블록을 효율적으로 찾기 위해서이다. 달리 표현해서 할당 블록에서는 풋터가 오히려 메모리 사용에 방해가 된다. 예를 들어 4byte의 데이터를 할당받는다고 할 때, 우리는 헤더, 풋터를 포함해서 총 12byte를 할당받는다. 매우 비효율적이라는 것이다. 즉 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있고, 헤더와 풋터가 할당된 블록의 절반을 차지하게 될 수도 있다.

 

한 블록의 포맷 예시 그림. 아래 Footer라는 풋터 블록을 찾을 수 있다.

 

 

다음 글에는 malloc lab을 Implicit 방법으로 구현한 것을 포스팅하려고 한다.