[OS] CPU 스케줄링의 원리와 알고리즘: FIFO, SJF, STCF, RR 비교와 I/O 통합

 

 

스케줄링 문제의 핵심: 어떻게 scheduling policy를 개발할 것인가?

CPU virtualizing는 프로세스(추상화)와 limit direct execution(메커니즘)을 통해 여러 CPU가 있는 것처럼 보이게 합니다. 여기서 스케줄링(Scheduling)은 OS의 핵심적인 policy에 해당합니다.

스케줄링 문제는 다음과 같습니다:

• 여러 개의 작업이 실행을 기다리고 있습니다. (예: K개의 작업)
• 하나 또는 여러 개의 CPU가 존재합니다. (예: N ≥ 1개의 CPU)

스케줄링 정책은 이러한 상황에서 "어떤 작업을 어떤 CPU에, 얼마나 오랫동안 할당할 것인가?"를 결정하는 것입니다. 여기서 작업(jobs)은 프로세스, 스레드 등 스케줄링 대상이 될 수 있는 모든 것을 의미합니다.

스케줄링 메커니즘은 정책을 실행하기 위한 기술적 도구입니다. 주요 메커니즘에는 Context Switch과 Process State Queues가 있습니다. context switch은 실제로 프로세스를 전환하는 기술이고, Process State Queues는 실행 대기 중인 작업들을 관리하는 자료구조입니다.

 

 

Workload Assumptions

OS 스케줄러 policy을 배우기 전에, 시스템에서 실행되는 프로세스(작업 부하)에 대해 다음과 같은 다섯 가지 가정을 합니다.

1. 모든 작업은 동일한 실행 시간을 가집니다.  (작업의 실행 시간이 모두 같다고 가정하여, 작업 길이의 변수를 제거합니다.)
2. 모든 작업은 동시에 도착합니다. (시간에 따른 작업의 도착 순서를 고려할 필요 없이 문제를 단순화합니다.)
3. 일단 시작된 작업은 완료될 때까지 실행됩니다. (작업이 일단 시작되면 중단되지 않는다고 가정하여, 선점(preemption)의 복잡성을 배제합니다.)
4. 모든 작업은 CPU만 사용합니다. ( I/O 작업으로 인해 프로세스가 대기하는 상황을 제외합니다.)
5. 각 작업의 실행 시간은 미리 알고 있습니다. (이 가정은 가장 강력하면서도 비현실적인 가정으로, 스케줄러가 완벽한 결정을 내릴 수 있게 합니다.)

이러한 가정들은 현실의 운영체제 환경과는 거리가 멀지만, 스케줄링의 기본 원리를 이해하는 데 중요한 토대가 됩니다. 앞으로 이 가정들을 하나씩 완화하며 현실적인 스케줄링 정책들을 배우게 됩니다

 

 

 

Scheduling Metrics

스케줄링 알고리즘의 효과를 측정하기 위해 우리는 Scheduling Metrics를 사용합니다. 이 지표들을 통해 서로 다른 스케줄링 정책들을 비교하고 어떤 정책이 더 나은 성능을 보이는지 판단할 수 있습니다.

 

1. Turnaround Time

turnaround time은 주요 성능 지표입니다. 이는 작업이 시스템에 도착한 순간부터 완료될 때까지 걸린 전체 시간을 측정합니다.

turnaround time이 짧을수록 작업이 더 빨리 완료되므로, 성능이 더 좋다고 평가합니다.

 

2. 공정성 (Fairness)

공정성은 또 다른 중요한 지표이지만, 성능과는 종종 상충됩니다. 공정한 스케줄러는 모든 작업이 CPU 자원을 적절하게 할당받도록 보장하여, 특정 작업이 자원을 전혀 얻지 못하고 대기하는 현상(기아 현상)을 막습니다. 예를 들어, 스케줄러가 짧은 작업 몇 개를 우선적으로 처리하여 전체적인 turnaround time을 낮출 수 있지만, 이로 인해 오랜 시간이 걸리는 작업이 계속 밀린다면 이는 공정하지 않다고 볼 수 있습니다. 이처럼 스케줄링에서는 성능과 공정성 사이의 균형을 맞추는 것이 중요합니다.

 

 

---

 

FIFO(First-In, First-Out) 스케줄링

FIFO(선입선출) 스케줄링은 가장 기본적인 알고리즘으로, 먼저 도착한 작업부터 순서대로 처리하는 방식입니다. 간단하고 구현하기 쉽다는 장점이 있습니다. 5가지 가정이 모두 충족될때는 가장 최적이지만, 가정이 무너진다면 최적이 아니게 됩니다. 

 

