CPU 스케줄링 알고리즘 비교 분석: FIFO, SJF, Round Robin의 원리와 성능 특성

운영체제가 여러 프로세스를 동시에 처리하는 것처럼 보이게 만드는 핵심 기술은 CPU 스케줄링이다. 단일 혹은 소수의 처리 코어를 다수의 프로세스가 공유해야 하는 상황에서, 어떤 프로세스에 언제 얼마만큼의 시간 동안 CPU를 할당할 것인지를 결정하는 규칙이 바로 스케줄링 알고리즘이다. 이 글에서는 운영체제 교과서와 실무 현장에서 가장 기본이 되는 세 가지 알고리즘인 FIFO(First-In-First-Out, 흔히 FCFS라고도 부른다), SJF(Shortest Job First), Round Robin을 원리와 동작 방식, 성능 지표, 실제 적용 시의 한계까지 종합적으로 비교한다.

 

 

 

 

 

 

 

 

▍ CPU 스케줄링의 기본 개념과 목표

 

운영체제 내부에는 실행을 기다리는 프로세스들이 모여 있는 준비 큐(ready queue)가 존재한다. CPU 스케줄러는 이 큐에서 다음에 실행할 프로세스를 선택하는 역할을 담당하며, 이때 사용하는 판단 기준과 절차 전체를 스케줄링 알고리즘이라 부른다. 스케줄링 알고리즘이 추구하는 목표는 크게 CPU 이용률의 극대화, 단위 시간당 처리량(throughput) 증가, 프로세스의 대기 시간과 반환 시간 최소화, 그리고 사용자가 체감하는 응답 시간 단축으로 요약할 수 있다.

 

다만 이 목표들은 서로 완전히 양립하기 어렵다. 처리량을 높이려면 긴 작업을 효율적으로 몰아서 처리하는 편이 유리하지만, 응답성을 높이려면 짧은 작업이나 대화형 작업에 CPU를 자주 넘겨주어야 한다. 결국 스케줄링 알고리즘의 설계는 이러한 상충 관계 속에서 시스템의 용도에 맞는 균형점을 찾는 과정이라 할 수 있다.

 

스케줄링 방식은 크게 선점형(preemptive)과 비선점형(non-preemptive)으로 나뉜다. 선점형 방식은 현재 CPU를 사용 중인 프로세스라도 스케줄러의 판단에 따라 강제로 중단시키고 다른 프로세스에 CPU를 넘길 수 있는 방식이며, 비선점형 방식은 프로세스가 스스로 CPU를 반납하거나 종료할 때까지 다른 프로세스가 개입할 수 없는 방식이다. 아래에서 다룰 FIFO와 SJF는 기본적으로 비선점형으로 설명되는 경우가 많고, Round Robin은 선점형 방식의 대표적인 사례다.

 

 

 

▍ FIFO(FCFS) 스케줄링의 동작 원리

 

FIFO 스케줄링은 준비 큐에 도착한 순서대로 프로세스에 CPU를 할당하는 가장 단순한 방식이다. 먼저 도착한 프로세스가 먼저 처리된다는 점에서 First-Come, First-Served라는 이름으로도 불리며, 큐 자료구조의 동작 방식과 완전히 일치한다는 점에서 구현이 매우 간단하다는 장점이 있다.

 

FIFO의 가장 큰 문제는 호위 효과(convoy effect)라 불리는 현상이다. 실행 시간이 매우 긴 프로세스가 먼저 큐에 들어와 CPU를 오래 점유하게 되면, 뒤이어 도착한 짧은 작업들조차 앞선 프로세스가 끝날 때까지 무작정 기다려야 한다. 이는 마치 고속도로에서 느린 대형 트럭 한 대가 뒤따르는 차량 전체의 흐름을 막는 상황에 비유할 수 있다. 결과적으로 전체 평균 대기 시간이 프로세스 도착 순서에 따라 크게 달라질 수 있다는 것이 FIFO의 구조적 한계다.

 

