13. 명시적 가용 리스트

묵시적 가용 리스트는 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 범용 할당기에 적합하지 않음

따라서 가용 블록들을 명시적 자료구조로 구성하는 게 더 좋음

• 가용 블록 본체(payload)는 프로그램에서 필요하지 않기 때문에 이 자료구조를 구현하는 포인터는 가용 블록의 본체 내에 저장될 수 있음
• (EX) 가용 블록 내에 predecessor, successor 포인터를 포함하는 이중 연결 가용 리스트로 구현

• 모든 블록의 리스트를 유지하는 게 아니라, 가용 블록들의 리스트만 유지하면 됨
  • 따라서 다음의 가용 블록은 어디든 될 수 있음

Freeing an allocated block

• LIFO Policy (fragmentation is worse than address-ordered policy)

  • Case 1

    

  • Case 2

    

  • Case 3

    

  • Case 4

    

• Address-ordered Policy (requires search)

14. 분리 가용 리스트 Seglist Allocator

모든 가능한 블록 크기를 크기 클래스라고 하는 동일 클래스의 집합들로 분리하는 것