8편. CPU 스케줄링 알고리즘 완전 정복 – 공정성, 속도, 우선순위의 비밀
8편. CPU 스케줄링 알고리즘 완전 정복 – 공정성, 속도, 우선순위의 비밀
📚 목차
1. CPU 스케줄링이 필요한 이유 - 왜 순서를 정해야 할까?
2. 주요 스케줄링 알고리즘 4가지 - FCFS, SJF, RR, Priority
3. 예제로 비교하는 작동 흐름 - 하나의 시나리오로 모두 분석
4. 실전 운영체제에서는 어떻게 쓸까? (Ubuntu vs Windows)
✔ 마무리 - 스케줄링을 이해하는 건 왜 중요할까?
하나의 컴퓨터에서 수십 개의 프로그램이 동시에 실행되는 오늘날, 우리는 운영체제가 알아서 똑똑하게 처리해준다고 생각하기 쉽습니다.
하지만 실제로는, 하나의 CPU가 한 번에 하나의 작업만 처리할 수 있기 때문에, 운영체제는 끊임없이 판단해야 합니다.
“지금 어떤 프로세스를 먼저 실행할까?”
“누구에게 CPU를 얼마나 할당할까?”
이러한 판단을 빠르게 내리고, 효율적으로 실행 순서를 조정하는 기술이 바로 CPU 스케줄링 알고리즘입니다.
스케줄링 알고리즘은 단순히 기술적인 룰을 넘어서, 시스템이 공정하고 빠르게 동작하도록 만들며, 사용자 경험과 전체 성능을 좌우하는 핵심 원리입니다.
이번 글에서는 스케줄링이 왜 필요한지를 다양한 예시와 함께 살펴보고, 대표적인 스케줄링 방식(FSCS, SJF, RR, Priority)을
그림과 시나리오를 통해 직관적으로 이해할 수 있도록 정리하였습니다.
1. CPU 스케줄링이 필요한 이유 – 왜 순서를 정해야 할까?
현대의 컴퓨터는 사용자에게 "동시에 여러 작업이 진행되고 있는 것처럼" 보이도록 동작합니다.
실제로는 하나의 CPU가 빠르게 여러 프로세스를 전환하면서 마치 여러 작업을 병렬로 처리하는 것처럼 연출하는 것입니다.
이처럼 하나의 CPU에 여러 프로세스가 동시에 실행을 요구하는 상황은 매우 일반적입니다.
예를 들어, 다음과 같은 상황을 생각해 봅시다.
당신이 노트북으로 유튜브 영상을 보며, 동시에 문서를 편집하고, 백신 프로그램이 실시간 검사를 수행하는 중이며, 클라우드 동기화 서비스가 파일을 업로드하고 있다고 가정해 보겠습니다. 이 모든 작업은 CPU 자원을 필요로 합니다.
이때 운영체제가 어떤 기준 없이 무작위로 프로세스를 처리한다면 어떤 일이 벌어질까요?
🔸유튜브 영상이 끊기고,
🔸문서 작성 중 입력한 글자가 지연되며,
🔸시스템 전체가 느려져 사용자는 답답함을 느끼게 될 것입니다.
즉, 운영체제가 어떤 프로세스를 언제 실행할지 판단하는 규칙이 없다면, 시스템은 효율을 잃고 사용자의 경험은 급격히 나빠질 수밖에 없습니다.
이러한 문제를 해결하고, 다양한 작업이 공존하는 환경에서도 시스템이 부드럽게 동작하도록 하는 핵심 기술이 바로 스케줄링 알고리즘(Scheduling Algorithm)입니다.
✔️ 쉽게 이해하는 비유: 병원 접수 시스템
스케줄링을 병원 접수와 비교해 보면 더욱 명확해집니다.
🔸FCFS 방식은 선착순 번호표대로 진료를 보는 방식입니다.
🔸SJF 방식은 증상이 가장 가벼운 환자부터 진료하는 방식입니다.
🔸우선순위 스케줄링은 응급환자를 가장 먼저 진료하는 방식입니다.
🔸Round Robin은 진료실을 여러 개 열고 모든 환자에게 조금씩 시간을 나눠주는 방식과 비슷합니다.
이러한 방식이 없다면, 병원은 접수 순서도 중요도도 없이 무작위로 환자를 진료하게 될 것이며, 환자들의 불만이 폭주하게 되겠지요.
운영체제도 마찬가지입니다. 스케줄링이 없다면 시스템은 병목 현상, 사용자 불편, 자원 낭비 등으로 혼란스러워질 수 있습니다.
2. 주요 스케줄링 알고리즘 4가지 – FCFS, SJF, RR, Priority
아래는 실제 운영체제에서 널리 쓰이는 대표적인 스케줄링 방식입니다. 각 방식은 서로 다른 장단점과 적용 시나리오를 가집니다.
🔷 FCFS (First-Come, First-Served) - 선착순 처리
🔸 개념: 프로세스가 도착한 순서대로 처리하는 가장 단순한 방식입니다. 누구든 먼저 도착하면 먼저 실행됩니다.
🔸 장점: 구현이 매우 간단하여 거의 모든 시스템에서 기본적으로 사용 가능
🔸 단점: 먼저 도착한 작업이 너무 오래 걸리는 경우, 뒤따라온 짧은 작업들이 모두 기다려야 하는 Convoy Effect(호위 효과) 발생
✔️ FCFS 처리 예시
예시 조건으로는 세 개의 프로세스가 존재합니다.
| 프로세스 | 도착시간 | 실행 시간 |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
▸ P1은 0초에 도착하여 8초 동안 실행됩니다.
▸ P2는 1초에 도착하고 실행 시간은 4초입니다.
▸ P3는 2초에 도착하며 실행 시간은 2초입니다.
FCFS(First-Come, First-Served) 방식에서는 도착 순서에 따라 프로세스를 처리하므로, 먼저 도착한 P1이 가장 먼저 실행되고, 이후에 도착한 P2와 P3는 순서대로 기다리게 됩니다.
이와 같이 P1이 8초 동안 CPU를 독점하는 동안, 뒤에 도착한 짧은 작업(P2, P3)조차 실행되지 못하고 대기하게 됩니다.
이로 인해 전체 시스템 응답이 지연되는 문제가 발생하며, 이를 Convoy Effect(호위 효과)라고 부릅니다.
즉, FCFS 방식은 구조가 단순하고 구현은 쉬우나, 긴 작업 하나가 전체 흐름을 느리게 만들 수 있다는 단점을 가지고 있습니다.
🔷 SJF (Shortest Job First) – 짧은 작업 우선
🔸 개념: 현재 실행 대기 중인 프로세스 중에서 실행 시간이 가장 짧은 작업부터 우선 처리합니다.
🔸 장점: 평균 대기 시간이 이론상 가장 낮아 매우 효율적
🔸 단점: 긴 작업은 계속 뒤로 밀릴 수 있어 기아(Starvation) 현상이 발생할 수 있음
✔️ SJF 처리 예시
예시 조건으로는 세 개의 프로세스가 존재합니다.(FCFS와 동일)
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
▸ P1은 0초에 도착하여 8초 동안 실행됩니다.
▸ P2는 1초에 도착하고 실행 시간은 4초입니다.
▸ P3는 2초에 도착하며 실행 시간은 2초입니다.
SJF(Shortest Job First) 스케줄링 방식은 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리합니다.
이 알고리즘은 프로세스들이 모두 대기 상태에 있는 시점에서 가장 짧은 작업을 먼저 실행함으로써 평균 대기 시간을 최소화하는 데 초점을 둡니다.
이 예시에서는, 도착 시점을 고려했을 때 실행 시간이 가장 짧은 P3가 먼저 실행되고, 다음으로 P2, 마지막으로 긴 작업인 P1이 실행됩니다.
'이처럼 SJF 알고리즘은 시스템 전체의 평균 대기 시간과 평균 반환 시간을 효과적으로 줄여줄 수 있습니다.
그러나 이 방식의 단점도 존재합니다.
긴 작업(P1)은 짧은 작업들이 먼저 처리되는 동안 대기하게 되며, 이러한 현상이 반복되면 긴 작업이 계속 뒤로 밀려 실행되지 못하는 '기아(Starvation)' 문제가 발생할 수 있습니다.
따라서 실제 운영체제에서는 이러한 기아 문제를 방지하기 위해 우선순위 상승(aging) 등의 보완 기법과 함께 사용되는 경우가 많습니다.
🔷 RR (Round Robin) – 돌아가며 처리
🔸 개념: 모든 프로세스에 일정한 시간 조각(Time Quantum)을 부여하고, 순서대로 돌아가면서 처리합니다. 시간이 다 되면 다음 프로세스로 전환됩니다.
🔸 장점: 사용자 응답성이 뛰어나며, 모든 프로세스가 공정하게 실행 기회를 가짐
🔸 단점: 타임퀀텀이 너무 짧으면 컨텍스트 스위칭 오버헤드가 커지고, 너무 길면 FCFS처럼 느껴질 수 있음
✔️ RR 처리 예시 (타임퀀텀: 2초)
예시 조건으로는 세 개의 프로세스가 존재합니다.(FCFS와 동일)
| 프로세스 | 도착 시간 | 실행 시간 |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
▸ P1은 0초에 도착하여 8초 동안 실행됩니다.
▸ P2는 1초에 도착하고 실행 시간은 4초입니다.
▸ P3는 2초에 도착하며 실행 시간은 2초입니다.
▸ 타임퀀텀(Time Quantum): 2초
Round Robin 스케줄링은 각 프로세스에게 동일한 시간 조각을 순차적으로 할당하여 실행하는 방식입니다.
이 알고리즘의 핵심은 공정성입니다. 모든 프로세스가 일정 시간마다 CPU를 사용할 수 있도록 보장함으로써, 특정 작업이 CPU를 독점하지 못하게 합니다.
이와 같이 Round Robin 방식은 모든 프로세스가 짧은 간격으로 CPU를 사용할 수 있게 하여,
사용자 응답 속도를 개선하고 대기 시간을 과도하게 늘리지 않도록 합니다.
특히 사용자 인터페이스나 터미널 입력처럼 빠른 반응이 필요한 환경에 적합한 방식입니다.
단, 타임퀀텀이 너무 짧으면 컨텍스트 스위칭 오버헤드가 증가하고, 너무 길면 FCFS와 유사해지는 단점이 있으므로, 시스템 특성에 맞는 적절한 설정이 중요합니다.
🔷 Priority Scheduling – 우선순위 기반 처리
🔸 개념: 각 프로세스에 우선순위(Priority)를 부여하고, 높은 우선순위를 가진 프로세스를 먼저 실행합니다.
🔸 장점: 중요하거나 긴급한 작업을 빠르게 처리 가능 (예: 시스템 백업, 인터럽트 응답 등)
🔸 단점: 낮은 우선순위 프로세스가 계속 밀려 실행되지 않는 기아 현상 발생 가능
✔️ Priority 처리 예시
| 프로세스 | 우선순위(낮을수록 높음) |
| P2 | 1 |
| P3 | 2 |
| P1 | 3 |
▸ P2: 우선순위 1 (가장 높음)
▸ P3: 우선순위 2
▸ P1: 우선순위 3 (가장 낮음)
가장 높은 우선순위를 가진 P2가 먼저 실행되며, 그 다음은 P3, 마지막으로 P1이 실행됩니다.
이처럼 우선순위 스케줄링은 중요하거나 긴급한 작업을 신속하게 처리할 수 있는 장점이 있습니다.
하지만 한편으로는, P1처럼 우선순위가 낮은 프로세스는 계속해서 뒤로 밀려 실행되지 않을 가능성이 있습니다.
이런 상황이 지속되면 기아(Starvation) 문제가 발생할 수 있으며, 이를 방지하기 위해 aging(시간이 지날수록 우선순위를 조금씩 높이는 기법) 등의 보완 전략이 함께 사용됩니다.
이처럼 각각의 스케줄링 알고리즘은 시스템의 목적(공정성, 성능, 응답성 등)에 따라 적합한 상황이 달라집니다.
실제 운영체제에서는 이러한 알고리즘들을 조합하거나 발전시킨 하이브리드 스케줄러를 사용하여 현실적인 환경을 효율적으로 관리합니다.
3. 예제로 비교하는 작동 흐름 – 하나의 시나리오로 모두 분석
다음은 도착 시간과 실행 시간이 서로 다른 4개의 프로세스를 대상으로 스케줄링 알고리즘이 어떻게 동작하는지를 시각적으로 비교한 예입니다.
| 프로세스 | 도착시간 | 실행시간 |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
| P4 | 3 | 1 |
✔️ FCFS (선착순)
🔸실행 순서: P1 → P2 → P3 → P4
🔸 P1이 0초에 도착하고 8초 동안 실행되므로, 나머지 프로세스는 순서대로 대기하게 됩니다.
✔️ SJF (최단 작업 우선)
🔸 실행 순서: P4 → P3 → P2 → P1
🔸 P4는 실행 시간이 1초로 가장 짧아 가장 먼저 처리되며, 이후 P3, P2 순으로 실행됩니다.
✔️ RR (타임퀀텀: 2초 기준)
🔸 실행 흐름: P1(2초) → P2(2초) → P3(2초) → P4(1초) → P1(2초) → P2(2초) → P1(4초)
🔸 모든 프로세스가 고르게 CPU를 사용하는 방식입니다.
4. 실전 운영체제에서는 어떻게 쓸까? (Ubuntu vs Windows)
운영체제마다 사용하는 스케줄러의 방식은 다르며, 시스템의 목적과 환경에 따라 최적화된 전략을 채택합니다.
대표적으로 Ubuntu는 CFS(Completely Fair Scheduler), Windows는 MLFQ(Multilevel Feedback Queue) 방식의 스케줄러를 사용합니다.
✔️ Ubuntu (Linux 커널 기반): CFS – Completely Fair Scheduler
Ubuntu는 Linux 커널 기반의 운영체제로, 기본적으로 CFS(Completely Fair Scheduler)라는 스케줄러를 사용합니다.
이름 그대로, "모든 프로세스에게 공평한 실행 기회를 제공"하는 것이 핵심 목표입니다.
CFS는 각 프로세스가 얼마나 오랫동안 CPU를 사용했는지를 추적하기 위해 가상 런타임이라는 값을 관리합니다.
🔸 CPU를 덜 사용한 프로세스일수록 더 빨리 실행되며,
🔸 반대로 CPU를 많이 사용한 프로세스는 잠시 대기합니다.
즉, 프로세스 간 CPU 점유 시간을 균등하게 유지하려는 알고리즘입니다.
🔸특징 요약
▸ 높은 사용자 반응성을 유지하며, GUI 환경에서 부드럽게 동작
▸ 배치 작업(대용량 연산)과 인터랙티브 작업(마우스 클릭 등) 간 균형 있는 처리
▸ 실시간 환경에는 부적합할 수 있으나, 범용적으로 매우 안정적
✔️ Windows: MLFQ – Multilevel Feedback Queue Scheduler
Windows는 MLFQ(멀티레벨 피드백 큐) 방식의 스케줄러를 채택하고 있으며, 다양한 우선순위 레벨과 동적 우선순위 조정 메커니즘을 갖춘 적응형 스케줄링 방식입니다.
Windows는 다음과 같은 전략으로 스케줄링을 수행합니다.
🔸 처음에는 높은 우선순위 큐에 배치
🔸 CPU를 많이 사용하는 프로세스는 자동으로 우선순위 하락
🔸 반대로, 대기 시간이 길거나 응답을 기다리는 프로세스는 우선순위가 올라감
이러한 구조는 사용자 프로그램, 시스템 서비스, 백그라운드 작업이 함께 실행될 때 효율적인 CPU 사용을 유도합니다.
🔸 특징 요약
▸ GUI 응용프로그램에 높은 우선순위를 부여해 부드러운 사용자 인터페이스 유지
▸ 우선순위 자동 조정 기능으로 기아 현상(Starvation)을 방지
▸ 실시간 서비스 및 게임 등에도 안정적인 스케줄링 제공
✔ 마무리– 스케줄링을 이해하는 건 왜 중요할까?
스케줄링 알고리즘은 단순히 작업 순서를 정하는 기술이 아닙니다.
시스템의 성능, 반응성, 공정성을 결정짓는 핵심 원리입니다.
🔸FCFS는 단순하지만 비효율을 초래할 수 있고
🔸SJF는 빠른 평균 응답을 제공하지만 기아 문제가 있으며
🔸RR은 공정하되 설정이 중요하고
🔸Priority는 실무 적용도가 높지만 균형이 필요합니다
실제 운영체제는 이들을 혼합한 하이브리드 전략을 사용합니다.
개발자는 이를 이해함으로써 시스템 병목 분석, 성능 튜닝, 우선순위 제어 등 다양한 실무 작업에서 효과적으로 활용할 수 있습니다.
※ 게시된 글 및 이미지 중 일부는 AI 도구의 도움을 받아 생성되거나 다듬어졌습니다.