또한 FIFO는 비선점형으로 동작하기 때문에 한 번 CPU를 할당받은 프로세스는 스스로 종료하거나 입출력 요청 등으로 CPU를 반납하기 전까지 다른 프로세스에게 자리를 내주지 않는다. 이는 문맥 교환(context switching)의 빈도를 낮춰 오버헤드를 줄인다는 장점으로 이어지지만, 동시에 응답성이 중요한 대화형 시스템에는 적합하지 않다는 단점으로도 이어진다.

 

 

 

 

 

 

▍ SJF(Shortest Job First) 스케줄링의 동작 원리

 

SJF 스케줄링은 준비 큐에 있는 프로세스 중 예상 실행 시간이 가장 짧은 프로세스를 우선적으로 처리하는 방식이다. 이론적으로 SJF는 평균 대기 시간을 최소화하는 알고리즘으로 알려져 있는데, 이는 짧은 작업을 먼저 처리함으로써 뒤따르는 작업들이 기다려야 하는 누적 시간을 줄일 수 있기 때문이다. 통계적, 수학적으로도 주어진 작업 집합에 대해 평균 대기 시간을 최소화하는 최적 알고리즘으로 다뤄지는 경우가 많다.

 

그러나 SJF에는 실질적인 구현상의 난제가 존재한다. 프로세스가 앞으로 얼마나 실행될지는 사전에 정확히 알기 어렵다는 점이다. 실제 운영체제에서는 프로세스의 과거 실행 이력을 바탕으로 다음 실행 시간을 추정하는 방식을 사용하는 경우가 많으며, 이러한 예측값의 정확도에 따라 SJF의 실제 성능이 달라진다.

 

SJF의 또 다른 단점은 기아 현상(starvation)이다. 짧은 작업들이 계속해서 큐에 새로 도착하는 상황에서는 상대적으로 실행 시간이 긴 프로세스가 계속 뒤로 밀려 무한정 대기하게 될 위험이 있다. 이를 완화하기 위해 대기 시간이 길어질수록 우선순위를 점차 높여주는 에이징(aging) 기법이 함께 논의되는 경우가 많다.

 

SJF는 비선점형으로 구현될 수도 있고, 실행 중인 프로세스보다 더 짧은 실행 시간을 가진 프로세스가 새로 도착했을 때 즉시 CPU를 넘겨주는 선점형 변형인 SRTF(Shortest Remaining Time First)로 구현될 수도 있다. 선점형으로 구현할 경우 평균 대기 시간은 더욱 줄어들 수 있지만, 문맥 교환이 잦아지는 대가를 치르게 된다.

 

 

 

▍ Round Robin 스케줄링의 동작 원리와 타임 슬라이스

 

Round Robin은 각 프로세스에 일정한 시간 단위, 즉 타임 슬라이스(time slice 또는 time quantum)를 정해두고, 그 시간이 지나면 실행 완료 여부와 무관하게 강제로 CPU를 회수하여 다음 프로세스에 넘기는 선점형 스케줄링 방식이다. 할당된 시간 안에 작업을 마치지 못한 프로세스는 준비 큐의 맨 뒤로 다시 삽입되어 자신의 차례를 기다리게 된다.

 

Round Robin의 핵심은 타임 슬라이스의 크기를 어떻게 설정하느냐에 있다. 타임 슬라이스가 지나치게 짧으면 프로세스 간 전환이 매우 빈번해지고, 그 과정에서 발생하는 문맥 교환 오버헤드가 커져 시스템 전체의 실질적인 처리 효율이 떨어질 수 있다. 반대로 타임 슬라이스가 지나치게 길면 사실상 FIFO와 유사하게 동작하게 되어, 응답성이 중요한 대화형 작업에서 지연이 발생하기 쉽다.

 

