malloc LAB #1 : FREE LIST 서론

가장 최근 목요일에 있었던 발제 이후 여러 일간 Free List에 대한 구현 개념에 대해 깊게 고려하고 있다.
CS:APP의 책 내용 기반으로 이뤄지는 만큼 크게 보면 세 가지의 방법으로 나뉜다 :

Implicit Free List | 묵시적 list.

Explicit Free List | 명시적 list.

Segregate Free List | 그룹분리형 list.

앞에 있는 implicit, explicit, segregate는 Free List를 어떻게 표현 할 것이냐? 에 대한 내용을 말하는 것이다.

Implicit Free List

• 표현 방식
  • 힙 메모리의 각 메모리 블록에 Header, 그리고 Footer를 위치시킨다.
  • 헤더 안에는 블록의 크기와 할당 여부를 포함한다.
• 블록 탐색
  • Free List 자체가 특별히 구현되어 있는 것이 아니다.
    따라서 할당 시 힙의 시작 점부터 끝까지 모든 블록을 순차 탐색하며 allocated 여부를 확인한다.
• 장단점
  • 세 가지의 방법 중 구현이 제일 쉬운 편에 속한다.
  • 힙의 크기에 탐색 속도가 영향을 받는다. 그리고 기본적으로도 탐색 속도가 느린 편에 속한다.

Explicit Free List 

• 표현 방식
  • 빈 블록들끼리만 모아서 별도의 연결 리스트를 유지한다. 이 경우, 양방향 연결 리스트가 필요하다.
  • 각 빈 블록의 실 데이터가 담겨야할 payload 영역의 일부는 연결 리스트에 있는 동안에는 next,prev 을 저장 할 수 있는 공간으로 사용 할 수 있도록 한다.
• 블록 탐색
  • 할당 요청 시에는 free list의 헤드 포인터만 따라가며 빈 블록을 빠르게 찾거나, Fit 전략을 적절하게 조정하여 순회 할 수 있다.
• 장단점
  • 탐색 속도가 빠르다.
  • 각 빈 블록에 포인터 오버헤드(2 * 포인터 크기)가 발생한다.

Segregate Free List

• 표현 방식
  • 빈 블록들을 크기 별로 구분하여 각각 별도의 free list로 관리한다.
  • 즉, 여러 개의 free list가 존재하며, 각 리스트는 특정 크기 범위의 빈 블록만 포함한다.
• 블록 탐색
  • 할당 요청 크기에 가장 적합한 크기 클래스를 선택하여, 그 클래스에 해당하는 free list에서 블록을 검색한다.
  • 만약 위 내용대로 하는데 적절한 블록이 없다면, 더 큰 크기 클래스에서 검색해서 분할해서 사용하는 식의 방법을 고려한다.
• 장단점
  • 매우 빠른 탐색. 전체 블록을 스캔 할 필요 없이 해당 크기대 리스트만 검색한다. 일종의 재고확인 처럼..
  • 외부 단편화 감소. 비슷한 크기의 블록끼리만 모아두게 되니, 쓸만한 빈 공간이 덜 쪼개진다.
  • 메모리 오버헤드 발생. 여러 Free List 포인터와 리스트 관리를 위한 추가 메타데이터를 필요로 한다.
  • 크기 클래스 설계가 복잡. 잘못 설계하는 경우, 공간 낭비나 성능 저하를 발생 시킬 수 있다.

한창 구현이 진행중이니 이어서 논하도록 하겠다.