OS CPU 스케줄링 알고리즘 종류와 차이

OS의 CPU 스케줄러는 준비 큐(Ready Queue)에 있는 프로세스 중 다음에 실행할 프로세스를 선택하는 핵심 모듈이다. 스케줄링 알고리즘의 선택은 처리량(Throughput), 평균 대기 시간(Waiting Time), 응답 시간(Response Time), 공정성(Fairness)에 직접 영향을 주며, 시스템 부하 특성에 따라 최적 알고리즘이 달라진다.

비선점형(Non-preemptive) 방식에서는 실행 중인 프로세스가 자발적으로 CPU를 반납하기 전까지 다른 프로세스가 개입할 수 없다. FCFS(First-Come-First-Served)는 도착 순서대로 실행하여 구현이 단순하다. 단점이 명확하다. 수행 시간이 긴 프로세스 뒤에 짧은 프로세스가 몰리는 호위 효과(Convoy Effect)가 발생하여 평균 대기 시간이 급격히 늘어난다. SJF(Shortest Job First)는 이론상 평균 대기 시간이 최소지만, CPU 버스트 시간을 사전에 예측하기 어렵고 긴 작업이 무한 대기 상태인 기아(Starvation)에 빠질 수 있다.

선점형(Preemptive) 방식의 대표는 Round Robin(RR)이다. 각 프로세스에 Time Quantum(타임 슬라이스)을 부여하고 초과 시 강제로 컨텍스트 스위칭이 발생한다. Time Quantum이 1ms 이하로 너무 짧으면 스위칭 오버헤드가 전체 CPU 시간을 잠식하고, 수백 ms 이상으로 길면 사실상 FCFS와 같아진다. 실무에서는 보통 10~100ms 범위로 설정한다.

Priority Scheduling은 각 프로세스에 우선순위를 부여하고 가장 높은 우선순위를 먼저 실행하는 방식이다. 기아 문제를 해결하기 위해 대기 시간이 길어질수록 우선순위를 점진적으로 올리는 에이징(Aging) 기법을 결합한다. Linux 커널의 CFS(Completely Fair Scheduler)는 각 프로세스의 가상 실행 시간(vruntime)을 레드-블랙 트리로 관리해 O(log n) 비용으로 다음 실행 프로세스를 선택하며, 커널 5.x 계열에서도 기본 스케줄러로 동작한다.

현대 범용 OS는 다단계 피드백 큐(MLFQ, Multilevel Feedback Queue)를 채택한다. CPU를 많이 소모할수록 낮은 우선순위 큐로 강등하고, I/O 대기 후 복귀하면 높은 큐로 승격하여 대화형 작업과 배치 작업 모두를 효율적으로 처리한다. MLFQ는 단일 알고리즘의 한계를 계층 구조로 극복한 설계다.