CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.10 가용 블록 연결하기
할당기가 어떤 블록을 해제할 때, 그 주변에 인접한 다른 가용 블록들이 존재할 수 있다.
이런 인접한 가용 블록들은 false fragmentation(오류 단편화)라는 문제를 일으킬 수 있다.
즉, 메모리는 충분히 남아 있지만, 작고 쪼개진 블록들로 흩어져 있어서 큰 요청을 처리할 수 없는 상황이 생기는 것이다.
예를 들어, 그림 9.38은 그림 9.37에서 할당됐던 블록을 free했을 때의 결과를 보여준다.
▼
free 이후, 3워드(payload) 크기를 가진 두 개의 인접한 가용 블록이 생겼다.
하지만 이렇게 쪼개져 있으면, 4워드 크기의 요청이 들어오면 할당에 실패하게 된다.
두 블록을 합치면 크기가 충분하지만, 각각 따로 떨어져 있어서 하나로 사용할 수 없기 때문이다.
이러한 오류 단편화 문제를 해결하기 위해, 현실적인 할당기라면 반드시 인접한 가용 블록을 합치는(coalescing) 과정을 수행해야 한다.
여기서 "언제 coalescing을 할 것인가?"라는 중요한 정책 결정이 생긴다.
할당기가 선택할 수 있는 방법은 두 가지이다.
1. 즉시 연결(immediate coalescing)
블록이 free될 때마다 인접한 가용 블록들을 바로 합치는 방법이다.
구현이 간단하고, 상수 시간 안에 처리할 수 있다는 장점이 있다.
하지만 특정 상황에서는 쓰래싱(thrashing) 현상을 일으킬 수 있다.
예로, 그림 9.38처럼 3워드 블록을 계속 할당하고 해제하는 패턴이 반복된다면, 필요없는 분할과 연결이 반복되어 성능이 오히려 저하될 수 있다.
2. 지연 연결(deferred coalescing)
free할 때는 가만히 두고, 나중에 필요할 때 한꺼번에 합치는 방법이다.
예로, 할당기가 메모리 요청에 실패했을 때, 힙 전체를 스캔하며 가용 블록을 모아서 합칠 수 있다.
이 책에서는 기본적으로 즉시 연결을 기본으로 가정하여 설명한다.
하지만 실제의 빠른 할당기들은 상황에 따라 지연 연결 방식을 선택하는 경우가 많다는 점도 알아야 한다.
