스케줄링의 개념과 기준

CPU는 하나(혹은 제한된 수)인데, 실행을 원하는 프로세스는 수십~수백 개입니다.

누가 먼저 CPU를 쓸 것인가?

얼마나 오래 쓸 것인가?

이 결정을 내리는 것이 CPU 스케줄러입니다.

스케줄러의 선택에 따라 시스템의 응답 속도, 처리량, 공정성이 완전히 달라집니다.

같은 하드웨어에서도 스케줄링 정책 하나로 느린 서버가 빠른 서버가 될 수 있습니다.

스케줄링은 제한된 CPU 시간을 준비 상태의 작업들 사이에 배분하는 문제입니다.

긴 작업을 계속 실행하면 짧은 작업의 응답 시간이 길어지고, 지나치게 자주 전환하면 문맥 교환 비용이 커집니다.

따라서 정책은 대기 시간, 응답 시간, 처리량, 공정성 사이의 균형을 정합니다.

CPU 스케줄러와 디스패처

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

스케줄러(Scheduler)는 Ready Queue에 있는 프로세스들 중에서 다음에 실행할 프로세스를 선택합니다.

이것은 "누구에게 CPU를 줄 것인가"라는 정책(Policy) 결정입니다.

디스패처(Dispatcher)는 스케줄러가 선택한 프로세스에게 실제로 CPU를 넘기는 메커니즘(Mechanism)을 수행합니다.

구체적인 작업은 다음과 같습니다.

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

이 전체 과정에 걸리는 시간이 디스패치 지연(Dispatch Latency)입니다.

디스패치 비용은 하드웨어, 주소 공간 전환, 캐시·TLB 상태와 커널 구현에 따라 달라집니다. 주소 공간이 바뀌어도 TLB를 항상 전부 비우는 것은 아니며, 일정한 시간이나 배수로 일반화할 수 없습니다.

스케줄링이 발생하는 시점

다음 상태 변화는 실행 대상을 다시 고르는 계기가 됩니다. I/O 요청도 실제로 블로킹되는 경우를 가정합니다.

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

상황 1과 4에서는 현재 작업이 실행을 계속할 수 없으므로 준비된 다른 작업을 고릅니다. 준비 작업이 없다면 CPU는 유휴 상태로 갑니다.

상황 3의 깨우기는 비선점형에서도 일어납니다. 깨어난 작업을 Ready Queue에 넣는 것과 현재 작업을 선점하는 것은 별개의 결정입니다. 상황 2는 선점뿐 아니라 명시적 양보로도 발생할 수 있습니다.

선점형 vs 비선점형

비선점형(Non-preemptive) 스케줄링: 프로세스가 자발적으로 CPU를 양보할 때까지 실행됩니다.

기본 모델에서는 블로킹 I/O, 동기화 대기, 종료, 명시적 양보(yield)처럼 현재 작업이 실행을 멈출 때 다음 작업을 고릅니다.

비선점형은 실행 전환 지점을 줄이지만 동기화를 대신하지는 않습니다. 다른 CPU, 인터럽트 처리기, 또는 양보 지점을 사이에 둔 공유 상태 접근은 여전히 보호해야 합니다.

단점은 하나의 프로세스가 CPU를 독점할 수 있다는 것입니다.

CPU 바운드 프로세스 하나가 10분 동안 돌면, 나머지 프로세스들은 10분을 기다려야 합니다.

선점형(Preemptive) 스케줄링: 타이머나 더 높은 우선순위 작업의 준비 같은 계기로, 현재 작업이 자발적으로 양보하기 전에도 CPU를 회수할 수 있습니다. 실제 전환 시점은 선점 금지 구간과 스케줄링 정책의 영향을 받습니다.

현대의 모든 범용 OS(Linux, Windows, macOS)가 선점형을 사용합니다.

시간 분할은 긴 작업 때문에 다른 작업의 첫 실행이 늦어지는 문제를 완화합니다. 선점 기능만으로 모든 작업의 응답 상한이나 기아 방지가 보장되는 것은 아닙니다.

선점형 스케줄링은 강력하지만, 대가가 있습니다.

공유 데이터를 수정하는 도중에 선점될 수 있으므로, 데이터 불일치가 발생할 수 있습니다.

이것이 6장의 동기화 문제입니다.

커널 코드 자체도 선점에 의한 데이터 손상을 방지해야 합니다.

