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

이전 포스팅에 이어서 명시적 가용 리스트를 구현해 보겠다.

2025.04.27 - [크래프톤 정글 (컴퓨터 시스템: CSAPP)/9장 가상 메모리] - 컴퓨터 시스템 : CSAPP 9장 정리 - 9.9.13 명시적 가용 리스트 Part.1

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

---

exstend_heap

extend_heap 함수의 경우 변경이 없다. 그래서 해당 함수는 이전 포스팅을 확인하라

---

coalesce: 가용 블록 병합 함수

Step 1: 이전 블록과 다음 블록의 할당 상태를 확인한다.

size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

• PREV_BLKP(bp): 이전 블록의 payload 주소를 구한다.
• FTRP(PREV_BLKP(bp)): 이전 블록의 푸터 주소를 구하고, 거기서 할당 여부를 읽는다.
• NEXT_BLKP(bp): 다음 블록의 payload 주소를 구한다.
• HDRP(NEXT_BLKP(bp)): 다음 블록의 헤더 주소를 구하고, 거기서 할당 여부를 읽는다.

즉, prev_alloc, next_alloc 변수를 통해 각각

• 이전 블록이 할당되어 있는지,
• 다음 블록이 할당되어 있는지를 알아낸다.

---

Step 2: 현재 블록의 사이즈를 저장한다.

size_t size = GET_SIZE(HDRP(bp));

• 현재 블록의 헤더에서 사이즈를 읽어와 저장한다.

Step 3: 병합 조건에 따라 분기 처리한다.

3-1. 이전, 다음 모두 할당된 경우

if (prev_alloc && next_alloc)
{
    add_free_block(bp);
    return bp;
}

• 주변 블록 모두 사용 중이면, 병합하지 않는다.
• 현재 블록 bp를 가용 리스트에 추가하고 반환한다.

3-2. 이전 블록은 할당되어 있고, 다음 블록은 비어 있는 경우

 else if (prev_alloc && !next_alloc)
{
    splice_free_block(NEXT_BLKP(bp));
    size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
}​

• 다음 블록이 비어있으면, NEXT_BLKP(bp)를 free list에서 제거하고 병합한다.
• size를 두 블록의 크기 합으로 갱신한다.
• 새로운 헤더와 푸터를 설정한다.

3-3. 이전 블록은 비어 있고, 다음 블록은 할당된 경우

else if (!prev_alloc && next_alloc)
{
    splice_free_block(PREV_BLKP(bp));
    size += GET_SIZE(HDRP(PREV_BLKP(bp)));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    bp = PREV_BLKP(bp);
}​

• 이전 블록이 비어있으면, PREV_BLKP(bp)를 free list에서 제거하고 병합한다.
• size를 두 블록의 크기 합으로 갱신한다.
• 새로운 헤더와 푸터를 설정한다.
• bp를 병합된 블록의 시작점으로 이동시킨다.

3-4. 이전 블록과 다음 블록 모두 비어 있는 경우

 

else
{
    splice_free_block(PREV_BLKP(bp));
    splice_free_block(NEXT_BLKP(bp));
    size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
    bp = PREV_BLKP(bp);
}

• 양쪽 모두 비어있으면, 양쪽 블록 모두 free list에서 제거하고 셋을 통합한다.
• size를 세 블록 크기 합으로 갱신한다.
• 새로운 헤더와 푸터를 설정한다.
• bp를 병합된 시작 블록으로 이동시킨다.

Step 4: 병합 후 free list에 추가한다.

	add_free_block(bp);
	return bp;
}

 

