CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.3 할당기의 요구사항과 목표
동적 메모리 할당기는 5가지 엄격한 제약 조건 안에서 동작해야 한다.
또한, 좋은 할당기가 되기 위해서는 처리량와 이용도라는 상충하는 두 가지 목표를 동시에 만족시켜야 한다.
1. 할당기의 제약 조건
동적 메모리 할당기는 다음 5가지 조건들을 반드시 지켜야 한다.
1) 임의의 요청 순서 처리하기
프로그램은 malloc과 free를 순서 없이 호출할 수 있다.
다만, free는 반드시 이전에 할당된 블록만 해제할 수 있다.
2) 요청에 즉시 응답하기
할당기는 요청이 들어오면 바로 응답해야 한다.
성능을 높이기 위해 요청을 지연시키거나 순서를 바꾸는 것은 허용되지 않는다.
3) 힙만 사용하기
확장성 있는 할당기를 만들기 위해, 할당기가 사용하는 데이터 구조는 힙 안에 저장되어야 한다.
즉, 할당기 내부에서 사용하는 모든 자료구조(메타데이터, 포인터 목록 등)는 힙에 저장되어야 한다.
스택이나 전역변수에 저장하면 다중 요청에서 오류가 발생할 수 있기 때문이다.
4) 블록 정렬하기(정렬 요건)
할당기는 할당하는 메모리 블록의 주소를 시스템 정렬 기준에 맞춰야 한다.
- 32비트 시스템: 8바이트 정렬
- 64비트 시스템: 16바이트 정렬
정렬이 맞지 않으면 성능 저하 또는 프로그램 오류가 발생할 수 있다.
5) 할당된 블록을 수정하지 않기
사용자가 할당받은 메모리 블록은 그 위치와 내용을 그대로 유지해야 한다.
따라서 할당기는 해당 블록을 건드려서는 안 된다.
블록 재정렬(compaction)이나 이동도 허용되지 않는다.
2. 할당기의 성능 목표
할당기는 위 조건을 지키면서도 다음 두 가지 목표를 동시에 달성해야 한다.
1) 처리량 최대화
처리량은 일정 시간 동안 얼마나 많은 할당/해제 요청을 처리할 수 있는지를 의미한다.
예로, 1초에 malloc 500개, free 500개를 처리했다면 처리량은 초당 1000개의 요청이다.
처리량을 높이기 위해서는 malloc, free 요청을 가능한 한 빠르게 처리해야 한다.
대부분의 할당기 구현은 다음과 같은 특징을 가진다:
malloc: 자유 블록을 탐색해야 하므로 최악의 경우 O(n)free: 블록에 마크만 하고 끝내면 되므로 O(1)
malloc은 오래 걸릴 수도 있지만, free는 항상 빠르게 처리되도록 만드는 것이 목표이다.
2) 메모리 활용도 최대화
당연한 말이지만, 가상 메모리 공간은 무한하지 않다.
가상 메모리의 총량은 디스크의 스왑 공간에 따라 제한된다.
따라서 효율적으로 메모리를 사용해야 하며, 할당기의 목표는 가능한 적은 힙으로 많은 payload를 처리하는 것이다.
메모리 활용도를 측정하는 대표 지표로는 최고 이용도(peak utilization)가 있다.
n번의 할당과 반환 요청의 배열이 주어졌을 때 형태는 다음과 같다.
어떤 프로그램이 p바이트를 요청하면, 할당된 블록의 payload(실제 데이터 공간)도 p바이트이다.
요청 까지 완료되었을 때는 다음과 같다.
- : 현재까지 할당된 블록들의 payload의 총합
- : 현재 힙 크기
처음 k+1개의 요청에 대한 최대 활용률 는 다음과 같이 계산된다.
여기서 높은 는 할당한 메모리를 최소한의 힙 공간으로 잘 사용하고 있다는 의미이다.
3. 두 목표 간의 균형 문제
하지만 이 두 목표는 동시에 달성하기 어려운 경우가 많다.
처리량과 이용도는 일반적으로 서로 반비례하는 관계이기 때문이다.
처리량에만 집중하면, malloc 요청마다 새로운 블록을 계속 잘라 주기 때문에 힙이 빠르게 증가하고, 낭비 공간(단편화)이 많아진다.
반대로 메모리를 최대한 활용하려 하면, malloc할 때마다 가장 알맞은 블록을 찾고, 블록을 분할하거나 병합해야 하므로 처리 속도가 느려진다.
따라서 좋은 할당기란 1) 빠르면서 2) 메모리를 효율적으로 쓰는 두 목표 사이의 균형을 잘 맞춘 구현이다.