Linux의 preempt_disable()/preempt_enable()은 현재 CPU의 커널 선점을 제어합니다. 이것만으로 다른 CPU의 공유 데이터 접근이나 인터럽트까지 막지는 못합니다.

정책	실행 전환과 한계
비선점형	현재 작업이 양보·대기·종료할 때 전환합니다. 긴 CPU 작업이 뒤의 작업을 지연시킬 수 있습니다.
선점형	현재 작업의 양보 전에도 회수할 수 있습니다. 공정성·응답 상한은 별도의 정책과 부하 조건에 달려 있습니다.

스케줄링 평가 기준

서로 다른 상황에서 좋은 스케줄링의 정의가 다릅니다.

스케줄링 알고리즘을 비교하기 위한 다섯 가지 핵심 기준을 살펴보겠습니다.

CPU 이용률(CPU Utilization): CPU가 유휴(idle) 상태 없이 일하는 비율입니다.

유휴 시간을 줄이는 데 유용하지만 이용률만 높다고 응답 시간이나 처리량이 좋은 것은 아닙니다. 부하와 지연 목표에 맞춰 해석합니다.

top 명령어에서 %Cpu(s) 행의 id(idle)가 낮을수록 CPU 이용률이 높은 것입니다.

처리량(Throughput): 단위 시간당 완료되는 프로세스 수입니다.

배치 시스템에서 가장 중요한 기준입니다.

"1시간에 100개 작업 완료"처럼 측정합니다.

반환 시간(Turnaround Time): 프로세스가 제출된 시점부터 완료될 때까지의 총 시간입니다.

대기 시간 + 실행 시간 + I/O 시간의 합입니다.

배치 작업의 응답을 기다리는 사용자에게 중요합니다.

대기 시간(Waiting Time): 프로세스가 Ready Queue에서 기다린 총 시간입니다.

기본 계산 문제에서는 CPU 버스트와 I/O 시간을 고정하고 준비 큐 대기를 비교합니다. 실제 시스템에서는 코어 배치와 캐시 상태 등이 실행 비용에도 영향을 줍니다.

응답 시간(Response Time): 요청이 제출된 후 첫 번째 응답이 나올 때까지의 시간입니다.

대화형 시스템에서 가장 중요합니다.

다음 절의 CPU 알고리즘에서는 도착부터 첫 CPU 실행까지로 계산합니다. 웹의 TTFB는 네트워크·서버 처리도 포함하므로 같은 측정값은 아닙니다.

반환 시간은 작업 전체 완료까지이고, 응답 시간은 첫 반응까지입니다.

기준 간의 트레이드오프

기준들은 서로 상충할 수 있습니다.

응답 시간을 줄이려면 타임 퀀텀을 짧게 해서 프로세스를 자주 전환해야 하는데, 그러면 컨텍스트 스위칭 오버헤드가 커져 처리량이 감소합니다.

처리량을 높이려면 컨텍스트 스위칭을 줄여야 하는데, 그러면 개별 프로세스의 응답 시간이 길어집니다.

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

환경	우선 살펴볼 목표의 예
데스크톱	입력에 대한 응답과 지연 변동
서버	요청 처리량과 응답 시간 목표를 함께 확인
배치	전체 처리량과 작업별 반환 시간
실시간	정해진 데드라인의 충족 가능성

CPU 버스트와 I/O 버스트

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

CPU 바운드 프로세스: CPU 버스트가 길고 I/O 버스트가 짧습니다.

과학 계산, 이미지 렌더링이 예입니다.

CPU를 오래 사용하고, 가끔 I/O를 합니다.

I/O 바운드 프로세스: CPU 버스트가 짧고 I/O 버스트가 깁니다.

텍스트 에디터, 웹 서버가 예입니다.

잠깐 CPU를 쓰고, 대부분 I/O를 기다립니다.

짧은 CPU 버스트가 많은 부하도 있지만, 그 분포와 길이는 프로그램·입력·하드웨어에 따라 달라집니다.

스케줄러는 이 특성을 활용합니다.

I/O를 기다리던 작업을 빨리 실행하면 다음 I/O를 일찍 시작하여 CPU 계산과 장치 작업을 겹칠 기회가 생깁니다.

반대로 CPU를 오래 쓰는 작업이 계속 앞서면 I/O 작업의 실행이 늦어지고 장치가 유휴 상태로 남을 수 있습니다.

이것이 현대 스케줄러가 대화형(I/O 바운드) 프로세스를 우대하는 이유입니다.

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