정글사관학교 40일차 TIL: 동적 메모리 할당(malloc), 힙 단편화(fragmentation)

malloc: Dynamic memory allocation(동적 메모리 할당)

 

Dynamic Memory Allocator

 

우리는 왜 동적 메모리 할당을 이용할까? C언어에서는 배열을 만들 때, 반드시 그 사이즈를 미리 선언해줘야 한다. 예컨대 2학년 3반 학생 수가 32명인데 이를 배열로 담는다고 하자. 그러면 정확히 size = 32라고 선언해줘야 한다. 그런데 2학년 모든 반에 대해 각각 배열을 만들어준다고 하면, 우리는 각 반 학생 수에 맞게 일일이 배열을 선언해줘야 한다. 이는 굉장히 비효율적이다. 일일이 타자를 치고 있는 상황을 생각해보라.

 

이런 낭비를 막기 위해, 학년 별 학생 수를 담고 있는 배열에서 숫자를 받아와 그 학생 수만큼 배열을 자체적으로 그때그때 생성할 수 있다면 프로그래머가 일일이 손대지 않고도 편하게 배열을 생성할 수 있게 된다. 이를 가능하게 하는 것이 바로 동적 메모리 할당, Dynamic memory allocation(줄여서 malloc)이다.

 

동적 메모리 할당은 말 그대로 가변적으로 메모리를 할당할 수 있다는 말이다. 프로그래머는 동적 메모리 할당기를 사용해 프로그램이 돌아가는 시간에 추가 가상메모리를 얻는다. 동적 메모리 할당기는 프로세스의 가상 메모리 영역을 관리하는데, 이 가상 메모리 영역을 heap(힙)이라고 한다. (힙에 대해 더 자세하게 정리된 내용은 요기 블로그를 참고)

 

 

 

위 그림에서 시작해 아래로 갈수록 메모리의 주소값이 높아진다. 주소값이 가장 낮은 영역에는 stack이 들어간다. stack 영역에서는 함수의 호출과 관련되는 지역 변수 및 매개변수를 저장한다. 그 다음이 동적으로 데이터를 저장하는 heap 영역이다.

 

Allocator는 크기가 조절 가능한 블록의 집합으로 힙을 관리한다. 각 블록은 할당(allocate)되거나 해제(free)되는데, 할당된다는 것은 그 영역이 응용 프로그램을 실행하는데 쓰여진다는 뜻이며 해제된다는 건 말 그대로 할당됐던 영역의 데이터가 지워지면서 다시 새롭게 쓰여질 준비가 되었다는 말이 된다.

 

2가지 Allocator 타입: Explicit / Implicit

 

1) Explicit allocator: Explicit이라는 말은 명시적으로 할당을 조율한다는 말로, 응용프로그램이 공간을 할당하거나 해제할 때 malloc()을 선언해야 한다. 외부에서 free function을 실행해야 하니 바깥에서 해제해주지 않는 이상 시스템이 임의로 메모리를 해제하지 않는다. C 프로그램에 존재하는 malloc과 free 함수는 모두 프로그래머가 실행해줘야 하는 explicit 함수이다.

 

2) Implicit allocator: 사람이 일일이 free를 선언해주지 않아도 시스템에서 자체적으로 free를 선언해준다. 즉, 응용 프로그램에서 일일이 free를 호출해줘야 하는 부담을 시스템에 이관해 시스템이 알아서 해제를 한다. 자바나 C++ 내에 들어있는 allocator가 이에 해당한다.

 

Garbage collection: 사용하지 않는 할당된 블록을 자동으로 해제하는 기능

 

제약사항(Constraints)

응용프로그램은 힙 영역 내에서 자기 맘대로 블록을 할당 혹은 해제한다. 할당기(allocator) 입장에서는 프로그램이 무슨 블록을 선택할지 예측이 불가능하다. 즉, allocator는 할당 블록의 크기/개수를 컨트롤할 수도, 블록을 움직일 수도 없으며 응용 프로그램의 동작에 대한 통제권 역시 없다. 일단 malloc이 app에 블록을 할당해주고 나면 그 다음부터는 암것도 못한다고 보면 된다.

 

또한, 프로그램이 퍼포먼스를 내기 위해서는 처리량과 메모리 utilization 사이의 밸런스를 잘 이뤄야 하는 제약 역시 존재한다. 이게 무슨 말이냐, 프로그램이 퍼포먼스를 잘 내려면 두 가지 목표를 달성해야 한다. 첫 번째는 처리량을 최대화하는 것이다. 여기서 처리량이란, 단위 시간 당 완료된 요청 개수를 의미한다. 예를 들어 10초 동안 5000개의 동적 메모리 할당과 5000개의 해제 요청을 완료했다면 1초당 1000개의 처리량을 완수했다고 보면 된다.

 

