메모리가 어떻게 할당되고 해제되는지 알기 쉽게 설명한 「Memory Allocation」

 

컴퓨터에서 프로그램을 실행할 때 꼭 필요한 것이 메모리입니다. 프로그램 자체를 메모리에 읽어야 하는 것은 물론, 프로그램이 하는 동작은 거의 「메모리로부터 값을 꺼내어 계산하고 다시 메모리에 보존한다」라고 해도 과언이 아닙니다. 프로그램이 동작할 때 메모리가 어떻게 관리되고 있는지에 대해서, 베테랑 프로그러머인 샘 로즈씨가 블로그에서 자세히 해설하고 있습니다.

Memory Allocation
https://samwho.dev/memory-allocation/

Memory Allocation

C 언어의 표준 라이브러리는 "malloc"과 "free"라는 두 가지 함수를 제공합니다. 이 두 가지는 무려 1979년 유닉스 v7 시절부터 존재하는 역사적인 함수로, malloc이 메모리 할당을 담당하고 free가 메모리의 해제를 담당하고 있습니다. 샘 로즈 씨의 해설은 "이 두 함수의 내용을 스스로 구현"하는 것을 염두에 두고 진행합니다.


그리고 아래 그림이 메모리의 이미지입니다.

1칸이 1바이트에 대응하고 있어 각각의 칸에 0~255의 숫자를 보존할 수 있습니다.

이번에는 이해를 쉽게 하기 위해 메모리가 전부 32바이트밖에 없는 상태로 설명한다는 것.

또한 프로그램에 의해 확보된 메모리를 진한 오렌지색으로 표현하기로 합니다.

아래 그림은 4바이트 메모리가 확보되어 있는 상태입니다.

한편, 얇은 오렌지색 쪽은 확보되지 않은 메모리를 표현하고 있습니다.

malloc 함수에 「몇 바이트의 메모리를 확보하고 싶은가」를 건네주면 그 바이트의 메모리를 확보해 줍니다.

예를 들어 malloc(4)를 실행하면 앞의 4 바이트가 할당되었습니다.

추가로 malloc(5), malloc(6)을 실행하면 대응하는 메모리가 사용 중으로 바뀝니다.

malloc은 "몇 바이트의 메모리를 확보할지"만 건네주면 됩니다만, 메모리를 해제하는 free는 메모리의 시작 주소를 가리켜야 합니다.

free(0x4)나 free(0x9)를 실행하면 해당 위치가 해제되었습니다.

이 "0x"라는 표기는 16진수 표기임을 나타내는 접두사입니다. 9까지의 숫자는 통상의 10 진수 표기와 같습니다.

"10"은 10진수에서는 2자리가 되지만 16진수에서는 "a"로 표현됩니다.

마찬가지로 15까지의 숫자는 알파벳으로 표시됩니다.

그리고 16이 되면 자릿수가 오르고, 「10」이라고 표기되는 것입니다.

메모리의 번지를 16진수로 나타내면 이렇습니다. 

본래라면 모든 칸에 「0x」라고 하는 접두사를 붙이는 것이 좋습니다만, 공간상 생략했다는 것.

자, 지금까지의 지식을 사용하면 스스로 "malloc"함수를 구현할 수 있게 됩니다. 

가장 간단한 구현으로서, 「빈 블록의 선두의 주소를 보존해 두고, 거기서부터 필요한 만큼 메모리를 확보하여,

확보한 제일 마지막 메모리의 다음 주소를 보존한다」라는 구현을 생각해 보겠습니다. 

우선 malloc(4)를 실행하면 4바이트의 메모리를 확보한 후, 그다음 번지로 표시가 이동합니다.

이 구현에서는, 메모리를 할당할 때에는 문제없지만, 「어디부터 어디까지가 1 블록인가」라는 정보가 없기 때문에 메모리를 해제할 수 없습니다.

프로그램의 사용 중에 끊임없이 메모리의 사용량이 늘어나기 때문에, 결함이 있는 구현이라고 할 수 있습니다만,

동작이 매우 가볍기 때문에, 미리 메모리의 사용량을 알고 있는 경우에는 효율적인 구현이 되는 경우도 있다는 것.

그러나 일반적인 메모리 할당자를 구현하는 경우에는 메모리를 해제하는 기능이 필수입니다.

이제 모든 할당된 메모리와 사용 가능한 메모리의 주소와 크기를 "할당 목록"과 "해제 목록"에 저장해 봅니다.

처음에는 해제 목록에 「0x0번지, 32바이트분」이라는 정보가 들어 있다는 것.

물론, 「할당 목록」, 「해제 목록」의 보관에도 메모리가 필요합니다만, 여기서는 다른 장소에 보관하고 있다고 생각합시다.

malloc이 호출되면 해제 목록을 위에서부터 순서대로 필요한 메모리 양을 확보 가능한 곳까지 찾아 메모리를 할당하고 할당 목록에 등록합니다.

