동적 메모리 할당(Malloc) 심화 및 구현 1-1

malloc-lab 함수별 상세 설명 + 메모리 관리 이론 정리

malloc이란?

malloc은 Memory Allocation의 줄임말로, 런타임에 프로그램이 필요한 만큼의 메모리를 동적으로 할당해주는 함수입니다.
C 언어 표준 라이브러리(stdlib.h)에 포함되어 있으며, 사용자가 요청한 바이트 수만큼 힙 영역(heap)에서 메모리를 확보해 포인터를 반환합니다.

• 성공 시: 할당된 메모리 블록의 시작 주소를 반환
• 실패 시: NULL 반환

할당한 메모리는 반드시 프로그램에서 free()를 호출해 해제해야 합니다.

1. mm_init()

힙을 초기화하는 함수입니다.

• 4워드 크기의 기본 힙 생성 (패딩, 프롤로그 헤더, 프롤로그 풋터, 에필로그 헤더)
• heap_listp를 프롤로그 블록의 페이로드 위치로 이동
• 힙을 CHUNKSIZE만큼 확장하기 위해 extend_heap() 호출
• last_fit를 heap_listp로 초기화

2. extend_heap(size_t words)

힙을 주어진 워드 수만큼 확장하는 함수입니다.

• 홀수 개 워드라면 1개 추가해 짝수 워드(8바이트 정렬)를 유지
• mem_sbrk()로 힙을 확장하고 새 블록에 Free 헤더/풋터 설정
• 에필로그 헤더를 새로 만듬
• coalesce()로 인접 가용 블록과 병합
• 마지막에 last_fit 포인터를 병합된 블록으로 갱신

3. coalesce(void *bp)

Free 블록을 인접한 Free 블록들과 병합하는 함수입니다.

• 앞, 뒤 블록의 할당 상태를 확인
• 뒤쪽, 앞쪽, 양쪽 모두 병합 가능한 경우 크기를 확장
• 병합 후 last_fit을 heap_listp로 초기화해 탐색 일관성 유지

4. mm_malloc(size_t size)

요청한 크기의 메모리를 힙에서 찾아 할당하는 함수입니다.

• payload 크기에 메타데이터(header/footer) 추가하고 8바이트 정렬
• find_fit()으로 적절한 가용 블록 탐색
• 발견하면 place()로 블록을 나누어 할당
• 없으면 힙 확장 후 할당

5. place(void *bp, size_t asize)

발견한 가용 블록을 필요한 만큼만 사용하여 나머지를 분할하는 함수입니다.

• 남은 공간이 충분히 크면 블록을 분할
• 작으면 통째로 할당

6. find_fit(size_t asize)

요청 크기에 맞는 가용 블록을 찾는 함수입니다. (Next Fit 방식)

• last_fit부터 힙 끝까지 탐색
• 찾지 못하면 힙 처음(heap_listp)부터 last_fit까지 탐색
• 찾으면 last_fit을 갱신 후 반환

7. mm_free(void *ptr)

메모리 블록을 Free 상태로 변경하는 함수입니다.

• 헤더와 풋터를 가용 상태로 수정
• coalesce()로 인접 블록들과 병합

8. mm_realloc(void *ptr, size_t size)

기존 블록의 크기를 변경하는 함수입니다.

• size가 0이면 free
• ptr이 NULL이면 malloc
• 기존 블록 크기로 충분하면 그대로 사용
• 다음 블록이 가용 상태라면 병합
• 아니면 새로 malloc해서 데이터 복사 후 free

9. 메모리 관리 관련 개념 정리

9.1 realloc이란?

realloc(ptr, new_size)는 기존 메모리 블록을 다른 크기로 다시 할당하고, 기존 데이터를 복사하는 함수입니다.
메모리 블록을 확장하거나 축소할 때 사용합니다.

9.2 Next Fit vs First Fit vs Best Fit

• First Fit : 처음 발견한 가용 블록에 바로 할당
• Best Fit : 모든 가용 블록을 확인하여 가장 작은 크기의 블록에 할당
• Next Fit : 직전에 할당한 블록 이후부터 탐색 시작 (First Fit의 개선형)

Next Fit은 메모리 전체를 매번 처음부터 검사하지 않아서 평균 성능이 좋지만, 최악의 경우 단편화가 심해질 수 있습니다.

9.3 묵시적 가용 리스트 vs 명시적 가용 리스트

• 묵시적 가용 리스트 : 모든 블록을 차례로 검사해 가용 블록을 찾음
• 명시적 가용 리스트 : 가용 블록끼리만 연결된 별도의 리스트를 유지해 빠르게 탐색

9.4 분리 가용 리스트 (Segregated Free List)

• 가용 블록을 크기별로 여러 리스트에 구분하여 관리
• 작은 블록, 중간 블록, 큰 블록 등으로 나누어 빠르게 탐색
• Best Fit과 비슷한 효과를 빠르게 낼 수 있음

9.5 버디 시스템 (Buddy System)

메모리를 항상 2의 거듭제곱 크기로 분할하는 방법입니다.

• 512B, 256B, 128B, 64B, 32B ... 단위로 메모리를 관리
• 할당/해제 시 Buddy 블록(짝꿍)을 확인해 병합 또는 분할
• 빠른 병합이 가능하지만, 낭비되는 메모리가 늘어날 수 있음 (내부 단편화)

10. 전체 흐름 요약

1. 초기화 단계에서 최소 힙 영역을 만들고 CHUNKSIZE만큼 확장합니다.
2. malloc이 호출되면 요청 사이즈에 맞는 Free 블록을 찾거나 힙을 확장합니다.
3. free가 호출되면 블록을 가용 상태로 만들고 인접 Free 블록과 병합합니다.
4. realloc은 필요한 경우 블록 크기를 늘리거나 줄입니다.
5. next-fit을 사용하므로 last_fit 포인터를 항상 정확하게 관리합니다.