개념

• 모든 가능한 블록 크기를 “크기 클래스”라고 하는 집합으로 분리한다.

• 예시 : 2의 제곱
  • {1}, {2}, {3, 4}, {5~8}, … {1025~2048}, {2049 ~ 4096}, {4097 ~ 무한대}
• 예시 : 크기가 작은 블록 - 각각 하나씩 & 크기가 큰 블록 - 2의 제곱
  • {1}, {2}, {3}, … {1023}, {1024}, {1025~2048}, {2049 ~ 4096}, {4097 ~ 무한대}

블록 할당법 - 간단한 분리저장장치

• 모든 크기 클래스는 동일한 블록 크기를 갖는다.
  • ex) 크기 클래스가 {17 ~ 32}로 정의되었으면 모든 블록의 크기는 32바이트이다.
• 블록을 찾았다면,
  • 분할하지 않고 해당 free 블록에 할당한다.
• 블록을 못 찾았다면,
  • 새로운 블록을 할당받는다.
• 장점
  • 블록 할당, 반환이 매우 단순하여 연산이 O(1)으로 가능하다.
  • 블록을 병합하지도, 분할하지도 않는다.
    • 헤더나 푸터가 필요로 하지 않다.
  • 할당/반환을 가용 리스트의 시작 부분에서 한다.
    • 단일 연결로 다음 가용블록을 가리키기만 하면 된다.
• 단점
  • 내부 단편화, 외부 단편화에 취약하다.

블록 할당법 - 분리 맞춤

• 각 가용 리스트는 명시적 or 묵시적 리스트로 관리된다.
• 할당 시, 적절한 크기의 크기 클래스를 찾는다.
• 크기 클래스의 리스트에서 적절한 크기의 블록을 찾는다면,
  • 블록을 사용하고, 남은 조각을 분리하여 맞는 리스트에 넣는다.
  • 블록을 찾지 못했다면, 더 큰 클래스에서 계속 시도해본다.
• 끝까지 블록을 찾지 못했다면,
  • sbrk()를 써서 추가 heap메모리를 요청한다.
  • 새 메모리에 n바이트짜리 블록을 할당한다.
  • 나머지를 맞는 클래스의 블록에 넣는다.
• C 표준 라이브러리에서 제공되는, GNU malloc 패키지 같은 수준의 할당기에서 자주 선택된다.
  • 빠르고 메모리 관리가 효율적이기 때문이다.
  • 검색을 전체 힙이 아니라 힙의 특정 부분에서만 하므로, 매우 빠르게 가능하다.