컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.13 명시적 가용 리스트 Part.1

9.9.13 명시적 가용 리스트 (Explicit Free Lists)

1. 명시적 가용 리스트의 필요성

암시적 가용 리스트(Implicit Free List)는 구현이 쉽지만, 힙에 블록이 많아질수록 malloc 호출 시 모든 블록을 순차적으로 탐색해야 한다. 이로 인해 탐색 시간이 길어져 성능이 크게 저하된다. 이를 해결하기 위해 명시적 가용 리스트를 사용한다.

2. 명시적 가용 리스트란 무엇인가

가용 블록을 포인터를 통해 직접 연결하여 관리하는 리스트를 의미한다.
가용 블록의 내부(payload) 공간에

• 이전 가용 블록을 가리키는 포인터(pred)
• 다음 가용 블록을 가리키는 포인터(succ)
  를 저장하여 이중 연결 리스트(doubly linked list) 형태로 구성한다.

이 방식을 사용하면 가용 블록만 빠르게 순회할 수 있어,
malloc이 전체 힙이 아닌 가용 블록 수에 비례하는 시간만 소모하게 된다.

3. 리스트 정렬 방식

명시적 가용 리스트는 주로 두 가지 방법으로 정렬할 수 있다.

• LIFO(후입선출) 방식으로 관리한다.
  • 새로운 가용 블록을 리스트의 맨 앞에 삽입한다.
  • 삽입이 O(1)의 빠른 시간에 가능하다.
  • 그러나 메모리 활용률이 다소 떨어질 수 있다.
• 주소순(Address Order) 정렬을 사용한다.
  • 가용 블록들의 주소를 오름차순으로 정렬하여 저장한다.
  • 삽입 시 선형 탐색이 필요해 느릴 수 있으나,
  • first-fit 전략 사용 시 best-fit에 가까운 메모리 활용률을 얻을 수 있다.

4. 명시적 가용 리스트의 단점

가용 블록 내부에 추가 포인터(pred, succ)를 저장해야 하므로, 블록당 오버헤드가 증가하고, 결과적으로 내부 단편화(Internal Fragmentation)가 증가할 수 있다.

항목	묵시적 가용 리스트	명시적 가용 리스트
관리 방식	모든 블록을 순회한다	포인터로 연결된 가용 블록만 순회한다
탐색 시간	전체 블록 수에 비례한다	가용 블록 수에 비례한다
추가 공간 오버헤드	없다	pred/succ 포인터 저장 공간이 필요하다
free 속도	느리다	매우 빠르다 (O(1))
메모리 활용률	보통이다	정렬 방식에 따라 향상될 수 있다

5. 명시적 리스트의 구조 (Figure 9.48 참조)

그림 9.48 : 이중 연결 가용 리스트를 사용하는 힙 블록의 포맷.

 

---

구현 설명

구현 방향 - 명시적 가용 리스트 + LIFO 방식

대부분의 코드는 이 전 포스팅에서 구현한 묵시적 가용리스트를 기반으로 하며 변경이 필요한 부분에 대해서 설명을 진행하겠다.

2025.04.27 - [크래프톤 정글 (컴퓨터 시스템: CSAPP)/9장 가상 메모리] - 컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.1

컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.1

2025.04.27 - [크래프톤 정글 (컴퓨터 시스템: CSAPP)/9장 가상 메모리] - 컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.2

컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.12 종합 설계 : 간단한 할당기의 구현 Part.2

---

가용 리스트 탐색 관련 매크로

#define GET_SUCC(bp) (*(void **)((char *)(bp) + WSIZE))
#define GET_PRED(bp) (*(void **)(bp))

명시적 가용 리스트를 위해:

• 이전 블록(PRED)과 다음 블록(SUCC) 포인터를 블록 내부에 저장한다.

전역 변수 선언

static char *free_listp;

• 가용 리스트의 맨 앞 블록을 가리키는 포인터다.

함수 선언부

static void splice_free_block(void *bp);
static void add_free_block(void *bp);

• 기존 함수 선언에 추가로 위 두 개의 함수를 선언해 둔다. 이 함수들은 free list 조작 함수들이다.

mm_init: 메모리 시스템 초기화

Step 1: 힙 공간 요청 (mem_sbrk)

if ((free_listp = mem_sbrk(8 * WSIZE)) == (void *)-1)
        return -1;

• 힙에서 8워드(64바이트) 만큼 공간을 확보한다.
• mem_sbrk는 힙을 확장하고 그 시작 주소를 반환한다.
• 실패하면 -1 리턴.