FIFO는 FCFS(First Come, First Served)라고도 불리며, 대기열에 들어온 순서대로 작업을 실행합니다. 한 작업이 시작되면 완료될 때까지 실행되며, 그 다음 작업이 시작됩니다.

 

예시 1: 모든 작업의 실행 시간이 동일할 때

A, B, C 세 개의 작업이 순서대로 도착하고, 각각 10초가 걸린다고 가정해 봅시다.

• A는 0초에 시작하여 10초에 완료됩니다.
• B는 10초에 시작하여 20초에 완료됩니다.
• C는 20초에 시작하여 30초에 완료됩니다.

평균 turnaround time은 (10 + 20 + 30) / 3 = 20초입니다. 이 경우, FIFO는 잘 작동합니다.

 

 

FIFO의 문제점: 컨보이 효과(Convoy Effect)

FIFO는 작업들의 실행 시간이 서로 다를 때 심각한 비효율성을 드러낼 수 있습니다. 이를 컨보이 효과라고 합니다.

예시 2: 작업 실행 시간이 다를 때

A, B, C가 순서대로 도착하지만, A는 100초가 걸리고 B와 C는 각각 10초씩 걸린다고 가정해 봅시다.

• A는 0초에 시작하여 100초에 완료됩니다.
• B는 A가 끝날 때까지 기다려야 하므로, 100초에 시작하여 110초에 완료됩니다.
• C는 마찬가지로 기다려야 하므로, 110초에 시작하여 120초에 완료됩니다.

평균 turnaround time은 (100 + 110 + 120) / 3 = 110초입니다.

이처럼 실행 시간이 긴 작업(A)이 먼저 도착하면, 뒤에 도착한 짧은 작업들(B, C)이 오랫동안 기다려야 하는 문제가 발생합니다. 이것이 바로 컨보이 효과이며, 이는 FIFO 스케줄링의 가장 큰 단점 중 하나입니다. 마트에서 장볼때 앞에 계산하는 사람이 물건을 많이 사서 뒤에 모든 사람이 줄줄이 기다리는 상황으로 이해하면 쉽습니다. 

 

즉, FIFO방법은 가정 1번(모든 작업은 동일한 실행 시간을 가진다)이 존재할때만 유용한 방법입니다. 

 

 

---

 

 

Shortest Job First, SJF 

SJF는 이름 그대로, 실행 시간이 가장 짧은 작업을 먼저 처리하는 방식입니다. 마치 마트에서 물건이 가장 적은 사람이 먼저 계산하는 것과 같습니다. 이 알고리즘은 최적의 평균 turnaround time을 달성하는 것으로 증명되었습니다. 하지만 이는 '모든 작업의 실행 시간을 미리 알고 있다'는 비현실적인 가정을 포함하여, 위에서 정의한 2~5번 가정이 성립할 때 최적인 방법입니다.

 

예시 1: 작업 실행 시간이 다를 때

• 작업 A: 100초
• 작업 B: 10초
• 작업 C: 10초

모두 동시에 도착했다고 가정하면, SJF는 짧은 작업인 B와 C를 먼저 실행합니다.

• B는 0초에 시작하여 10초에 완료됩니다.
• C는 10초에 시작하여 20초에 완료됩니다.
• A는 20초에 시작하여 120초에 완료됩니다.

평균 turnaround time은 (10 + 20 + 120) / 3 = 50초입니다. 이는 FIFO의 110초보다 훨씬 효율적입니다.

 

SJF의 Optimality

SJF는 주어진 작업 세트에서 가장 낮은 평균 turnaround time을 보장합니다.

P1(8초), P2(4초), P3(2초) 세 작업이 있다고 가정해 봅시다.

 

이 표에서 보듯이, 실행 시간이 짧은 작업(P3, P2)을 먼저 실행하는 SJF가 가장 낮은 평균 turnaround time을 기록합니다.

 

 

SJF와 늦게 도착하는 작업

이제 '모든 작업이 동시에 도착한다'라는 2번 가정을 완화해 봅시다.

예시 3: 작업이 늦게 도착할 때

• A는 0초에 도착하고 100초가 걸립니다.
• B와 C는 10초에 도착하고 각각 10초씩 걸립니다.

FIFO와 달리 SJF는 도착 즉시 모든 정보를 알 수 없으므로, 스케줄링 결정 시점에 이미 도착한 작업만 고려합니다.

1. t=0: A만 도착했으므로 A를 실행합니다.
2. t=10: A가 10초간 실행된 시점에 B와 C가 도착합니다. 하지만 SJF는 이미 실행 중인 A를 중단시키지 않습니다.
3. A는 100초에 완료됩니다.
4. A가 완료된 후, B와 C 중 더 짧은 작업이 없으므로(둘 다 10초), B를 실행합니다. B는 100초에 시작해 110초에 완료됩니다.
5. C는 110초에 시작해 120초에 완료됩니다.

