CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.4 단편화
힙의 활용도가 떨어지는 가장 큰 원인은 단편화이다.
단편화란, 메모리가 분명히 남아있지만 할당 요청을 수용하지 못하는 상황을 말한다.
이는 메모리가 연속적이지 않거나 낭비 공간이 존재하기 때문에 발생한다.
단편화에는 크게 두 가지 종류로 나뉜다.
- 내부 단편화
- 외부 단편화
1. 내부 단편화
내부 단편화는 프로세스가 메모리 블록을 할당받았을 때, 할당된 블록이 payload(실제로 저장할 데이터)보다 큰 경우이다.
즉, 블록 내부에서 사용하지 못한 공간이 남아있는 상황을 말한다.
예를 들어, 위 그림처럼 5단위의 free 블록이 있는데 그 중 2단위만 할당에 사용되었다면, 남은 3단위는 다른 요청에서 쓸 수 없다.
이러한 방식으로 메모리가 계속 낭비된다면 내부 단편화는 점점 심해진다.
내부 단편화는 여러가지 이유로 발생할 수 있는데, 그 중 두 가지 이유는 다음과 같다.
1) 할당기의 최소 블록 크기
내부 단편화는 할당기의 구현상 최소 블록 크기가 요청한 크기보다 클 때 발생한다.
예로, 최소 블록은 16바이트부터 제공된다는 규칙을 가지고 있다면, 1바이트만 요청해도 16바이트가 할당되므로 15바이트가 낭비된다.
2) 정렬 조건
정렬 조건을 만족시키기 위해서도 내부 단편화가 발생한다.
예로, 5워드만 필요해도 8바이트 정렬을 만족시키기 위해 6워드가 할당될 수 있다.
이 경우 정렬을 위해 1워드를 더 써야 하니 내부 단편화가 생긴다.
내부 단편화는 요청 크기와 실제 할당된 블록 크기 간의 차이값들의 총합으로 계산할 수 있다.
즉, 이미 결정된 할당 방식에 따라 고정적으로 낭비되는 공간이며, 현재 힙 상태만으로 계산이 가능하다.
2. 외부 단편화
외부 단편화는 여러 개의 빈 블록이 메모리 내에 흩어져 있어서 요청된 크기의 메모리를 연속적으로 할당할 수 없는 경우에 발생한다.
위 그림을 보면, 5단위 free 블록에 2단위의 블록이, 7단위 free 블록에 3단위의 블록이 할당되었다.
이제는 4단위 이상 크기의 연속된 빈 공간이 없으므로 4단위를 초과하는 요청은 수용할 수 없다.
이렇듯 외부 단편화는 언제나 빈 블록들이 여러 조각으로 쪼개져 있는 것이 원인이다.
외부 단편화는 내부 단편화보다 측정하기 훨씬 어렵다.
왜냐하면 외부 단편화는 단순히 현재 상태뿐만 아니라, 미래에 어떤 요청이 들어올지도 영향을 주기 때문이다.
예로, 위 사례에서 2워드 이하만 요청된다면 외부 단편화는 문제되지 않는다.
하지만 4워드를 초과하는 요청이 들어온다면 외부 단편화로 인해 요청을 수용하지 못하게 된다.
외부 단편화는 정량화도 어렵고 예측도 불가능하기 때문에, 할당기들은 일반적으로 다음과 같은 휴리스틱 전략을 사용한다.
"작은 free 블록을 여러 개 유지하기보다는, 큰 free 블록 몇 개를 만들어두는 것이 좋다."
