리눅스 내부 구조 03 - 프로세스 스케줄링

스케줄링이 왜 필요한가?

현대 시스템에서는 수백 개의 프로세스가 동시에 실행된다. 하지만 CPU 코어 수는 한정되어 있으며, 하나의 코어는 한 번에 하나의 프로세스만 실행할 수 있다. 스케줄러는 어떤 프로세스가 언제 CPU를 사용할지를 결정하는 커널의 구성 요소이다.

스케줄링이 단순히 순서를 정하는 문제라면 큰 어려움이 없을 것이다. 하지만 현실에서 스케줄러가 해결해야 하는 문제는 복합적이다. 인터랙티브 프로세스는 사용자 입력에 빠르게 반응해야 하고, 배치 작업은 최대 처리량을 원하며, 실시간 프로세스는 정해진 시간 안에 반드시 실행되어야 한다. 이 상충하는 요구사항을 동시에 만족시켜야 하는 것이 스케줄러의 핵심 과제인 것이다.

선점형과 비선점형

스케줄링 방식은 크게 두 가지로 나뉜다. 비선점형(cooperative) 스케줄링에서는 실행 중인 프로세스가 자발적으로 CPU를 양보할 때까지 다른 프로세스가 기다려야 한다. 만약 하나의 프로세스가 CPU를 양보하지 않으면 나머지 프로세스는 무한히 대기하게 되며, 시스템 전체가 멈춘 것처럼 보이는 것이다. 초기 Windows와 Mac OS가 이 방식을 사용했고, 하나의 프로그램이 멈추면 전체 시스템을 재부팅해야 했던 경험이 이 때문이다.

선점형(preemptive) 스케줄링에서는 커널이 실행 중인 프로세스를 강제로 중단하고 다른 프로세스에게 CPU를 넘길 수 있다. 리눅스는 선점형 스케줄링을 사용한다. 각 프로세스에게 타임슬라이스라고 불리는 CPU 사용 시간을 할당하고, 이 시간이 소진되면 커널이 개입하여 다른 프로세스를 실행시키는 것이다. 이 덕분에 하나의 프로세스가 무한 루프에 빠지더라도 다른 프로세스는 정상적으로 실행될 수 있다.

O(1) 스케줄러의 역사

리눅스의 스케줄링은 여러 차례 진화를 거쳤다. 초기 리눅스의 스케줄러는 단순한 구조였으나, 프로세스 수가 증가하면 성능이 저하되는 문제가 있었다. 2003년 리눅스 2.6에서 Ingo Molnar가 O(1) 스케줄러를 도입했다. 이름이 말해주듯 프로세스 수에 관계없이 상수 시간에 다음 실행할 프로세스를 선택할 수 있는 스케줄러였다.

O(1) 스케줄러는 활성 큐와 만료 큐라는 두 개의 우선순위 배열을 사용했다. 각 배열에는 140개의 우선순위 수준이 있었고, 비트맵을 통해 가장 높은 우선순위를 가진 프로세스를 즉시 찾을 수 있었다. 활성 큐의 모든 프로세스가 타임슬라이스를 소진하면 두 큐의 포인터만 교환하는 방식으로 동작했는데, 이 설계는 서버 환경에서 잘 동작했으나 데스크톱 환경에서 인터랙티브 프로세스의 응답성이 떨어지는 문제가 있었다. 인터랙티브 프로세스를 식별하기 위한 휴리스틱이 복잡하고 예측하기 어려웠기 때문이다.

CFS: 완전 공정 스케줄러

2007년 리눅스 2.6.23에서 Con Kolivas의 아이디어에 영향을 받은 Ingo Molnar가 CFS(Completely Fair Scheduler)를 도입했다. CFS의 핵심 철학은 이상적인 멀티태스킹 CPU를 시뮬레이션하는 것이다. 이상적인 CPU라면 n개의 프로세스에게 각각 1/n의 CPU 시간을 동시에 제공할 것이다. 현실에서는 불가능하지만, CFS는 이 이상에 최대한 가깝게 CPU 시간을 분배하려 한다.

CFS의 핵심 개념은 vruntime(virtual runtime)이다. 각 프로세스는 자신이 실제로 CPU를 사용한 시간을 추적하는 vruntime 값을 갖는다. CFS는 항상 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택한다. CPU를 많이 사용한 프로세스는 vruntime이 크므로 후순위로 밀리고, CPU를 적게 사용한 프로세스는 vruntime이 작으므로 우선 실행되는 것이다.

vruntime이 작은 순서대로 정렬 (레드-블랙 트리)

        [vruntime=5]
       /            \
  [vruntime=3]    [vruntime=8]
     /
[vruntime=1]  ← 다음에 실행될 프로세스

이 프로세스들을 효율적으로 관리하기 위해 CFS는 레드-블랙 트리를 사용한다. 레드-블랙 트리는 자가 균형 이진 탐색 트리로, 삽입, 삭제, 최솟값 검색이 모두 O(log n) 시간에 수행된다. 가장 왼쪽 노드가 vruntime이 가장 작은 프로세스이므로, 다음에 실행할 프로세스를 찾는 것은 트리의 최좌측 노드를 선택하는 것과 같은 셈이다.

nice 값과 우선순위

과연 모든 프로세스에게 동일한 CPU 시간을 부여하는 것이 공정한가? 항상 그렇지는 않다. 중요한 서비스 프로세스와 백그라운드 로그 정리 작업이 같은 비율로 CPU를 나눠 갖는 것은 바람직하지 않을 수 있다. nice 값이 이 문제를 해결한다.

