컴퓨터 시스템의 심장이라 할 수 있는 중앙 처리 장치(CPU)는 한정된 자원입니다. 현대 운영체제는 수십, 수백 개의 프로세스가 동시에 실행되는 것처럼 보이게 하는 멀티태스킹 환경을 제공하지만, 실제로 특정 순간에 하나의 CPU 코어에서 실행될 수 있는 프로세스는 단 하나뿐입니다. 그렇다면 운영체제는 어떤 기준으로, 어떤 순서로 수많은 프로세스에게 이 소중한 CPU 자원을 배분하는 것일까요? 바로 이 질문에 대한 해답이 CPU 스케줄링입니다.
CPU 스케줄링은 단순히 프로세스를 줄 세우는 작업이 아닙니다. 이는 시스템 전체의 성능과 사용자 경험을 좌우하는 매우 정교하고 중요한 결정 과정입니다. 어떤 스케줄링 알고리즘을 선택하느냐에 따라 시스템의 처리율이 극대화될 수도 있고, 특정 프로세스가 무한정 대기 상태에 빠지거나, 사용자가 프로그램의 반응이 느리다고 느끼게 될 수도 있습니다. 따라서 스케줄링의 목표는 명확합니다. CPU를 최대한 효율적으로 사용하면서도, 모든 프로세스에게 공평한 기회를 제공하고, 사용자가 원하는 작업을 지연 없이 처리하는 것입니다. 이 글에서는 가장 기본적이면서도 모든 현대 스케줄링 알고리즘의 근간이 되는 세 가지 핵심 알고리즘, 즉 FCFS, SJF, Round Robin에 대해 심층적으로 분석하고, 각각의 장단점과 그 이면에 숨겨진 철학을 탐구해 보겠습니다.
스케줄링 알고리즘 평가의 척도
특정 알고리즘이 얼마나 '좋은지'를 판단하려면 객관적인 기준이 필요합니다. CPU 스케줄링에서는 주로 다음과 같은 지표를 사용하여 성능을 평가합니다.
- CPU 이용률 (CPU Utilization): 전체 시간 중 CPU가 실제로 작업을 처리한 시간의 비율입니다. 시스템이 유휴 상태에 빠지지 않고 최대한 바쁘게 일하게 만드는 것이 목표입니다. 100%에 가까울수록 이상적입니다.
- 처리율 (Throughput): 단위 시간당 완료된 프로세스의 개수입니다. 시스템이 얼마나 많은 작업을 처리할 수 있는지를 나타내는 지표로, 높을수록 좋습니다.
- 총 처리 시간 (Turnaround Time): 프로세스가 시스템에 제출된 순간부터 실행을 완전히 마칠 때까지 걸린 총 시간입니다. 이는 실제 CPU 사용 시간과 대기 시간을 모두 포함합니다. 사용자 관점에서 작업이 완료되기까지 걸리는 시간이므로 짧을수록 좋습니다. (총 처리 시간 = 종료 시간 - 도착 시간)
- 대기 시간 (Waiting Time): 프로세스가 준비 큐(Ready Queue)에서 CPU 할당을 기다리며 보낸 시간의 총합입니다. 이 시간 동안 프로세스는 아무 작업도 하지 못하고 대기만 하므로, 짧을수록 효율적입니다.
- 응답 시간 (Response Time): 프로세스가 준비 큐에 들어온 후 처음으로 CPU를 할당받기까지 걸린 시간입니다. 대화형 시스템(Interactive System)에서 사용자 입력에 대한 시스템의 '반응성'을 측정하는 중요한 지표이며, 짧을수록 사용자는 시스템이 빠르다고 느낍니다. (응답 시간 = 첫 실행 시간 - 도착 시간)
이러한 지표들은 종종 상충 관계(trade-off)에 있습니다. 예를 들어, 처리율을 극대화하려는 시도가 특정 프로세스의 대기 시간을 무한정 늘릴 수 있고, 모든 프로세스의 응답 시간을 줄이려다 보면 잦은 문맥 교환(Context Switching)으로 인해 전체적인 CPU 이용률이 떨어질 수도 있습니다. 좋은 스케줄링 알고리즘은 시스템의 목적(예: 일괄 처리 시스템, 대화형 시스템)에 맞게 이 지표들 사이에서 최적의 균형점을 찾는 것입니다.
1. 선입 선처리 (First-Come, First-Served, FCFS)
FCFS 알고리즘은 이름 그대로 가장 단순하고 직관적인 스케줄링 방식입니다. "먼저 온 손님부터 서비스한다"는 원칙에 따라, 준비 큐에 먼저 도착한 프로세스에게 CPU를 먼저 할당합니다. 이 알고리즘은 비선점형(Non-preemptive)으로, 일단 한 프로세스가 CPU를 점유하면 해당 프로세스가 자발적으로 CPU를 놓아주거나 (I/O 요청 등), 실행을 완전히 마칠 때까지 다른 프로세스는 CPU를 빼앗을 수 없습니다.
구현이 매우 간단하다는 장점이 있지만, FCFS는 치명적인 약점을 가지고 있습니다. 바로 호위 효과(Convoy Effect)입니다.
호위 효과: FCFS의 아킬레스건
호위 효과란 실행 시간이 매우 긴 프로세스 하나가 CPU를 독점하게 되어, 그 뒤에 대기하는 수많은 짧은 프로세스들이 하염없이 기다려야 하는 현상을 말합니다. 마치 고속도로 1차선을 느린 트럭 한 대가 막고 있어서 뒤따르는 수많은 승용차들이 거대한 정체 행렬을 이루는 것과 같습니다.
예를 들어, 다음과 같은 세 개의 프로세스가 거의 동시에 도착했다고 가정해 봅시다.
- P1: CPU Burst Time = 24ms
- P2: CPU Burst Time = 3ms
- P3: CPU Burst Time = 3ms
만약 P1, P2, P3 순서로 큐에 도착했다면, FCFS 스케줄링에 따른 간트 차트(Gantt Chart)는 다음과 같습니다.
P1 (24ms) | P2 (3ms) | P3 (3ms) +-------------------------------+----------+----------+ 0 24 27 30
이 경우 각 프로세스의 대기 시간은 다음과 같이 계산됩니다.
- P1의 대기 시간: 0ms (도착 즉시 실행)
- P2의 대기 시간: 24ms (P1이 끝날 때까지 대기)
- P3의 대기 시간: 27ms (P1과 P2가 끝날 때까지 대기)
평균 대기 시간: (0 + 24 + 27) / 3 = 17ms
하지만 만약 프로세스들이 P2, P3, P1 순서로 도착했다면 어떻게 될까요?
P2 (3ms) | P3 (3ms) | P1 (24ms) +----------+----------+-------------------------------+ 0 3 6 30
이때의 대기 시간은 크게 달라집니다.
- P2의 대기 시간: 0ms
- P3의 대기 시간: 3ms
- P1의 대기 시간: 6ms
평균 대기 시간: (0 + 3 + 6) / 3 = 3ms
단지 도착 순서가 바뀌었을 뿐인데, 시스템의 평균 대기 시간이 17ms에서 3ms로 극적으로 감소했습니다. 이 예시는 FCFS가 도착 순서에 따라 성능이 매우 불안정하며, 특히 긴 작업이 짧은 작업들을 막는 호위 효과에 얼마나 취약한지를 명확하게 보여줍니다. 이 때문에 FCFS는 현대적인 시분할 시스템에서는 단독으로 거의 사용되지 않으며, 다른 알고리즘과 결합하는 형태로만 그 명맥을 유지하고 있습니다.
2. 최단 작업 우선 (Shortest-Job-First, SJF)
SJF 알고리즘은 FCFS의 비효율성을 해결하기 위한 아이디어에서 출발합니다. "가장 빨리 끝날 수 있는 작업부터 처리하자"는 이 단순한 전략은, 주어진 프로세스 집합에 대해 평균 대기 시간을 최소화할 수 있다는 것이 수학적으로 증명된 최적의 알고리즘입니다. SJF는 준비 큐에 있는 프로세스들 중에서 다음 CPU 버스트(burst) 시간이 가장 짧은 것을 선택하여 실행합니다.
SJF는 두 가지 버전으로 나눌 수 있습니다.
- 비선점형 (Non-preemptive) SJF: FCFS와 마찬가지로, 일단 한 프로세스가 CPU를 할당받으면 자신의 CPU 버스트가 끝날 때까지 누구도 이를 빼앗을 수 없습니다.
- 선점형 (Preemptive) SJF: 현재 실행 중인 프로세스보다 더 짧은 CPU 버스트 시간을 가진 새로운 프로세스가 준비 큐에 도착하면, 운영체제는 즉시 현재 프로세스를 중단시키고 새로운 짧은 프로세스에게 CPU를 할당합니다. 이 선점형 SJF는 특별히 최소 잔여 시간 우선(Shortest-Remaining-Time-First, SRTF) 알고리즘이라고도 부릅니다.
SJF의 동작 예시 (비선점형 vs 선점형)
다음과 같은 프로세스들이 있다고 가정해 봅시다.
| 프로세스 | 도착 시간 (Arrival Time) | 실행 시간 (Burst Time) |
|---|---|---|
| P1 | 0 | 7ms |
| P2 | 2 | 4ms |
| P3 | 4 | 1ms |
| P4 | 5 | 4ms |
가) 비선점형 SJF
시간의 흐름에 따라 스케줄링을 추적해 봅시다.
- 시간 0: P1이 도착합니다. 준비 큐에는 P1만 있으므로 P1이 실행을 시작합니다.
- 시간 2: P2가 도착하지만, P1이 비선점형으로 실행 중이므로 P2는 대기해야 합니다.
- 시간 4: P3가 도착하지만, 여전히 P1이 실행 중이므로 P3도 대기합니다.
- 시간 5: P4가 도착하고, P1은 아직 실행 중이므로 P4도 대기합니다.
- 시간 7: P1의 실행이 종료됩니다. 이제 준비 큐에는 P2(4ms), P3(1ms), P4(4ms)가 있습니다. 이 중 실행 시간이 가장 짧은 P3가 선택되어 실행됩니다.
- 시간 8: P3의 실행이 종료됩니다. 이제 큐에는 P2(4ms)와 P4(4ms)가 남았습니다. 실행 시간이 같을 경우 FCFS 원칙에 따라 먼저 도착한 P2가 실행됩니다.
- 시간 12: P2의 실행이 종료되고, 마지막으로 남은 P4가 실행됩니다.
- 시간 16: 모든 프로세스가 종료됩니다.
간트 차트는 다음과 같습니다.
P1 (7ms) | P3 (1ms) | P2 (4ms) | P4 (4ms) +-------------+----------+-------------+-------------+ 0 7 8 12 16
평균 대기 시간 = ((7-0-7) + (12-2-4) + (8-4-1) + (16-5-4)) / 4 = (0 + 6 + 3 + 7) / 4 = 4ms
나) 선점형 SJF (SRTF)
같은 예시를 선점형 방식으로 실행하면 결과가 달라집니다.
- 시간 0: P1이 도착하여 실행을 시작합니다. (남은 시간: 7ms)
- 시간 2: P2가 도착합니다. P2의 실행 시간(4ms)이 P1의 남은 시간(5ms)보다 짧으므로, P1은 선점되고 P2가 실행을 시작합니다.
- 시간 4: P3가 도착합니다. P3의 실행 시간(1ms)이 현재 실행 중인 P2의 남은 시간(2ms)보다 짧으므로, P2는 선점되고 P3가 실행을 시작합니다.
- 시간 5: P3가 실행을 마칩니다. P4가 도착합니다. 이제 준비 큐에는 P1(남은 시간 5ms), P2(남은 시간 2ms), P4(실행 시간 4ms)가 있습니다. 이 중 남은 시간이 가장 짧은 P2가 다시 실행됩니다.
- 시간 7: P2가 실행을 마칩니다. 큐에는 P1(5ms)과 P4(4ms)가 있습니다. 남은 시간이 더 짧은 P4가 실행됩니다.
- 시간 11: P4가 실행을 마칩니다. 마지막으로 남은 P1이 실행됩니다.
- 시간 16: 모든 프로세스가 종료됩니다.
간트 차트는 다음과 같습니다.
P1 | P2 | P3 | P2 | P4 (4ms) | P1 (5ms) +----+----+----+----+-------------+-------------+ 0 2 4 5 7 11 16
평균 대기 시간 = ((16-0-7) + (7-2-4) + (5-4-1) + (11-5-4)) / 4 = (9 + 1 + 0 + 2) / 4 = 3ms
선점형 방식(SRTF)이 비선점형 방식보다 더 나은 평균 대기 시간을 보여줍니다. 이는 짧은 작업이 시스템에 들어왔을 때 즉각적으로 반응할 수 있기 때문입니다.
SJF의 현실적 한계: 예언가의 딜레마
SJF는 이론적으로는 최적이지만, 현실 세계에서는 치명적인 문제점을 안고 있습니다. 바로 "프로세스의 다음 CPU 버스트 시간을 어떻게 알 수 있는가?"라는 질문입니다. 운영체제는 프로세스가 앞으로 얼마나 오래 CPU를 사용할지 미리 알 수 없습니다. 이는 마치 점쟁이가 미래를 예측해야 하는 것과 같습니다.
이 문제를 해결하기 위해 실제 시스템에서는 과거의 CPU 버스트 기록을 바탕으로 미래를 '예측'하는 기법을 사용합니다. 가장 대표적인 것이 지수 평균(Exponential Averaging)입니다. 다음과 같은 공식을 사용합니다.
τn+1 = α * tn + (1 - α) * τn
τn+1: 다음에 예측할 CPU 버스트 시간tn: 가장 최근에 실제로 측정한 CPU 버스트 시간τn: 이전에 예측했던 CPU 버스트 시간α: 가중치 (0 ≤ α ≤ 1), 최근의 실제 측정값에 얼마나 비중을 둘지 결정
이 예측 기법은 어느 정도 효과적이지만 완벽할 수는 없습니다. 또한, SJF는 또 다른 문제인 기아 상태(Starvation)를 유발할 수 있습니다. 시스템에 짧은 작업들이 계속해서 들어온다면, 실행 시간이 긴 작업은 자신의 차례가 영원히 오지 않고 무한정 대기할 수 있습니다. 이러한 한계 때문에 순수한 SJF/SRTF 역시 현대 운영체제에서 그대로 사용되지는 않습니다.
3. 라운드 로빈 (Round Robin, RR)
라운드 로빈은 현대적인 시분할(Time-sharing) 시스템을 위해 설계된 가장 대표적인 스케줄링 알고리즘입니다. FCFS의 단순함과 선점형 방식의 이점을 결합한 형태로, 모든 프로세스가 공평하게 CPU를 나누어 사용하도록 하는 데 초점을 맞춥니다. RR은 각 프로세스에게 시간 할당량(Time Quantum 또는 Time Slice)이라는 작은 CPU 사용 시간을 할당합니다. 프로세스는 이 시간 할당량만큼 실행된 후, 작업이 끝나지 않았더라도 CPU를 내어놓고 준비 큐의 맨 뒤로 돌아가야 합니다.
RR의 성능은 이 '시간 할당량'의 크기에 매우 민감하게 좌우됩니다.
- 시간 할당량이 너무 큰 경우: 예를 들어 시간 할당량이 1000ms인데 대부분의 프로세스가 10ms 안에 끝난다면, 모든 프로세스는 할당량을 다 쓰기 전에 작업을 마칠 것입니다. 이 경우, 선점은 거의 일어나지 않으며 RR은 사실상 FCFS처럼 동작하게 됩니다.
- 시간 할당량이 너무 작은 경우: 예를 들어 시간 할당량이 1ms라면, 프로세스들은 매우 자주 교체됩니다. 이는 응답 시간을 단축시키는 효과가 있지만, 심각한 오버헤드를 유발합니다. 프로세스를 교체하는 문맥 교환(Context Switching)에는 레지스터 상태 저장 및 복원, 메모리 맵 변경 등 상당한 비용이 듭니다. 시간 할당량이 문맥 교환 시간과 비슷할 정도로 작아지면, CPU는 실제 작업보다 프로세스 교체에 더 많은 시간을 낭비하게 되어 시스템 전체의 효율성이 급격히 떨어집니다.
따라서 적절한 시간 할당량을 설정하는 것이 RR 스케줄링의 핵심 과제입니다. 일반적으로 대부분의 CPU 버스트가 한 번의 시간 할당량 안에 처리될 수 있도록 설정하는 것이 이상적입니다 (보통 10ms ~ 100ms 범위).
라운드 로빈의 동작 예시
FCFS 예시에서 사용했던 프로세스들을 시간 할당량(q) = 4ms로 RR 스케줄링해 봅시다.
- P1 (24ms), P2 (3ms), P3 (3ms)
간트 차트는 다음과 같이 그려집니다.
P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 +----+----+----+----+----+----+----+----+ 0 4 7 10 14 18 22 26 30
실행 흐름은 다음과 같습니다.
- P1이 4ms 실행 (남은 시간 20ms), 큐의 맨 뒤로 이동. 큐: [P2, P3, P1]
- P2가 3ms 실행 (작업 완료).
- P3가 3ms 실행 (작업 완료).
- P1이 4ms 실행 (남은 시간 16ms), 다시 뒤로 이동.
- 이 과정을 P1이 작업을 마칠 때까지 반복합니다.
RR의 평균 대기 시간은 보통 SJF보다 길지만, 응답 시간이 매우 빠르다는 결정적인 장점이 있습니다. 위 예시에서 P2는 4ms만에, P3는 7ms만에 첫 응답을 받습니다. FCFS의 첫 번째 예시에서 P2와 P3가 24ms, 27ms를 기다려야 했던 것과 비교하면 엄청난 개선입니다. 이러한 빠른 응답성 덕분에 RR은 여러 사용자가 동시에 상호작용하는 시스템에 가장 적합한 알고리즘으로 평가받습니다.
알고리즘 종합 비교 분석
이제 세 가지 알고리즘을 동일한 조건 하에 비교하여 그 특성을 명확히 해보겠습니다. SJF 예시에서 사용했던 프로세스 집합을 다시 가져와 모든 알고리즘에 적용해 보겠습니다.
| 프로세스 | 도착 시간 (Arrival Time) | 실행 시간 (Burst Time) |
|---|---|---|
| P1 | 0 | 7ms |
| P2 | 2 | 4ms |
| P3 | 4 | 1ms |
| P4 | 5 | 4ms |
1. FCFS 결과
P1 (7ms) | P2 (4ms) | P3 (1ms) | P4 (4ms) +-------------+-------------+----------+-------------+ 0 7 11 12 16
- 총 처리 시간: P1(7), P2(9), P3(8), P4(11) -> 평균 8.75ms
- 대기 시간: P1(0), P2(5), P3(7), P4(7) -> 평균 4.75ms
2. 비선점형 SJF 결과
P1 (7ms) | P3 (1ms) | P2 (4ms) | P4 (4ms) +-------------+----------+-------------+-------------+ 0 7 8 12 16
- 총 처리 시간: P1(7), P2(10), P3(4), P4(11) -> 평균 8ms
- 대기 시간: P1(0), P2(6), P3(3), P4(7) -> 평균 4ms
3. 선점형 SJF (SRTF) 결과
P1 | P2 | P3 | P2 | P4 (4ms) | P1 (5ms) +----+----+----+----+-------------+-------------+ 0 2 4 5 7 11 16
- 총 처리 시간: P1(16), P2(5), P3(1), P4(6) -> 평균 7ms
- 대기 시간: P1(9), P2(1), P3(0), P4(2) -> 평균 3ms
4. 라운드 로빈 (q=3ms) 결과
P1 | P2 | P3 | P1 | P4 | P2 | P1 +----+----+----+----+----+----+----+ 0 3 6 7 10 13 14 16
- 총 처리 시간: P1(16), P2(12), P3(3), P4(8) -> 평균 9.75ms
- 대기 시간: P1(9), P2(8), P3(2), P4(4) -> 평균 5.75ms
(RR의 계산은 문맥 교환이 빈번하여 복잡하므로, 각 프로세스가 큐에서 대기한 시간을 모두 합산하여 계산합니다.)
비교 요약표
| 지표 | FCFS | SJF (비선점) | SRTF (선점 SJF) | Round Robin |
|---|---|---|---|---|
| 평균 대기 시간 | 나쁨 (17ms/4.75ms) | 좋음 (4ms) | 최적 (3ms) | 보통 (5.75ms) |
| 평균 응답 시간 | 매우 나쁨 | 나쁨 | 좋음 | 매우 좋음 |
| 기아 상태 (Starvation) | 없음 | 발생 가능성 높음 | 없음 | |
| 구현 복잡도 | 매우 쉬움 | 어려움 (버스트 시간 예측 필요) | 보통 (타이머 인터럽트 필요) | |
| 시스템 종류 | 일괄 처리 시스템 | 일괄 처리, 특수 목적 시스템 | 대화형, 시분할 시스템 | |
결론: 완벽한 알고리즘은 없다
지금까지 살펴본 것처럼, 모든 상황에 완벽한 '최고의' CPU 스케줄링 알고리즘은 존재하지 않습니다. 각 알고리즘은 서로 다른 철학과 목표를 가지고 있으며, 특정 환경에서 강점을 보이는 대신 다른 환경에서는 약점을 드러냅니다.
- FCFS는 공평성과 단순함을 추구하지만, 효율성을 희생합니다.
- SJF/SRTF는 시스템 전체의 평균 대기 시간을 최소화하여 최고의 효율성을 추구하지만, 기아 상태를 유발하고 미래를 예측해야 하는 비현실적인 가정을 전제로 합니다.
- Round Robin은 모든 프로세스에게 공평한 기회와 빠른 응답성을 제공하여 사용자 경험을 극대화하지만, 잦은 문맥 교환으로 인한 오버헤드 때문에 총 처리 시간 면에서는 손해를 볼 수 있습니다.
현대의 범용 운영체제(Linux, Windows, macOS 등)는 이러한 기본 알고리즘들을 그대로 사용하지 않습니다. 대신, 이들의 장점을 결합하고 단점을 보완한 훨씬 더 정교하고 복잡한 스케줄링 기법을 사용합니다. 예를 들어, 다단계 큐 스케줄링(Multilevel Queue Scheduling)이나 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)은 프로세스의 특성(대화형 작업, 백그라운드 작업 등)에 따라 여러 개의 큐를 두고 각 큐마다 다른 스케줄링 알고리즘(예: 전면 큐는 RR, 후면 큐는 FCFS)을 적용합니다. 또한, 우선순위를 동적으로 조정하여 기아 상태를 방지하는 '노화(Aging)' 기법 등을 도입합니다.
결국 CPU 스케줄링의 역사는 시스템의 효율성과 사용자의 편의성이라는 두 마리 토끼를 잡기 위한 끊임없는 트레이드오프의 역사입니다. FCFS, SJF, RR이라는 세 가지 고전적인 알고리즘을 깊이 이해하는 것은 이러한 복잡한 현대 스케줄러의 근간을 파악하고, 우리가 매일 사용하는 컴퓨터 시스템이 어떻게 수많은 작업을 조화롭게 처리해내는지에 대한 근본적인 통찰을 얻는 첫걸음이 될 것입니다.
0 개의 댓글:
Post a Comment