이러한 특성 때문에 Round Robin은 다수의 사용자가 동시에 시스템을 이용하는 시분할 시스템(time-sharing system)에 특히 적합한 알고리즘으로 평가받는다. 데스크톱 운영체제나 다중 사용자 환경에서 널리 채택되는 이유도 여기에 있다. 타임 슬라이스의 구체적인 최적값은 시스템의 특성, 프로세스의 평균 실행 시간, 하드웨어 성능 등에 따라 달라지므로 일률적으로 정하기보다는 시스템 운용 목적에 맞추어 조정하는 것이 일반적이다.

 

 

 

 

다음은 타임 슬라이스 길이에 따른 트레이드오프를 정리한 표다.

 

 

 

 

이 표에서 볼 수 있듯이 타임 슬라이스는 응답성과 처리 효율 사이에서 균형을 맞추는 핵심 매개변수로 작동한다. 따라서 실무에서는 시스템의 용도, 즉 서버 환경인지 데스크톱 환경인지 혹은 실시간성이 요구되는 환경인지에 따라 값을 다르게 설정하는 접근이 일반적으로 권장된다.

 

 

 

▍ 세 알고리즘의 성능 특성 비교

 

세 알고리즘은 각각 서로 다른 우선순위를 두고 설계되었다는 점에서 단순 우열을 가리기보다는 상황별 적합성을 따지는 것이 합리적이다. FIFO는 구현의 단순함과 예측 가능성을 우선하며, SJF는 평균 대기 시간의 최소화라는 이론적 효율을 우선하고, Round Robin은 다수의 프로세스에 공평하게 CPU 기회를 나누는 공정성과 응답성을 우선한다.

 

아래 표는 각 알고리즘의 주요 특징을 방식, 장점, 단점 측면에서 요약한 것이다.

 

 

 

 

세 알고리즘의 차이는 결국 어떤 프로세스가 먼저 CPU를 할당받아야 하는가에 대한 판단 기준의 차이에서 비롯된다. FIFO는 도착 순서만을 기준으로 삼고, SJF는 작업의 길이를 기준으로 삼으며, Round Robin은 순서와 시간 배분을 동시에 고려한다. 이 때문에 동일한 프로세스 집합이라도 각 알고리즘을 적용했을 때 평균 대기 시간과 평균 반환 시간이 서로 다르게 산출된다.

 

 

 

 

 

 

▍ 실제 시스템에서의 적용과 한계

 

실제 상용 운영체제는 앞서 설명한 세 알고리즘을 그대로 단독으로 사용하기보다, 이들의 개념을 조합하거나 확장한 형태의 스케줄링 기법을 채택하는 경우가 많다. 예를 들어 다단계 큐(multilevel queue) 스케줄링은 우선순위가 다른 여러 개의 준비 큐를 두고 큐마다 서로 다른 스케줄링 방식을 적용하는 방식이며, 다단계 피드백 큐(multilevel feedback queue) 스케줄링은 여기에 프로세스가 큐 사이를 이동할 수 있는 유연성을 더한 방식이다.

 

이러한 확장 기법들이 등장한 배경에는 FIFO, SJF, Round Robin 각각이 가진 한계를 보완하려는 목적이 있다. FIFO의 호위 효과, SJF의 기아 현상, Round Robin의 타임 슬라이스 설정 문제는 단일 알고리즘만으로는 완전히 해결하기 어려운 구조적 특성이기 때문에, 실제 커널 수준의 스케줄러는 우선순위와 시간 할당, 대기 시간에 따른 가중치 조정 등을 복합적으로 반영하는 방향으로 발전해 왔다.

 

다만 이러한 세부 구현은 운영체제 종류와 버전에 따라 상당한 차이가 있으며, 특정 커널이 정확히 어떤 파라미터와 정책을 사용하는지는 공식 문서나 소스 코드를 통해 확인하는 것이 가장 정확하다. 이 글에서 다룬 FIFO, SJF, Round Robin은 어디까지나 스케줄링 이론의 기초를 이루는 모델이며, 실제 시스템의 동작을 그대로 재현하는 것은 아니라는 점을 염두에 둘 필요가 있다.

 

 

 

 

 

 

