스케줄링의 개념과 기준

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

누가 먼저 CPU를 쓸 것인가?

얼마나 오래 쓸 것인가?

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

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

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

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

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

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

---

CPU 스케줄러와 디스패처

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

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

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

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

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

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

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

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

---

스케줄링이 발생하는 시점

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

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

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

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

I/O 완료는 준비로 돌아가는 전이

실행 중인 작업이 I/O를 기다린다. 정책에 따라 선택된 뒤 실제 실행한다. 각 단계의 값과 전환 이유를 비교합니다.

CPU SCHEDULING · STATE TRANSITIONS

I/O 완료는 ‘준비’로 돌아가는 전이

깨어난 작업은 준비 큐에 합류합니다. 실제로 CPU를 받는 시점은 스케줄링 정책이 정합니다.

• 준비 → 실행

  스케줄러가 선택한 작업을 디스패처가 실행합니다.

• 실행 → 대기

  블로킹 I/O나 이벤트 대기로 CPU 실행을 멈춥니다.

• 대기 → 준비 · I/O 완료

  준비 큐로 돌아옵니다. 즉시 실행되거나 현재 작업을 반드시 선점하는 것은 아닙니다.

• 실행 → 준비

  타이머 등에 의한 선점 또는 명시적 양보로 준비 큐로 돌아옵니다.

• 실행 → 종료

  작업이 끝납니다. 다른 준비 작업이 없다면 CPU는 유휴 상태로 갑니다.

깨우기와 선점은 별개입니다. 비선점형에서도 대기 → 준비 전이는 일어납니다.

스케줄러 · 정책

준비 큐에서 다음 실행 대상을 고릅니다.

디스패처 · 메커니즘

문맥을 저장·복원해 선택된 작업에 CPU를 넘깁니다.

이 예의 조건

• 본문과 전체 도표의 예를 따라 블로킹부터 디스패치까지 진행합니다.

관계도의 보충 설명

전체 도표의 표기·관계·조건

구분	전체 도표의 내용
구분제목	전체 도표의 내용I/O 완료는 준비로 돌아가는 전이
구분관계 설명	전체 도표의 내용데스크톱과 같은 준비·실행·대기·종료의 네 상태와 다섯 방향 화살표다. 왼쪽은 I/O 완료로 준비 복귀, 오른쪽 위는 실행에서 준비로 선점 또는 양보, 오른쪽 아래는 실행 종료. 깨우기는 즉시 실행이 아니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
블로킹 실행 중인 작업이 I/O를 기다린다.	값·보충 정보 준비·실행 상태 1: Running→Waiting	변화·이유 CPU 실행을 멈춤
완료 깨우기 준비 큐로 돌아간다.	값·보충 정보 준비·실행 상태 1: Waiting→Ready 준비·실행 상태 2: 현재 작업 선점 보장 없음	변화·이유 실행 가능
디스패치 정책에 따라 선택된 뒤 실제 실행한다.	값·보충 정보 준비·실행 상태 1: Ready→Running	변화·이유 CPU 재개

I/O 완료는 준비로 돌아가는 전이

실행 중인 작업이 I/O를 기다린다. 정책에 따라 선택된 뒤 실제 실행한다. 각 단계의 값과 전환 이유를 비교합니다.

CPU SCHEDULING · STATE TRANSITIONS

I/O 완료는 ‘준비’로 돌아가는 전이

깨어난 작업은 준비 큐에 합류합니다. 실제로 CPU를 받는 시점은 스케줄링 정책이 정합니다.

• 준비 → 실행

  스케줄러가 선택한 작업을 디스패처가 실행합니다.

• 실행 → 대기

  블로킹 I/O나 이벤트 대기로 CPU 실행을 멈춥니다.

• 대기 → 준비 · I/O 완료

  준비 큐로 돌아옵니다. 즉시 실행되거나 현재 작업을 반드시 선점하는 것은 아닙니다.

• 실행 → 준비

  타이머 등에 의한 선점 또는 명시적 양보로 준비 큐로 돌아옵니다.

• 실행 → 종료

  작업이 끝납니다. 다른 준비 작업이 없다면 CPU는 유휴 상태로 갑니다.

깨우기와 선점은 별개입니다. 비선점형에서도 대기 → 준비 전이는 일어납니다.

스케줄러 · 정책

준비 큐에서 다음 실행 대상을 고릅니다.

디스패처 · 메커니즘

문맥을 저장·복원해 선택된 작업에 CPU를 넘깁니다.

이 예의 조건

• 본문과 전체 도표의 예를 따라 블로킹부터 디스패치까지 진행합니다.

관계도의 보충 설명

전체 도표의 표기·관계·조건

