임베디드/시스템 프로그래밍에서의 malloc

1. Determinism (결정론적 동작)의 붕괴: WCET 문제

"malloc은 시간 복잡도가 O(1)이 아닙니다. O(Unknown)입니다."

임베디드(특히 RTOS)에서 가장 중요한 건 '빠른 속도'가 아니라 '예측 가능한 속도(Determinism)'입니다.

• 일반적인 상황: malloc은 미리 캐싱해둔 'Free List(Bin)'에서 툭 꺼내줍니다. 10ns 소요.
• 최악의 상황:
  1. Free List가 비어있음.
  2. 인접한 청크들을 병합(Coalescing) 시도 -> 리스트 순회 발생.
  3. 그래도 부족함 -> Syscall (sbrk or mmap) 호출.
  4. 커널 모드로 전환(Context Switch).
  5. 물리 메모리(Page)가 부족해서 Page Fault 발생 -> 디스크 스왑핑까지 갈 수 있음.

결과: 평소에 10ns 걸리던 코드가 갑자기 10ms(100만 배)가 걸립니다.
에어백이 터져야 하는 순간에 malloc이 커널에게 "메모리 좀 더 줘"라고 빌고 있다면? 이것이 WCET(Worst-Case Execution Time) 위반입니다.

---

2. The Hidden Syscall: brk vs mmap과 가상 메모리

malloc은 단순한 라이브러리 함수가 아닙니다. 커널의 메모리 관리자(VMM)와 협상하는 외교관입니다.

Under the Hood (Glibc 기준)

malloc(size)를 요청했을 때 크기에 따라 동작이 완전히 다릅니다. (임계값: 보통 128KB)

1. Small alloc (< 128KB): sbrk() 사용

   • 데이터 세그먼트의 끝(Program Break)을 힙 쪽으로 늘립니다.
   • 문제: 메모리를 free해도 OS에게 바로 반납되지 않습니다. 힙의 꼭대기(Top chunk)가 아닌 중간에 있는 구멍들은 프로세스가 죽을 때까지 해당 프로세스가 움켜쥐고 있습니다.

2. Large alloc (>= 128KB): mmap() 사용

   • 커널에게 "새로운 메모리 페이지를 맵핑해줘"라고 요청합니다.
   • Deep Dive: mmap은 매우 비싼 연산입니다.
     • TLB (Translation Lookaside Buffer) Shootdown: 멀티코어 시스템에서 페이지 테이블이 변경되면, 다른 코어의 TLB 캐시를 강제로 비워야 합니다. 전체 시스템 성능 저하를 유발합니다.
     • Zeroing Overhead: OS는 보안을 위해 새로 할당하는 페이지를 모두 0으로 밉니다(Zero-fill). 여기서 막대한 CPU 사이클이 소모됩니다.

---

3. Re-entrancy (재진입성)와 Priority Inversion (우선순위 역전)

상황 A: 인터럽트 핸들러(ISR)에서의 malloc (자살행위)

malloc은 전역 힙 상태를 관리하기 위해 내부적으로 Lock(Mutex)을 겁니다.

1. Main Loop: malloc 호출 -> Lock 획득 -> 힙 구조 조작 중.
2. Hardware Interrupt 발생! -> Main Loop 중단, ISR 실행.
3. ISR: 급하게 메모리가 필요해서 malloc 호출.
4. Deadlock: malloc은 Lock이 걸려있음을 확인하고 풀릴 때까지 대기(Spin or Sleep). 하지만 Lock을 쥔 Main Loop는 ISR이 끝나야 다시 실행될 수 있음. -> 시스템 영구 정지

상황 B: 우선순위 역전 (Priority Inversion)

RTOS 환경에서 태스크 우선순위가 High > Middle > Low라고 칩시다.

1. Low Task: malloc 호출 -> Lock 획득.
2. High Task: (선점하여 실행됨) 나도 malloc 호출! -> Lock 때문에 대기 상태로 전환.
3. Middle Task: (High가 자니까 실행됨) CPU를 차지하고 신나게 돔.
4. 비극: 가장 중요한 High Task가 아무 상관 없는 Middle Task가 끝날 때까지(Low가 다시 돌아서 Lock을 풀 때까지) 기다려야 합니다.
   • NASA 화성 탐사선 패스파인더(Pathfinder)가 실제로 이 버그 때문에 화성에서 계속 리부팅되었습니다.

---

4. Deep C Mentor's Solution: Custom Allocator & Memory Pool

그래서 전문가들은 malloc을 안 씁니다. 직접 만들어서 사용하는 경향이 강합니다.

예시: O(1) Block Allocator (Memory Pool) 설계

동적 할당을 하되, 모든 부작용(단편화, 속도 저하, Lock 문제)을 없애는 기법입니다.

• 원리: 똑같은 크기의 블록(예: 네트워크 패킷용 256B)을 미리 배열로 잔뜩 잡아놓습니다.
• 자료구조: 단순한 연결 리스트(Free List).

// 전문가의 O(1) 할당자 (개념적 코드)
struct Block {
    struct Block* next;
};

static struct Block* free_list = NULL;

// 할당: 맨 앞의 것 하나 톡 떼어줌 (Lock-free 가능, O(1) 보장)
void* pool_alloc() {
    if (!free_list) return NULL; // Error handling
    struct Block* ptr = free_list;
    free_list = free_list->next; // 포인터 1회 이동
    return (void*)ptr;
}

// 해제: 맨 앞에 다시 끼워넣음 (O(1) 보장)
void pool_free(void* ptr) {
    struct Block* block = (struct Block*)ptr;
    block->next = free_list;
    free_list = block; // 포인터 1회 이동
}

Why Professional?
1. NO Search: 리스트를 뒤지지 않습니다. 무조건 맨 앞을 줍니다.
2. NO Syscall: sbrk, mmap 따위 호출하지 않습니다.
3. NO External Fragmentation: 모든 블록 크기가 같아서 낭비되는 구멍이 없습니다.
4. Cache Friendly: 비슷한 시점에 할당된 객체들이 메모리에 모여 있을 확률이 높습니다.