C에서 동적 메모리를 사용하는 이유가 뭘까?

파이썬으로 프로그래밍 언어를 시작했다면, 사실 내가 메모리를 관리해줄 필요는 없다. 선언, 정의와 동시에 알아서 탁탁 메모리를 할당해주기 때문이다.

사실은 그 안에서는 CPU가 열심히 메모리를 할당해줄테다.

파이썬은 배열 자체가 사이즈를 지정하지 않아도 마음대로 사용할 수 있다. 파이썬에서 사용하는 배열의 형태로 C언어에서 사용하면 안 된다.

C언어는 컴퓨터와 가까운 언어로, 이러한 메모리 할당을 해주어야 한다.

C언어는 사이즈를 지정해주지 않은 배열은 사용할 수 없다. 그래서 보통은 배열을 사용할 때, 미리 사이즈를 아주 크게 선언해주고 사용한다. 아주 크게 할당을 받았지만 더 더 큰 프로그램은 언제든지 생겨날 수 있다. 그럴 경우, 아주 위험하다.(오버 플로우) 그리고 실제로 사용하지 않은 만큼은 누수가 발생한다.

그래서 고민했다. 어느 사이즈만큼 사용할지 알 수 없을 때, 프로그램의 런타임에서 동적으로 메모리를 할당해줄 수는 없을까?

---

동적 메모리 할당

동적 메모리는 힙 영역에 저장된다. 힙 영역은 위쪽으로 커졌다 작아졌다 하는 무요구 메모리 영역이다.

힙은 어떻게 이루어져 있을까? 블록 단위로 관리된다. 각 블록은 할당 되었거나, 가용(free)한 블록들의 연속적인 묶음 형태이다.

동적 메모리 할당기는 힙 영역을 관리한다.

할당기들은 두 개의 유형이 있다. 두 유형 전부 명시적으로 블록을 할당하도록 요구하지만 할당된 블록을 반환하기 위해서 무엇을 사용하는 지에 차이가 있다.

• 명시적인 할당기 프로그램에서 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. 즉, ‘너가 다 쓴 메모리는 너가 free 해라!’ 라고 요구한다.
• 묵시적인 할당기 언젠가 할당되었던 블록이 더 이상 프로그램에서 사용되지 않을 때 블록을 자동으로 반환시켜준다. 가비지 컬렉터로 알려져 있다.

명시적 할당기

malloc함수, free함수는 이미 몇 차례 다룬 적 있다.

프로그램은 malloc 함수를 호출하면서 힙으로부터 블록들을 할당받는다.

이 때, malloc 함수는 요구된 사이즈 만큼의 크기를 가질 수 있는 블록을 찾아다가 그 블록 시작점의 포인터를 리턴한다.

"calloc" 
값을 0으로 초기화하여 메모리를 할당한다.

"realloc"
이전에 할당된 블록의 크기를 변경하기 위해 사용한다.

할당기는 다음의 정보를 가진다. 하나씩 알아보자.

구성 요소	역할
가용 리스트 (free list)	아직 쓰지 않은 메모리 블록들 목록
할당 정책	어떤 블록을 줄지 결정 (first-fit, best-fit 등)
확장 로직	메모리가 부족하면 OS에게 추가 요청 (sbrk, mmap)
병합 로직	블록 반환 시 인접한 빈 공간끼리 합치기 (coalescing)

그래서 할당기는 어떻게 할당해 주는 건데?

malloc! 해주면 그냥 알아서 되던데?

사실은 그 안에서는 일부 과정을 거쳐 더 좋은 성능을 가질 수 있도록 노력한다..

위의 사진을 보면 어떻게 동작하는 지 확실하게 이해할 수 있다.

[ malloc ]

1. 프로그램이 특정 크기(N)만큼의 블록을 요청한다.
2. malloc은 가용 블록의 앞부분에서 N만큼을 잘라내고 이 블록의 첫 위치를 가리키는 포인터를 리턴한다.
   1. N만큼을 잘랐을 때, 이 크기가 더블 워드 경계에 딱 맞지 않다면 딱 맞게 패딩을 추가한다.

[ free ]

1. 할당된 N만큼의 블록을 반환한다.

※ 리턴한 후에 포인터는 여전히 같은 블록을 가리킨다. 이 포인터까지 지우진 않지만, 프로그램은 이 포인터가 다시 초기화될 때까지 절대 사용하지 않는다.

이런 과정으로 할당기는 요구에 맞게 열심히 일한다.

할당기는 사실 엄격한 룰을 가진 집단에 소속되어 있다.