nice 값은 -20부터 19까지의 범위를 갖는다. 값이 낮을수록 우선순위가 높고, 값이 높을수록 우선순위가 낮다. 이름의 유래가 흥미로운데, nice 값이 높은 프로세스는 다른 프로세스에게 "nice"하게 양보하는 셈이다.

CFS에서 nice 값은 vruntime의 증가 속도에 영향을 준다. nice 값이 낮은(우선순위 높은) 프로세스는 vruntime이 실제 실행 시간보다 느리게 증가하여 더 많은 CPU 시간을 받게 되고, nice 값이 높은(우선순위 낮은) 프로세스는 vruntime이 빠르게 증가하여 CPU를 적게 받게 되는 것이다. 이 방식의 장점은 우선순위가 낮은 프로세스도 완전히 CPU를 못 받는 상황이 발생하지 않는다는 점이다. 기아(starvation) 현상이 구조적으로 방지되는 것이다.

# 현재 프로세스의 nice 값 확인
nice

# nice 값 10으로 프로세스 실행
nice -n 10 ./background_job

# 실행 중인 프로세스의 nice 값 변경
renice -n -5 -p 1234

실시간 스케줄링

일반적인 프로세스에는 CFS가 적합하지만, 반드시 정해진 시간 안에 실행되어야 하는 프로세스도 존재한다. 오디오 처리, 산업 제어 시스템, 통신 장비 등이 그런 예이다. 이러한 요구사항을 위해 리눅스는 실시간 스케줄링 정책을 제공한다.

SCHED_FIFO는 선입선출 방식의 실시간 스케줄링이다. SCHEDFIFO 프로세스는 일반 프로세스보다 항상 우선 실행되며, 자발적으로 CPU를 양보하거나 더 높은 우선순위의 SCHEDFIFO 프로세스가 나타나기 전까지는 계속 실행된다. 타임슬라이스 개념이 없으므로 실행 시간에 제한이 없는 것이다.

SCHED_RR은 SCHED_FIFO와 동일하지만, 같은 우선순위의 프로세스들 사이에서는 라운드 로빈 방식으로 타임슬라이스를 나눈다. 동일 우선순위 프로세스가 여러 개 있을 때 하나가 CPU를 독점하는 것을 방지하는 것이다.

실시간 프로세스의 우선순위는 1부터 99까지이며, 일반 프로세스(CFS)의 우선순위보다 항상 높다. 이는 실시간 프로세스가 실행 대기 중이면 일반 프로세스는 CPU를 전혀 받지 못한다는 의미이기도 하다. 잘못 설계된 실시간 프로세스가 무한 루프에 빠지면 시스템 전체가 응답 불가 상태에 빠질 수 있으므로, 실시간 스케줄링은 신중하게 사용해야 하는 것이다.

컨텍스트 스위칭의 비용

스케줄러가 실행 중인 프로세스를 교체할 때 컨텍스트 스위칭이 발생한다. 이 과정에서 현재 프로세스의 CPU 레지스터 상태를 저장하고, 다음 프로세스의 레지스터 상태를 복원하며, 메모리 맵(페이지 테이블)을 전환해야 한다.

레지스터 저장과 복원 자체는 빠르지만, 진짜 비용은 간접적인 곳에서 발생한다. 페이지 테이블이 전환되면 TLB(Translation Lookaside Buffer)가 무효화되고, 새 프로세스의 데이터가 CPU 캐시에 없으므로 캐시 미스가 빈번하게 발생한다. 이러한 간접 비용이 직접 비용보다 훨씬 크며, 프로세스가 사용하는 메모리가 클수록 이 비용은 증가하는 것이다.

같은 프로세스 내의 스레드 간 전환은 프로세스 간 전환보다 가벼운데, 스레드는 같은 주소 공간을 공유하므로 페이지 테이블 전환이 필요 없고 TLB를 유지할 수 있기 때문이다. 이것이 멀티스레드 프로그래밍의 성능상 이점 중 하나인 것이다.

CPU 친화성

기본적으로 스케줄러는 프로세스를 어느 CPU 코어에서든 실행할 수 있다. 하지만 프로세스가 특정 코어에서 실행되다가 다른 코어로 이동하면, 이전 코어의 캐시에 있던 데이터를 새 코어에서 다시 로드해야 하므로 성능 저하가 발생한다.

CPU 친화성(affinity)은 프로세스가 실행될 수 있는 CPU 코어를 제한하는 메커니즘이다. 프로세스를 특정 코어에 고정하면 캐시 효율이 높아지고, NUMA 아키텍처에서는 로컬 메모리 접근을 보장할 수 있다.

# 프로세스 1234를 CPU 0, 1에서만 실행되도록 설정
taskset -p -c 0,1 1234

# CPU 2에서만 실행되도록 프로그램 시작
taskset -c 2 ./my_program

리눅스 스케줄러 자체도 이 점을 인식하고 있어, 가능한 한 프로세스를 마지막으로 실행된 코어에서 다시 실행하려는 소프트 친화성을 기본으로 적용한다. taskset으로 설정하는 것은 이보다 강한 하드 친화성으로, 지정된 코어 외에서는 절대 실행되지 않도록 강제하는 것이다.

다음 포스트에서는 메모리 관리를 살펴본다.