왜 8 워드?
패딩 + 초기 프롤로그 블록(헤더/푸터) + 첫 가용 블록(헤더/푸터/프리포인터 2개) + 에필로그 블록까지 필요하다.

Step 2: 힙 구조 세팅

PUT(free_listp, 0);

• [0]: 정렬 패딩. (힙을 16바이트 정렬시키기 위한 자리)

PUT(free_listp + (1 * WSIZE), PACK(2 * WSIZE, 1));
PUT(free_listp + (2 * WSIZE), PACK(2 * WSIZE, 1));

 

• [1], [2]: 프롤로그 블록 (2 워드 크기, 할당됨)
• 항상 존재하는 가상의 블록, 경계조건 처리를 편하게 함.

PUT(free_listp + (3 * WSIZE), PACK(4 * WSIZE, 0));

 

• [3]: 첫 번째 가용 블록의 헤더 (크기: 32바이트, 비할당)

PUT(free_listp + (4 * WSIZE), NULL);
PUT(free_listp + (5 * WSIZE), NULL);

 

• [4], [5]: 명시적 가용 리스트용 PRED와 SUCC 자리
• 현재는 비어 있음.

PUT(free_listp + (6 * WSIZE), PACK(4 * WSIZE, 0));

 

• [6]: 첫 번째 가용 블록의 푸터

PUT(free_listp + (7 * WSIZE), PACK(0, 1));

 

• [7]: 에필로그 블록 (0바이트 크기, 항상 할당 상태)
• 힙의 끝을 표시한다.

Step 3: free_listp 조정

free_listp += (4 * WSIZE);

 

• free_listp를 첫 번째 가용 블록의 payload를 가리키도록 이동한다.

Step 4: 힙 확장

if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;

 

• 힙을 추가로 CHUNKSIZE(4096바이트) 만큼 확장한다.
• extend_heap 함수는 새로 확보한 블록을 coalesce 하여 반환한다

 

int mm_init(void)
{
    // 초기 힙 생성
    if ((free_listp = mem_sbrk(8 * WSIZE)) == (void *)-1)
        return -1;
    PUT(free_listp, 0);                                
    PUT(free_listp + (1 * WSIZE), PACK(2 * WSIZE, 1)); 
    PUT(free_listp + (2 * WSIZE), PACK(2 * WSIZE, 1));
    PUT(free_listp + (3 * WSIZE), PACK(4 * WSIZE, 0)); 
    PUT(free_listp + (4 * WSIZE), NULL);               
    PUT(free_listp + (5 * WSIZE), NULL);               
    PUT(free_listp + (6 * WSIZE), PACK(4 * WSIZE, 0)); 
    PUT(free_listp + (7 * WSIZE), PACK(0, 1));      

    free_listp += (4 * WSIZE); // 첫번째 가용 블록의 bp

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;

    return 0;
}

---

mm_malloc: 메모리 블록 할당 함수

Step 1: 잘못된 요청 처리

  if (size == 0)
        return NULL;

• size가 0이면 의미 없는 요청이므로 그냥 NULL 반환한다.

Step 2: 요청 사이즈 조정 (asize 계산)

size_t asize;
size_t extendsize;
char *bp;

지역 변수 선언:

• asize: 실제 할당할 조정된 크기.
• extendsize: 힙을 확장해야 할 경우 필요한 크기.
• bp: 블록 포인터.

사이즈 조정 코드:

if (size <= DSIZE)
    asize = 2 * DSIZE;
else
    asize = DSIZE * ((size + DSIZE + DSIZE - 1) / DSIZE);

설명:

• 요청한 크기 size를 기반으로 실제로 할당할 크기 asize를 결정한다.
• 최소 블록 크기는 16바이트(헤더+푸터+포인터 공간) 이상이어야 한다.
• 항상 16바이트 단위로 정렬되도록 올림 한다.

예를 들어 요청 size=13바이트 → 패딩 포함하면 32바이트가 된다.

---

Step 3: 가용 블록 탐색

if ((bp = find_fit(asize)) != NULL)
{
    place(bp, asize);
    return bp;
}

 

• find_fit(asize) 호출:
  적절한 크기의 가용 블록을 찾는다.
• 찾으면:
  • place(bp, asize) 호출: 블록을 실제로 배치한다.
  • bp 리턴.

Step 4: 가용 블록이 없을 경우, 힙 확장

extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
    return NULL;
place(bp, asize);
return bp;

 

