들어가기 전에: 스케줄링은 왜 필요할까?
지난 글에서는 하나의 프로세스에서 다른 프로세스로 CPU의 제어권을 넘기는 low-level 메커니즘, 컨텍스트 스위치(Context Switch)에 대해 알아보았다. 운영체제는 타이머 인터럽트(Timer Interrupt)와 같은 하드웨어의 도움을 받아 실행 중인 프로세스를 멈추고, 현재까지의 작업 상태(레지스터 값, 프로그램 카운터 등)를 PCB(Process Control Block)에 저장한 뒤, 다음 실행할 프로세스의 상태를 불러와 실행을 이어 나간다.
이러한 컨텍스트 스위치는 프로세스 전환을 '가능하게' 하는 기술적인 방법론이다. 그렇다면 여기서 한 단계 더 나아가, "수많은 대기 중인 프로세스 중에서, 어떤 프로세스를 다음에 실행할 것인지" 결정하는 문제가 남는다. 이 고수준의 의사결정 정책이 바로 CPU 스케줄링이다. 효율적인 스케줄링은 한정된 CPU 자원을 여러 프로세스에 공정하고 효율적으로 배분하여 시스템 전체의 성능을 극대화하는 것을 목표로 한다.
스케줄링을 이해하기 위한 두 가지 준비물
본격적으로 정책들을 살펴보기 전에, 논의를 단순화하고 각 정책의 성능을 객관적으로 평가하기 위한 두 가지 개념을 먼저 짚고 넘어가겠다.
1. 워크로드 가정 (Workload Assumptions)
현실 세계의 작업(프로세스)들은 그 특성이 매우 다양하고 복잡하다. 따라서 스케줄링 알고리즘의 핵심 아이디어를 이해하기 위해, 보통 다음과 같은 비현실적이지만 유용한 가정들을 전제로 논한다.
가정 1: 모든 작업의 실행 시간은 동일하다.
가정 2: 모든 작업은 시스템에 동시에 도착한다.
가정 3: 모든 작업은 실행이 시작되면 끝날 때까지 CPU만 사용한다. (즉, I/O 작업을 수행하지 않는다)
가정 4: 각 작업의 총 실행 시간은 미리 알려져 있다.
이 가정들로부터 시작하여, 각 가정을 하나씩 현실적으로 바꾸어 나갈 때 기존 정책이 어떤 문제에 부딪히고, 이를 해결하기 위해 어떻게 새로운 정책이 등장했는지 그 발전 과정을 따라가는 것이 이번 글의 핵심 흐름이다.
2. 스케줄링의 평가 지표 (Scheduling Metrics)
'좋은 스케줄링'이란 무엇일까? 이를 평가하기 위한 기준이 필요하다. 주로 두 가지 상반된 지표가 사용된다.
반환 시간 (Turnaround Time): 작업이 시스템에 도착한 순간부터 완료될 때까지 걸린 총 시간. 시스템의 처리량(Throughput)과 관련된 지표로, 시스템 관리자의 입장에서 중요하다.
응답 시간 (Response Time): 작업이 도착한 후 '처음으로' CPU를 할당받기까지 걸린 시간. 시스템의 반응성(Responsiveness)과 관련된 지표로, 사용자의 입장에서 중요하다.
이상적으로는 두 지표 모두 낮은 것이 좋지만, 대부분의 경우 이 둘은 서로 상충 관계(trade-off)에 있다. 이제 이 지표들을 기준으로 각 정책의 장단점을 살펴보겠다.
1. FIFO: 가장 단순한 시작
선입선출(First In, First Out 또는 First Come, First Served)은 이름 그대로 시스템에 먼저 도착한 작업을 순서대로 처리하는 가장 간단한 정책이다.
FIFO
위의 워크로드 가정이 모두 성립한다면(모든 작업의 실행 시간이 같고 동시에 도착한다면) FIFO는 매우 합리적으로 동작한다. 하지만 실제 상황에서는 각 작업의 실행 시간이 제각각이라는 점에서 문제가 시작된다.
문제점: 호위 효과 (Convoy Effect)
하지만 가정 1을 버리고, '각 작업의 실행 시간이 다르다'는 현실을 반영하면 문제가 시작된다. 만약 실행 시간이 매우 긴 작업(A: 100초)이 먼저 도착하고, 그 뒤를 이어 짧은 작업들(B: 10초, C: 10초)이 도착했다고 가정해 보자.
Convoy Effect in FIFO
B와 C는 A가 끝날 때까지 꼼짝없이 기다려야만 한다. 이처럼 무거운 작업 하나가 전체 시스템의 흐름을 막는 현상을 호위 효과라고 한다. 이 경우 평균 반환 시간은 (100 + 110 + 120) / 3 = 110초로 매우 비효율적인 결과를 낳는다.
2. SJF: 짧은 작업 먼저
호위 효과를 해결하기 위한 아이디어는 간단했다. "가장 짧은 작업을 먼저 실행하면 되지 않을까?" 이것이 바로 최단 작업 우선(Shortest Job First, SJF) 정책이다.
SJF는 위와 같은 상황에서 B(10초)와 C(10초)를 먼저 실행하고, 가장 긴 A(100초)를 마지막에 실행한다.
SJF
그 결과 평균 반환 시간은 (10 + 20 + 120) / 3 = 50초로 FIFO에 비해 극적으로 개선되었다. 반환 시간만 놓고 보면 SJF는 최적의 정책임이 증명되었다.
문제점: 작업 도착 시간을 모른다면?
하지만 SJF 역시 가정 2를 버리고, '작업이 각기 다른 시간에 도착한다'는 현실을 마주하면 한계가 드러난다. 만약 A(100초)가 t=0에 도착하고, B와 C(각 10초)가 t=10에 도착했다면 어떻게 될까? SJF는 비선점(non-preemptive) 방식이므로, 일단 A가 실행을 시작하면 B와 C가 도착하더라도 A가 끝날 때까지 기다려야 한다. 결국 호위 효과가 다시 발생하고 만다.
Convoy Effect in SJF
3. STCF: 선점을 통한 개선
이 문제를 해결하기 위해 SJF에 선점(preemption) 개념을 도입한 것이 최단 완료 시간 우선(Shortest Time-to-Completion First, STCF) 정책이다.
STCF는 새로운 작업이 도착할 때마다 현재 실행 중인 작업의 남은 시간과 새로운 작업의 실행 시간을 비교한다. 그리고 남은 실행 시간이 가장 짧은 작업을 즉시 실행한다.
STCF
위의 예시에서, A가 10초 동안 실행된 시점(t=10)에 B와 C가 도착하면, 스케줄러는 남은 작업 시간을 비교한다. (A: 90초, B: 10초, C: 10초) B의 실행 시간이 가장 짧으므로 A의 실행을 중단(선점)하고 B를 실행한다. 그 후 C를 실행하고, 마지막으로 남은 A를 실행한다.
이 경우 평균 반환 시간은 50초로, 다시 최적의 효율을 보여준다.
문제점: 응답 시간과 기아 현상
STCF는 평균 반환 시간을 최적화하는 데에는 탁월했지만, 새로운 시대의 요구와는 맞지 않았다. 여러 사용자가 동시에 시스템과 상호작용하는 시분할 시스템(time-shared systems)이 등장하면서, 작업이 완료되는 시간만큼이나 '얼마나 빨리 응답하는가'가 중요해졌다. STCF 환경에서는 짧은 작업들이 계속 들어오면 긴 작업은 영원히 CPU를 할당받지 못하는 기아 현상(Starvation)이 발생할 수 있고, 모든 작업이 응답 시간을 보장받지 못한다.
4. Round Robin: 공정한 분배의 미학
응답 시간을 개선하기 위해 등장한 정책이 바로 라운드 로빈(Round Robin, RR)이다. RR은 모든 작업에게 시간 할당량(time slice)이라는 아주 짧은 실행 시간을 부여하고, 이 시간이 끝나면 즉시 다음 작업으로 전환한다. 모든 준비된(ready) 작업을 돌아가며 실행하는 방식이다.
예를 들어, 5초짜리 작업 A, B, C가 동시에 도착했을 때, 시간 할당량을 1초로 설정한 RR 스케줄러는 A, B, C를 1초씩 번갈아 실행한다. 이 방식은 평균 반환 시간 측면에서는 (13 + 14 + 15) / 3 = 14초로 STCF((5 + 10 + 15) / 3 = 10초)보다 비효율적이다.
Round Robin
하지만 평균 응답 시간은 A: 0초, B: 1초, C: 2초로 평균 1초에 불과하다. 반면 STCF는 평균 5초의 응답 시간을 가진다. RR은 반환 시간을 희생하는 대신, 모든 프로세스에 공정하고 빠른 응답 시간을 제공하는 데 초점을 맞춘다.
문제점: 컨텍스트 스위치 비용
RR의 성능은 시간 할당량의 크기에 매우 민감하다. 시간 할당량이 너무 짧으면 컨텍스트 스위치가 너무 자주 발생하여 오버헤드가 커지고, 너무 길면 FIFO처럼 동작하여 응답 시간이 나빠진다. 결국 반환 시간과 응답 시간 사이의 이상적인 균형점을 찾는 것은 여전히 숙제로 남았다.
5. MLFQ: 과거로부터 미래를 예측하다
지금까지의 정책들은 한 가지 치명적인 맹점을 가지고 있었습니다. 바로 가정 4, 즉 작업의 실행 시간을 미리 알고 있다는 비현실적인 가정이다. 또한, STCF는 반환 시간에, RR은 응답 시간에만 강점을 보였다.
다단계 피드백 큐(Multi-Level Feedback Queue, MLFQ)는 이 두 가지 문제를 모두 해결하기 위해 탄생했다. MLFQ의 목표는 다음과 같다.
작업의 실행 시간을 미리 알지 못하는 상황에서,
STCF처럼 반환 시간을 최적화하고 (CPU 집중적인 긴 작업)
RR처럼 응답 시간을 최적화한다. (상호작용적인 짧은 작업)
MLFQ는 작업의 과거 행동을 관찰하여 미래 행동을 예측하는, 매우 영리한 접근 방식을 사용한다.
MLFQ의 동작 규칙
MLFQ는 여러 개의 큐(Queue)를 계층적으로 관리하며, 각 큐는 서로 다른 우선순위를 가진다.
규칙 1 & 2: 우선순위가 높은 큐의 작업이 먼저 실행된다. 같은 큐 내에서는 RR 방식으로 스케줄링된다.
규칙 3: 새로운 작업은 무조건 가장 높은 우선순위 큐에 들어간다. (일단 짧은 작업일 것이라 낙관적으로 예측)
규칙 4:
4a: 작업이 주어진 시간 할당량을 모두 사용하면 우선순위가 한 단계 낮아진다. (CPU를 오래 쓰는 것을 보니 긴 작업일 가능성이 높다고 판단)
4b: 작업이 시간 할당량을 다 쓰기 전에 스스로 CPU를 반납하면(주로 I/O 대기) 우선순위를 그대로 유지한다. (상호작용 작업일 가능성이 높다고 판단)
이 규칙들을 통해 MLFQ는 실행 시간을 모르는 상태에서도 짧은 작업은 상위 큐에서 빠르게 처리하고, 긴 작업은 서서히 하위 큐로 내려가게 함으로써 STCF를 근사적으로 구현해낸다.
문제점과 해결책: 우선순위 상승
하지만 이 기본 규칙만으로는 여전히 문제가 남는다.
기아 현상: 상호작용 작업이 너무 많으면 하위 큐의 긴 작업은 영원히 실행되지 않을 수 있다.
행동 변화: 초반에는 CPU 집중적이었던 작업이 나중에 상호작용적으로 변해도 계속 하위 큐에 머무른다.
이 문제들을 해결하기 위해 마지막 규칙이 추가되었다.
규칙 5 (Priority Boost): 주기적으로 모든 작업을 최상위 큐로 이동시킨다.
이 우선순위 상승을 통해 기아 현상을 방지하고, 작업의 행동 변화에 유연하게 대응할 수 있게 된다.
결론
단순한 FIFO에서 시작하여 호위 효과를 해결한 SJF, 선점을 도입한 STCF, 응답 시간을 개선한 RR, 그리고 이 모든 것의 장점을 결합하고 현실적인 제약을 극복하려 한 MLFQ까지. CPU 스케줄링 정책의 발전 과정은 결국 시스템의 목표(처리량 vs 응답성)와 주어진 작업의 특성 사이에서 최적의 균형점을 찾으려는 끊임없는 노력의 역사라는 생각이 들었다.
어떤 정책도 모든 상황에서 완벽할 수는 없다. 시스템이 어떤 종류의 작업을 주로 처리하는지에 따라 최적의 스케줄러는 달라질 것이다. Solaris 운영체제가 60개의 큐를 두고 복잡한 튜닝 파라미터를 제공하는 이유도 바로 여기에 있을 것이다. 다음에도 이어서 스케줄링 기법에 대해 더 깊이 알아보고자 한다.
추천글:
[운영체제] CPU 가상화 | Logical Control Flow에서 Context Switch까지
[운영체제] 운영체제란? | Virtualization, Concurrency, Persistence 핵심 개념 이해