두 번째 목표는 peak memory utilization(U)을 최대화하는 것이다. 이건 또 뭐냐? allocator가 얼마나 힙을 효율적으로 사용하는지를 분석하는 지표이다. n개의 블록을 할당해달라는 요청이 들어왔다고 해보자. 블록의 양이 늘어나면 힙의 영역을 늘려줘야 한다. 그런데 힙은 무엇이라 했나? 가상 메모리 영역과도 같다 그랬다. 이전 시간에서 가상 메모리는 무엇과 무엇의 합이라 했는지 기억할 것이다. 하드 디스크와 메모리 용량의 합이며, 힙 영역이 커진다는 뜻은 메인 메모리 용량은 한정되어 있으니 하드 디스크로 넘치는 양이 증가한다는 뜻이다. 처리량이 많아지면 하드로 넘치는 정보량이 많아지며 page fault가 그만큼 많아질테니 속도가 느려진다. 그래서 처리량이 많아질수록 메모리 유틸이 낮아진다는 뜻이 된다. 힙이 클수록 한 번에 처리할 수 있는 양이 많아지나 그만큼 할당/해제를 많이 해야 하니 속도가 느려지는 tradeoff 가 발생한다. 실전 예시는 여기를 보면 잘 나와 있다.

 

단편화

위에서 소개한 memory utilization이 좋지 않으면 단편화(fragmentation)을 야기한다. 단편화란, 힙 영역에 메모리가 남아있으나 블록을 할당하기 어려운 상황, 즉 공간이 파편화되는 현상을 말한다. (힙 단편화 관련해서는 여기 글을 참조.) 단편화의 종류는 내부 단편화와 외부 단편화가 있다.

 

내부 단편화

내부 단편화는 malloc에서 할당해준 블록이 실제로 정보를 담을 블록보다 공간이 큰 경우에 양옆으로 자잘한 공간이 남아서 발생하는 현상이다. 이는 힙 자료구조를 관리하는 과정에서 오버헤드가 발생해서 일어난다. 예시를 보자. 

 

 

위 그림에서 진한 하늘색으로 칠해진 영역이 비었다고 생각하고 보자. 현재 할당된 블록은 검은색 경계가 칠해진 6칸짜리 블록인데 p2에서 실제로 데이터가 들어가는 영역(payload)은 int 사이즈로 5칸이다. 따라서 이 경우에는 할당된 블록의 공간을 전부 사용하지 않으니 내부 단편화가 일어난다.

 

근데 그림에서 실제로는 p2의 마지막 칸에 진한 하늘색이 칠해져있다. 이건 비어있다는 뜻인가? 놉. 이 역시 p2의 일부이다. p2는 int 사이즈로 5칸을 요청했으나 현재 작업하는 컴파일러가 32비트 모드이기 때문에 할당기 주소는 8바이트의 배수에 맞게 배치되어야 한다. 하지만 현재 전체 블록 크기는 int 사이즈 4바이트 * 5= 20 바이트로, 한 칸을 더 붙여줘야 24바이트로 8의 배수가 된다. 이렇게 실제 데이터에는 들어가지 않으나 블록 사이즈를 조정하기 위해 추가적으로 덧대는 블록을 padding이라고 한다.

 

외부 단편화

외부 단편화는 할당 요청을 만족시키기 위한 힙 내부의 free 메모리가 충분하지만 정렬이 똑바로 되어 있지 않아 할당하지 못하는 경우에 발생하는 현상을 말한다.

 

위 그림은 p4까지 할당을 받고 free인 블록이 앞에 4칸, 뒤에 2칸이 있다. 여기서 만약 6칸짜리 블록을 할당해달라고 요청하면 어떻게 될까? 내부 공간은 6칸만큼의 자리가 있지만 이를 연속적으로 연결해야 하기 때문에 요청을 들어줄 수 없는 상황이 된다. 따라서 이런 상황을 방지하기 위해, 할당기는 작은 free 블록을 많이 남겨놓는 것보다 큰 free 블록을 적게 유지하는 방식을 채택한다. 예컨대, 앞뒤로 free인 블록이 구분되어 있다면 이 둘을 합쳐서 하나의 큰 free 블록으로 만드는 것이다.

 

 

 

참고자료

답수님 블로그

https://rninche01.tistory.com/entry/heap1-Dynamic-Memory-Allocation