동적 메모리 할당?
C언어를 공부하면서 배열을 정할 때 배열의 크기도 명확하게 설정해야 하는 것이 파이썬과 달라 조금 낯설었다.
예를 들어 A대학교 B학과의 학년 별로 코로나 백신 접종을 얼마나 했는지 결과를 출력하는 프로그램을 만든다고 생각해보자. 각 학년 별로 학생 수가 모두 다르기 때문에 배열을 일일히 정하는 것은 효율적이지 않다고 느껴진다(물론 학생 수 정도야 귀찮아도 가능하겠지만, 다뤄야 하는 데이터가 방대해진다면 어질어질해진다). 그렇다고 크기를 '충분히 크게' 잡게 된다면 메모리가 낭비되는 경우가 발생할 것이다.
이런 낭비를 막기 위해 '학년 별 학생 수'를 입력 받고 그 학생 수 만큼 배열의 크기를 정할 수 있다면 효율적일 것이고, 이를 가능하도록 하는 방법이 바로 동적 메모리 할당이다.
동적 메모리 할당은 말그대로 동적, 즉 가변적으로 메모리를 할당할 수 있다는 것이고, 동적 메모리 할당기는 힙(heap) 프로세스의 가상 메모리 영역을 이용하여 관리한다.
프로그래머들이 동적 메모리 할당을 사용하는 가장 중요한 이유는 종종 프로그램을 실제로 실행시키기 전에 자료구조의 크기를 알 수 없는 경우들이 있기 때문이다. 위의 예시처럼 학년별 학생 수 기준이라면 크게 문제되지 않겠지만 수백만 라인의 코드와 수많은 사용자가 있는 큰 규모의 소프트웨어 제품에서는 관리하는 데 어려움을 겪을 수 있다.
이런 문제를 해결하는 방법으로 런타임 시 메모리에 데이터를 동적으로 할당하는 것이다. 이 방법으로 메모리의 최대 크기는 가용한 가상 메모리의 양에 의해서만 제한된다.
동적 메모리를 할당은 두 가지 유형이 있다.
| 명시적 할당기
- 명시적 할당기는 응용이 명시적으로 할당된 블록을 반환해줄 것을 요구
- C 표준 라이브러리는 malloc 패키지를 제공
- C 프로그램은 malloc 함수를 호줄해서 블록을 할당, free 함수를 호출해서 블록 반환
| 묵시적 할당기
- 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출할 수 있을 것을 요구
- 묵시적 할당기는 가비지 컬렉터(garbage collector)라고 알려져 있으며, 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 부름
- List, ML, 자바 같은 상위 수준 언어들이 가비지 컬렉션 사용
이번 포스팅은 Malloc Lab 과제를 통해 명시적 할당기를 구현하는 과정을 정리하려고 한다.
| malloc, free 예시
명시적 할당기의 요구사항과 목표
명시적 할당기들은 다음과 같은 제한 사항들을 고려하여 구현해야 한다.
- 임의의 요청 순서 처리하기
- 요청에 즉시 응답하기
- 힙만 사용하기
- 블록 정렬하기
- 할당된 블록을 수정하지 않기
즉, malloc 프로그램을 구현하기 위해서는 힙 영역 늘리기, 가용/할당 블록 여부 파악 후 가용블록 선택, 블록 합치기, 블록 할당 반환, 블록의 남는 부분 처리 등의 기능이 들어가야 한다.
이러한 제한사항들을 가지고 프로그램을 구현할 때, 우리는 처리량 극대화와 메모리 이용도 최대화라는 종종 상충되기도 하는 두 가지 목표 사이에 적절한 균형을 찾아 최적의 결과를 도출하도록 해야 한다.
단편화
단편화는 메모리 할당 요청을 만족시킬 수 없을 때 일어난다.
| 내부 단편화
내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다.
위 그림에서 p2는 int 사이즈 5칸을 요청했지만, malloc lab 프로젝트의 gcc가 32비트 모드이기 때문에 할당기의 주소가 8바이트의 배수에 맞게 배치되어야 하고, 따라서 1칸(4바이트)을 더 할당하게 된다.
| 외부 단펴화
외부 단편화는 할당 요청을 만족시키기기 위한 가용 메모리가 충분하지만, 정렬 문제로 메모리에 할당하지 못 하는 경우 발생한다.
위의 그림을 보면 가용 가능한 블록은 6개가 있다. 즉 총 24바이트의 여유 메모리가 있지만, 4, 2로 나뉘어 있기 때문에 24바이트의 블록을 할당할 수 없다.
외부 단편화는 측정하기 어렵고 예측하기 불가능하기 때문에 할당기들은 많은 수의 더 작은 가용 블록들보다는 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법들을 채택하고 있다.
구현 이슈
가장 간단히 상상할 수 있는 할당은 힙을 하나의 커다란 바이트의 배열과 이 배열의 첫 번째 바이트를 가리키는 포인터로 구성할 수 있다. '외부 단편화'에서 사용한 그림을 예시로 하자면, 포인터 p1, p2, p3는 각각 할당된 공간의 처음을 가리킨다.
처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다.
- 가용 블록 구성: 어떻게 가용 블록을 지속적으로 추적하는가?
- 배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
- 분할: 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무어을 할 것인가?
- 연결: 방금 반환된 블록으로 무엇을 할 것인가?
묵시적 가용 리스트(Implicit list), 명시적 가용 리스트(Explicit list)
| 묵시적 가용 리스트(Implicit list)
implicit 방법은 할당된 블록과 가용한 블록이 모두 연결되어 있다.
| 명시적 가용 리스트(Explicit list)
ecplicit 방법은 가용 가능한 블록끼리만 연결되어 있다.
다음 포스팅에서는 Implicit 방법에 대해 구체적으로 글을 작성하도록 하겠다.
댓글