3주차 - 가용 블록을 어떻게 관리할까: Implicit / Explicit / Segregated Free List

암시적 / 명시적은 가용 블록끼리의 연결이 명시되어 있느냐를 가리킴

동적 메모리 할당기에서 쓰는 가용 블록 관리 방식. 암시적 / 명시적은 가용 블록끼리의 연결이 명시되어 있느냐를 가리킴.

implicit: 별도의 포인터 없이 헤더의 크기 필드로 다음 블록을 유추, 힙의 모든 블록을 훑음
explicit: 가용 블록의 payload에 pred/succ 포인터를 심어 가용 블록끼리만 연결
seglist: 블록 크기에 따라 크기 클래스를 나누고 클래스마다 별도의 가용 리스트를 둠
implicit → explicit → seglist로 검색 범위가 좁아짐

implicit free list: 연결 관계가 크기 필드에 암묵적으로 담겨 있어서 implicit

연결 관계가 크기 필드에 암묵적으로 담겨 있어서 implicit. 별도의 포인터가 없고, 헤더의 크기 필드로 다음 블록 주소로 계산해서 힙의 모든 블록을 처음부터 훑음. 할당된 블록까지 다 지나가면서 헤더의 alloc 비트를 확인.

[16/1][32/0][48/1][24/0][64/0]   ← 크기/할당여부
  훑음  후보  훑음  후보  후보

next = bp + GET_SIZE(HDRP(bp));   // 크기로 다음 위치를 "유추"

구현은 간단하지만, 가용 블록 하나 찾자고 할당된 블록까지 전부 지나가야 해서 느림

장점: 구조의 단순함, 오버 헤드 최소화, 작은 최소 블록 크기

단점: 느린 탐색 속도

Explicit free list: 가용 블록끼리만 연결리스트를 만듬

연결이 명시적. 가용 블록의 payload 자리에 pred/succ 포인터를 심어 가용 블록끼리만 연결리스트를 만듬.

[16/1][32/0][48/1][24/0][64/0]
        |            |      |
root ---+------------+------+---> NULL

→ 검색이 가용 블록 개수에만 비례, 할당된 블록은 건너 뜀

다만 가용 블록을 하나의 리스트로 관리하면 Explicit free list 큰 블록을 찾을 때 리스트 전체를 훑어야 함

장점: 빠른 탐색 속도

단점: 추가 메모리 필요

Segregated Free list (분리 가용 리스트): 크기 클래스마다 별도의 리스트를 둠

seglist는 블록 크기에 따라 크기 클래스를 나누고 클래스마다 별도의 가용 리스트를 둠, 보통 2의 거듭제곱으로 나눔. seglist는 explicit list를 크기별로 여러 개 두는 것. implicit → explicit → seglist로 검색 범위가 좁아짐.

class[0] -> {16}        -> [블록] -> [블록] -> NULL
class[1] -> {17~32}     -> [블록] -> NULL
class[2] -> {33~64}     -> NULL
class[3] -> {65~128}    -> [블록] -> [블록] -> ...
...

할당 (Malloc) 과정

요청 크기에 맞는 클래스 인덱스를 계산
그 리스트를 검색해서 맞는 블록을 찾음 (first fit)
없으면 더 큰 클래스로 올라가며 반복
끝까지 없으면 mem_sbrk로 힙을 확장함
찾은 블록이 충분히 크면 분할하고 남은 조각은 해당 클래스 리스트에 다시 넣음

해제 (free) 과정

들어가기 전 경계 태그란

컴퓨터 시스템의 메모리 관리(동적 메모리 할당)에서 할당된 메모리 블록의 앞과 뒤에 **메타데이터(크기, 사용 여부)**를 기록하는 기법을 말함

사용 이유:

인접한 빈 메모리 블록을 하나로 합치는 과정을 빠르고 효율적으로 처리하기 위해 사용함
만약 경계 태그가 없으면 이전 블록이 비어 있는지 확인을 위해 메모리 처음부터 탐색해야 해서 시간이 오래 걸림

경계 태그로 앞 뒤 블록을 확인해 연결한 뒤 최종 크기에 해당하는 클래스 리스트에 삽입
삽입은 보통 LIFO(맨 앞에 넣기)가 간단하고 빠름

왜 쓰나

검색 범위가 해당 크기 클래스로 좁혀져 처리량이 좋음
각 클래스 안에서 first fit이 전체 힙에 대한 best fit에 근사하므로 메모리 이용률이 좋음
glibc의 malloc도 fastbin/smallbin/largebin/tcache 형태의 분리 저장 구조를 씀
버디 시스템도 Seglist의 특수한 경우로 볼 수 있음

구현 주의

가용 블록의 payload 영역에 pred/succ 포인터 저장
최소 블록 크기가 헤더 + 푸터 + 포인터 2개 (64비트에서 보통 24 ~ 32 바이트)로 결정
클래스별 루트 포인터 배열은 힙 맨 앞에 두는 방식이 흔함
리스트에서 블록을 뺄 때, 넣을 때 경계 조건 처리가 빡셈
분할 연결 시, 리스트에서 빼는 걸 빠뜨리지 않았는지 확인해야함

#malloc #free-list #메모리할당 #seglist

시리즈에서 이어 읽기 · Malloc Lab →