평균 turnaround time은 (100 + (110 - 10) + (120 - 10)) / 3 = (100 + 100 + 110) / 3 = 103.33초입니다.

이 예시에서 볼 수 있듯이, SJF는 실행 중인 작업을 중단시키지 않는 비선점형(non-preemptive) 알고리즘이므로, 늦게 도착한 짧은 작업들이 긴 작업 때문에 오랫동안 기다릴 수 있는 문제가 있습니다.

 

 

---

 

 

STCF(최단 완료 시간 우선) 스케줄링

Shortest Time-to-Completion First (STCF)는 SJF에 선점(preemption)기능을 추가한 스케줄링 알고리즘입니다. 이를 통해 '한 번 시작된 작업은 완료될 때까지 실행된다'는 가정(위의 3번 가정)을 완화합니다.

 STCF는 PSJF(Preemptive Shortest Job First)라고도 불립니다. 이 알고리즘은 새로운 작업이 도착할 때마다 스케줄러가 시스템 내의 모든 작업(새로운 작업 포함)의 남은 실행 시간을 재평가합니다. 그중 남은 시간이 가장 짧은 작업을 선택하여 실행합니다.

이 방식은 선점형(preemptive) 스케줄링에 속합니다.

 

• 비선점형(Non-preemptive) 스케줄링은 한 작업을 시작하면 완료될 때까지 중단할 수 없습니다.
• 선점형(Preemptive) 스케줄링은 더 짧은 작업이 도착하면 현재 실행 중인 작업을 잠시 중단시키고 다른 작업을 실행할 수 있습니다. 이 과정에는 context switch가 필요합니다.

 

CPU 스케줄링이 발생하는 시점은 다음과 같습니다.

1. 프로세스가 running 상태에서 waiting 상태로 전환될 때.
2. 프로세스가 running 상태에서 ready 상태로 전환될 때.
3. 새로운 프로세스나 대기 중이던 프로세스가 ready 상태로 전환될 때.
4. 프로세스가 종료(exits)될 때.

비선점형 스케줄러는 1번과 4번에서만 스케줄링을 결정하지만, 선점형 스케줄러는 이 네 가지 시점 모두에서 스케줄링을 수행합니다.

 

 

STCF 예시

• A는 0초에 도착하고 100초가 필요합니다.
• B와 C는 10초에 도착하고 각각 10초가 필요합니다.

STCF는 A를 실행하다가 B와 C가 도착하면 더 짧은 작업이 있는지 확인하고 교체합니다.

1. t=0: A만 도착했으므로 A를 실행합니다.
2. t=10: A가 10초간 실행된 상태에서 B와 C가 도착합니다.
   • 남은 시간: A (90초), B (10초), C (10초).
   • B와 C가 A보다 남은 시간이 훨씬 짧으므로, OS는 A를 중단하고 B를 실행합니다.
3. t=10~t=20: B를 실행하여 B는 20초에 완료됩니다.
4. t=20: 이제 남은 작업은 A와 C입니다. C의 남은 시간(10초)이 A의 남은 시간(90초)보다 짧으므로, C를 실행합니다.
5. t=20~t=30: C를 실행하여 C는 30초에 완료됩니다.
6. t=30: 남은 유일한 작업인 A를 다시 시작하여 120초에 완료됩니다.

이 예시의 평균 turnaround time은 다음과 같습니다.

• A: 120초 (120 - 0)
• B: 10초 (20 - 10)
• C: 20초 (30 - 10)

평균 turnaround time은 (120 + 10 + 20) / 3 = 50초입니다. 이 방식은 비선점형 SJF의 103.33초보다 훨씬 효율적입니다.

 

 

---

 

 

새로운 지표: Response Time

이 지표는 과거 배치 시스템의 Turnaround Time 지표가 가진 한계를 극복하기 위해 등장했습니다.

과거 배치 시스템에서는 모든 작업이 한꺼번에 처리되고 turnaround time이 완료 시간을 기준으로 측정되었습니다. 하지만 시간이 지나며 사용자가 터미널에서 직접 시스템과 상호작용하는 시분할(time-shared) 시스템이 등장하면서, 작업이 도착한 후 얼마나 빨리 반응을 보여주는지가 중요해졌습니다.

​

Response Time: 작업이 시스템에 도착한 순간부터 처음으로 실행되기 시작하는 순간까지의 시간.

 

STCF의 문제점과 해결책

STCF(최단 완료 시간 우선)와 같은 알고리즘은 Response time에 좋지 않습니다. 예를 들어, 사용자가 터미널에 입력(작업 도착)한 후 10초가 걸리는 긴 작업이 있다면, STCF는 그 작업을 먼저 처리하기 때문에 사용자의 입력에 대한 즉각적인 반응을 기대하기 어렵습니다. 이는 사용자 경험을 크게 저해합니다.

