운영체제의 스케줄링 알고리즘: 개념과 종류

스케줄링 알고리즘

1. CPU 스케줄링이란?

운영체제는 한정된 CPU 자원을 효율적으로 분배하기 위해 프로세스를 관리해야 한다.
이때, CPU가 어떤 프로세스를 실행할지 결정하는 과정이 **CPU 스케줄링(CPU Scheduling)**이다.

CPU는 한 번에 하나의 프로세스만 실행할 수 있으므로, 여러 프로세스를 공정하고 효율적으로 배치하는 방법이 필요하다.
운영체제는 특정 규칙을 기반으로 프로세스의 실행 순서를 결정하는데, 이를 CPU 스케줄링 알고리즘이라고 한다.

1-1. 스케줄링 알고리즘의 목표

• CPU 사용률(CPU Utilization) 극대화: CPU가 최대한 유휴 상태 없이 동작하도록 함
• 처리량(Throughput) 증가: 단위 시간당 더 많은 프로세스를 처리
• 응답 시간(Response Time) 최소화: 사용자 요청에 대한 응답 시간을 단축
• 대기 시간(Waiting Time) 감소: 프로세스가 대기 큐에서 머무는 시간을 최소화
• 공정성(Fairness) 유지: 모든 프로세스가 CPU를 공정하게 배분받도록 보장

---

2. 프로세스 스케줄링의 종류

운영체제에서 CPU 스케줄링은 크게 두 가지 방식으로 나뉜다:

• 비선점형(Non-Preemptive) 스케줄링
• 선점형(Preemptive) 스케줄링

이 두 방식의 차이는 CPU를 한 프로세스가 점유하는 방식에서 나타난다.

2-1. 비선점형(Non-Preemptive) 스케줄링

비선점형 스케줄링은 한 프로세스가 CPU를 할당받으면, 해당 프로세스가 자발적으로 종료하거나 대기 상태에 들어가기 전까지 CPU를 계속 점유하는 방식이다.

특징

• 실행 중인 프로세스는 스스로 종료할 때까지 CPU를 점유
• 운영체제가 강제로 프로세스를 중단하지 않음
• 대기 프로세스는 실행 중인 프로세스가 종료될 때까지 기다려야 함

장점

• 프로세스가 예측 가능한 환경에서 실행됨 (일정한 실행 흐름 유지)
• 프로세스 간 컨텍스트 스위칭(Context Switching) 비용이 적음
• 특정 작업(예: 배치 처리)에서 효율적

단점

• 실행 시간이 긴 프로세스가 먼저 실행되면, 짧은 프로세스가 오랫동안 대기할 가능성이 있음 (Convoy Effect, 호위 효과)
• 멀티태스킹 환경에서 비효율적 (CPU 자원이 특정 프로세스에 오래 점유됨)

사용되는 알고리즘

FCFS (First Come First Served, 선입선출)	먼저 도착한 프로세스가 먼저 실행됨
SJF (Shortest Job First, 최단 작업 우선) - 비선점형	실행 시간이 가장 짧은 프로세스부터 실행

예시: 비선점형 스케줄링 동작 과정

1. P1(실행 시간: 10ms), P2(실행 시간: 3ms), P3(실행 시간: 2ms) 순서로 도착
2. FCFS 방식이라면, P1 → P2 → P3 순서로 실행됨
3. P1이 오래 실행되므로 P2와 P3는 대기 시간이 증가함
4. Convoy Effect로 인해 전체 시스템 성능이 저하될 가능성이 있음

2-2. 선점형(Preemptive) 스케줄링

선점형 스케줄링은 운영체제가 특정 조건에 따라 CPU를 한 프로세스에서 다른 프로세스로 강제로 변경할 수 있는 방식이다.
즉, 실행 중인 프로세스가 있어도 운영체제가 필요하다고 판단하면 CPU를 다른 프로세스에 할당할 수 있다.

특징

• 운영체제가 CPU를 프로세스 간에 자유롭게 전환 가능
• 특정 프로세스가 **우선순위(Priority)**가 높다면, 현재 실행 중인 프로세스를 중단하고 CPU를 할당할 수 있음
• 멀티태스킹 환경에서 더 효율적

장점

• 여러 프로세스를 빠르게 전환하면서 반응 속도를 높일 수 있음
• 긴 작업과 짧은 작업이 섞여 있어도, 짧은 작업을 먼저 실행 가능
• 응급 작업(예: 실시간 시스템, 네트워크 패킷 처리 등)에 적합

단점

• 컨텍스트 스위칭(Context Switching) 비용이 증가하여, CPU 리소스 낭비 가능
• 우선순위가 낮은 프로세스가 너무 오랫동안 실행되지 못하는 Starvation(기아 현상) 발생 가능
• 일정한 실행 흐름이 보장되지 않아, 특정 애플리케이션에서 예상치 못한 동작이 발생할 수 있음

사용되는 알고리즘

Round Robin (RR, 라운드 로빈)	일정한 타임 슬라이스(Time Quantum)마다 프로세스를 교체
SJF (Shortest Job First, 최단 작업 우선) - 선점형	실행 시간이 짧은 프로세스를 우선 실행하되, 새로운 짧은 프로세스가 들어오면 실행 중인 프로세스를 중단하고 교체
Priority Scheduling (우선순위 스케줄링)	우선순위가 높은 프로세스가 먼저 실행됨