▍ 대기 시간과 반환 시간 계산의 기본 개념

 

스케줄링 알고리즘의 성능을 비교할 때 자주 사용되는 지표로 대기 시간(waiting time)과 반환 시간(turnaround time)이 있다. 대기 시간은 프로세스가 준비 큐에서 CPU 할당을 기다린 총 시간을 의미하며, 반환 시간은 프로세스가 시스템에 도착한 시점부터 실행을 완전히 마칠 때까지 걸린 전체 시간을 의미한다.

 

이 두 지표는 동일한 프로세스 집합에 대해서도 어떤 스케줄링 알고리즘을 적용하느냐에 따라 크게 달라질 수 있다. 예를 들어 실행 시간이 짧은 프로세스와 긴 프로세스가 섞여 있는 상황에서 FIFO를 적용하면 짧은 프로세스가 긴 프로세스 뒤에 도착했을 경우 불필요하게 오래 기다려야 하지만, SJF를 적용하면 짧은 프로세스가 먼저 처리되어 전체 평균 대기 시간이 줄어드는 결과가 나타난다. Round Robin의 경우에는 모든 프로세스가 일정 주기로 번갈아 CPU를 할당받기 때문에 특정 프로세스가 지나치게 오래 기다리는 극단적 상황은 줄어들지만, 타임 슬라이스 단위로 실행이 쪼개지는 특성상 반환 시간 자체는 다른 알고리즘보다 길어질 수 있다.

 

이처럼 지표별로 유리한 알고리즘이 달라질 수 있기 때문에, 특정 알고리즘이 모든 상황에서 우월하다고 단정하기는 어렵다. 시스템 설계자는 처리량, 응답성, 공정성 중 어느 목표를 우선할 것인지 먼저 결정한 뒤, 그에 맞는 스케줄링 전략을 선택하거나 여러 기법을 조합하는 방식으로 접근하는 것이 일반적이다.

 

 

 

 

 

 

▍ 결론: 상황에 맞는 스케줄링 전략 선택의 중요성

 

FIFO, SJF, Round Robin은 CPU 스케줄링을 이해하기 위한 가장 기초적이면서도 핵심적인 세 가지 모델이다. FIFO는 구현이 간단하지만 호위 효과로 인한 대기 시간 증가라는 한계를 지니고, SJF는 이론적으로 평균 대기 시간을 최소화할 수 있지만 실행 시간 예측의 어려움과 기아 현상이라는 현실적 제약을 안고 있다. Round Robin은 타임 슬라이스를 통해 여러 프로세스에 공평하게 CPU 기회를 배분함으로써 응답성을 확보하지만, 타임 슬라이스 설정에 따라 문맥 교환 오버헤드가 달라진다는 트레이드오프를 갖는다.

 

결국 어떤 알고리즘이 가장 우수한가라는 질문에는 절대적인 정답이 존재하지 않는다. 시스템이 처리량을 극대화하는 배치 작업 중심인지, 다수 사용자의 응답성을 중시하는 시분할 환경인지에 따라 적합한 스케줄링 전략이 달라지기 때문이다. 운영체제를 학습하거나 시스템을 설계하는 과정에서는 각 알고리즘의 원리와 장단점을 명확히 이해한 뒤, 실제 워크로드의 특성에 맞추어 스케줄링 정책을 선택하거나 다단계 큐와 같은 혼합 기법을 검토하는 것이 바람직한 접근이라 할 수 있다. CPU 스케줄링에 대한 이해는 운영체제의 동작 원리를 파악하는 출발점이자, 시스템 성능을 최적화하는 실질적인 기반이 된다는 점에서 꾸준히 살펴볼 가치가 있는 주제다.