[CS] 동적 메모리 할당

동적 메모리 할당

• 가상 메모리의 영역을 저수준의 mmap과 munmap함수를 사용하여 생성하고 삭제할 수 있지만, 추가적인 가상 메모리를 런타임에 획득할 필요가 있을 때, 동적 메모리 할당을 활용한다.
• 프로그램을 실제로 실행시키기 전에는 자료 구조의 크기를 알 수 없는 경우들이 있기 때문에 동적 할당이 필요하다.
• 정적으로 할당한 배열에 더 큰 데이터가 입력값으로 들어온다면 프로그램을 다시 컴파일 하는 것 외에 방법이 없다.

동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상 메모리 영역을 관리한다.
힙은 Uninitialized된 데이터 영역 직후에 시작해서 위쪽으로 메모리 주소가 커지는 영역이다.
(그와 반대로 스택 영역은 아래로 내려오면서 메모리 주소가 작아진다.)
커널은 힙의 꼭대기를 가리키는 변수 brk를 사용한다. (파란색 막대기)

동적 메모리 할당기

할당기는 힙을 다양한 크기의 블록들의 집합으로 관리 하는데 각 블록은 할당된 상태(Allocated Space)이거나 할당받기를 기다리는 상태(Free Space)로 존재한다.
할당된 블록은 프로그램에 의해 명시적으로 또는 메모리 할당기에 의해 묵시적으로 반환될 때까지 할당된 채로 남아 있다.

명시적 메모리 할당 / 묵시적 메모리 할당

• 명시적 메모리 할당: C 프로그램에서 malloc 함수를 호출하여 블록을 할당하거나, free 함수를 호출하여 블록을 반환하는 것
• 묵시적 메모리 할당: 묵시적 할당기는 가비지 컬렉터(Garbage Collector)라고도 알려져 있으며 자동으로 사용하지 않은 할당된 블록들을 반환시켜주는 작업을 가비지 컬렉션이라고 부른다.
  - List, ML, 자바 같은 상위수준 언어들은 가비지 컬렉션을 사용한다.

malloc & free (with sbrk)

malloc

#include <stdlib.h>
void *malloc(size_t size);
/*Returns: pointer to allocated block if OK, NULL on error*/

• C 표준 라이브러리는 malloc 패키지로 알려진 명시적인 할당기를 제공하며 malloc 함수를 호출하여 힙으로부터 블록들을 할당받는다.
• Malloc은 리턴하는 메모리를 초기화 하지않는다.
• 초기화된 메모리를 원한다면 calloc 함수를 사용하면 된다.
• 이전에 할당된 블록의 크기를 변경하려면 realloc 함수를 사용하면 된다.

sbrk

#include <unistd.h>
void *sbrk(intptr_t incr);
/*Returns: old brk pointer on success, -1 on error*/

• sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다.
• 성공한다면 이전의 brk 값을 리턴하고 아니면 -1을 리턴한다.
• 만일 incr이 0이면, sbrk는 현재의 brk 값을 리턴한다.

free

#include <stdlib.h>
void free(void *pt)
/*Returns: nothing*/

• 프로그램들은 할당된 힙 블록을 free 함수를 호출해서 반환한다.
• free 함수의 ptr 인자는 malloc, calloc, realloc에서 획득한 할당된 블록의 시작을 가리켜야 한다.
• free 함수는 리턴값이 없기 때문에 제대로 동작을 했다는 것을 알기 어렵다.

• free 함수를 호출하여 블록을 반환하더라도 포인터 p2는 여전히 malloc된 블록을 가리킨다.
• p2가 새로운 malloc 콜에 의해 다시 초기화될 때까지 p2를 사용하지 않는다.

---

동적 할당기의 가용(free) 리스트

할당기들은 여려가지 방식으로 가용 상태의 블록들의 정보를 추적한다.

• 명시적 가용 리스트 (Implicit list)
• 묵시적 가용 리스트 (Explicit list)
• 분리 가용 리스트 (Segregated free list)
• ...

모든 할당기들은 블록 경계를 구분하고, 할당된 블록과 가용상태의 블록들을 구분하기 위한 자료구조를 가진다.

묵시적 가용 리스트

묵시적 가용 리스트에서는 해당 정보를 블록 내의 헤더에 저장하는데 블록의 크기와 해당 블록이 할당되었는지 가용 상태인지를 인코딩 하여 저장 한다.

위 자료 구조를 참고하였을 때 크기가 24바이트(0x18)인 블록의 헤더에는

헤더와 풋터 (Header / Footer)

| 블록크기 | 가용 or 할당 상태 |

0x00000018 | 0x1 = 0x00000019

0x00000019라는 값이 들어가게 되고 풋터에는 헤더와 똑같은 값이 들어간다.

위에서 계산한 값을 가진 4byte 크기의 헤더와 풋터는 양쪽 끝에 들어가게 되고 그 중간에 데이터와 해당 블록을 정렬하기 위한 패딩이 들어가게 된다.

패딩 (Padding)

• 패딩은 정렬 요구사항을 만족하기 위해 필요하다.
• 외부 단편화를 극복하기 위한 전략일 수 있다.

만약 메모리 공간을 8byte 단위로 정렬한다고 했을 때 5바이트의 데이터를 저장하기 위한 메모리 공간을 할당한다면

헤더와 풋터가 각각 4byte를 차지하고 실제 데이터는 5byte, 즉 13byte를 할당해야 하지만 메모리 공간을 8의 배수로 정렬하기 위해 3byte의 패딩을 추가하여 해당 블록의 크기를 16byte로 만든다.

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

---

명시적 가용 리스트

명시적 가용 리스트에서는 가용 블록들로 이중 연결 리스트를 만들어 관리한다.

위 사진에서 볼 수 있듯이 NEXT와 PREV 포인터를 포함하여 이중 연결 가용 블록 리스트를 구성할 수 있다.

묵시적 가용 리스트가 아닌 이중 연결 리스트를 활용한 명시적 가용 리스트를 사용하면 할당 시간을 전체 블록 수에 비례하는 것이 아닌 가용 블록 수에 비례하도록 시간을 줄일 수 있다.

하지만 블록을 반환하는 시간은 가용 리스트를 어떤 방식으로 정렬하냐에 따라 가용 블록의 수에 비례하거나 상수 시간을 가진다.

• 가용 블록을 LIFO 순으로 유지한다면 상수 시간에 수행
• 주소 순으로 가용 블록을 관리한다면 반환할 적당한 블록을 찾는 데 선형 검색 시간이 걸림

명시적 가용 리스트는 NEXT, PREV 포인터 모두 포함해야 하기 때문에 가용 블록들이 충분히 클 필요가 있다는 단점이 있다. 이 단점으로 최소 블록 크기가 커지고 내부 단편화 가능성이 증가하게 된다.