시작하기
가상 메모리는 mmap와 munmap 함수를 이용해 생성 및 삭제할 수 있다.
mmap: 메모리의 내용을 파일이나 디바이스에 맵핑(mapping)하기 위해 사용한다.munmap: 맵핑된 메모리를 해제한다.
하지만 이러한 방식은 프로그램을 실행하기 전에 크기를 할당해야 한다. 만약 가상 메모리를 런타임에 획득하는 것이 필요하다면, 동적 메모리 할당기를 사용한다.
동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상 메모리 영역을 관리한다. 힙은 미초기화된 데이터 영역 직후부터 시작해서 위쪽으로(= 높은 주소 방향으로) 커진다. 이때 힙의 꼭대기를 가리키는 변수를 brk(break)라고 한다.
할당기는 힙을 다양한 크기의 블록들의 집합으로 관리하고, 각 블록은 할당되었거나 사용 가능한 가상 메모리의 묶음이다.
메모리 할당 방법
명시적 할당(Explicit Allocation)
응용 프로그램이 직접 메모리를 할당하고 반환한다.
- C의 malloc 패키지는
malloc함수를 호출해서 블록을 할당하고,free함수를 호출해서 블록을 반환한다.
묵시적 할당(Implicit Allocation)
응용 프로그램이 메모리를 할당하지만, 직접 반환하지 않는다. 따라서 할당기가 더이상 사용하지 않는 메모리 블록을 찾아 검출할 수 있어야 한다.
- 자바의 가비지 컬렉터는 사용하지 않는 할당된 블록을 반환하는 가비지 컬렉션이 있다.
malloc과 free 함수
C 언어는 malloc 패키지라고 불리는 명시적인 할당기를 갖는다.
malloc 함수
#include <stdlib.h>
void *malloc(size_t size);
// Return: pointer to allocated block if OK, NULL on error ****메모리에 담을 수 있는 정렬된 최소 size 바이트를 갖는 메모리 블록 포인터를 반환한다.
정렬 방식은 컴파일 환경에 따라 다르다. 32비트 환경(gcc -m32)에서 malloc은 주소가 8의 배수인 블록을 리턴하고, 64비트 모드(기본 설정)에서는 주소를 16의 배수로 반환한다.
malloc vs calloc vs realloc
- malloc: 리턴하는 메모리를 초기화하지 않는다.
- calloc: 할당된 메모리를 0으로 초기화하여, 초기화한 동적 메모리를 사용할 수 있다.
- realloc: 이전에 할당된 블록의 크기를 변경한다.
sbrk 함수
#include <unistd.h>
void *sbrk(intptr_t incr);
// Return: old brk pointer on success, -1 on error커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다.
free 함수
#include <stdlib.h>
void free(void *ptr);
// Return: nothing할당된 힙 블록을 호출하여 반환한다. ptr은 malloc, calloc, realloc에 의해 할당된 블록의 시작을 가리켜야 한다.
할당기 요구사항
명시적 할당기는 다음 요구사항을 만족해야 한다.
- 임의의 요청 순서 처리하기
A 할당(allocate) 요청에 대한 A 해제(free) 요청이 연속으로 온다는 보장이 없다. 임의의 순서로 들어오는 할당, 해제 요청을 처리할 수 있어야 한다. - 요청에 즉시 응답하기
성능을 향상시키기 위해 재정렬하거나 버퍼에 잠깐 담아둘 수 없다. 바로 요청을 처리해야 한다. - 힙만 사용하기
힙은 런타임에 메모리를 동적으로 할당하고 해제할 수 있다. 즉 프로그램이 다양한 크기와 수명을 가진 객체를 효율적으로 관리할 수 있도록 돕는다. - 블록 정렬하기
어떤 타입의 데이터라도 저장하기 위해 블록을 정렬해둔다.
+) 데이터에 따라 메모리에 저장되는 크기가 다르기 때문에, 필요한 만큼의 블록을 할당한다. - 할당된 블록 수정안하기
이러한 제한 사항을 갖고 처리량과 메모리 이용도를 최대화하기 위한 성능 목표를 달성하기 위해 노력한다.
할당기 구현 목표
- 처리량 극대화하기
n번의 할당과 반환 요청이 들어왔다.
500개의 할당 요청과 500개의 반환 요청을 1초 안에 수행한다면 초당 1000연산이 된다. - 메모리 이용도 최대화하기
프로세스에 의해 할당된 가상 메모리 양은 디스크 내 스왑 공간의 양에 따라 다르다. 따라서 가상 메모리 블록을 효율적으로 할당하고 반환하는 것은 중요하다.
할당기가 힙을 효율적으로 사용하는지 판단하는 척도를 peak utilization이라고 한다.
이처럼 할당기를 만드는데 힙 이용도와 처리량 사이의 적절한 균형을 찾는 것은 중요하다.
단편화(Fragmentation)
단편화는 낮은 메모리 사용 효율의 원인이다.
할당기는 8바이트 더블 워드 경계에 정렬된 블록을 리턴한다고 하자.
내부 단편화
최소 블록 크기 단위에 의해, 할당기가 요청한 데이터보다 더 큰 크기의 블록을 할당하여 발생한다. 즉, 남는 공간이 발생하는 것을 내부 단편화라고 한다.
내부 단편화는 할당된 블록의 크기와 저장하는 데이터 차 들의 합으로 계산하며 된다. 따라서 내부 단편화 양은 이전에 요청한 패턴과 할당기 구현에 의존하기 때문에 예측하기 쉽다.
외부 단편화
총 메모리 공간은 충분하지만 하나의 블록만으로 요청을 처리할 수 없는 경우를 말한다.
단일 가용 블록의 최대 길이가 4이고, 할당을 요청한 데이터의 크기는 8이므로 할당할 수 없는 상태이다. 외부 단편화는 미래의 요청에 대응해야 하기 때문에 측정이 어렵다.
따라서 할당기는 처음부터 가용 블록의 단위를 크게 만들어, 작은 가용 블록들보다 더 적은 수의 큰 가용 블록을 유지하는 방법을 채택하여 예측하기 어려운 외부 단편화는 막는다.
구현 이슈
처리량과 메모리 이용도를 모두 만족하기 위해 다음 이슈들을 고려한다.
- 가용 블록 구성(Free block organization)
- 가용 블록을 어떻게 추적할 것인가?
- 배치(Placement)
- 새롭게 할당된 블록을 배치하기 위해 가용 블록을 어떻게 선택할 것인가?
- 분할(Splitting)
- 새롭게 할당한 블록을 가용 블록에 배치하고 가용 블록의 나머지 부분들로 무엇을 할 것인가?
- 연결(Coalescing)
- 방금 반환된 블록으로 무엇을 할 것인가?
다음 글에서는 묵시적 가용 리스트를 알아보고 직접 구현해보겠다.
