[Computer System] 동적 메모리 할당

동적 메모리 vs 정적 메모리

우리가 특정 프로세스를 실행하면, 운영체제는 실행된 프로세스에게 특정 메모리 공간을 할당해 준다. 그 메모리 공간을 그림으로 간단하게 나타내면 아래와 같다. 

위의 그림에서 .bss, .data, .text 영역은 정적인 데이터들이 저장되는 공간이다. 정적 메모리는 데이터들이 컴파일 단계에서 메모리 할당이 이루어지는 공간이다. 

이와 달리 Heap 영역이나 Stack 영역은 컴파일 이후에 프로그램이 실행되고 나서 메모리 할당이 발생하는 공간이다. Stack 영역은 함수의 지역 변수 또는 매개 변수가 저장되는 공간이고, Heap 영역이 바로 우리가 malloc 또는 free 함수를 통해 변수에 메모리를 할당하고 해제할 수 있는 영역이다. 

 

이렇게만 표현해서는 정확히 정적 메모리와 동적 메모리가 무엇이 다른지 알기 힘들 수 있다! 좀 더 쉽게 이해하기 위해 한 가지 예시를 들어보자. 

 

C언어에서 배열을 초기화할 때, 배열의 최대 크기를 지정해 줘야 컴파일 단계에서 에러가 나지 않는다. 이는 배열을 선언했을 때 변수에 메모리를 할당하는 방식 때문이다. 

위의 그림과 같이 우리가 크기가 10이고 담기는 데이터의 자료형이 int인 배열을 선언했을때, .bss 영역에 배열의 element들이 들어갈 메모리 공간을 할당해 준다. 이 영역은 정적 메모리 공간이기 때문에 컴파일 단계에서 메모리가 할당되고, 프로그램 실행 중에는 변경되지 않는다. 

 

하지만 위의 상황과 같이 배열의 크기를 먼저 정해주는 것은 경우에 따라 효율적이지 않을 수도 있다. 입력받을 데이터의 개수를 몰라 배열의 크기를 미리 지정할 수 없는 상황이거나, 경우에 따라 배열의 크기를 유동적으로 조정하는 것이 효율적인 상황이 있을 수 있다. 이때 동적 메모리 공간인 Heap 영역을 활용하여 메모리 할당을 진행하고, 이를 동적 메모리 할당이라고 부른다. 

 

위의 그림은 동적 할당을 나타낸 것이다. 먼저 arr 변수에는 주소값만 담으면 되기 때문에, arr 변수 자체는 정적 메모리 공간에 할당이 된다. 이제 malloc 함수를 통해 특정 크기의 메모리 공간을 요청하면, Heap에서 메모리 공간을 할당해 준다. 이때 할당해 주는 메모리 공간의 단위를 block이라고 하고 arr 변수에 담기는 값은 block pointer라고 부르는 block의 payload 시작 주소이다. 이런 방식을 통해 처음에 배열의 크기를 알지 못해도 입력 데이터에 따라 동적으로 배열을 사용할 수 있게 되었다!

 

 

 

동적 메모리 할당 방식

Heap 영역의 경우 프로그램이 실행되는 도중에 메모리의 할당과 반환이 이루어지기 때문에 메모리 공간을 효율적으로 활용하기 위해서는 빈 메모리를 할당하는 방식에 대한 고민이 필요하다. 메모리 할당을 효율적으로 하기 위해 여러 가지 방식들이 존재하는데, 여기서 몇 가지에 대해 알아보자. 

 

 

Heap block

본격적으로 할당기의 종류를 알아보기 전에 기본적으로 Heap에서 어떤 방식으로 메모리를 할당해 주는 방법을 살펴볼 것이다. Heap에서 공간을 할당할 때에는 메모리 단편화를 방지하기 위해 8의 배수 크기로 할당을 진행한다. 이때 메모리 할당 요청이 들어오면 적당한 크기의 block을 할당해준다. 

위의 그림은 동적 메모리 할당 시 할당해주는 block을 나타낸 그림이다. block은 크게 세 가지 영역으로 구분된다.

• Header : block의 전체 크기와 block의 할당 여부에 대한 정보를 가지고 있음
• Payload : 할당 이후 실제 데이터가 저장되는 공간
• Padding : 메모리의 단편화 방지 및 시스템의 요구 사항에 따른 alignment 만족시키기 위해 존재