• 임의의 요청 순서 처리 - 어떤 순서로 오든 전부 적절하게 처리해야 한다.
• 요청에 즉시 응답 - 일말의 지연도 안 된다.
• 힙만 사용 - 스택, 코드 등의 영역은 사용할 수 없다.
• 블록 정렬 - CPU가 읽기 쉽게 8bytes 혹은 16bytes 정렬되어야 한다.
• 할당된 블록을 수정하지 않음 - 이미 사용 중이기에 수정할 수 없다.

할당기는 이 많은 룰을 지키면서도 효율적인 방법으로 성능 목표를 달성하려하는 기특한 친구다.

목표는 두 개다.

할당기의 목표

1. 처리량 극대화

   N번의 할당과 반환 요청의 배열이 주어졌을 때, 최대한 많이 처리하려 한다.

   할당 요청의 최악 실행시간은 가용 블록의 수에 비례한다.

2. 메모리 이용도 최대화

   수많은 방법이 있지만, 가장 유용한 단위는 최고 이용도 peak uilization이다.

그리고 이 목표를 위해 고려해야 할 점은 다음과 같다.

• 가용 블록 구성 : 어떻게 가용 블록을 추적하는가?
• 배치 : 새롭게 할당된 블록을 배치하기 위한 가용 블록은 어떻게 선택하는가?
• 분할 : 가용 블록에 배치하였다면 나머지 부분들로 무엇을 할 수 있는가?
• 연결 : 방금 반환된 블록으로 무엇을 할 수 있는가?

단편화

힙을 잘못 썼다. 라고 판단되는 대표적인 현상이 바로 단편화다.

할당 요청의 메모리 블록을 할당해줄 수 없을 때 일어난다.

내부 단편화

할당된 블록이 데이터 자체보다 더 클 때 일어난다.

그니까, 앞서 말한 패딩의 개념이 기억 나는가? 내가 1byte 만큼의 메모리만 사용할 건데, CPU를 위한 정렬을 이유로 3bytes 만큼의 패딩을 둔다는 거다.(8bytes 정렬을 가정함)

이런 상황에서는 데이터 자체보다 할당된 블록이 더 크다. 이 현상을 최소화해야 한다.

외부 단편화

메모리 할당이 10bytes 만큼 요청되었다. 지금 힙 영역에는 3, 4, 4 등으로 쪼개진 영역은 무수하다. 하지만 연속된 단일한 가용블록이 없는 경우에 일어난다.

이는 내부 단편화 보다 훨씬 복잡하게 측정된다. 미래에 어떤 사이즈의 요청이 들어올 지는 알 수 없기 때문이다.

묵시적 가용 리스트 implicit free list

블록은 어떤 구조로 관리해야 할까? 사실 정답은 하나가 아니다. 이번에는 가장 간단한 묵시적 가용 리스트의 구조를 보자.

묵시적 가용 리스트는 모든 블록을 메모리에 쭉 나열하고 필요할 때 앞에서부터 차례차례 검사하여 가용 블록을 찾아 할당하는 방식이다.

이 방법은 1. 단순하다는 장점이 있다. 하지만, 2. 힙에 있는 전체 블록을 탐색해야 한다는 단점이 있다.

자, 일단 묵시적 가용 리스트 implicit free list 가 어찌 생겨먹었는 지 보자.

블록이 할당 되었는지 아니면 가용 블록인지 구분해야 한다. 그렇게 하기 위해서 하나의 블록에는 헤더가 필요할 것이다.

한 블록은 1워드의 헤더, 데이터, 추가적인 패딩으로 구성된다. 헤더에는 블록 크기와 블록이 할당되었는지 여부를 나타내는 가용 상태를 인코딩한다.

간단한 힙 블록 포맷이다.

위의 포맷으로 힙의 연속된 할당 및 가용 블록의 배열을 다음과 같이 나타낼 수 있다.

간결하지 않은가?
앞선 PTE의 구조와 유사하게 헤더에 해당 엔트리의 정보를 담는 것이다.
쉽게 떠올릴 수 있는 구조다.

블록의 조정

할당한 블록의 배치

할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다.
이 검색을 수행하는 방법은 배치 정책에 의해 결정된다.

배치 정책

• first fit : 크기가 맞는 첫 번째 가용 블록 선택
• next fit : 이전 검색이 종료된 지점에서 검색을 시작하여 첫 번째 가용 블록 선택
• best fit : 모든 가용 블록을 검사하며 크기가 가장 작은 블록을 선택

best fit

딱 봐도 best fit은 메모리 이용도가 매우 좋을 것 같다.
하지만 이 방법은 묵시적 가용 리스트에서 힙의 모든 블록을 전부 검색해야 한다는 단점이 있다.
first fit과 next fit은 어떨까?

first fit

