커널 데이터 구조
운영체제 커널은 수많은 동적 정보를 효율적으로 관리하기 위해 다양한 데이터 구조를 사용합니다. 이들 데이터 구조는 프로세스 관리, 메모리 관리, 파일 시스템, 입출력 장치 관리, 네트워크 스택 등 거의 모든 커널 서브시스템의 기반이 됩니다.
프로세스 관리용 데이터 구조
프로세스 제어 블록(Process Control Block, PCB)
프로세스의 상태(실행, 대기, 중단, 종료), 레지스터 복원 정보, 스케줄링 우선순위, 부모·자식 프로세스 포인터를 저장
링크드 리스트나 레드-블랙 트리로 관리하여 빠른 탐색·삽입·삭제 지원
태스크 구조체(task_struct, Linux)
PCB를 확장한 형태로 스레드 그룹, 자식 리스트, 파일 디스크립터 테이블 포인터, 메모리 맵(mm_struct) 등 포함
해시 테이블: PID → task_struct 매핑
메모리 관리용 데이터 구조
페이지 프레임 매니저
물리 메모리 프레임을 비트맵(bit map) 또는 연결 리스트로 추적
Buddy Allocator: 2^k 크기의 블록으로 분할·병합하여 외부 단편화 감소
페이지 테이블(Page Table)
각 프로세스별 가상 주소 ↔ 물리 주소 매핑
다단계 페이지 테이블(multi-level), 해시 기반 해시 페이지 테이블(hashed page table), 역 페이지 테이블(inverted page table)
TLB(Translation Lookaside Buffer)
자주 참조되는 페이지 매핑을 캐시에 보관
커널은 TLB 리필(fault) 및 TLB 플러시를 관리
파일 시스템용 데이터 구조
인노드(Inode)
파일 메타데이터(소유권, 권한, 크기, 블록 포인터)를 저장
디렉터리는 파일명 → inode 번호 매핑을 다이렉트 인덱스 또는 B-트리로 구현
버퍼 캐시(Buffer Cache)
디스크 블록을 메모리의 캐시에 저장하여 I/O 성능 향상
읽기 리스트와 쓰기 리스트 두 개의 연결 리스트로 관리, LRU 교체 정책 사용
저널링(Journaling) 데이터 구조
파일 시스템 변경 전 로그 영역에 메타데이터 기록
저널 로그를 순차적 쓰기 구조로 관리해 장애 복구 시 일관성 보장
입출력 장치 관리용 데이터 구조
장치 드라이버 큐(Device Queue)
I/O 요청을 순서대로 보관하는 FIFO 큐
요청 우선순위나 스케줄링 정책에 따라 우선순위 큐 또는 다단계 큐 사용
DMA Descriptor Ring
DMA 전송 단위를 순환 버퍼(원형 버퍼)로 관리
하드웨어-소프트웨어 간의 동기화 포인트
네트워크 스택용 데이터 구조
소켓(Sock) 구조체
네트워크 연결 상태, 프로토콜, 버퍼 포인터를 저장
해시 테이블로 포트 번호 → 소켓 매핑
패킷 버퍼(skbuff, Linux)
수신/송신 패킷 데이터 구조, 참조 카운트(refcount)로 메모리 공유
버디 할당자나 **슬랩 할당자(slab allocator)**로 효율적 메모리 할당
동기화 및 락(lock) 구조
뮤텍스(Mutex)
상호배제를 위한 이진 세마포어와 유사하나, 소유자 정보를 보유
스핀 락(Spinlock)
짧은 임계 구역에서 사용, 대기 중 CPU를 계속 점유
읽기-쓰기 락(Read-Write Lock)
다수의 읽기 락 허용, 쓰기 락은 배타적
타이머 및 이벤트 관리
타이머 휠(Timer Wheel)
지연 작업(Delayed Work) 예약을 위한 원형 큐
다계층 타이머 휠로 다양한 지연 시간 지원
워크 큐(Workqueue)
커널 스레드 풀을 사용해 비동기 작업 처리
우선순위 큐 구조로 관리 가능
Last updated