CPU 스케줄링의 선택 기준과 실패 모드
CPU 스케줄링은 어떤 작업에 CPU를 언제, 얼마나 줄지 정하는 운영체제의 핵심 정책이다. FCFS, SJF, Round Robin, Priority의 원리와 실패 모드가 Linux, Kubernetes, Node.js까지 어떻게 이어지는지 살펴본다.
Script Companion
오디오와 함께 스크립트 보기
- 01
CPU 스케줄링의 출발점은 단순한 불일치다. 현대 컴퓨터에서는 수십 개에서 수백 개의 프로세스가 동시에 실행되기를 원하지만, CPU 코어는 한 번에 하나의 명령만 처리할 수 있다. 이 불일치를 그대로 두면 한 프로세스가 CPU를 오래 붙잡는 동안 다른 프로세스는 기다리고, I/O를 기다리는 작업이 CPU를 점유하면 처리량도 낭비된다. 결국 스케줄링은 사용자 응답 시간, 시스템 처리량, 공정성을 동시에 다루는 정책이다. BackOps 관점에서는 Linux 우선순위 조정, Kubernetes Pod Priority와 Preemption, Node.js Event Loop 지연 대응까지 같은 질문으로 이어진다.
- 02
가장 먼저 볼 축은 선점과 비선점이다. 비선점 방식에서는 프로세스가 스스로 CPU를 반납할 때까지 운영체제가 기다린다. 구현은 단순하고 전환 비용은 낮지만, 앞 작업이 길면 뒤 작업의 응답 시간이 길어진다. 선점 방식에서는 운영체제가 실행 중인 프로세스를 강제로 CPU에서 내릴 수 있어서 응답 시간을 줄일 수 있다. 대신 Context Switching 비용이 생긴다. 전환할 때는 레지스터 값과 프로그램 카운터 같은 상태를 PCB에 저장하고 다음 프로세스 상태를 복원한다. 전환 자체는 수 마이크로초 수준이지만, L1/L2 캐시 콜드 미스 복구까지 포함하면 실제 비용은 10~100μs 범위로 측정된다.
- 03
Context Switching은 단순히 많이 할수록 좋은 장치가 아니다. Linux에서는 프로세스가 I/O 대기나 lock 때문에 스스로 CPU를 반납하는 Voluntary 전환과, Time Quantum을 다 써서 운영체제가 강제로 선점하는 Involuntary 전환을 구분한다. 이 차이는 성능 분석에서 중요하다. 자발적 전환이 많으면 작업이 CPU보다 외부 대기를 자주 만난다는 신호일 수 있고, 비자발적 전환이 많으면 CPU 경쟁이나 시간 할당량 설정을 의심할 수 있다. 선점은 응답성을 만들지만, 너무 잦은 전환은 캐시와 상태 복원 비용으로 처리량을 깎는다.
- 04
FCFS, First Come First Served는 가장 단순한 비선점 스케줄링이다. 먼저 도착한 프로세스가 Ready Queue에 먼저 들어가고, 앞 프로세스가 끝날 때까지 CPU를 양보하지 않는다. 은행 창구처럼 이해하기 쉽지만, 긴 작업이 앞에 있으면 짧은 작업들이 모두 오래 기다리는 Convoy Effect가 생긴다. 이 방식은 구현이 단순하다는 장점이 있지만 평균 대기 시간이 매우 길어질 수 있고, 실시간 시스템이나 대화형 시스템에는 부적합하다. 배치 처리처럼 응답성보다 순서와 단순성이 중요한 맥락에서 주로 설명되는 이유가 여기에 있다.
- 05
SJF, Shortest Job First는 실행 시간이 짧은 프로세스를 먼저 실행해 평균 대기 시간을 이론적으로 가장 짧게 만드는 알고리즘이다. 하지만 핵심 한계는 미래의 CPU 실행 시간을 알 수 없다는 점이다. 실제 구현에서는 과거 실행 시간의 지수 평균, Exponential Moving Average로 다음 실행 시간을 예측한다. 선점 버전인 SRTF, Shortest Remaining Time First는 새 프로세스가 도착했을 때 현재 실행 중인 프로세스보다 남은 시간이 짧으면 CPU를 빼앗는다. 문제는 짧은 작업이 계속 들어오면 긴 작업이 영원히 실행되지 못하는 Starvation이다.
- 06
SJF의 실무적인 실패는 예측값이 정상처럼 보이는데 체감 응답이 느려지는 경우다. α=0.5에서 한 번 들어온 100ms long burst는 약 4~5 사이클 동안 예측값에 영향을 남긴다. 그동안 새로 들어오는 3ms 짧은 burst도 여전히 20ms 이상으로 추정되어 SJF 큐 뒤로 밀릴 수 있다. 측정 지표상 예측은 동작하지만 사용자는 느리게 느낀다. 감지는 스케줄링 횟수 대비 wait 누적 시간이 평균보다 2배 이상인지 보는 방식으로 접근한다. 대응은 α를 0.8~0.9로 올려 최근 burst에 가중치를 주는 것이지만, 잡음에 더 민감해지는 trade-off가 생긴다. Kafka consumer lag 예측과 AWS Auto Scaling의 평균 CPU 기반 scale-out도 같은 EMA 휴리스틱 함정에 빠질 수 있다.
- 07
Round Robin은 각 프로세스에게 Time Quantum, 즉 시간 할당량 q만큼 CPU를 주고, 시간이 끝나면 Ready Queue의 맨 뒤로 보내는 선점 방식이다. 회의 발언권을 돌아가며 주는 구조에 가깝다. n개의 프로세스가 있을 때 각 프로세스는 최대 (n-1) × q 이하의 시간을 기다린다는 점에서 시분할 시스템의 기본 알고리즘이 된다. 하지만 Time Quantum 선택이 핵심이다. 너무 작으면 Context Switching이 잦아져 오버헤드가 커지고, 너무 크면 FCFS처럼 긴 작업 뒤에서 짧은 작업이 기다리는 문제가 다시 커진다. Round Robin은 공평함을 만들지만, 시간 조각의 크기가 응답성과 처리량 사이의 균형을 결정한다.
- 08
Priority Scheduling은 각 프로세스에 우선순위 번호를 주고 높은 우선순위부터 CPU를 할당하는 방식이다. 보통 낮은 숫자가 높은 우선순위를 의미하며, 선점형과 비선점형 모두로 구현할 수 있다. 핵심 실패 모드는 Starvation이다. 높은 우선순위 프로세스가 계속 들어오면 낮은 우선순위 프로세스는 실행되지 못한다. Aging은 오래 기다린 프로세스의 우선순위를 점진적으로 높여 이 문제를 완화한다. 예시는 15분마다 우선순위 +1이지만, 이 900초 간격은 임의값이 아니라 SLA에서 역산해야 한다. 큐 wait 시간의 max값이 SLA의 100배를 넘으면 aging_interval 단축이나 max_priority_gap 축소를 검토해야 한다. K8s PriorityClass도 시간 차원이 없으면 낮은 priority Pod가 무한 Pending에 빠질 수 있다.
- 09
Multilevel Queue는 Ready Queue를 시스템 프로세스, 인터랙티브, 배치처럼 여러 개로 나누고 각 Queue마다 다른 스케줄링 알고리즘을 적용한다. Queue 간 우선순위는 고정되어 있다. 확장 버전인 Multilevel Feedback Queue는 프로세스가 Queue 사이를 이동할 수 있게 한다. CPU를 많이 쓰면 낮은 Queue로 내려가고, I/O를 많이 쓰면 높은 Queue로 올라간다. 이 구조가 필요한 이유는 실제 시스템에 성격이 다른 작업이 공존하기 때문이다. 텍스트 편집기처럼 인터랙티브하고 I/O 위주의 작업은 짧은 응답 시간이 중요하고, 비디오 인코딩처럼 CPU 집약적인 작업은 처리량이 중요하다. 하나의 알고리즘만으로 두 요구를 동시에 만족시키기 어렵기 때문에, CFS와 EEVDF도 이 원리를 더 수학적으로 일반화한 형태로 이해할 수 있다.
- 10
Linux CFS, Completely Fair Scheduler의 핵심은 vruntime이다. CFS는 모든 프로세스가 CPU를 공평하게 나눠 쓰는 이상적인 멀티태스킹 CPU를 가상으로 모델링하고, 각 프로세스가 그 이상적 CPU에서 실행한 시간을 vruntime으로 추적한다. 실행 가능한 프로세스는 vruntime을 키로 하는 Red-Black Tree에 저장되고, 가장 왼쪽 노드, 즉 vruntime이 가장 작은 프로세스가 다음 실행 대상이 된다. Red-Black Tree를 쓰는 이유는 삽입, 삭제, 최솟값 조회를 모두 O(log n)에 처리하면서 최악의 경우에도 균형을 보장하기 때문이다. 수천 개의 프로세스가 동시에 실행 가능한 서버 환경에서는 단순 큐나 정렬 배열보다 이 특성이 중요하다.
- 11
EEVDF, Earliest Eligible Virtual Deadline First는 Linux 6.6부터 도입되었고 Linux 6.12에서 CFS 코드가 완전히 제거되며 유일한 공정 스케줄러가 되었다. EEVDF도 vruntime 기반이지만, 각 태스크에 가상 데드라인을 추가로 계산한다. lag, 즉 이상적 vruntime에서 실제 vruntime을 뺀 값이 0 이상인 eligible 태스크 중 가상 데드라인이 가장 빠른 태스크를 선택한다. 직관적으로 가중치가 클수록, 다시 말해 nice 값이 낮을수록 데드라인이 더 가깝게 잡혀 더 자주 선택된다. CFS가 vruntime 한 변수에 기대었다면, EEVDF는 태스크가 얼마나 짧은 슬라이스를 원하는지도 표현해 레이턴시 민감 워크로드와 처리량 민감 배치를 같은 트리 안에서 다르게 다룬다.
- 12
Kubernetes와 ECS에서도 CPU 스케줄링의 언어가 반복된다. Kubernetes 스케줄러는 프로세스를 Pod로, CPU를 Node의 CPU와 Memory로, Ready Queue를 Pending Pod Queue로 확장해 본 구조다. PriorityClass는 우선순위이고, Pod Preemption은 높은 우선순위 Pod를 위해 낮은 우선순위 Pod를 퇴출하는 선점이다. 모든 노드의 리소스가 부족할 때 critical-workload Pod가 요청되면, 스케줄러는 낮은 우선순위 Pod를 Evict하고 기본 30초 Graceful Termination 뒤 리소스를 회수한다. AWS ECS의 binpack은 CPU와 메모리를 빽빽하게 채우는 처리량 최적화에 가깝고, spread는 인스턴스나 AZ에 균등 분산하는 공정성에 가깝다. random은 FCFS와 유사한 단순 배치로 이해할 수 있다.
- 13
Node.js와 NestJS에서는 이벤트 루프가 스케줄러처럼 보인다. 이벤트 루프가 어떤 콜백을 언제 실행할지 결정하는 일은 운영체제가 어떤 프로세스에 CPU를 줄지 결정하는 일과 같은 원리로 연결된다. Node.js는 단일 스레드이지만 내부적으로 우선순위 기반 스케줄링을 사용하고, 이벤트 루프의 각 페이즈는 Round Robin처럼 순환하며 microtask는 macrotask보다 높은 우선순위를 갖는다. NestJS의 Interceptor나 Service에서 대용량 JSON 변환, 복잡한 정규식, 동기 파일 읽기 같은 CPU 집약 작업을 실행하면 그 시간 동안 다른 모든 요청의 콜백이 대기한다. 이것은 긴 Job 하나가 CPU를 독점해 Convoy Effect를 만드는 상황과 같다. 문서의 예시처럼 동기 처리로 p99가 2000ms까지 치솟던 응답이 setImmediate 배치 처리 후 p99 50ms 이하로 회복될 수 있다.
- 14
Node.js에서 CPU 집약 작업을 만났을 때 선택 기준은 작업의 길이와 지속성이다. 이벤트 루프 차단이 50ms 미만이고 마이크로 배치로 나눌 수 있으면 setImmediate로 양보해 점유 시간을 쪼개는 편이 맞다. CPU 집약 작업이 100ms를 넘고 단일 서버 안에서 처리한다면 Worker Thread가 적합하다. 별도 V8 인스턴스에서 CPU 병렬 실행을 하므로 이벤트 루프를 분리할 수 있다. 서버 재시작 후 복구가 필요하거나, 우선순위 큐잉과 Dead Letter Queue가 필요하거나, 멀티 서버 분산 처리가 필요하면 외부 큐가 필요하다. BullMQ나 RabbitMQ 같은 외부 큐는 Redis에 작업을 영속화하고 재시도 정책과 failed job 처리를 제공한다.
- 15
트러블슈팅에서 중요한 것은 증상과 원인을 스케줄링 언어로 번역하는 것이다. CPU 사용률 100%에서 배치 작업과 API 서버가 같은 nice=0으로 경쟁하면 CFS가 공평하게 나누려 해도 배치 작업의 CPU 버스트가 길어 API 응답이 늦어진다. K8s에서 critical-api-v2 Pod가 계속 Pending이면 priorityClassName이 없거나 배치 워커와 우선순위가 같아 선점이 일어나지 않을 수 있다. Node.js 서버에서 Event Loop Lag이 급증하면 대용량 JSON.parse, 복잡한 정규식, 동기 파일 읽기 같은 동기 코드가 이벤트 루프를 막고 있는지 봐야 한다. PostgreSQL에서는 autovacuum이 OLTP 백엔드와 같은 nice 값으로 fork되어 CPU 동률 경합을 만들 수 있다. 다만 nice를 +19처럼 너무 올리면 autovacuum이 거의 진행되지 않아 table bloat로 이어질 수 있고, pg_stat_user_tables.n_dead_tup 비율이 10%를 넘으면 nice를 다시 내려야 한다.
- 16
정리하면 CPU 스케줄링은 누구에게, 얼마나, 언제 CPU를 줄 것인가를 정하는 정책이다. FCFS는 단순하지만 Convoy Effect에 약하고, SJF는 평균 대기 시간은 좋지만 예측 실패와 Starvation을 조심해야 한다. Round Robin은 시간 할당량으로 공평함을 만들고, Priority Scheduling은 중요한 작업을 앞세우지만 Aging 같은 보정 없이는 낮은 우선순위 작업이 밀릴 수 있다. 이 원리는 Linux의 CFS와 EEVDF, Kubernetes Pod Preemption, ECS 배치 전략, Node.js Event Loop까지 이어진다. 이름과 계층은 달라도 핵심 질문은 CPU나 그에 해당하는 자원을 어떤 기준으로 나누고, 그 기준이 실패할 때 어떤 지표로 알아차릴 것인가에 있다.
같은 레이어