구분	전체 도표의 내용
구분제목	전체 도표의 내용I/O 완료는 준비로 돌아가는 전이
구분관계 설명	전체 도표의 내용데스크톱과 같은 준비·실행·대기·종료의 네 상태와 다섯 방향 화살표다. 왼쪽은 I/O 완료로 준비 복귀, 오른쪽 위는 실행에서 준비로 선점 또는 양보, 오른쪽 아래는 실행 종료. 깨우기는 즉시 실행이 아니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
블로킹 실행 중인 작업이 I/O를 기다린다.	값·보충 정보 준비·실행 상태 1: Running→Waiting	변화·이유 CPU 실행을 멈춤
완료 깨우기 준비 큐로 돌아간다.	값·보충 정보 준비·실행 상태 1: Waiting→Ready 준비·실행 상태 2: 현재 작업 선점 보장 없음	변화·이유 실행 가능
디스패치 정책에 따라 선택된 뒤 실제 실행한다.	값·보충 정보 준비·실행 상태 1: Ready→Running	변화·이유 CPU 재개

---

선점형 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 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는 네트워크·서버 처리도 포함하므로 같은 측정값은 아닙니다.

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

세 시간을 같은 작업으로 계산해 봅시다. 작업 A가 t=0에 도착하여 준비 큐에서 2ms 기다리고, t=2~5에 CPU를 3ms 사용한 뒤 t=5~9에 I/O를 기다린다고 합시다. I/O 완료 후 즉시 실행하지 못해 준비 큐에서 다시 1ms 기다리고, t=10~12에 CPU를 2ms 사용하여 끝납니다. 문맥 전환 비용은 무시합니다.

반환 시간은 12−0=12ms, 대기 시간은 준비 큐의 두 구간 2+1=3ms, 이 절의 첫 CPU 실행 기준 응답 시간은 2−0=2ms입니다. 반환 시간도 CPU 5ms + I/O 4ms + 준비 큐 대기 3ms = 12ms로 확인할 수 있습니다. I/O를 기다린 4ms를 준비 큐 대기에 더하면 서로 다른 상태를 섞게 됩니다.

독립 확인: 작업 B는 t=1에 도착하여 t=4~6에 처음 실행하고, t=6~8에 I/O를 기다립니다. t=8~9에 준비 큐에서 기다린 뒤 t=9~10에 실행을 마친다면 반환·대기·응답 시간은 각각 얼마일까요? 문맥 전환 비용은 무시하고, I/O 완료와 첫 실행을 구별하여 계산하세요.

풀이 확인

반환 시간은 10−1=9ms입니다. 준비 큐 대기는 도착 후 4−1=3ms와 I/O 완료 후 9−8=1ms를 더한 4ms이며, 응답 시간은 첫 실행까지의 4−1=3ms입니다. CPU 사용 2+1=3ms, I/O 2ms, 준비 큐 4ms의 합도 9ms입니다. I/O 완료 t=8은 준비 상태 복귀 시각이며 실제 재개는 t=9입니다.

기준 간의 트레이드오프

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

라운드로빈(Round Robin, RR)은 준비 큐의 작업에 정해진 시간 단위인 타임 퀀텀을 차례로 배분하는 정책입니다.

같은 부하를 RR 정책으로 처리할 때 타임 퀀텀을 줄이면 준비된 다른 작업이 첫 실행 기회를 빨리 얻을 수 있습니다. 다른 작업으로 실제 전환하는 횟수가 늘면 문맥 전환 비용이 커져 유효한 CPU 작업의 몫과 처리량이 줄 수 있습니다. 준비된 다른 작업이 없다면 퀀텀 만료가 곧 작업 전환을 뜻하지는 않습니다.

반대로 같은 RR 부하에서 퀀텀을 늘려 전환 횟수를 줄이면, 긴 작업 뒤에서 기다리는 작업의 첫 실행이 늦어질 수 있습니다. 응답 시간은 퀀텀뿐 아니라 작업의 선택 순서·도착 시각·CPU 버스트에도 달려 있으므로, 이 조건부 트레이드오프를 모든 스케줄링 정책의 필수조건으로 일반화하지 않습니다.

선점 횟수를 늘리지 않고도 첫 실행이 달라지는 경우를 계산해 봅시다. P1·P2·P3가 모두 t=0에 도착하고 CPU 요구량은 각각 24ms·3ms·3ms라고 합시다. I/O와 문맥 전환 비용은 없으며 선택한 작업은 끝까지 실행합니다. 준비 큐 순서 P1→P2→P3를 따르면 첫 실행 시각은 0·24·27ms여서 평균 응답 시간은 (0+24+27)/3=17ms입니다. 짧은 CPU 요구부터 P2→P3→P1로 고르면 각각 0·3·6ms에 처음 실행하여 평균은 (0+3+6)/3=3ms입니다. 두 순서 모두 완료까지 30ms이고 작업 사이 전환은 두 번입니다. 이 계산은 앞에서 정의한 첫 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를 기다립니다.

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

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

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

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

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

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