• 병합된 새 블록을 free list의 맨 앞에 추가한다.
• 병합 결과 블록의 포인터를 반환한다.

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록 할당 상태
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록 할당 상태
    size_t size = GET_SIZE(HDRP(bp));                   // 현재 블록 사이즈

    if (prev_alloc && next_alloc) // 모두 할당된 경우
    {
        add_free_block(bp); // free_list에 추가
        return bp;          // 블록의 포인터 반환
    }
    else if (prev_alloc && !next_alloc) // 다음 블록만 빈 경우
    {
        splice_free_block(NEXT_BLKP(bp)); // 가용 블록을 free_list에서 제거
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0)); // 현재 블록 헤더 재설정
        PUT(FTRP(bp), PACK(size, 0)); // 다음 블록 푸터 재설정 (위에서 헤더를 재설정했으므로, FTRP(bp)는 합쳐질 다음 블록의 푸터가 됨)
    }
    else if (!prev_alloc && next_alloc) // 이전 블록만 빈 경우
    {
        splice_free_block(PREV_BLKP(bp)); // 가용 블록을 free_list에서 제거
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록 헤더 재설정
        PUT(FTRP(bp), PACK(size, 0));            // 현재 블록 푸터 재설정
        bp = PREV_BLKP(bp);                      // 이전 블록의 시작점으로 포인터 변경
    }
    else // 이전 블록과 다음 블록 모두 빈 경우
    {
        splice_free_block(PREV_BLKP(bp)); // 이전 가용 블록을 free_list에서 제거
        splice_free_block(NEXT_BLKP(bp)); // 다음 가용 블록을 free_list에서 제거
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); // 이전 블록 헤더 재설정
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); // 다음 블록 푸터 재설정
        bp = PREV_BLKP(bp);                      // 이전 블록의 시작점으로 포인터 변경
    }
    add_free_block(bp); // 현재 병합한 가용 블록을 free_list에 추가
    return bp;          // 병합한 가용 블록의 포인터 반환
}

 

---

find_fit: 적합한 가용 블록 찾기 함수

Step 1: 가용 리스트의 첫 번째 블록부터 순회한다.

void *bp = free_listp;

• bp를 가용 리스트의 맨 앞 블록 포인터로 초기화한다.

Step 2: 가용 리스트를 따라 순회하면서 조건을 검사한다.

while (bp != NULL)
{

• 가용 블록 bp가 NULL이 아니면 (즉, 아직 리스트 끝에 도달하지 않았으면) 반복한다.

Step 3: 현재 블록이 요청 크기에 적합한지 검사한다.

if ((asize <= GET_SIZE(HDRP(bp))))
    return bp;

• 현재 블록의 크기가 asize 이상이면, 즉 요청 크기를 수용할 수 있으면
• 해당 블록을 바로 반환한다.

"first-fit" 방식으로 찾는다.
가장 먼저 맞는 블록을 찾으면 바로 반환하여 빠르게 처리한다.

Step 4: 다음 가용 블록으로 이동한다.

	bp = GET_SUCC(bp);
}

• 현재 블록의 SUCC(다음 블록) 포인터를 따라 이동한다.

Step 5: 적합한 블록을 찾지 못한 경우

	return NULL;
}

 

• 순회를 모두 마쳤는데도 적합한 블록이 없으면 NULL을 반환한다.
• 이 경우, mm_malloc 함수가 힙을 확장하게 된다.

---

place: 가용 블록에 메모리를 할당하는 함수

Step 1: 먼저 free list에서 해당 블록을 제거한다.

splice_free_block(bp);

 

• bp에 해당하는 가용 블록을 명시적 가용 리스트에서 제거한다.
• (할당되었으므로 free list에 남아있으면 안 된다.)

Step 2: 현재 블록의 크기를 가져온다.

size_t csize = GET_SIZE(HDRP(bp));

• 현재 블록의 헤더를 통해 전체 블록 크기(csize)를 가져온다.

Step 3: 블록 분할 여부를 결정한다.

if ((csize - asize) >= (2 * DSIZE))

• 현재 블록과 요청 크기의 차이가 32바이트(2 * 16) 이상이면
• 블록을 분할할 수 있다고 판단한다.

왜 32바이트인가?

• 최소 블록 크기가 16바이트(헤더+푸터+PRED/SUCC) 필요하기 때문에, 분할된 나머지 블록도 가용 블록의 최소 조건을 만족해야 한다.

---

Step 3-1: 블록을 분할하는 경우

{
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));

현재 블록의 헤더와 푸터에 요청한 크기 asize를 쓰고, 할당 표시(1)를 한다.

