Malloc Lab
동적 메모리 할당(Dynamic Memory Allocator)
C언어에서 변수와 함수를 선언하고 사용하는 과정에서 이들을 저장하기 위한 메모리를 사용한다. 작성자가 정의한 변수와 함수는 스택(Stack)영역에 저장되고, 함수가 호출되면 스택영역의 메모리를 사용하며 커지게 되며, 리턴되면 줄어드는 방식으로 작동하게 된다.
프로그램들이 동적 메모리 할당을 사용하는 가장 중요한 이유는 종종 이들이 프로그램을 실제 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문이다. 동적 메모리 할당은 유용하고 중요한 프로그래밍 기술이다. 그렇지만, 프로그래머들은 할당기를 정확하고 효율적으로 사용하기 위해서 어떻게 동작하는지 이해할 필요가 있다.
동적 할당된 메모리는 힙(Heap)영역에 malloc과 free를 사용하여 할당되고 해제된다. 힙 영역을 그림으로 표현하면 다음과 같다.
각 칸을 4byte 차이만큼 표시한 이유는 32bit 시스템의 경우에는 포인터의 사이즈가 4byte이기 때문이다. 파란색 부분은 할당된 부분, 흰색 부분은 할당이 해제된 부분이다. 그림은 할당된 부분과 해제된 부분이 차례로 그려졌지만, 할당된 부분들은 얼마든지 연속적으로 붙어있거나 떨어져있을 수 있다. 단, 할당이 해제된 부분은 단편화 문제를 해결하기 위해 연속적으로 존재할 수 없다.
단편화(Fragmentation)
단편화는 사용하지 않거나 사용하지 못하는 메모리가 쌓여서 메모리 누수를 유발할 수 있는 경우를 말한다. 단편화는 크게 내부 단편화(Internal Fragmentation), 외부 단편화(External Fragmentation)로 나뉜다.
내부 단편화
내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다. 즉, 할당된 블록이 payload보다 클 때 일어난다. 할당된 주소는 (64bit 기준) 16의 배수라는 규칙을 지키기 위함이다. 예를 들어 요청된 paylaod는 5 더블 워드라면, 5 * 8로 현재 메모리주소로부터 40바이트 뒤에 다음 payload가 할당되게 된다. 현재 주소는 이미 16의 배수라는 가정 하에, +40 byte 된 다음 주소가 16의 배수가 아니게 되는것이다. 따라서 요청된 payload보다 더 큰 메모리를 할당해 다음 payload가 할당될 주소를 맞춰주는데, 이때 추가할당되는 메모리를 padding이라고 한다.
내부 단편화는 정량화하기가 간단하다. 내부 단편화는 외부 단편화와 달리 메모리가 얼마나 추가할당되었는지 계산하기 편하다. 실제 할당된 메모리 - payload크기의 합으로 구할 수 있다.
외부 단편화
외부 단편화는 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
외부 단편화는 이후에 어떤 할당 요청이 들어오냐에 따라 생길수도 있고 생기지 않을수도있는 문제이다. 같은 양의 메모리가 요청되어도 작은 양이 여러번 요청되면 생기지 않을 수 있는 문제가 크게 한번에 요청되면 남은 공간이 분할되어있어서 그만한 큰자리가 남아있지 않을 수도 있기 때문이다. 따라서 계산이 어렵고 예측이 불가능하다.
외부 단편화가 측정이 어렵고 예측하기 불가능하기 때문에 할당기들은 대개 많은 수의 더 작은 가용 블록들보다는 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법들을 채택하고 있다.
이러한 단편화 현상을 방지하는 효과적인 메모리 동적할당을 위해서는 다음과 같은 필요한 정보들과 유의점들이 있다.
- 할당할 메모리의 크기는 얼마만큼인가?
- 할당할 메모리의 위치는 어디인가?
- 메모리를 할당할 수 있을 만큼의 비어있는 공간은 어떻게 찾을 것인가?
- 해당 메모리 공간이 할당되어있는지, 비어있는지는 어떻게 알 것인가?
- 해제되어 비어있는 메모리들을 어떻게 관리해서 다시 할당받을 수 있게 할 것인가?
- 공간의 효율성을 높일 수 있게 단편화는 어떻게 해결할 것인가?
유의점들을 효과적으로 알 수 있게 하여 메모리를 관리하고자 구조화 한 것이 블록(block)이다.
블록(block)
블록은 다음과 같은 구조이다. 좌측과 우측의 블록은 서로 다른 블록이며, 아래 설명하는 할당 방법들에 따라 사용하는 블록의 형태는 달라진다.
블록은 malloc 함수를 이용해 할당된 정보들이 저장되는 공간이다. malloc 함수는 heap 다음과 같은 블록은 여러가지 정보들을 저장하고 있다.
-
Header(4byte) : 블록의 시작점을 나타내는 부분이다. 해당 블록의 사이즈와 할당이 되어있는지 정보를 32bit(4byte)의 unsigned int 형태로 가지고 있다. 31부터 3번째 index의 bit는 사이즈 정보를 0번째 index의 bit는 할당여부 정보를 나타낸다. 1은 할당, 0은 할당 해제를 나타낸다.
-
Payload( byte) : 실제 정보들이 들어가는 부분이다. 정보의 양에 따라 여러 크기를 가질 수 있지만, 편의상 4byte 단위로 반올림하여 저장할 용량을 결정한다.
-
Padding (가변적, byte) : 패딩의 크기는 가변적이다. 패딩은 외부 단편화를 극복하기 위한 할당기 전략의 일부분이다. 패딩은 정렬 요구사항을 만족하기 위해 필요할 수 있다.
-
Footer(4byte) : 블록의 끝점을 나타내는 부분이다. header의 정보와 동일한 정보를 가지고 있다.
-
Previous or Next free block pointer(4byte) : 할당의 방법 중 할당이 해제된 블록들의 정보만을 관리하는 경우에 이용한다. 할당이 해제된 블록의 포인터들이 저장되어 있으며, 이중 연결리스트의 형태로 할당 해제된 블록들의 정보를 저장한다.
할당기
할당기는 크게 명시적 할당기, 묵시적 할당기가 있다.
-
명시적 할당기 : 어플리케이션이 명시적으로 할당된 블록을 반환해줄 것을 요구함
- C에서는 malloc 함수를 호출해서 블록을 할당, free 함수를 호출해서 블록을 반환.
-
묵시적 할당기 : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고, 언제 블록을 반환하는지를 할당기가 검출할 수 있어야 한다.
- 자바에서는 grabage collector라는 개념이 있으며, 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 한다.
명시적 할당기의 조건은 다음과 같다
- 임의의 요청 순서 처리
- 가용할 수 있는 블록이 할당 요청에 의해 할당되어야 한다. 아무순서로 할당과 반환요청을 할 수 있어야 한다.
- 요청에 즉시 응답 & 블록 정렬
- 할당기는 블록들이 어떤 종류의 데이터 객체라도 저장할 수 있고 정렬해야 한다.
- 힙만 사용
- 할당기가 사용하는 비확장적인 자료 구조는 힙 자체에 저장되어야 한다.
- 할당된 블록을 수정하지 않기
- 일단 블록이 할당되면 임의로 이들을 수정하거나 이동하지 않아야 한다.
또한 메모리는(가상메모리라도) 무한하지 않다. 결국 한정된 디스크 크기에 기반하기 때문에 우리는 무조건적으로 할당기를 통해 할당만 할 수는 없다. 할당과 해제를 적절히 처리해줘야하는 것이다. 그러므로 할당기는 가용한 힙에 가능한 많은 데이터를 넣기 위해 적절한 균형을 찾아야 한다.
Malloc Lap 구현 Github 링크
Malloc Lap