예시: 선점형 스케줄링 동작 과정

1. P1(우선순위: 3), P2(우선순위: 1), P3(우선순위: 2) 순서로 도착
2. 운영체제는 우선순위가 가장 높은 P2를 먼저 실행
3. P2 실행 도중, 우선순위가 더 높은 P4가 도착하면 P2는 중단되고 P4 실행
4. 선점형 스케줄링이므로 CPU를 높은 우선순위 프로세스에게 즉시 할당 가능

2-3. 비선점형 vs 선점형 비교

구분	비선점형 스케줄링	선점형 스케줄링
CPU 점유 방식	프로세스가 CPU를 점유하면 스스로 종료하기 전까지 유지	운영체제가 강제로 CPU를 회수 가능
운영 방식	프로세스가 끝날 때까지 다른 프로세스가 실행되지 않음	우선순위나 타임 슬라이스에 따라 CPU를 할당
장점	컨텍스트 스위칭 비용이 적고, 일정한 실행 흐름 유지	반응 속도가 빠르고, 멀티태스킹에 적합
단점	긴 프로세스가 먼저 실행되면 대기 시간이 길어질 수 있음 (Convoy Effect)	컨텍스트 스위칭 비용 증가, 우선순위 문제 발생 가능
사용 예시	FCFS, SJF (비선점형)	RR, Priority Scheduling, SJF (선점형)

---

3. 주요 CPU 스케줄링 알고리즘

3-1. FCFS (First Come First Served, 선입선출)

가장 간단한 스케줄링 방식으로, 먼저 도착한 프로세스부터 실행하는 방식이다.

특징

• 대기 큐에 먼저 들어온 순서대로 CPU를 할당받음
• 비선점형 방식이므로, 실행 중인 프로세스를 강제로 중단하지 않음

장점

• 구현이 간단하며, FIFO(First In First Out) 원칙을 따름
• 공정성(Fairness)이 보장됨

단점

• Convoy Effect (호위 효과) 발생 가능 → 실행 시간이 긴 프로세스가 먼저 도착하면 뒤의 짧은 프로세스들이 오래 기다려야 함

예시

프로세스도착 시간실행 시간

P1	0ms	8ms
P2	1ms	4ms
P3	2ms	2ms

• 실행 순서: P1 → P2 → P3
• P3는 실행 시간이 짧지만, P1이 끝날 때까지 8ms 동안 대기해야 함

3-2. SJF (Shortest Job First, 최단 작업 우선)

실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식이다.

특징

• 대기 중인 프로세스 중 실행 시간이 가장 짧은 프로세스를 먼저 실행
• 비선점형 / 선점형 둘 다 가능

장점

• 평균 대기 시간이 짧아 효율적
• 처리량(Throughput)이 증가

단점

• Starvation(기아 현상) 발생 가능 → 실행 시간이 긴 프로세스가 계속 뒤로 밀릴 수 있음
• 정확한 실행 시간을 예측하기 어려움

3-3. RR (Round Robin, 라운드 로빈)

모든 프로세스에 일정한 시간(Time Quantum, 타임 슬라이스)을 할당하는 방식이다.

특징

• 선점형 스케줄링 방식 → 정해진 시간 동안 실행 후, 다음 프로세스로 교체
• 각 프로세스가 공평한 CPU 사용 기회를 가짐

장점

• 모든 프로세스가 일정하게 CPU를 할당받아 공정성 유지
• 긴 프로세스가 짧은 프로세스를 블로킹하는 현상(Convoy Effect)이 없음

단점

• 타임 슬라이스가 너무 길면 FCFS와 비슷해짐
• 타임 슬라이스가 너무 짧으면 Context Switching 비용 증가

3-4. Priority Scheduling (우선순위 스케줄링)

각 프로세스에 우선순위(Priority)를 부여하고, 높은 우선순위를 가진 프로세스부터 실행하는 방식

특징

• 우선순위 값이 작을수록 높은 우선순위를 가짐 (낮은 숫자가 높은 우선순위)
• 선점형과 비선점형 모두 가능

장점

• 중요한 작업을 먼저 수행할 수 있음
• 다양한 환경에서 적용 가능

단점

• Starvation (기아 현상) 발생 가능 → 낮은 우선순위의 프로세스가 오랫동안 실행되지 않을 수 있음
• 해결 방법: Aging 기법(시간이 지남에 따라 우선순위를 높임)

---

4. 실제 운영체제에서 사용되는 스케줄링

4-1. Windows 운영체제

• Windows NT, XP, 10, 11에서는 우선순위 기반 스케줄링(Priority Scheduling)과 RR 방식을 혼합하여 사용
• 실시간 프로세스는 우선순위가 높은 상태에서 실행됨

4-2. Linux 운영체제

• **CFS (Completely Fair Scheduler, 완전 공정 스케줄러)**를 사용하여 모든 프로세스에 공정한 실행 기회를 제공

4-3. Android 운영체제

• 멀티스레드 환경을 고려한 우선순위 기반 스케줄링 사용