안동민 개발노트

CPU는 하나(혹은 제한된 수)인데, 실행을 원하는 프로세스는 수십~수백 개입니다. 누가 먼저 CPU를 쓸 것인가? 얼마나 오래 쓸 것인가? 이 결정을 내리는 것이 CPU 스케줄러입니다. 스케줄러의 선택에 따라 시스템의 응답 속도, 처리량, 공정성이 완전히 달라집니다. 같은 하드웨어에서도 스케줄링 정책 하나로 느린 서버가 빠른 서버가 될 수 있습니다.

왜 스케줄링이 필요한지를 직관적으로 이해해 봅시다. 은행 창구에 고객 10명이 대기하고 있습니다. 한 명이 30분짜리 복잡한 업무를 처리하는 동안, 1분이면 끝나는 간단한 업무의 고객 9명이 기다려야 합니다. 어떤 순서로 처리하느냐에 따라 고객들의 총 대기 시간이 크게 달라집니다. CPU 스케줄링은 정확히 이 문제입니다.

CPU 스케줄러와 디스패처

CPU 스케줄링 과정은 두 단계로 나뉩니다.

스케줄러(Scheduler)는 Ready Queue에 있는 프로세스들 중에서 다음에 실행할 프로세스를 선택합니다. 이것은 "누구에게 CPU를 줄 것인가"라는 정책(Policy) 결정입니다.

디스패처(Dispatcher)는 스케줄러가 선택한 프로세스에게 실제로 CPU를 넘기는 메커니즘(Mechanism)을 수행합니다. 구체적인 작업은 다음과 같습니다.

현재 실행 중인 프로세스의 컨텍스트 저장 (레지스터, PC, 스택 포인터)
새 프로세스의 컨텍스트 복원
커널 모드에서 사용자 모드로 전환
새 프로세스의 PC 위치로 점프

이 전체 과정에 걸리는 시간이 디스패치 지연(Dispatch Latency)입니다. 최신 하드웨어에서 보통 수 마이크로초(μs) 수준이지만, 타임 퀀텀이 수 밀리초인 것을 감안하면 무시할 수 없는 비용입니다. TLB 플러시가 필요한 프로세스 간 전환은 스레드 간 전환보다 2~5배 더 느립니다.

스케줄링이 발생하는 시점

CPU 스케줄링은 다음 네 가지 상황에서 발생합니다.

프로세스가 Running → Waiting으로 전환할 때 (I/O 요청, wait() 호출)
프로세스가 Running → Ready로 전환할 때 (타이머 인터럽트에 의한 선점)
프로세스가 Waiting → Ready로 전환할 때 (I/O 완료)
프로세스가 종료될 때

상황 1과 4에서는 선택의 여지가 없습니다. CPU를 쓰던 프로세스가 자발적으로 CPU를 놓으므로, 반드시 다른 프로세스를 선택해야 합니다. 이것은 비선점형에서도 발생합니다.

상황 2와 3에서의 스케줄링은 선점형에서만 발생합니다. 현재 실행 중인 프로세스를 강제로 중단하고 다른 프로세스를 실행하는 것이기 때문입니다.

선점형 vs 비선점형

비선점형(Non-preemptive) 스케줄링: 프로세스가 자발적으로 CPU를 양보할 때까지 실행됩니다. CPU를 놓는 경우는 I/O 요청, 종료, 명시적 양보(yield)뿐입니다. MS-DOS, Windows 3.1이 이 방식이었습니다.

비선점형의 장점은 구현이 단순하고 동기화 문제가 적다는 것입니다. 공유 데이터를 수정하는 도중에 선점당하지 않으므로, 임계 영역 보호가 덜 필요합니다. 단점은 하나의 프로세스가 CPU를 독점할 수 있다는 것입니다. CPU 바운드 프로세스 하나가 10분 동안 돌면, 나머지 프로세스들은 10분을 기다려야 합니다.

선점형(Preemptive) 스케줄링: OS가 타이머 인터럽트를 통해 언제든 CPU를 빼앗을 수 있습니다. 현대의 모든 범용 OS(Linux, Windows, macOS)가 선점형을 사용합니다. 특정 프로세스가 CPU를 독점하는 것을 방지하고, 대화형 프로세스의 응답성을 보장합니다.

선점형 스케줄링은 강력하지만, 대가가 있습니다. 공유 데이터를 수정하는 도중에 선점될 수 있으므로, 데이터 불일치가 발생할 수 있습니다. 이것이 6장의 동기화 문제입니다. 커널 코드 자체도 선점에 의한 데이터 손상을 방지해야 합니다. Linux는 preempt_disable()/preempt_enable()로 커널 내 임계 영역에서 선점을 일시적으로 비활성화합니다.

