C Academy · 강의

사용 가능 목록과 재사용

블록을 추적하고 재활용해 보세요.

사용 가능 목록과 재사용은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

범프 할당기 너머

개별 block을 해제하고 재사용하려면 관리 정보가 필요합니다. 자유 목록은 사용 가능한 block을 연결한 목록으로, 할당기가 새 메모리를 확보하기 전에 검색합니다.

각 block에는 헤더가 있어 할당기가 크기를 확인하고 연결된 다음 block으로 이어질 수 있습니다.

연결 정보가 있는 Block 헤더

헤더를 next 포인터와 free 플래그를 추가하도록 확장합니다. 이 둘을 함께 사용하면 풀이 탐색 가능한 block 목록으로 바뀝니다.

메모리에서 payload는 헤더 바로 뒤에 배치됩니다.

typedef struct block {
    size_t size;          /* payload bytes */
    int free;             /* 1 if reusable */
    struct block *next;   /* next block in pool */
} block_t;

하나의 큰 자유 Block 초기화

시작할 때 전체 풀은 하나의 거대한 자유 block입니다. 할당이 이루어지면 이를 나누고, 해제할 때는 block을 다시 사용할 수 있다고 표시합니다.

목록의 첫 항목은 arena 전체를 덮는 이 초기 block입니다.

static unsigned char pool[4096];
static block_t *head;

void heap_init(void) {
    head = (block_t *)pool;
    head->size = sizeof(pool) - sizeof(block_t);
    head->free = 1;
    head->next = NULL;
}

최초 적합 검색

가장 단순한 재사용 전략은 최초 적합입니다. 목록을 순회하면서 크기가 충분한 첫 번째 자유 block을 반환합니다. 빠르고 작은 block을 앞부분에 유지하는 경향이 있습니다.

대안으로는 가장 작은 충분한 block을 선택하는 최적 적합과, 속도를 단편화 양상과 맞바꾸는 최악 적합이 있습니다.

block_t *first_fit(size_t size) {
    for (block_t *b = head; b; b = b->next)
        if (b->free && b->size >= size)
            return b;
    return NULL;
}

자유 Block에서 할당하기

적합한 block을 찾으면 사용 중으로 표시하고 헤더 바로 뒤의 포인터를 반환합니다. 지금은 전체 block을 넘겨주며, 분할은 다음 레슨에서 다룹니다.

반환되는 포인터는 block + 1이며, 호출자에게 헤더를 숨깁니다.

void *my_alloc(size_t size) {
    block_t *b = first_fit(size);
    if (!b) return NULL;
    b->free = 0;
    return (void *)(b + 1);
}

Block 해제하기

해제하려면 사용자 포인터에서 뒤로 이동해 헤더를 찾고 자유 플래그를 전환합니다. 그러면 다음 검색에서 재사용할 수 있는 block이 됩니다.

payload에서 헤더를 복원하는 방법은 앞에서 살펴본 한 단계 포인터 기법과 같습니다.

void my_free(void *p) {
    if (!p) return;
    block_t *b = (block_t *)p - 1;
    b->free = 1;
}

인접한 자유 Block 병합

해제만 하면 풀에 작은 자유 block이 가득 남습니다. 병합은 해제된 block과 다음 block도 자유 상태일 때 둘을 합쳐 더 큰 연속 영역을 다시 만듭니다.

이렇게 외부 단편화를 줄여 앞으로도 큰 요청을 처리할 수 있습니다.

void coalesce(block_t *b) {
    if (b->next && b->next->free) {
        b->size += sizeof(block_t) + b->next->size;
        b->next = b->next->next;
    }
}

실행 가능한 자유 목록 데모

이 완전한 프로그램은 풀을 초기화하고 두 block을 할당한 뒤 첫 번째 block을 해제합니다. 그런 다음 더 작은 요청에 이를 재사용하여 자유 목록이 제대로 작동함을 증명합니다.

#include <stdio.h>
#include <stddef.h>

typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;

void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }

int main(void){
    heap_init();
    int *a = my_alloc(sizeof(int));
    *a = 7;
    printf("a=%d free=%d\n", *a, head->free);
    my_free(a);
    printf("after free: free=%d\n", head->free);
    return 0;
}

검색 비용

단일 연결 자유 목록에서는 block 수에 따라 할당 시간이 O(n)이 됩니다. 할당이 많아지면 느려집니다.

실제 할당기는 크기별로 나눈 자유 목록이나 트리를 사용해 검색을 O(1)에 가깝게 만듭니다. 재사용이라는 원리는 동일합니다.

/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */

이중 해제와 손상

block을 두 번 자유 상태로 표시하거나 block의 크기를 넘어 써 버리면 인접한 헤더가 손상됩니다. 그러면 다음 검색이 엉터리 next 포인터를 따라가다가 충돌합니다.

이 때문에 C의 메모리 버그가 매우 위험합니다. 할당기 자체의 메타데이터가 여러분의 데이터 바로 옆에 있기 때문입니다.

재사용을 하나로 묶기

제대로 작동하는 자유 목록 할당기에는 초기화, 적합한 block을 찾는 전략, 할당, 해제, 병합이 필요합니다. 이를 갖추면 메모리가 계속 늘어나는 대신 풀 안에서 순환합니다.

남은 개선 사항은 크기가 너무 큰 block을 분할하고 정렬을 준수하는 것이며, 이는 마지막 레슨의 주제입니다.

빠른 확인

자유 목록이 심하게 단편화되지 않도록 하는 요소가 무엇인지 생각해 보세요.

복습

자유 목록은 헤더를 통해 block을 연결하므로 개별 할당을 해제하고 재사용할 수 있습니다. 최초 적합 검색으로 block을 찾고, 해제할 때 플래그를 전환하며, 병합으로 이웃 block을 합쳐 단편화를 줄입니다.

선형 검색은 O(n)이며, 실제 할당기는 속도를 위해 크기별로 나눕니다. 다음에는 분할과 정렬을 추가합니다.

자주 묻는 질문

“사용 가능 목록과 재사용” 강의는 무료인가요?

네 — “사용 가능 목록과 재사용” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“사용 가능 목록과 재사용”에서 뭘 배우나요?

블록을 추적하고 재활용해 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

C Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“사용 가능 목록과 재사용” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← C Academy(으)로 돌아가기