할당 리스트를 보면 몇 바이트의 메모리를 해제하면 되는지 알기 때문에, free를 실행하는 것이 가능하게 되었습니다. 해제된 메모리는 해제 목록에 등록됩니다.

이 구현에서는 메모리의 할당 · 해제를 반복하면 점점 1블록의 크기가 작아져, 전체적으로 보면 메모리 공간이 비어 있는데도 메모리를 할당할 수 없는 문제가 발생합니다.

거기서, 메모리의 해제 시에 해제 리스트를 확인해, 옆의 블록이 비어 있으면 결합(Coalescing) 하도록 수정해 보겠습니다.

그러면, 완벽한 메모리 할당자가 완성된 것처럼 보이지만 여전히 문제가 남아 있습니다.

아래 그림과 같이 메모리의 할당과 해제를 반복하면 「너무 작아서 사용하기 어려운」 블록이 출현합니다. 이것을 메모리의 단편화(fragmentation)라고 합니다.

malloc 했을 때에 할당된 메모리 주소가 프로그램에 저장되어 free의 지정에 이용되기 때문에, 메모리 할당자측에서 마음대로 메모리의 배치를 바꿀 수 없습니다.

이러한 단편화를 방지하기 위해 다양한 방법이 개발되고 있습니다. 

예를 들어 아래 그림은 "작은 바이트 수의 메모리를 확보하는 명령이 있을 때 최소 4바이트를 확보한다"라는 것.

단편화가 일어나기 어렵지만, 필요한 메모리 양이 실제 사용되는 메모리 양보다 커진다는 단점이 있습니다.

또 다른 접근법은 작은 할당을 위해 다른 공간을 확보하는 기술도 있습니다.

이 방법으로도 단편화를 억제할 수 있습니다만, 정리된 큰 할당이 필요할 때에 사용할 수 있는 영역이 줄어들어 버린다는 단점이 있습니다.

이 접근법을 채택한 할당자를 슬랩(Slab) 할당자라고 합니다.

실제로는 크고 작은 2 종류의 영역뿐만 아니라 다양한 크기에 대응하는 영역을 준비하여 이용한다는 것.

지금까지 나오지 않았습니다만, malloc으로 0을 지정한 경우에 대해서도 생각해 보겠습니다.

최소 4바이트를 확보하는 단순한 구현의 경우, malloc(0)이 호출된 횟수만큼 4바이트의 영역이 확보되어 갑자기 메모리가 낭비되어 버립니다.

한편, 메모리 할당자의 구현에 따라서는 malloc(0)의 실행 시에 일괄로 「널 포인터」를 돌려주는 것도 있다는 것.

프로그램이 널 포인터를 지정해 읽고 쓰기를 실행하려고 하면 크래쉬(종료) 되어 버리기 때문에, 어떤 경우에도 「malloc(0)」를 사용해서는 안됩니다.

그런데, 지금까지의 메모리 할당자의 구현은 메모리의 다른 영역에 보존한 「할당 목록」과 「해제 목록」를 이용하고 있었습니다.

이러한 목록을 사용하지 않는 접근법도 존재합니다.

예를 들어, 아래 그림은 할당되지 않은 여유 공간이지만 여유 공간 앞뒤에 해당 영역의 정보가 저장됩니다.

선두와 말미의 「29」는 영역의 바이트수로, 2번째 칸의 「1」은 그 영역이 미사용인 것을 나타내고 있습니다.

언뜻 보면, 영역의 바이트수가 선두와 말미에 중복 보존되는 것은 쓸데없는 것처럼 느껴집니다만, 영역을 결합할 때에는 중요하다는 것.

여기에 4바이트의 메모리를 확보하는 경우, 메모리 할당자는 메모리의 앞부터 영역을 확인하고, 충분한 공간의 빈 영역을 발견하면 거기에 새로운 영역을 할당합니다.

한번 더 4바이트의 영역을 확보하면 아래 그림과 같이 됩니다.

이 접근법의 장점은 메모리를 해제할 때, 첫 번째 +1 번지 플래그를 "1"로 설정하는 것만으로 OK라는 것입니다.

메모리를 해제할 때에는 전후의 메모리의 사용 상황을 확인해, 빈 공간이 있으면 결합할 필요가 있습니다. 

말미에도 영역의 크기를 보존하는 것으로, 이전 영역의 어디를 보면 메모리의 이용 상황을 확인할 수 있는지 알 수 있다는 것입니다.

모든 영역이 비어 있기 때문에 결합되어 첫 번째 상태로 돌아왔습니다.

샘 로즈 씨는 Allocator Playground 라는 도구를 공개하고 있으며, 다양한 메모리 할당자의 구현을 확인할 수 있습니다. 

Hello World 등의 간단한 프로그램의 동작시 메모리가 어떻게 이용되는지 직관적으로 이해할 수 있어 유용합니다.