따라서, Response time에 민감한 스케줄러를 만들기 위해서는 새로운 접근 방식이 필요합니다.

• 선점(Preemption) 기능과 함께 짧은 시간 단위로 CPU를 번갈아 가며 할당하는 방식이 대표적인 해결책이 될 수 있습니다.
• 이는 다음에 설명할 라운드 로빈(Round Robin) 스케줄링의 기본 개념이기도 합니다.

 

 

---

 

 

 

라운드 로빈(Round Robin, RR) 스케줄링

라운드 로빈(RR) 스케줄링은 Response time 문제를 해결하기 위해 고안된 선점형(preemptive) 알고리즘입니다. 이 방식은 각 작업을 time slice라고 불리는 아주 짧은 시간 동안만 실행하고, run queue에 있는 다음 작업으로 전환하는 것을 반복합니다. time slice는 timer-interrupt 주기의 배수로 설정됩니다.

 

RR은 모든 작업에 공평하게 CPU 시간을 할당하므로 공정성(fairness) 측면에서 우수합니다. 하지만, 잦은 문맥 교환으로 인해 response time이 길어지는 단점이 있습니다.

 

 

RR 스케줄링 예시

A, B, C 세 작업이 동시에 도착했고, 각각 5초의 실행 시간이 필요하다고 가정해 봅시다.

1. SJF(Shortest Job First) 방식

• A의 response time: 0초
• B의 response time: 5초
• C의 response time: 10초
• 평균 response time: (0+5+10)/3=5초

 

2. RR 방식 (time slice: 1초)

RR은 각 작업을 1초씩 번갈아 가며 실행합니다.

• A는 0초에 시작
• B는 1초에 시작
• C는 2초에 시작
• 평균 response time: (0+1+2)/3=1초

이 예시에서 볼 수 있듯이, RR은 SJF보다 평균 response time이 훨씬 빠릅니다. 

 

 

time slice 길이의 중요성

타임 슬라이스의 길이를 결정하는 것은 중요한 trade-off 문제입니다.

• 타임 슬라이스가 짧을수록:
  • response  time이 좋아집니다. 사용자의 입력에 더 빠르게 반응할 수 있습니다.
  • 하지만 context switch 비용이 전체 성능을 지배하게 됩니다. 잦은 문맥 교환으로 인해 CPU의 유용한 작업 시간이 줄어듭니다.
• 타임 슬라이스가 길수록:
  • context switch 비용을 분산시킬 수 있어 효율성이 높아집니다.
  • 하지만 response time이 나빠집니다.

시스템 설계자는 이 두 가지 요소를 고려하여 적절한 타임 슬라이스 길이를 설정해야 합니다.

 

 

---

 

 

 

 

I/O 작업의 통합

이제 모든 프로그램이 I/O(입출력) 작업을 수행한다고 가정해 봅시다(4번 가정을 완화). 이 경우 스케줄러는 작업이 I/O를 요청할 때와 I/O가 완료될 때 추가적인 결정을 내려야 합니다.

• 작업이 I/O를 요청할 때:
  • 해당 작업은 I/O가 완료될 때까지 blocked 상태로 전환됩니다.
  • CPU는 유휴 상태가 되므로, 스케줄러는 즉시 다른 작업을 CPU에 할당해야 합니다.
• I/O가 완료될 때:
  • 하드웨어에서 interrupt가 발생합니다.
  • OS는 이 interrupt를 처리하여 해당 프로세스의 상태를 blocked상태에서 다시 ready상태로 옮깁니다. 이제 이 프로세스는 다시 CPU를 할당받을 수 있게 됩니다.

 

I/O가 포함된 예시

• 작업 A: CPU 시간 50ms 필요. 10ms 실행 후 10ms의 I/O 작업 수행.
• 작업 B: CPU 시간 50ms 필요. I/O 작업 없이 CPU만 사용.

 

자원이 비효율적으로 사용되는 경우: 만약 A가 I/O 작업을 수행하는 10ms 동안 CPU가 아무 일도 하지 않고 기다린다면, 자원 활용도가 매우 낮아집니다.

자원이 효율적으로 사용되는 경우: 스케줄러는 A가 I/O를 기다리는 동안 B와 같은 다른 작업을 CPU에 할당합니다. 이처럼 계산 작업(CPU-intensive jobs)과 I/O 작업(I/O-intensive jobs)이 겹치도록(overlap) 스케줄링함으로써, 프로세서의 활용도를 최대로 높일 수 있습니다.

 

 

 

 

 

 

 

 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료