CPU 스케줄링

왜 스케줄링이 필요한가

CPU 코어 하나는 한 번에 하나의 프로세스만 실행합니다. 그런데 우리 컴퓨터에서는 수백 개의 프로세스가 동시에 돌아가는 것처럼 보입니다. 이것은 OS의 CPU 스케줄러가 매우 빠르게 실행 대상을 교체하기 때문입니다.

스케줄링의 핵심 질문은 이것입니다: "지금 Ready 큐에 있는 프로세스 중 어떤 것을 다음에 실행할 것인가?"

이 질문에 답하는 방식이 바로 스케줄링 알고리즘이며, 어떤 알고리즘을 선택하느냐에 따라 시스템의 응답 시간, 처리량, 공정성이 달라집니다.

CPU burst와 I/O burst

프로세스의 실행은 CPU burst와 I/O burst 의 반복입니다.

• CPU burst : CPU가 명령어를 실행하는 구간 (계산, 로직 처리)
• I/O burst : 디스크 읽기, 네트워크 요청 등 I/O 완료를 기다리는 구간

Process 실행 흐름:
  CPU burst --> I/O burst --> CPU burst --> I/O burst --> ...

CPU 스케줄러가 개입하는 시점은 CPU burst가 끝나거나, 타이머 인터럽트가 발생하거나, 더 높은 우선순위의 프로세스가 도착했을 때입니다.

프로세스는 CPU burst 길이에 따라 두 유형으로 나뉩니다.

대부분의 프로세스는 I/O-bound입니다. 이것은 스케줄링 알고리즘 설계에 중요한 힌트를 줍니다 -- 짧은 CPU burst를 먼저 처리하면 전체 응답 시간이 줄어듭니다.

선점형 vs 비선점형

스케줄링 알고리즘은 CPU를 빼앗을 수 있는지 여부로 크게 나뉩니다.

비선점형 (Non-preemptive) : 프로세스가 자발적으로 CPU를 반환할 때까지 기다립니다. CPU burst가 끝나거나 I/O 요청을 할 때만 스케줄러가 개입합니다. 구현이 단순하지만, 긴 작업이 CPU를 독점할 수 있습니다.

선점형 (Preemptive) : OS가 타이머 인터럽트 등으로 실행 중인 프로세스를 강제 중단하고 다른 프로세스에 CPU를 넘깁니다. 컨텍스트 스위칭 비용이 발생하지만, 한 프로세스가 CPU를 독점하는 것을 방지합니다.

현대 OS (Linux, Windows, macOS)는 모두 선점형 스케줄링을 사용합니다.

FCFS (First-Come, First-Served)

가장 단순한 알고리즘입니다. 도착 순서대로 실행하고, 한번 시작하면 끝까지 실행합니다 (비선점형).

장점은 구현이 매우 간단하다는 것이고, 단점은 Convoy Effect입니다 -- CPU burst가 긴 프로세스가 먼저 도착하면 뒤의 짧은 프로세스들이 오래 기다립니다.

아래 시각화에서 FCFS의 동작을 단계별로 확인하세요. 각 프로세스가 끝날 때까지 다음 프로세스는 Ready 큐에서 대기합니다.

SJF (Shortest Job First)

CPU burst가 가장 짧은 프로세스를 먼저 실행합니다. 평균 대기 시간을 수학적으로 최소화 하는 최적 알고리즘입니다.

하지만 실용적인 문제가 있습니다 -- 다음 CPU burst 길이를 미리 알 수 없습니다. 과거 burst 기록을 기반으로 예측 (지수 이동 평균)하는 방식을 사용하지만 정확하지 않습니다.

예측 공식 (지수 이동 평균):
  예측값(n+1) = a * 실측값(n) + (1-a) * 예측값(n)
  a = 가중치 (보통 0.5)

SRTF (Shortest Remaining Time First) 는 SJF의 선점형 버전입니다. 새 프로세스가 도착했을 때 남은 burst가 현재 실행 중인 프로세스보다 짧으면 CPU를 빼앗습니다.

SJF/SRTF의 또 다른 문제는 기아 상태입니다 -- 짧은 프로세스가 계속 도착하면 긴 프로세스는 영원히 실행되지 못합니다.

라운드 로빈 (Round Robin)

FCFS에 타임 퀀텀 (Time Quantum)을 추가한 선점형 알고리즘입니다. 각 프로세스는 최대 Q 시간만 CPU를 사용하고, 시간이 다 되면 Ready 큐 맨 뒤로 돌아갑니다.

