Allocator
프로세스는 메모리 공간을 필요로 한다. 하지만, 프로세스가 실행되기 전까진 필요한 공간의 크기를 알기 힘들다.
따라서, 정적 메모리 할당이란 각 프로세스들가 시작할 때 똑같은 크기의 적당히 큰 공간을 할당하는 방법이다.
하지만 이 방법은 메모리 공간이 낭비될 수 밖에 없고, 예기치 않게 프로세스가 종료되거나 실행되지 않을 수 있다. (전자는 프로세스가 할당받은 메모리 공간을 사용하다가 부족해질 경우, 후자는 실행 중인 프로세스가 너무 많아 할당받을 메모리 공간이 없는 경우)
반면에 동적 메모리 할당이란, 프로세스가 실행 중일 때 실시간으로 메모리를 요청하면 할당해주고 프로세스가 종료되거나 메모리 사용이 끝나면 반환받는 방법이다.
동적 메모리를 할당하는 방법은 힙 영역을 관리하는 '할당기(Allocator)'를 통해 구현한다.
명시적 할당기란(Explict Allocator), 명시적으로 공간을 할당하고, 반환해야 하는 방식으로서 사용 중인 프로세스에서 일련의 작업을 직접 처리 해줘야 한다.
묵시적 할당기(Implict Allocator)란, 할당한 공간에 대해서 더 이상 사용되지 않는다고 판단될 때 자동으로 반환해주는 방식으로 묵시적 할당기를 가비지 컬렉터(Garbage Collector), 작업을 자동으로 처리하는 것을 가비지 컬렉션(Garbage Collection)이라고 부른다.
Malloc
Malloc 은 메모리를 동적으로 할당하는 방법이며, 그 중에서도 할당받은 메모리의 일부분을 사용하고 남은 부분(가용한 부분)을 어떻게 관리하느냐에 따라 명시적, 묵시적, 분리 방법으로 나뉜다.
우리가 공부하는 CSAPP에는 묵시적(Implict) 방법으로서, malloc 함수가 호출되었을 때 각 할당 블럭과 가용 블럭의 헤더와 풋터에 담긴 사이즈를 확인하고, 블럭의 사이즈만큼씩 건너뛰며 가용 블럭을 찾는 방법을 알려주고 있다. 즉, 브루트 포스(brute force)와 비슷하다고 볼 수 있다.
가용 블럭을 고르는 방법에는 3가지가 있다.
- 전체 공간의 제일 앞 블럭부터 찾아서, 가장 먼저 만난 가용 블럭을 고르는 방법(first-fit)과
- 마지막 할당 블럭 다음부터, 가장 먼저 만난 가용 블럭을 고르는 방법(next-fit)
- 모든 가용 블럭을 다 순회하여 할당할 사이즈보다 크면서 할당 블럭 중 가장 작은 것을 고르는 방법(best-fit)
묵시적 방법은 가장 간단하지만 할당받은 전체 공간(힙)의 크기가 클수록, 할당과 해제가 여러번 반복될수록 점점 느려질 수 밖에 없다. (블럭의 수가 늘어나는 만큼, 건너뛰는 횟수가 많아지기 때문에)
따라서, 가용 블럭은 할당되기 전까지 빈 공간이므로 그 빈 공간을 그냥 놀리는 것이 아니라 빈 공간을 활용하여 가용 블럭을 찾는 시간을 단축하는 방법이 고안되었다.
그것이 바로 명시적(explict) 방법으로, 가용 블럭 안에 다음 또는 이전의 가용 블럭의 주소를 저장함으로써 할당 블럭은 배제하고 가용 블럭만 건너뛰며 가용 블럭을 찾는 방법이다. 하지만, 명시적 방법도 결국 묵시적 방법보다 덜 느려질 뿐, 느려지는 것은 필연적이다.
따라서, 아예 가용 블럭을 크기에 따라 관리하는 방법이 등장했다. 분리(segregated) 방법은, 미리 데이터 크기 별로 구역을 나누어 범위에 해당하면 데이터를 할당하는 방법이다. 이 방법은 들어갈 구역으로 한 번 나누고, 구역 안의 가용 블럭을 확인하는 방법으로 찾는 시간을 단축한다.
Fragmentation
결과적으로, 어떤 방법이 더 효율적인지는 기준을 어디에 두느냐에 따라 달라질 수 있다.
검색 시간(Time)으로 따진다면, 분리 방법이 가장 효율적일 것이다. 하지만 공간 활용(Space)으로 따진다면, 분리 방법이 가장 효율적이라고 보기 힘들다.
블럭 안에 빈 공간이 생기면 내부 단편화라고 한다. 블럭 외부, 즉 블럭이 들어갈 공간 자체에 빈 공간이 생기면 외부 단편화라고 한다. 결국 단편화라는 것은 공간 효율을 떨어트린다고 볼 수 있으며, 가용 공간을 분리한다는 것은 외부 단편화를 야기할 수 있기 때문이다.
동적으로 메모리를 할당하고 메모리 영역을 관리하는 방법은 결국 사용자가 어떤목적을 가지고 있는지에 따라 다양한 방식으로 구현될 수 있다.
