가상메모리
위에서 소개한 memory utilization이 좋지 않으면 단편화(fragmentation)을 야기한다. 단편화란, 힙 영역에 메모리가 남아있으나 블록을 할당하기 어려운 상황, 즉 공간이 파편화되는 현상을 말한다. (힙 단편화 관련해서는 여기 글을 참조.) 단편화의 종류는 내부 단편화와 외부 단편화가 있다.
내부 단편화
내부 단편화는 malloc에서 할당해준 블록이 실제로 정보를 담을 블록보다 공간이 큰 경우에 양옆으로 자잘한 공간이 남아서 발생하는 현상이다. 이는 힙 자료구조를 관리하는 과정에서 오버헤드가 발생해서 일어난다. 예시를 보자.
위 그림에서 진한 하늘색으로 칠해진 영역이 비었다고 생각하고 보자. 현재 할당된 블록은 검은색 경계가 칠해진 6칸짜리 블록인데 p2에서 실제로 데이터가 들어가는 영역(payload)은 int 사이즈로 5칸이다. 따라서 이 경우에는 할당된 블록의 공간을 전부 사용하지 않으니 내부 단편화가 일어난다.
근데 그림에서 실제로는 p2의 마지막 칸에 진한 하늘색이 칠해져있다. 이건 비어있다는 뜻인가? 놉. 이 역시 p2의 일부이다. p2는 int 사이즈로 5칸을 요청했으나 현재 작업하는 컴파일러가 32비트 모드이기 때문에 할당기 주소는 8바이트의 배수에 맞게 배치되어야 한다. 하지만 현재 전체 블록 크기는 int 사이즈 4바이트 * 5= 20 바이트로, 한 칸을 더 붙여줘야 24바이트로 8의 배수가 된다. 이렇게 실제 데이터에는 들어가지 않으나 블록 사이즈를 조정하기 위해 추가적으로 덧대는 블록을 padding이라고 한다.
외부 단편화
외부 단편화는 할당 요청을 만족시키기 위한 힙 내부의 free 메모리가 충분하지만 정렬이 똑바로 되어 있지 않아 할당하지 못하는 경우에 발생하는 현상을 말한다.
위 그림은 p4까지 할당을 받고 free인 블록이 앞에 4칸, 뒤에 2칸이 있다. 여기서 만약 6칸짜리 블록을 할당해달라고 요청하면 어떻게 될까? 내부 공간은 6칸만큼의 자리가 있지만 이를 연속적으로 연결해야 하기 때문에 요청을 들어줄 수 없는 상황이 된다. 따라서 이런 상황을 방지하기 위해, 할당기는 작은 free 블록을 많이 남겨놓는 것보다 큰 free 블록을 적게 유지하는 방식을 채택한다. 예컨대, 앞뒤로 free인 블록이 구분되어 있다면 이 둘을 합쳐서 하나의 큰 free 블록으로 만드는 것이다.