padding 영역을 통해 block의 크기를 8의 배수 단위로 맞춰준다. block의 크기가 항상 8의 배수로 나타나기 때문에, header의 하위 3bit은 block의 size에 영향을 끼치지 않는다. 따라서 마지막 1bit을 block의 할당 여부를 나타내는 데 사용하고, 나머지 2bit 에는 다른 추가적인 정보를 저장할 수 있다. 이러한 특성을 통해 block의 header 값이 짝수인지 홀수인지를 확인해 block의 할당 여부를 확인할 수 있다. 

 

Fragmentation

앞에서 메모리 단편화에 대해 언급했다. 메모리 단편화는 크게 두 가지로 나눌 수 있다. 

 

Internal fragmentation(내부 단편화)

위에서 block을 할당해 줄 때, 시스템의 alignment 요구 조건이나 외부 단편화 방지를 위해 padding을 해준다고 했는데, 이 부분이 바로 내부 단편화이다. 필요 이상의 메모리를 할당받아 사용하지 않는 메모리 공간이 생겨버리는 것이다. 그림으로 보면 아래와 같다. 

위와 같이 실제 사용하는 공간에 비해 큰 block이 할당되었을 때 내부 단편화가 발생한다. 

 

External fragmentation(외부 단편화)

외부 단편화의 경우 내부 단편화와 조금 다르다. 위의 그림과 같은 상황을 생각해 보자. 그림에서 굵은 선으로 block을 구분하였다. 현재 총 4 word 만큼의 여유 공간이 있지만, 각각의 block이 2 word의 공간으로 구분되어 있기 때문에 4 word의 공간 할당 요청이 들어왔을 때 할당이 불가능하다. 이러한 상황을 외부 단편화라고 부른다. 

 

그렇다면 이러한 단편화를 어떻게 방지할까? 각각의 단편화에 대해 해결법을 생각해보자.

 

1. 내부 단편화 해결 방법

내부 단편화를 최대한 방지하기 위해서 어떻게 해야 할까? 바로 요청받은 크기와 가장 비슷한 크기의 block을 할당해 주면 될 것이다! 다만 이러한 방식은 치명적인 단점이 있다. Heap에서 어느 영역의 block이 요청받은 크기와 가장 비슷한지 알 수 없기 때문에 Heap의 모든 영역을 탐색해 봐야 하기 때문에, 요청이 들어올 때마다 Heap의 모든 영역을 모두 탐색해야 한다. 이렇게 내부 단편화와 요청 처리 시간에 어느 정도의 trade off가 존재한다. 

 

2. 외부 단편화 해결 방법

외부 단편화의 경우 내부 단편화보다 해결하기가 어렵다. 내부 단편화는 현재 들어온 요청에 의해 크기가 결정되지만, 외부 단편화는 현재의 요청이 아닌 미래의 요청에 의해 결정되기 때문이다. 미래에 어느 요청이 어느 크기로 들어올지 모르기 때문에 외부 단편화가 내부 단편화보다 측정하기도 어렵고, 해결도 까다롭다. 

일단 위의 그림에서 발생한 외부 단편화의 경우, block을 반환할 때 옆에 free block이 있는 경우 둘을 합쳐주는 방식으로 외부 단편화를 어느 정도 방지할 수 있다. 이보다 조금 더 이상적인 방법으로는 위의 그림에서 오른쪽 끝에 2 word 크기만큼 할당되어 있는 block을 왼쪽으로 끌어와 할당된 블록들이 항상 왼쪽부터 차있도록 하는 방법이 있을 수 있다. 하지만 이렇게 구현을 하려면 이미 할당을 진행했던 변수들에 대해 포인터를 모두 바꿔줘야하기 때문에 사실상 불가능한 방법이다. 따라서 외부 단편화를 최대한 방지하기 위해 메모리를 할당할 때 내부 단편화를 어느정도 감수하고 외부 단편화를 최소화하는 방법들도 존재한다. 

 

이렇게 동적 메모리 할당에 대해 알아보았다! 다음 글에서는 동적 메모리 할당기의 종류들과, 각각의 할당기의 장점 및 한계점에 대해서 알아볼 것이다.