리눅스가 프로세스 관리를 위해 침습형 연결 리스트를 사용하는 이유

Intrusive Linked Lists

이 글은 침습형 연결 리스트(intrusive linked list)의 개념과 리눅스 커널에서의 활용을 설명한다. 일반적인 연결 리스트와 달리, 침습형 연결 리스트는 링크 포인터를 데이터 구조 내부에 직접 포함시켜 메모리 할당 횟수를 줄이고 캐시 효율을 높인다. 리눅스는 프로세스(task)를 관리하기 위해 순환 이중 연결 리스트를 사용하며, `list_head` 구조체와 `container_of` 매크로를 통해 각 프로세스를 효율적으로 추적한다. 또한, 리눅스에서 연결 리스트 연산 중 순회가 차지하는 비중이 낮다는 점을 강조하며, 이 구조가 왜 적합한지 설명한다.