PUT(HDRP(NEXT_BLKP(bp)), PACK((csize - asize), 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK((csize - asize), 0));

 

• 남은 공간은 새로운 가용 블록으로 만들어준다.
• 남은 블록의 헤더/푸터를 설정하고, 할당 안 됨(0) 표시를 한다.

add_free_block(NEXT_BLKP(bp));

 

• 새로 생긴 가용 블록을 free list에 추가한다.

Step 3-2: 블록을 분할하지 않는 경우

    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }

• 현재 블록 전체를 요청자에게 할당한다.
• 헤더와 푸터를 크기 csize, 할당 표시(1)로 설정한다.
• 남는 공간이 없으므로 분할하지 않는다.

static void place(void *bp, size_t asize)
{
    splice_free_block(bp); // free_list에서 해당 블록 제거

    size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 크기

    if ((csize - asize) >= (2 * DSIZE)) // 차이가 최소 블록 크기 16보다 같거나 크면 분할
    {
        PUT(HDRP(bp), PACK(asize, 1)); // 현재 블록에는 필요한 만큼만 할당
        PUT(FTRP(bp), PACK(asize, 1));

        PUT(HDRP(NEXT_BLKP(bp)), PACK((csize - asize), 0)); // 남은 크기를 다음 블록에 할당(가용 블록)
        PUT(FTRP(NEXT_BLKP(bp)), PACK((csize - asize), 0));
        add_free_block(NEXT_BLKP(bp)); // 남은 블록을 free_list에 추가
    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1)); // 해당 블록 전부 사용
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

---

splice_free_block: 가용 리스트에서 블록 제거

Step 1: 만약 bp가 가용 리스트의 맨 앞이면 처리한다.

 if (bp == free_listp)
{
    free_listp = GET_SUCC(free_listp);
    return;
}

• 제거하려는 블록이 가용 리스트의 맨 앞에 있으면,
• free_listp를 그 블록의 다음 블록(SUCC)으로 갱신한다.
• 이후 추가 처리를 하지 않고 함수를 종료한다.

즉, 맨 앞 블록을 제거할 때는 free_listp 포인터만 변경하면 된다.

---

Step 2: 일반적인 경우 (가운데 블록인 경우) 처리한다.

GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);

• bp의 이전 블록(PRED(bp))의 SUCC 포인터를
• bp의 다음 블록(SUCC(bp))로 연결한다.

즉, bp를 가리키던 선을 건너뛰고, 그다음 블록으로 바로 연결한다.

if (GET_SUCC(bp) != NULL)
    GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);

• 만약 bp의 다음 블록이 존재하면,
• 그 다음 블록의 PRED 포인터를 bp의 이전 블록으로 연결한다.

즉, bp를 양쪽에서 모두 "빼버린다".

static void splice_free_block(void *bp)
{
    if (bp == free_listp)
    {
        free_listp = GET_SUCC(free_listp);
        return;
    }
    GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);
    if (GET_SUCC(bp) != NULL)
        GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);
}

---

add_free_block: 가용 리스트에 블록 추가

Step 1: SUCC(bp)를 현재 free_listp로 설정한다.

GET_SUCC(bp) = free_listp;

• 현재 가용 리스트의 맨 앞 블록을
• bp의 SUCC(다음 블록 포인터)로 설정한다.

Step 2: 기존 맨 앞 블록이 존재한다면, 그 블록의 PRED를 bp로 설정한다.

if (free_listp != NULL)
    GET_PRED(free_listp) = bp;

• 기존 가용 리스트에 블록이 있었다면,
• 그 블록의 PRED를 새로 추가하는 bp로 연결한다.

Step 3: free_listp를 bp로 갱신한다.

	free_listp = bp;
}

• 가용 리스트의 맨 앞을 새로 추가한 bp로 변경한다.

즉, bp가 새로운 루트 블록이 된다.

static void add_free_block(void *bp){
    GET_SUCC(bp) = free_listp; 
    if (free_listp != NULL)        
        GET_PRED(free_listp) = bp;
    free_listp = bp;               
}