first fit 정책을 사용하면 앞쪽 가용 블록이 점점 작아지고, 큰 가용 블록들은 전부 뒤에 남게 된다. 이럴 경우 큰 블록을 찾는 데 오랜 시간이 결린다.

next fit

그래서 제안된 방법이 next fit 정책이다. 이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다는 아이디어다.

next fit은 first fit 보다 훨씬 빠른 속도를 가진다.
하지만 일부 의견으로는 낮은 메모리 이용도를 갖는 것으로 밝혀졌다.

가용 블록의 분할

할당기가 크기가 맞는 가용 블록을 찾은 후에 가용 블록의 어느 정도를 할당할지에 대해 정책을 세워야 한다. 만약, 가용 블록의 전체 크기 만큼을 할당한다면 사용하고자 하는 크기에 비해 훨씬 큰 크기를 할당받을 수 있다.

이렇게 될 경우, 내부 단편화가 생긴다. 만일 배치 정책으로 크기가 잘 맞는다면 일부 내부 단편화는 수용할 수 있지만 잘 맞지 않는다면 다른 정책이 필요하다.

할당기는 대개 가용 블록을 두 부분으로 나눈다.

1. 실제로 요청 받은 크기 만큼의 할당한 블록
2. 새로운 가용 블록

추가적인 힙 메모리 획득

할당기가 요청한 크기의 블록을 찾을 수 없다면 어떻게든 마련해야겠지?

malloc은 힙 영역이 부족하면 새로운 메모리 공간을 더 달라고 커널에게 요청할 수 있다. 어? 이 개념 어디에서 본 적 있지 않은가? sork 함수와 mmap 함수가 떠올랐다면 옳다.

malloc은 동적 메모리를 할당하면서 더이상 할당할 수 없을 때, mmap() 함수를 호출하면서 커널은 페이지 단위로 메모리를 매핑하여 제공한다.

Q. mmap(MAP_ANONYMOUS) 등으로 익명 매핑한 메모리 페이지는 언제 실제 물리 메모리에 할당되나?

A.
1. 가상 페이지에 처음 접근(읽기/쓰기)할 때
2. 페이지 폴트 발생
3. 운영체제가 실제 물리 메모리(RAM)에 페이지를 붙여줌

익명 매핑으로 만든 가상 주소는 처음 접근할 때까지 실제 메모리를 차지하지 않고,
접근 시점에 운영체제가 페이지 폴트를 이용해 진짜 물리 메모리를 붙여주는 방식이다.
이를 지연 할당(demand paging)이라고 한다.

책에서는 sbrk 함수를 호출해서 추가적인 힙 메모리를 요청한다고 하지만, mmap() 함수를 사용하는 방법이 현대적이라고 한다. sbrk 함수는 힙 영역의 확장을 위해 존재하는 함수이다.

가용 블록 연결

블록을 반환(free)할 때, 그 블록에 인접한 다른 가용 블록들이 있다면 오류 단편화 false fragmentation 현상을 유발할 수 있다.

"오류 단편화 현상?"
작고 사용할 수 없는 가용 블록이 많이 존재한다면 연속된 공간에서 가용 상태이지만, 
분리되어있기 때문에 요청에 만족시킬 수는 없게 된다. 

위의 상황에서 세번째 블록이 반환되었다.

인접한 가용 블록은 총 32bytes이지만 실제로 32bytes의 요청이 들어오면 할당기는 메모리를 할당할 수 없다. 인접하긴 하지만 별도의 블록으로 여겨지기 때문이다. 이런 경우를 극복해야 한다.

오류 단편화를 극복하기 위해서는 연결 coalescing 의 과정을 거쳐 인접 가용 블록들을 통합해야 한다.

이 연결 정책에는 반환 즉시 인즙 블록을 통합하는 즉시 연결, 일정 시간 후에 연결하기 위해 기다리는 지연 연결이 있다.

보통은 지연 연결은 선택하는데, 즉시 연결은 다소 잦은 연결과 분할이 일어나기 때문이다.

연결 방법 : 경계 태그

연결을 구현하는 방법으로 경계 태그를 사용하면 된다.

경계 태그는 현재 블록의 다음 블록이 가용한지 여부를 추가하는 것이다. 이 방법을 사용하면 블록은 상수 시간 내에 연결할 수 있다. 가용한지의 여부를 양방향으로 추적할 수 있기 때문이다.

경계 태그를 사용하는 힙 블록 포맷
위와 같이 Footer를 추가하여 연결에 필요한 정보를 담는다.
구조는 헤더를 복사한 것과 같다. 할당기는 이 Footer를 사용하여 시작 위치와 이전 블록의 상태를 알 수 있다.

블록을 반환할 때 가능한 경우는 총 네 가지이다.