아래 시각화에서 타임 퀀텀 Q=2인 라운드 로빈의 동작을 확인하세요.

타임 퀀텀의 크기가 성능을 결정합니다.

라운드 로빈은 공정성 이 가장 큰 장점입니다. 모든 프로세스가 Q 시간 안에 한 번은 CPU를 사용할 수 있으므로 기아 상태가 발생하지 않습니다.

우선순위 스케줄링

각 프로세스에 우선순위 번호를 부여하고, 가장 높은 우선순위를 먼저 실행합니다. SJF도 "burst 길이가 곧 우선순위"인 우선순위 스케줄링의 특수한 경우입니다.

우선순위는 내부 요인 (메모리 사용량, I/O 대 CPU 비율)과 외부 요인 (사용자 설정, 비용 지불)으로 결정됩니다.

핵심 문제는 역시 기아 상태입니다. 해결책은 에이징 (Aging) -- 오래 기다린 프로세스의 우선순위를 점진적으로 높이는 방법입니다.

현대 OS는 다단계 피드백 큐 (Multilevel Feedback Queue) 를 사용합니다.

• 여러 우선순위 큐가 존재
• 각 큐마다 다른 스케줄링 알고리즘 사용 가능 (상위 큐: 라운드 로빈, 하위 큐: FCFS)
• CPU를 많이 쓰면 낮은 큐로 강등, I/O 위주면 높은 큐로 승격
• 에이징으로 기아 방지

우선순위 높음  [Q0: RR, Q=8ms ]  <-- 새 프로세스는 여기서 시작
             [Q1: RR, Q=16ms]  <-- Q0에서 퀀텀 소진 시 강등
우선순위 낮음  [Q2: FCFS      ]  <-- Q1에서 퀀텀 소진 시 강등

스케줄링 알고리즘 비교

실무에서의 연결

이론적인 스케줄링이 실제 개발에서 어떻게 나타나는지 살펴봅니다.

JavaScript 이벤트 루프 = 협력적 스케줄링 : JavaScript는 싱글 스레드에서 이벤트 루프로 작업을 처리합니다. 이것은 비선점형 (협력적) 스케줄링입니다. 하나의 콜백이 오래 실행되면 다른 모든 작업이 블로킹됩니다. setTimeout(fn, 0)으로 "자발적으로 CPU를 양보"하는 패턴은 협력적 스케줄링의 전형입니다.

// 긴 작업을 쪼개서 이벤트 루프에 양보하는 패턴
function processChunk(items, index) {
  const CHUNK = 100;
  const end = Math.min(index + CHUNK, items.length);

  for (let i = index; i < end; i++) {
    heavyWork(items[i]);
  }

  if (end < items.length) {
    // 다음 청크를 태스크 큐에 넣어 양보
    setTimeout(() => processChunk(items, end), 0);
  }
}

OS 스케줄러가 JS 실행에 미치는 영향 : Node.js 서버가 CPU-bound 작업을 하면 OS 스케줄러가 해당 프로세스의 타임 슬라이스를 소진시키고 다른 프로세스에 CPU를 넘깁니다. 이것이 setTimeout(fn, 10)의 실제 지연이 10ms보다 훨씬 길어질 수 있는 이유입니다. OS 레벨의 선점형 스케줄링이 JavaScript의 타이머 정확도에 직접 영향을 줍니다.

Linux EEVDF (Earliest Eligible Virtual Deadline First) : Linux 6.6 (2023) 부터 CFS를 대체한 기본 스케줄러입니다. 각 프로세스에 가상 마감 시한을 부여하고, 마감이 가장 임박한 프로세스를 다음에 실행합니다. nice 값으로 프로세스의 가중치를 조절할 수 있습니다.

nice -n 19 node heavy-computation.js   # 가장 낮은 우선순위로 실행
nice -n -20 node critical-server.js    # 가장 높은 우선순위 (root 필요)

scheduler.yield() (Web API) : 브라우저의 새 API로, 긴 작업 중에 메인 스레드를 명시적으로 양보합니다. setTimeout(fn, 0)과 달리 현재 작업의 우선순위를 유지하면서 렌더링과 입력 처리에 기회를 줍니다. 이것은 브라우저 레벨의 협력적 스케줄링입니다.

다음 단계

이 글에서는 CPU 스케줄링의 기본 알고리즘들을 살펴봤습니다. 다음 글에서는 프로세스 동기화 -- 여러 프로세스/스레드가 공유 자원에 안전하게 접근하는 방법 (뮤텍스, 세마포어, 교착 상태)을 다루겠습니다.