9.5 구현 이슈

할당기가 처리량, 이용도 사이에 균형을 맞추려먼 다음 이슈들을 고려해야 함

<aside> 🔥 고려해야 할 이슈들

가용 블록 구성 —— 9.6과 연결

• 어떻게 가용 블록을 지속적으로 추적하는가?

배치(Placement) —— 9.7과 연결

• 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?

분할(Splitting) —— 9.8과 연결

• 새롭게 할당한 블록을 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?

연결(Coalescing) —— 9.10, 9.11과 연결

• 막 반환된 블록으로 무엇을 할 것인가? </aside>

9.6 묵시적 가용 리스트

실용적인 할당기는 블록의 경계를 구분하고, 할당된 블록 / 가용 블록을 구분하는 데이터 구조를 필요로 함

그리고 대부분의 할당기는 이 정보를 블록 내에 저장

• 블록은 1워드 헤더, 데이터(payload), 추가적인 패딩으로 구성

(1) 헤더 (header)

헤더는 블록 크기 (헤더, 패딩 포함) + 블록 할당 여부 인코딩

• 더블 워드(8byte) 정렬 제한조건 부과시 블록 크기는 항상 8의 배수(byte)

➡️ 따라서 헤더에서는 블록 크기의 상위 29비트만 저장할 필요가 있고, 나머지 3비트는 다른 정보를 인코드하기 위해 남겨둠

• 최소 중요 비트 (할당된 비트)를 사용해 정보 나타냄

  (EX) 0x00000018(0x00000018, 0x0) | 0x00000019(0x000000018, 0x1) (블록크기 24바이트)

(2) 데이터 (payload)

데이터는 application이 malloc을 불렀을 때 요구한 데이터가 따라옴

(3) 패딩 (padding)

패딩의 크기는 가변적 (더블 워드 정렬 요구조건 → 블록은 8배수 크기(byte)여야 하므로 이를 채우기 위함)

• 외부 단편화 극복 위한 전략의 일부분
• 정렬 요구사항을 만족하기 위해 필요