9.9.11 경계 태그로 연결하기
현재 블록 : 반환하려는 블록
다음 가용 블록이 있으면 바로 연결하는 것은 쉽고 효율적임
현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이것은 다음 블록이 가용한지 결정하기 위해 체크될 수 있음(Linked list concept?)
-->이렇게 된다면 크기는 단순히 현재 헤더의 크기에 더해지고, 블록은 상수 시간 내에 연결할 수 있음
그림 - 경계태그를 포함한 힙 블록의 포맷
헤더를 사용하는 묵시적 가용 리스트가 이전 블록을 연결하는 유일한 옵션은 이전 블록의 위치를 기억하면서 현재 블록에 도달할 때까지 전체 리스트를 탐색하는 것 --> 각각의 free 호출은 힙의 크기에 비례하는 시간을 소모한다
이를 해결하기 위해서 경계태그라는 개념이 도입됨 위 그림처럼 footer 라는 태그를 추가함으로써 allocator는 시작위치와 이전 블록의 상태를 자신의 footer를 통해서 결정할 수 있게됨allocator가 현재 블록을 반환할 때 가능한 모든 경우
1. 이전과 다음 블록이 모두 할당
2. 이전 블록은 할당, 다음 블록은 가용
3. 이전 블록은 가용, 다음 블록은 할당
4. 이전 블록과 다음 블록이 모두 가용
경계 태그를 사용하면 연결 시간은 상수 시간에 이루어짐
단점 - 각 블록이 헤더와 풋터를 유지해야하므로 만일 application이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다
위 단점을 해결하기 위하여
경계태그를 최적화 하는 방법이 존재
할당된 블록의 하위 비트중 하나에 이전 블록의 할당/가용 비트를 저장한다고 하면 할당된 블록에는 footer가 필요 없게됨
(footer - 이전 블록의 상태와 현재 블록의 시작 위치를 가지고 있음)
footer가 필요 없게 되면 추가적인 공간을 데이터에 할당 가능함
(단, free block은 footer가 필요함)
