프로세스 메모리의 구조, 동적 할당과 가용 리스트의 관리

프로세스가 실행되면 프로세스를 수행하기 위한 정보가 메모리에 로드되는데, 이는 크게 코드, 데이터, 힙, 스택 영역으로 구분된다.

 

코드 영역은 프로세스를 구성하는 코드 텍스트, 데이터 영역은 프로세스 전체에 선언된 전역 변수를 관리하는 영역이고, 프로세스에 할당된 메모리에서 가장 앞(값이 작은 주소)에 존재한다. 반대로 스택 영역은 각 스레드별로 선언된 지역변수, 매개변수를 관리하는 영역이고, 이름에서 알 수 있듯이 할당된 메모리 구역의 끝에서부터 역순으로 채워지는 스택의 구조이다.

 

이 세 영역은 컴파일 단계에서 그 크기가 정해지는데, 프로세스의 런타임에 인터랙션이 존재하는 경우 컴파일 단계에서는 크기를 예측할 수 없는 메모리의 요구가 발생한다. 이 요구에 대해 메모리를 할당하기 위해 존재하는 것이 데이터와 스택 영역 사이의 힙 영역이며, 여기에서 프로세스 런타임 중 동적으로 요구되는 메모리의 할당과 해제를 담당하는 것이 메모리 동적 할당 시스템이다.

 

메모리 동적 할당 시스템은 사용 가능한 공간, 사용중인 공간을 블록화하여 관리하는데, 각 블록마다 header와 footer를 가져 경계를 나눈다. 또한 여기에는 블록의 사이즈와 할당 여부를 명시하여 블록간의 이동, 할당할 공간의 탐색을 용이하게 한다.

원시적인 메모리 동적 할당 시스템인 묵시적(Implicit) 가용 리스트는 이 HDR, FTR에 기록된 블록의 크기와 할당 여부를 통해 가용상태이며 용량이 충분한 블록을 찾을 때까지 메모리를 순회한다. 하지만 이는 점유 상태라 사용이 불가능한 블록들도 탐색에 포함되기 때문에 비효율적이다. 따라서 HDR, PTR 외에 추가적으로 16바이트(char* x2)의 오버헤드를 더 사용하는 것으로 linked list의 prev, next element를 명시하여, 가용 상태인 블록들만의 리스트를 구축하는 것으로 불필요한 탐색을 건너뛸 수 있다. 이를 명시적(Explicit) 가용 리스트라고 한다.

 

명시적 가용 리스트를 채택한 동적 할당 시스템에서는 이 linked list를 어떤 방식으로 관리하고 탐색할 것인지에 따라 시간, 공간 활용성에서 일장일단이 있다.

 

먼저 항상 start node부터 탐색을 시작하는 first fit이 있다. 일반적으로 구축된 가용 리스트는 블록의 물리적 주소값 순서대로 정렬되어 있는데, 이를 처음부터 순차적으로 탐색하기 때문에 항상 할당가능한 사이즈의 블록 중 가장 낮은 주소값의 블록부터 할당되고, 이는 메모리 할당을 낮은 주소값에 편향시키는 결과를 만들어 외부 단편화를 최소화한다.

 

다음으로 이전 할당된 블록의 위치부터 탐색을 시작하는 next fit이 있다. 새 할당이 요구되었을 때, 그 사이즈는 직전에 할당된 블록보다 클 수도 있고 작을 수도 있다. 만약 그보다 클 경우에는, first fit으로 탐색을 한다면 이미 직전 탐색에서 크기가 부족함이 확인된 블록들을 다시 한 번 순회해야 하는 비효율이 발생한다. 따라서 next fit은 이런 비효율을 확률적으로 개선하는 것으로 할당을 위한 탐색의 시간을 줄인다. 하지만 next fit은 메모리 전체를 균등하게 순회하기 때문에 할당된 블록이 first fit과는 달리 낮은 주소값에 편향되지 않고, 이는 외부 단편화에 더 취약함을 의미한다.

 

마지막으로 가장 공간의 낭비가 적은 블록을 탐색하는 best fit이 있다. best fit은 물리적 주소값 순서로 정렬된 가용 리스트를 전체 순회하여 최적의 블록을 선택하거나, 가용 리스트를 사이즈 역순으로 정렬하여 할당가능한 가장 작은 블록에서 탐색을 멈추는 것으로 구현이 가능하다. next fit과 마찬가지로 할당된 블록들이 편향되어있지 않아 외부 단편화에는 취약하지만, 할당된 블록 내에서 가장 공간의 낭비가 적으므로 내부 단편화는 가장 적다. 하지만 best fit을 찾는 과정을 거치므로 다른 시스템에 비해 시간이 더 소요된다.