• 찾지 못하면, 요청 사이즈(asize)나 CHUNKSIZE 중 큰 크기로 힙을 확장한다.
• 확장 성공하면 새로 생긴 블록을 배치하고 반환한다.
• 확장 실패 시 NULL 반환.

void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize; 
    char *bp;

    if (size == 0)
        return NULL;

    if (size <= DSIZE) 
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + DSIZE + DSIZE - 1) / DSIZE);

    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize); 
        return bp;        
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

---

mm_free: 메모리 블록 반환 함수

Step 1: 블록 사이즈 읽어오기

size_t size = GET_SIZE(HDRP(bp));

 

• 현재 블록의 헤더 포인터(HDRP(bp))를 통해 블록의 크기를 가져온다.
• GET_SIZE: 헤더에 저장된 값을 읽어서 size만 추출한다.

Step 2: 헤더/푸터 갱신 (free 표시)

PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));

 

• 헤더와 푸터를 모두 업데이트한다:
  • 크기는 그대로,
  • 할당 비트는 0으로 설정 (free 상태).

헤더와 푸터를 모두 업데이트하는 이유:

• 나중에 블록 병합(coalescing)할 때 이전/다음 블록 상태를 빠르게 확인하기 위해.

---

Step 3: 병합(coalescing) 시도

coalesce(bp);

coalesce(bp) 호출:

• 만약 인접한 블록들 중 free 된 것이 있다면 합친다.
• 병합 결과는 free list에도 반영된다.

void mm_free(void *bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

---

mm_realloc: 메모리 블록 재할당 함수

Step 1: 특수한 경우들을 먼저 처리한다.

if (ptr == NULL)
    return mm_malloc(size);

• ptr이 NULL인 경우, 새 메모리를 할당하는 것과 동일하므로 mm_malloc(size)를 호출하고 반환한다.

if (size <= 0)
{
    mm_free(ptr);
    return 0;
}

• 요청한 size가 0 이하이면, 기존 블록을 반환(free)하고 NULL을 반환한다.

즉, realloc은 malloc + free를 모두 포괄하는 함수이다.

Step 2: 새로 할 블록을 malloc으로 요청한다.

void *newptr = mm_malloc(size);
if (newptr == NULL)
    return NULL;

• 새로운 크기로 메모리를 할당한다.
• 실패하면 NULL을 반환한다.

Step 3: 기존 블록 데이터를 새 블록으로 복사한다.

size_t copySize = GET_SIZE(HDRP(ptr)) - DSIZE;

• 기존 블록 크기에서 메타데이터(Header/Footer 2개 = 16바이트)를 제외한 payload 영역 크기를 가져온다.

if (size < copySize)
    copySize = size;

• 만약 요청한 size가 기존 데이터보다 작다면,
• 복사할 크기를 size로 줄인다.

즉, 기존 payload보다 작은 공간만 요청했으면 일부만 복사한다.

 memcpy(newptr, ptr, copySize);

• memcpy를 이용해 기존 블록의 데이터를 새 블록으로 복사한다.

Step 4: 기존 블록을 반환한다.

mm_free(ptr);

• 이전 블록은 더 이상 필요 없으므로 반환(free)한다.

Step 5: 새 블록 포인터를 반환한다.

	return newptr;
}

• 복사 완료된 새 블록의 포인터를 반환한다.

void *mm_realloc(void *ptr, size_t size)
{
    /* 예외 처리 */
    if (ptr == NULL) // 포인터가 NULL인 경우 할당만 수행
        return mm_malloc(size);

    if (size <= 0) // size가 0인 경우 메모리 반환만 수행
    {
        mm_free(ptr);
        return 0;
    }

    /* 새 블록에 할당 */
    void *newptr = mm_malloc(size); // 새로 할당한 블록의 포인터
    if (newptr == NULL)
        return NULL; // 할당 실패

    /* 데이터 복사 */
    size_t copySize = GET_SIZE(HDRP(ptr)) - DSIZE; // payload만큼 복사
    if (size < copySize)                           // 기존 사이즈가 새 크기보다 더 크면
        copySize = size;                           // size로 크기 변경 (기존 메모리 블록보다 작은 크기에 할당하면, 일부 데이터만 복사)

    memcpy(newptr, ptr, copySize); // 새 블록으로 데이터 복사

    /* 기존 블록 반환 */
    mm_free(ptr);
    
    return newptr;
}

---

다음 포스팅에 이어서 명시적 가용 리스트의 핵심 코드들을 설명하겠다.