1. 이전과 다음 블록이 모두 할당되어 있다.
   
2. 이전 블록은 할당 상태, 다음 블록은 가용 상태이다.
   
3. 이전 블록은 가용 상태, 다음 블록은 할당 상태이다.
   
4. 이전 블록과 다음 블록 모두 가용 상태이다.
   

명시적 가용 리스트 explicit free list

묵시적 가용 리스트를 사용하여 할당기를 이해해보았다.

하지만 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 묵시적 가용 리스트는 범용 할당기에 적합하지 않다.

이를 개선할 수 있는 방법이 있다. 명시적 가용 리스트다.
명시적 가용 리스트는 적합한 free block을 찾고 할당하는 선형적인 시간을 단축시키기 위해 Linked List 자료구조의 컨셉을 가져왔다.

이렇게 pred(이전 free block) 포인터, succ(직후 free block) 포인터의 정보를 페이로드에 저장하는 것이다.
할당된 블록은 묵시적 가용 리스트와 동일하지만, 가용 블록은 다음과 같은 정보가 포함된다.
이러한 구조는 이중 연결 리스트로 양방향 접근이 가능토록 한다.

또한 이중 연결 리스트를 사용하면,
first fit 할당 시간을 ‘전체 블록 수’ → ‘가용 블록 수’ 로 줄일 수 있다.

• LIFO 순서 & first fit 배치 정책 할당기는 대부분의 최근에 사용된 블록들을 먼저 조사한다. 이 경우 블록의 반환은 상수 시간에 수행된다. 경계 태그를 사용하면 연결도 상수 시간에 수행할 수 있다.
  
• 주소 순 & first fit 배치 정책 best fit의 이용도에 근접하는 더 좋은 메모리 이용도를 가진다.
  

명시적 리스트의 단점은 일반적으로 가용 블록들이 충분히 커서 모든 필요한 포인터 뿐만 아니라, 헤어 푸터까지 포함해야 한다는 점이다. 그 결과, 최소 블록 크기가 커지고 잼재적인 내부 단편화 가능성이 증가한다.

분리 가용 리스트 segregated free list

여러 가용 리스트를 두고 free block을 분리하는 방법이다.

각 리스트는 유사한 크기의 free block들을 저장한다. 이 방법을 사용하면 free block의 할당 시간을 훨씬 줄일 수있다.(명시적 가용 리스트 방식으로도 가용 블록 수만큼의 시간이 걸린다.)

이 방법은 각 가용 리스트를 어떤 기준으로 분리할 것인지가 핵심이다. 이를 size class라고 하며, 모든 가용 블록을 동일한 클래스의 집합들로 분리하는 것이다. 이 클래스를 정의하는 방법은 여러 가지다.

1. 간단한 분리 저장장치

   특정 크기의 블록을 할당하기 위해서, 첫 전째 블록 전체를 할당한다. 가용 블록들은 할당 요청을 만족시키기 위해서 절대로 분할하지 않는다.

   만약, 리스트가 비어있다면 할당기는 운영체제로부터 추가적인 고정 크기의 메모리를 요청하고 이를 또 동일한 크기의 블록으로 나누어 사용한다.

   단점 : 내부/외부 단편화에 취약하다. → 분할하지 않기 때문

2. 분리 맞춤 Segregated Fits

   분리 가용 리스트의 가장 일반적인 형태이다.

   블록 크기별로 여러 개의 가용 리스트를 만들어서 할당 요청이 오면 해당 크기에 가장 가까운 리스트만 검색하면 된다.

   2의 배수 간격으로 리스트를 나누어, 16bytes, 32bytes … 등의 범위에서 찾는다. 예를 들어, 요청한 크기가 20bytes라면 17~32bytes 리스트에서 검색한다.

3. 버디 시스템 buddy system

   2^k 단위로 메모리를 분할하고, 같은 크기끼리 병합하는 기법이다.

   • 메모리를 2의 거듭제곱 크기 단위로 관리한다. (16B, 32B, 64B, 128B…)
   • 블록을 둘로 나누면 버디가 된다. (두 개는 항상 짝)
     • 할당 요청에서 반으로 쪼개어 할당할 수 있다면 둘로 나눈다.
     • 두 버디 블록이 모두 free일 때 병합해서 상위 크기로 합친다.

   예를 들어보자.

   1. 128B 블록의 할당 요청이다.
   2. 현재 256B 블록 있음 → 128 + 128으로 쪼개어 하나를 할당한다.
   3. 두 128B가 다시 free 되면 → 인접한 블록으로 다시 256B로 병합된다.

   단점 : 블록 크기 제한되며, 내부 단편화 증가 가능성 크다.