특성	비선점형	선점형
CPU 양보 시점	프로세스가 자발적으로	OS가 강제로
독점 방지	불가능	타이머 인터럽트로 보장
구현 복잡도	단순	동기화 필요
주 사용처	초기 OS, 임베디드	현대 모든 범용 OS
응답성	보장 불가	타임 퀀텀으로 보장

스케줄링 평가 기준

서로 다른 상황에서 좋은 스케줄링의 정의가 다릅니다. 스케줄링 알고리즘을 비교하기 위한 다섯 가지 핵심 기준을 살펴보겠습니다.

CPU 이용률(CPU Utilization): CPU가 유휴(idle) 상태 없이 일하는 비율입니다. 높을수록 좋습니다. 실제 시스템에서 경부하 시 40%, 중부하 시 90% 이상을 목표로 합니다. top 명령어에서 %Cpu(s) 행의 id(idle)가 낮을수록 CPU 이용률이 높은 것입니다.

처리량(Throughput): 단위 시간당 완료되는 프로세스 수입니다. 배치 시스템에서 가장 중요한 기준입니다. "1시간에 100개 작업 완료"처럼 측정합니다.

반환 시간(Turnaround Time): 프로세스가 제출된 시점부터 완료될 때까지의 총 시간입니다. 대기 시간 + 실행 시간 + I/O 시간의 합입니다. 배치 작업의 응답을 기다리는 사용자에게 중요합니다.

대기 시간(Waiting Time): 프로세스가 Ready Queue에서 기다린 총 시간입니다. 스케줄링 알고리즘이 직접 영향을 미칠 수 있는 유일한 시간입니다. 실행 시간과 I/O 시간은 프로세스 자체의 특성이므로 스케줄러가 바꿀 수 없습니다.

응답 시간(Response Time): 요청이 제출된 후 첫 번째 응답이 나올 때까지의 시간입니다. 대화형 시스템에서 가장 중요합니다. 웹 서버에서 TTFB(Time To First Byte)와 같은 개념입니다. 반환 시간은 작업 전체 완료까지이고, 응답 시간은 첫 반응까지입니다.

기준 간의 트레이드오프

모든 기준을 동시에 최적화하는 것은 불가능합니다. 응답 시간을 줄이려면 타임 퀀텀을 짧게 해서 프로세스를 자주 전환해야 하는데, 그러면 컨텍스트 스위칭 오버헤드가 커져 처리량이 감소합니다. 처리량을 높이려면 컨텍스트 스위칭을 줄여야 하는데, 그러면 개별 프로세스의 응답 시간이 길어집니다.

따라서 시스템의 목적에 따라 최적화 기준이 달라집니다.

시스템	최우선 기준	이유
데스크톱	응답 시간	사용자 입력에 즉시 반응해야 함
서버	처리량, CPU 이용률	단위 시간당 최대 요청 처리
배치 시스템	반환 시간	작업이 빨리 끝나는 것이 중요
실시간 시스템	데드라인 충족	정해진 시간 안에 반드시 완료

CPU 버스트와 I/O 버스트

프로세스의 실행은 CPU 버스트(CPU를 사용하는 구간)와 I/O 버스트(I/O를 기다리는 구간)가 번갈아 나타납니다.

CPU 바운드 프로세스: CPU 버스트가 길고 I/O 버스트가 짧습니다. 과학 계산, 이미지 렌더링이 예입니다. CPU를 오래 사용하고, 가끔 I/O를 합니다.

I/O 바운드 프로세스: CPU 버스트가 짧고 I/O 버스트가 깁니다. 텍스트 에디터, 웹 서버가 예입니다. 잠깐 CPU를 쓰고, 대부분 I/O를 기다립니다.

대부분의 프로세스는 I/O 바운드입니다. 실험에 따르면 CPU 버스트 시간의 분포는 지수 분포에 가까워, 대부분의 버스트가 짧고(8ms 이하) 아주 긴 버스트는 드뭅니다.

스케줄러는 이 특성을 활용합니다. I/O 바운드 프로세스에게 높은 우선순위를 주면 빠르게 CPU를 쓰고 I/O로 돌아가므로, CPU와 I/O 장치 모두 바쁘게 일합니다. CPU 바운드 프로세스에게 높은 우선순위를 주면, I/O 바운드 프로세스가 굶주려서 I/O 장치가 놀게 됩니다. 이것이 현대 스케줄러가 대화형(I/O 바운드) 프로세스를 우대하는 이유입니다.

다음 절에서는 구체적인 스케줄링 알고리즘들을 비교해 보겠습니다.

스케줄링의 개념과 기준