CSAPP 책은 쌩으로 읽는다면 이해하기 매우 어렵습니다.
따라서 소단원만 그대로 따라가되, 내용을 이해하기 쉽게 재구성했습니다.
9.9.11 경계 태그로 연결하기
1. 가용 블록의 연결
할당기는 어떻게 가용 블록들을 연결하는가?
할당기가 어떤 블록을 free할 때, 그 주변에 인접한 가용 블록이 있을 수 있다.
우리가 해제하려는 블록을 '현재 블록'이라고 부르자.
현재 블록과 다음 블록을 합치는 것은 간단하다.
현재 블록의 header를 통해 다음 블록의 header를 찾을 수 있고, 다음 블록이 free인지 바로 확인할 수 있기 때문이다.
만약 다음 블록이 free라면, 두 블록을 단순히 합쳐서 O(1) 시간 안에 연결할 수 있다.
하지만, 앞쪽 블록과 연결하려면 문제가 발생한다.
header만 있는 묵시적 가용 리스트 구조에서는 앞 블록을 찾으려면 리스트 전체를 처음부터 순회해야 한다.
결국 free할 때마다 힙 크기에 비례하는 시간이 걸리게 된다.
더 복잡한 free list 구조를 쓰더라도, 앞 블록을 찾는 검색 시간이 O(1)이 될 수는 없다.
2. 경계 태그 기법
이 문제를 해결하기 위해 Knuth는 경계 태그(boundary tags)라는 기발한 방법을 고안했다.
아이디어는 단순하다.
각 블록의 끝에 header를 복사한 footer를 추가하면 된다.
이렇게 footer를 추가하면, 현재 블록의 시작점 바로 앞(1워드 거리)에 있는 이전 블록의 footer를 읽어서 이전 블록의 크기와 상태를 바로 알 수 있다.
즉, 앞 블록도 O(1) 시간에 찾을 수 있다.
3. Coalescing의 4가지 경우
할당기가 현재 블록을 free할 때, 발생할 수 있는 경우는 총 4가지이다.
- 이전 블록과 다음 블록이 모두 할당된 경우
- 이전 블록은 할당되었고, 다음 블록은 free인 경우
- 이전 블록은 free이고, 다음 블록은 할당된 경우
- 이전 블록과 다음 블록 모두 free인 경우
각각의 경우에 대해 어떻게 coalescing을 할 수 있는지 확인해보자.
모든 4가지 경우에서 coalescing은 O(1)의 시간 복잡도를 갖는다.
1) 이전 블록과 다음 블록이 모두 할당된 경우
coalescing이 불가능한 경우이다.
따라서 현재 블록의 상태만 단순히 '할당됨'에서 'free'로 변경한다.
2) 이전 블록은 할당되었고, 다음 블록은 free인 경우
현재 블록을 다음 블록과 합친다.
현재 블록의 header와 다음 블록의 footer에 합쳐진 크기를 새로 기록한다.
3) 이전 블록은 free이고, 다음 블록은 할당된 경우
이전 블록과 현재 블록을 합친다.
이전 블록의 header와 현재 블록의 footer에 합쳐진 크기를 새로 기록한다.
4) 이전 블록과 다음 블록 모두 free인 경우
이전 블록 + 현재 블록 + 다음 블록, 세 블록을 모두 합쳐 하나의 큰 가용 블록을 만든다.
이전 블록의 header와 다음 블록의 footer에 세 블록을 합친 총 크기를 새로 기록한다.
4. 경계 태그의 장단점
경계 태그 개념은 확장성이 뛰어나기 때문에 다양한 종류의 할당기나 free list 구조에도 쉽게 적용할 수 있다.
하지만 한 가지 단점이 있다.
모든 블록에 header와 footer를 추가해야 하므로 메모리 오버헤드가 생긴다는 점이다.
특히, 작은 블록을 많이 다루는 프로그램에서는 문제가 심각해진다.
예로, 그래프 프로그램처럼 노드를 자주 생성하고 삭제할 때, 각 노드가 몇 워드밖에 필요로 하지 않는다면, header와 footer가 전체 블록의 절반 이상을 차지하게 된다.
5. 경계 태그 최적화
다행히도, 이 문제를 해결할 수 있는 최적화 방법이 있다.
핵심은 할당된 블록에서는 footer가 필요 없다는 것이다.
free할 때는 앞 블록의 상태를 알아야 하니깐 footer가 필요하지만, 할당된 블록은 합칠 일이 없기 때문에 굳이 footer를 둘 필요가 없다.
대신, 현재 블록의 남는 비트(낮은 비트 영역)에 이전 블록이 할당됐는지/free인지를 저장한다.
이렇게 하면, 1) 할당된 블록은 footer 없이 더 많은 공간을 payload로 쓸 수 있고, 2) free 블록만 footer를 유지하면 된다.
가용 블록은 여전히 footer가 꼭 필요하다는 점을 주의해야 한다.
연습문제 9.7
1. 문제
다음의 각 정렬 요구조건과 블록 형식에 대해 최소 블록 크기를 결정하시오. 가정: 묵시적 가용 리스트 사용, 데이터의 크기는 1보다 커야 하고 헤더와 풋터는 4바이트 워드에 저장된다.
2. 문제 풀이
Alignment: Single word라면 4바이트, Double word라면 8바이트 정렬
Allocated block: 헤더만 있거나, 헤더 + 풋터
Free block: 항상 헤더 + 풋터 필요
데이터 크기: 1바이트 이상
1) Single word / Header and footer / Header and footer
- 정렬: 4바이트 정렬
- 블록 구성: 헤더(4B) + 페이로드(1B) + 풋터(4B) = 총 9바이트
- 4바이트 정렬을 위해 12바이트로 올린다.
2) Single word / Header, but no footer / Header and footer
- 정렬: 4바이트 정렬
- 블록 구성: 헤더(4B) + 페이로드(1B) = 총 5바이트
- 4바이트 정렬을 위해 8바이트로 올린다.
3) Double word / Header and footer / Header and footer
- 정렬: 8바이트 정렬
- 블록 구성: 헤더(4B) + 페이로드(1B) + 풋터(4B) = 총 9바이트
- 8바이트 정렬을 위해 16바이트로 올린다.
4) Double word / Header, but no footer / Header and footer
- 정렬: 8바이트 정렬
- 블록 구성: 헤더(4B) + 페이로드(1B) = 총 5바이트
- 8바이트 정렬을 위해 8바이트로 올린다.
3. 정답
| Alignment | Allocated block | Free block | 최소 블록 크기(bytes) |
|---|---|---|---|
| Single word | Header and footer | Header and footer | 12 |
| Single word | Header, but no footer | Header and footer | 8 |
| Double word | Header and footer | Header and footer | 16 |
| Double word | Header, but no footer | Header and footer | 8 |
