CPU 스케줄링 알고리즘 정리
운영체제는 여러 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정해야 한다.
CPU는 한정된 자원이기 때문에 모든 프로세스가 동시에 CPU를 사용할 수 없다.
따라서 운영체제는 일정한 기준에 따라 CPU를 사용할 프로세스를 선택한다.
이때 사용하는 방법을 CPU 스케줄링 알고리즘이라고 한다.
이번 글에서는 대표적인 CPU 스케줄링 방식들을 정리해보고자 한다.
스케줄링 계산에서 자주 쓰는 용어
CPU 스케줄링 문제를 풀 때는 보통 다음 값들이 주어진다.
도착 시간 Arrival Time
CPU 사용 시간 Burst Time
완료 시간 Completion Time
자주 계산하는 값은 반환 시간과 대기 시간이다.
반환 시간 Turnaround Time = 완료 시간 - 도착 시간
대기 시간 Waiting Time = 반환 시간 - CPU 사용 시간
반환 시간은 프로세스가 도착해서 완전히 끝날 때까지 걸린 전체 시간이다.
대기 시간은 그중에서 실제로 CPU를 사용하지 못하고 기다린 시간이다.
에를 들어 어떤 프로세스가 0초에 도착했고, 10초에 끝났으며, CPU를 실제 사용한 시간이 6초라면 다음과 같이 계산한다.
반환시간 = 10 - 0 = 10
대기시간 = 10 - 6 = 4
즉, 전체 10초 중 CPU를 사용한 6초를 제외한 4초 동안 기다린 것이다.
예제 프로세스
이 프로세스를 기준으로 여러 스케줄링에 대해 알아보고, 계산해보고자 한다.
프로세스 도착 시간 CPU 사용 시간
P1 0 8
P2 1 4
P3 2 2
P4 3 1
1. 선입 선처리 스케줄링 FCFS(First Come First Served)
FCFS는 먼저 도착한 프로세스부터 CPU에 할당하는 방식이다.
즉, 준비 큐에 먼저 들어온 프로세스가 먼저 실행된다.
FCFS는 비선점형 스케줄링으로, 한 프로세스가 CPU를 할당받으면, 그 프로세스가 끝날 때까지 CPU를 계속 사용한다.
예제에서는 프로세스 도착 순서가 P1 -> P2 -> P3 -> P4 이므로, 실행 순서도 동일한다.
0 8 12 14 15
| P1 | P2 | P3 | P4 |
각 프로세스의 완료 시간은 다음과 같다.
P1 완료 시간 = 8
P2 완료 시간 = 12
P3 완료 시간 = 14
P4 완료 시간 = 15
이제 반환 시간과 대기 시간을 계산해보자.
P1 반환 시간 = 8 - 0 = 8
P1 대기 시간 = 8 - 8 = 0
P2 반환 시간 = 12 - 1 = 11
P2 대기 시간 = 11 - 4 = 7
P3 반환 시간 = 14 - 2 = 12
P3 대기 시간 = 12 - 2 = 10
P4 반환 시간 = 15 - 3 = 12
P4 대기 시간 = 12 - 1 = 11
정리하면 다음과 같다.
프로세스 완료 시간 반환 시간 대기 시간
P1 8 8 0
P2 12 11 7
P3 14 12 10
P4 15 12 11
평균 대기 시간은 다음과 같다.
평균 대기 시간 = (0 + 7 + 10 + 11) / 4 = 7
FCFS의 가장 큰 부작용은 호위 효과이다.
호위 효과란 CPU 사용 시간이 긴 프로세스가 먼저 실행되면, 뒤에 있는 짧은 프로세스들이 오래 기다리게 되는 현상이다.
예를 들어 P1이 100초 동안 CPU를 사용한다면, 그 이후 프로세스들은 계속 기다려야 하는 것과 같다.
2. 최단 작업 우선 스케줄링 SJF(shortest job first)
SJF(Shortest Job First)는 CPU 사용 시간이 가장 짧은 프로세스부터 실행하는 방식이다.
이는 호위 효과를 방지할 수 있다.
SJF는 선점형과 비선점형 모두 가능하지만, 보통 기본적으로 비선점형 방식으로 설명한다.
비선점형 SJF에서는 한 번 CPU를 할당받은 프로세스는 끝날 때까지 실행된다.
예제를 보면 0초에는 P1만 도착해있다. 따라서 P1이 먼저 실행된다.
P1이 실행되는 동안 P2, P3, P4가 도착하지만, 비선점형이므로 P1이 끝날 때까지 계속 실행된다.
P1이 끝난 8초 뒤에는 P2, P3, P4가 모두 준비 큐에 있으며, 이때 CPU 사용 시간이 가장 짧은 순서대로 실행한다.
P4: 1초
P3: 2초
P2: 4초
따라서 실행 순서는 다음과 같다.
0 8 9 11 15
| P1 |P4 | P3 | P2 |
즉, 완료 시간은 다음과 같다.
P1 완료 시간 = 8
P4 완료 시간 = 9
P3 완료 시간 = 11
P2 완료 시간 = 15
반환 시간과 대기 시간을 계산해보자.
P1 반환 시간 = 8 - 0 = 8
P1 대기 시간 = 8 - 8 = 0
P2 반환 시간 = 15 - 1 = 14
P2 대기 시간 = 14 - 4 = 10
P3 반환 시간 = 11 - 2 = 9
P3 대기 시간 = 9 - 2 = 7
P4 반환 시간 = 9 - 3 = 6
P4 대기 시간 = 6 - 1 = 5
정리하면 다음과 같다.
프로세스 완료 시간 반환 시간 대기 시간
P1 8 8 0
P2 15 14 10
P3 11 9 7
P4 9 6 5
평균 대기 시간은 다음과 같다.
평균 대기 시간 = (0 + 10 + 7 + 5) / 4 = 5.5
SJF는 짧은 작업부터 처리하므로 FCFS보다 평균 대기 시간을 줄일 수 있다.
따라서 호위 효과를 완화할 수 있다.
다만 현실에서는 각 프로세스가 CPU를 얼마나 사용할지 정확히 알기 어렵다는 문제가 있다.
3. 라운드 로빈 스케줄링(Round Robin, RR)
Round Robin은 FCFS에 타임 슬라이스(time slice)를 추가한 방식으로, 선점형 스케줄링이다.
타임 슬라이스는 각 프로세스가 한 번에 CPU를 사용할 수 있는 정해진 시간이다.
보통 공학에서 Round Robin은 쭉 돌아가면서 차례대로 무엇인가 수행할 때 이름을 붙인다.
프로세스는 준비 큐에 들어온 순서대로 CPU를 사용하지만, 정해진 타임 슬라이스만큼만 CPU를 사용할 수 있다.
만약 그 시간 안에 작업을 끝내지 못하면, CPU를 반납하고 준비 큐의 맨 뒤로 들어간다.
예제에서 타임 슬라이스를 2초라고 할 때, 실행 흐름은 다음과 같다.
0 2 4 6 8 9 11 13 15
| P1 | P2 | P3 | P1 |P4 | P2 | P1 | P1 |
자세히 보면 다음과 같다.
P1: 0~2 실행, 남은 시간 6
P2: 2~4 실행, 남은 시간 2
P3: 4~6 실행, 완료
P1: 6~8 실행, 남은 시간 4
P4: 8~9 실행, 완료
P2: 9~11 실행, 완료
P1: 11~13 실행, 남은 시간 2
P1: 13~15 실행, 완료
완료 시간은 다음과 같다.
P1 완료 시간 = 15
P2 완료 시간 = 11
P3 완료 시간 = 6
P4 완료 시간 = 9
반환 시간과 대기 시간을 계산하면 다음과 같다.
P1 반환 시간 = 15 - 0 = 15
P1 대기 시간 = 15 - 8 = 7
P2 반환 시간 = 11 - 1 = 10
P2 대기 시간 = 10 - 4 = 6
P3 반환 시간 = 6 - 2 = 4
P3 대기 시간 = 4 - 2 = 2
P4 반환 시간 = 9 - 3 = 6
P4 대기 시간 = 6 - 1 = 5
정리하면 다음과 같다.
프로세스 완료 시간 반환 시간 대기 시간
P1 15 15 7
P2 11 10 6
P3 6 4 2
P4 9 6 5
평균 대기 시간은 이렇게 된다.
평균 대기 시간 = (7 + 6 + 2 + 5) / 4 = 5
Round Robin은 CPU를 돌아가면서 사용하기 때문에 특정 프로세스가 CPU를 독점하지 못한다.
하지만 타임 슬라이스가 너무 작으면 문맥 교환이 자주 발생한다.
반대로 타임 슬라이스가 너무 크면 FCFS와 비슷해진다.
따라서 적절한 타임 슬라이스를 정하는 것이 중요하다.
4. 최소 잔여 시간 우선 스케줄링 (Shortest Remaning Time; SRT)
SRT는 SJF의 선점형 버전이라고 볼 수 있다.
SJF는 CPU 사용 시간이 가장 짧은 프로세스를 먼저 실행한다.
SRT는 현재 남은 CPU 사용 시간이 가장 짧은 프로세스를 선택한다.
실행 중인 프로세스가 있더라도, 새로 도착한 프로세스의 남은 시간이 더 짧으면 CPU를 빼앗길 수 있다.
예제를 보자.
프로세스 도착 시간 CPU 사용 시간
P1 0 8
P2 1 4
P3 2 2
P4 3 1
0초에는 P1만 있으므로 P1이 실행된다.
1초에는 P2가 도착한다.
이때 P1의 남은 시간은 7초이고, P2의 CPU 사용 시간은 4초이다.
P2가 더 짧으므로 P1을 중단하고 P2를 실행한다.
2초에는 P3이 도착한다.
이때 P2의 남은 시간은 3초이고, P3은 2초이다.
P3이 더 짧으므로 P2를 중단하고 P3을 실행한다.
3초에 P4가 도착한다.
이때 P3의 남은 시간은 1초이고, P4도 1초이다.
남은 시간이 같으므로 기존에 실행 중이던 P3을 계속 실행한다고 하자.
실행 순서는 다음과 같다.
0 1 2 4 5 8 15
|P1|P2| P3 |P4| P2 | P1 |
완료 시간은 다음과 같다.
P1 완료 시간 = 15
P2 완료 시간 = 8
P3 완료 시간 = 4
P4 완료 시간 = 5
반환 시간과 대기 시간을 계산하면 다음과 같다.
P1 반환 시간 = 15 - 0 = 15
P1 대기 시간 = 15 - 8 = 7
P2 반환 시간 = 8 - 1 = 7
P2 대기 시간 = 7 - 4 = 3
P3 반환 시간 = 4 - 2 = 2
P3 대기 시간 = 2 - 2 = 0
P4 반환 시간 = 5 - 3 = 2
P4 대기 시간 = 2 - 1 = 1
정리하면 다음과 같다.
프로세스 완료 시간 반환 시간 대기 시간
P1 15 15 7
P2 8 7 3
P3 4 2 0
P4 5 2 1
평균 대기 시간은 이렇다.
평균 대기 시간 = (7 + 3 + 0 + 1) / 4 = 2.75
SRT는 짧은 작업을 빠르게 처리할 수 있어 평균 대기 시간을 줄이는 데 유리하다.
다만 새 프로세스가 도착할 때마다 남은 시간을 비교해야 하고, 실행 중인 프로세스가 자주 바뀔 수 있어 문맥 교환 오버헤드가 발생할 수 있다.
5. 우선순위 스케줄링
우선순위 스케줄링은 프로세스마다 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 방식이다.
우선순위가 같은 프로세스끼리는 보통 FCFS 방식으로 처리한다.
예를 들어 다음과 같은 프로세스가 있다고 하자.
프로세스 도착 시간 CPU 사용 시간 우선순위
P1 0 4 3
P2 0 3 1
P3 0 2 2
숫자가 작을 수록 우선순위가 높다고 가정하면 실행 순서는 P2 -> P3 -> P1 이다.
0 3 5 9
| P2 | P3 | P1 |
완료 시간은 다음과 같다.
P2 완료 시간 = 3
P3 완료 시간 = 5
P1 완료 시간 = 9
반환 시간과 대기 시간은 다음과 같다.
P1 반환 시간 = 9 - 0 = 9
P1 대기 시간 = 9 - 4 = 5
P2 반환 시간 = 3 - 0 = 3
P2 대기 시간 = 3 - 3 = 0
P3 반환 시간 = 5 - 0 = 5
P3 대기 시간 = 5 - 2 = 3
우선 순위 스케줄링은 중요한 작업을 먼저 처리할 수 있다는 장점을 가진다.
그러나 근본적인 문제가 있는데, 바로 우선순위가 낮은 프로세스는 계속 뒤로 밀릴 수 있는 기아(starvation) 현상이 발생한다는 것이다.
이를 해결하기 위한 방법이 aging이다.
aging은 오래 기다린 프로세스의 우선순위를 점차 높여주는 방식이다.
처음에는 우선순위가 낮더라도 오래 기다리면 점점 우선순위가 높아지므로 언젠가는 CPU를 할당받을 수 있다.
참고로 SJF와 SRT도 넓은 의미에서 우선순위 스케줄링으로 볼 수 있다.
CPU 사용 시간이 짧은 프로세스에게 높은 우선순위를 준 방식이라고 볼 수 있기 때문이다.
6. 다단계 큐 스케줄링 (Multilevel Que Scheduling)
다단계 큐 스케줄링(Multilevel Queue Scheduling)은 우선순위별로 준비 큐를 여러 개 두는 방식이다.
하나의 준비 큐만 사용하는 것이 아니라 프로세스 성격이나 우선순위에 따라 여러 큐로 나누어 관리한다.
예를 들어 다음과 같이 나눌 수 있다.
높은 우선순위 큐
중간 우선순위 큐
낮은 우선순위 큐
운영체제는 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리한다.
가장 높은 큐가 비어 있으면 그 다음 우선순위 큐를 확인한다.
1순위 큐가 비어 있지 않으면 1순위 큐 실행
1순위 큐가 비어 있으면 2순위 큐 실행
2순위 큐도 비어 있으면 3순위 큐 실행
큐를 여러개 두면 우선순위별로 프로세스를 관리하기 쉽고, 큐마다 서로 다른 스케줄링 방식을 적용할 수도 있다.
예를 들어 높은 우선순위 큐는 Round Robin을 사용하고, 낮은 우선순위 큐는 FCFS를 사용할 수 있다.
또는 큐마다 타임 슬라이스를 다르게 줄 수 있다.
하지만 다단계 큐 스케줄링에는 근본적 문제가 있는데, 바로 프로세스가 큐 사이를 이동할 수 없다는 것이다.
처음 낮은 우선순위 큐에 들어간 프로세스는 계속 낮은 우선순위 큐에 머무른다.
따라서 높은 우선순위 큐에 프로세스가 계속 들어오면 낮은 우선순위 큐의 프로세스는 실행되지 못할 수 있다(=기아 현상).
7. 다단계 피드백 큐 스케줄링 (Multilevel feedback queue scheduling)
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)은 다단계 큐 스케줄링을 보완한 방식이다.
가장 큰 차이는 프로세스가 큐 사이를 이동할 수 있다는 점이다.
다단계 큐에서는 한 번 들어간 큐에서 이동할 수 없기 때문에 기아 현상이 발생할 수 있었다.
다단계 피드백 큐에서는 이 문제를 줄이기 위해 프로세스 행동에 따라 우선순위를 조정한다.
기본 흐름은 다음과 같다.
새롭게 준비 상태가 된 프로세스는 가장 우선순위가 높은 큐에 들어간다.
이 프로세스는 정해진 타임 슬라이스만큼 CPU를 사용한다.
만약 그 시간 안에 작업이 끝나면 그대로 종료된다.
하지만 타임 슬라이스를 모두 사용했는데도 작업이 끝나지 않았다면, CPU를 오래 사용하는 프로세스라고 판단하여 그 다음 우선순위 큐로 내려간다.
즉, CPU를 오래 쓰는 프로세스는 점점 우선순위가 낮아진다.
반대로 낮은 우선순위 큐에서 너무 오래 기다리는 프로세스는 aging을 적용해 우선순위를 높일 수 있다.
따라서 다단계 피드백 큐는 다음 두가지를 모두 고려한다.
CPU를 오래 쓰면 우선순위를 낮춘다.
너무 오래 기다리면 우선순위를 높인다.
이 방식은 CPU를 짧게 사용하는 대화형 프로세스에는 빠른 응답을 제공하고, CPU를 오래 사용하는 프로세스는 낮은 우선순위에서 처리하도록 만든다.
따라서 실제 운영체제의 CPU 스케줄링 방식으로 자주 언급된다.
정리
각 스케줄링 알고리즘을 정리하면 다음과 같다.
FCFS
- 먼저 도착한 프로세스 먼저 실행
- 비선점형
- 단순하지만 호위 효과 발생 가능
SJF
- CPU 사용 시간이 가장 짧은 프로세스 먼저 실행
- 보통 비선점형으로 설명
- 평균 대기 시간을 줄일 수 있음
- CPU 사용 시간을 미리 알아야 한다는 한계가 있음
Round Robin
- FCFS + 타임 슬라이스
- 선점형
- 정해진 시간만큼 돌아가며 CPU 사용
- 타임 슬라이스가 너무 작으면 문맥 교환 오버헤드 증가
SRT
- 남은 CPU 사용 시간이 가장 짧은 프로세스 먼저 실행
- SJF의 선점형 버전
- 평균 대기 시간을 줄이는 데 유리
- 문맥 교환이 자주 발생할 수 있음
우선순위 스케줄링
- 우선순위가 높은 프로세스 먼저 실행
- 기아 현상 발생 가능
- aging으로 보완 가능
다단계 큐 스케줄링
- 우선순위별로 여러 준비 큐 사용
- 큐마다 다른 스케줄링 적용 가능
- 큐 간 이동이 어려워 기아 현상 발생 가능
다단계 피드백 큐 스케줄링
- 큐 간 이동이 가능한 다단계 큐
- CPU를 오래 쓰면 우선순위 하락
- 오래 기다리면 우선순위 상승
- 실제 운영체제 스케줄링 방식으로 자주 언급됨
계산 문제에서는 다음 순서로 푼다.
1. 실행 순서를 정한다.
2. 간트 차트를 그린다.
3. 각 프로세스의 완료 시간을 구한다.
4. 반환 시간을 구한다.
반환 시간 = 완료 시간 - 도착 시간
5. 대기 시간을 구한다.
대기 시간 = 반환 시간 - CPU 사용 시간
6. 평균 대기 시간이나 평균 반환 시간을 계산한다.
'STUDY' 카테고리의 다른 글
| [운영체제] 스레드란? 멀티 프로세스와 멀티 스레드 비교 (0) | 2026.05.27 |
|---|---|
| [운영체제] 프로세스 상태와 프로세스 계층 구조 정리 (0) | 2026.05.27 |
| [운영체제] 프로세스 개요: PCB, 문맥 교환, 메모리 영역 정리 (0) | 2026.05.27 |
| [운영체제] 프로세스 동기화: 실행 순서 제어와 상호 배제 (0) | 2026.05.27 |
| [운영체제] 스케줄링 큐와 프로세스 상태 변화 정리 (0) | 2026.05.27 |