연결 리스트와 메모리 풀

연결 리스트는 각 노드가 다음 노드의 주소를 들고 있는 구조입니다. 중간에 넣고 빼기가 쉬워서 타이머 목록, 대기 중인 작업 목록에 씁니다.

malloc을 피하는 이유

• 할당과 해제를 반복하면 빈 공간이 조각나서, 전체 여유는 충분한데 큰 덩어리를 못 얻는 단편화가 생깁니다.
• 할당에 걸리는 시간이 일정하지 않습니다.
• 실패했을 때 할 수 있는 일이 거의 없습니다.

그래서 많은 임베디드 코딩 규칙이 초기화 이후의 동적 할당을 금지합니다.

메모리 풀

같은 크기의 블록을 미리 배열로 잡아 두고, 빈 블록을 연결 리스트(free list)로 엮어 둡니다.

typedef struct node { struct node *next; uint8_t data[32]; } node_t;
static node_t pool[16];
static node_t *free_list;

void pool_init(void) {
    for (int i = 0; i < 15; i++) pool[i].next = &pool[i + 1];
    pool[15].next = NULL; free_list = pool;
}
node_t *pool_alloc(void) { node_t *n = free_list; if (n) free_list = n->next; return n; }
void pool_free(node_t *n) { n->next = free_list; free_list = n; }

할당과 해제가 항상 O(1)이고 단편화가 없습니다. 블록 수를 다 썼을 때의 처리만 정해 두면 됩니다.