정렬과 분할
블록을 사용하기 좋고 깔끔하게 만들어 보세요.
정렬과 분할은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
정렬이 중요한 이유
모든 형식에는 정렬 요구 사항이 있습니다. 주소가 어떤 2의 거듭제곱의 배수여야 한다는 뜻입니다. double은 일반적으로 8바이트 정렬이 필요합니다.
malloc은 무엇을 저장할지 알 수 없으므로 가장 엄격한 형식에 맞춰 정렬된 포인터를 반환해야 합니다. 64비트 시스템에서는 보통 16바이트입니다.
#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t); /* often 16 */align_up 기법
크기를 2의 거듭제곱인 정렬 단위의 다음 배수로 올림하는 것은 고전적인 비트 기법입니다. a - 1을 더한 다음 낮은 비트를 마스크로 지웁니다.
이 방법은 a가 2의 거듭제곱일 때만 작동하며, 실제 정렬 값은 모두 이에 해당합니다.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1);
}
/* align_up(13, 8) == 16, align_up(16, 8) == 16 */수식이 실행되는지 확인하기
실행 가능한 프로그램으로 align_up을 확인해 보겠습니다. 여러 크기를 8바이트 및 16바이트 경계까지 올림하고 결과를 출력합니다.
#include <stdio.h>
#include <stddef.h>
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1);
}
int main(void) {
printf("%zu\n", align_up(13, 8)); /* 16 */
printf("%zu\n", align_up(16, 8)); /* 16 */
printf("%zu\n", align_up(1, 16)); /* 16 */
printf("%zu\n", align_up(33, 16)); /* 48 */
return 0;
}요청 크기 정렬하기
할당기 내부에서는 모든 요청의 첫 단계로 요청된 크기를 정렬 단위까지 올림합니다. 이렇게 하면 다음 block도 정렬된 위치에서 시작합니다.
패딩 바이트는 내부 단편화이며, 보편적인 정렬을 위해 지불하는 비용입니다.
#define ALIGN 16
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
/* now find a block of this aligned size */
/* ... */
return NULL;
}전체 Block 재사용의 문제
이전 레슨에서는 아주 작은 요청에도 자유 block 전체를 반환했습니다. 16바이트 요청에 4000바이트 자유 block을 넘기면 나머지 공간이 낭비됩니다.
분할하면 block을 사용하는 부분과 자유 상태로 남겨 둘 나머지 부분으로 나눌 수 있습니다.
Block 분할하기
선택한 block이 필요한 크기보다 훨씬 크면 요청한 영역의 끝에 새 헤더를 배치합니다. 남은 부분은 목록의 더 작은 자유 block이 됩니다.
나머지가 헤더와 일부 payload를 담을 만큼 클 때만 분할합니다. 그렇지 않으면 그 조각은 쓸모가 없습니다.
void split(block_t *b, size_t size) {
size_t rem = b->size - size;
if (rem < sizeof(block_t) + ALIGN) return; /* too small */
block_t *nb = (block_t *)((char *)(b + 1) + size);
nb->size = rem - sizeof(block_t);
nb->free = 1;
nb->next = b->next;
b->size = size;
b->next = nb;
}할당, 정렬, 분할
이제 전체 할당 과정에서 크기를 정렬하고, 적합한 block을 찾고, 큰 나머지 부분을 분할해 떼어 낸 다음 block을 사용 중으로 표시합니다.
이렇게 하면 block의 크기를 꼭 필요한 만큼 유지하면서 뒤에 사용할 수 있는 자유 공간을 남깁니다.
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
block_t *b = first_fit(size);
if (!b) return NULL;
split(b, size);
b->free = 0;
return (void *)(b + 1);
}풀 자체를 정렬 상태로 유지하기
정확성을 위해 풀의 시작 주소와 헤더 크기도 정렬을 따라야 모든 payload가 경계에 배치됩니다.
정적 버퍼에 alignas를 사용하면 전체 구조가 정렬된 상태에서 시작하도록 보장할 수 있습니다.
#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */실행 가능한 정렬 할당
이 프로그램은 정렬된 풀에서 할당하고 반환된 주소를 16으로 나눈 나머지를 출력합니다. 그 값이 항상 0이므로 올바르게 정렬되었음을 보여 줍니다.
#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>
static size_t align_up(size_t n, size_t a){ return (n+a-1)&~(a-1); }
alignas(16) static unsigned char pool[1024];
static size_t off = 0;
void *alloc16(size_t s){ off=align_up(off,16); if(off+s>sizeof(pool)) return NULL; void*p=&pool[off]; off+=s; return p; }
int main(void){
void *a = alloc16(1);
void *b = alloc16(20);
printf("a %% 16 = %lu\n", (unsigned long)((size_t)a % 16));
printf("b %% 16 = %lu\n", (unsigned long)((size_t)b % 16));
return 0;
}분할과 병합
분할과 병합은 서로 반대되는 작업으로 균형을 이룹니다. 할당할 때는 큰 block을 나누고, 해제할 때는 작은 block을 다시 합칩니다.
둘을 함께 사용하면 요청 크기의 구성이 바뀌어도 같은 풀로 서비스를 제공하면서 공간을 누수시키거나 영구적으로 단편화하지 않을 수 있습니다.
장난감 할당기에서 실제 할당기로
이제 네 가지 핵심 요소를 모두 갖추었습니다. 메모리 원천, 정렬된 헤더, 병합을 통한 자유 목록 재사용, 그리고 분할입니다. 실제 할당기는 속도와 확장성을 위해 크기 등급별 구간, 스레드 캐시, OS 통합을 추가합니다.
하지만 여기서 만든 핵심 개념은 모든 malloc 구현의 기반이 됩니다.
빠른 확인
할당 중에 block을 분할하는 이유를 생각해 보세요.
복습
정렬은 비트 기법 (n + a - 1) & ~(a - 1)을 사용해 크기를 올림하므로 모든 payload가 어떤 형식에도 맞습니다. 분할은 지나치게 큰 자유 block을 사용 중인 부분과 자유 상태의 나머지 부분으로 나누고, 병합은 해제할 때 이를 되돌립니다.
이 네 가지 핵심 요소가 함께 완전하고 올바른 메모리 할당기를 구성합니다.
자주 묻는 질문
“정렬과 분할” 강의는 무료인가요?
네 — “정렬과 분할” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“정렬과 분할”에서 뭘 배우나요?
블록을 사용하기 좋고 깔끔하게 만들어 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“정렬과 분할” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.