2-4. FCFS, SJF, SRT 스케줄링

1. 스케줄링의 기본 개념과 중요성

운영체제는 여러 프로세스들이 동시에 실행되는 것처럼 보이도록 관리합니다. 실제로는 CPU가 한 번에 하나의 프로세스만 실행할 수 있기 때문에, 운영체제는 CPU 사용 시간을 프로세스들에게 적절히 분배하여 마치 여러 프로세스가 병렬적으로 실행되는 듯한 환경을 제공합니다. 이러한 작업, 즉 CPU 사용 시간을 프로세스들에게 할당하는 과정을 스케줄링이라고 합니다.

스케줄링은 운영체제의 핵심 기능 중 하나이며, 시스템의 전체적인 성능에 매우 큰 영향을 미칩니다. 스케줄링 알고리즘의 선택에 따라 프로세스들의 응답 시간, 처리량(throughput), 자원 사용 효율 등이 달라지기 때문입니다. 예를 들어, 응답 시간이 중요한 인터랙티브 작업에는 빠르게 반응하는 알고리즘이, 처리량이 중요한 배치 작업에는 많은 작업을 처리할 수 있는 알고리즘이 적합합니다.

스케줄링 알고리즘은 크게 선점형(preemptive)과 비선점형(non-preemptive)으로 나뉩니다. 선점형 스케줄링은 프로세스가 CPU를 사용하고 있는 동안에도 운영체제가 CPU 사용 권한을 빼앗아 다른 프로세스에게 할당할 수 있습니다. 반면, 비선점형 스케줄링은 프로세스가 CPU를 스스로 반납할 때까지 CPU를 계속 사용합니다. 이번 포스트에서는 비선점형 스케줄링 알고리즘인 FCFS, 그리고 선점형 스케줄링 알고리즘인 SJF, SRT에 대해 자세히 살펴보겠습니다.

2. FCFS (First-Come, First-Served) 스케줄링

FCFS 스케줄링은 가장 간단한 스케줄링 알고리즘입니다. 말 그대로 "먼저 온 순서대로" 프로세스에게 CPU를 할당합니다. 즉, CPU를 요청하는 순서대로 프로세스를 실행하며, 큐(Queue) 형태로 관리됩니다.

1) 동작 방식

FCFS는 프로세스가 도착한 순서대로 CPU를 할당합니다. 프로세스가 CPU를 점유하면, 해당 프로세스가 완료될 때까지 다른 프로세스는 대기합니다. 이는 비선점형 스케줄링 방식이기 때문에, 이미 CPU를 할당받은 프로세스는 스스로 CPU를 반납할 때까지 계속 실행됩니다.

2) 장점과 단점

• 장점:

  • 구현이 매우 간단합니다.
  • 공정성(Fairness)을 보장합니다. 먼저 도착한 프로세스가 먼저 실행되기 때문에, 특정 프로세스가 무한정 대기하는 상황을 방지합니다.

• 단점:

  • Convoy Effect(호위 효과)가 발생할 수 있습니다. I/O 위주의 프로세스(짧은 CPU burst)가 CPU를 오래 사용하는 프로세스(긴 CPU burst)를 기다려야 하는 상황이 발생하여 시스템 전체의 효율을 저하시킵니다.
  • 평균 대기 시간이 길어질 수 있습니다. 짧은 작업이 긴 작업 뒤에 대기하는 경우, 짧은 작업은 긴 시간 동안 CPU를 기다려야 합니다.
  • 응답 시간(Response time)이 좋지 않습니다. 긴 작업을 먼저 처리해야 하는 경우, 짧은 작업은 오랜 시간 동안 CPU를 기다려야 하므로, 응답성이 떨어집니다.

3) 예시

다음과 같은 프로세스들이 CPU를 사용하기 위해 대기하고 있다고 가정해 봅시다.

FCFS 스케줄링을 적용하면 다음과 같은 방식으로 CPU가 할당됩니다.

1. P1이 0ms에 도착하여 CPU를 할당받고, 8ms 동안 실행됩니다.
2. P2는 1ms에 도착했지만, P1이 실행 중이므로 8ms까지 대기합니다. 8ms에 CPU를 할당받고 4ms 동안 실행됩니다.
3. P3는 2ms에 도착했지만, P1, P2가 실행 중이므로 12ms까지 대기합니다. 12ms에 CPU를 할당받고 9ms 동안 실행됩니다.
4. P4는 3ms에 도착했지만, P1, P2, P3가 실행 중이므로 21ms까지 대기합니다. 21ms에 CPU를 할당받고 5ms 동안 실행됩니다.

이를 간트 차트(Gantt chart)로 나타내면 다음과 같습니다.

각 프로세스의 대기 시간과 평균 대기 시간을 계산해 봅시다.

• P1: 0ms
• P2: 8ms - 1ms = 7ms
• P3: 12ms - 2ms = 10ms
• P4: 21ms - 3ms = 18ms

평균 대기 시간 (0 + 7 + 10 + 18) / 4 8.75ms

이 예시에서, P2는 비교적 짧은 작업(4ms)이지만, P1, P3과 같은 긴 작업(8ms, 9ms) 때문에 긴 시간 동안 CPU를 기다려야 했습니다. Convoy Effect의 전형적인 예시입니다.

3. SJF (Shortest Job First) 스케줄링

SJF 스케줄링은 "CPU 사용 시간이 가장 짧은" 프로세스에게 CPU를 먼저 할당하는 방식입니다. FCFS의 단점인 Convoy Effect를 줄이고 평균 대기 시간을 최소화하는 것을 목표로 합니다.

1) 동작 방식

SJF는 각 프로세스의 CPU burst time을 기준으로 CPU를 할당합니다. CPU burst time이 짧은 프로세스가 먼저 실행되도록 큐를 정렬합니다. SJF는 비선점형 스케줄링 방식이므로, 프로세스가 CPU를 점유하면, 해당 프로세스가 완료될 때까지 다른 프로세스는 대기합니다.

2) 장점과 단점

• 장점:

  • 평균 대기 시간을 최소화할 수 있습니다. CPU 사용 시간이 짧은 프로세스부터 처리하기 때문에, 긴 작업에 의해 짧은 작업이 오랫동안 대기하는 현상을 줄입니다.
  • 처리량(throughput)을 향상시킬 수 있습니다. 짧은 작업이 빠르게 완료되므로, 시스템 전체의 작업 처리 속도가 빨라집니다.

• 단점:

  • CPU burst time을 정확하게 예측하기 어렵습니다. 실제 CPU burst time은 예측과 다를 수 있으며, 예측 오류가 발생하면 성능이 저하될 수 있습니다.
  • Starvation(기아 현상)이 발생할 수 있습니다. CPU burst time이 긴 프로세스는 CPU burst time이 짧은 프로세스에 의해 지속적으로 밀려나, 무한정 대기할 수 있습니다.
  • 공정성(Fairness)을 보장하지 못합니다. CPU burst time이 긴 프로세스는 짧은 프로세스보다 CPU를 할당받는 데 더 많은 시간을 기다려야 합니다.

3) 예시

FCFS 예시와 동일한 프로세스들을 SJF 스케줄링으로 처리해 봅시다.

SJF 스케줄링을 적용하면 다음과 같은 방식으로 CPU가 할당됩니다.

1. 0ms에 P1이 도착하지만, P2, P4가 P1보다 CPU burst time이 짧으므로, P2가 먼저 실행됩니다. P2는 1ms에 도착하여 4ms 동안 실행됩니다.
2. P4는 3ms에 도착하여 CPU를 할당받고, 5ms 동안 실행됩니다.
3. P1은 0ms에 도착하여 CPU를 할당받고, 8ms 동안 실행됩니다.
4. P3은 2ms에 도착하여 CPU를 할당받고, 9ms 동안 실행됩니다.

이를 간트 차트로 나타내면 다음과 같습니다.

각 프로세스의 대기 시간과 평균 대기 시간을 계산해 봅시다.

• P1: 4ms - 0ms = 4ms
• P2: 0ms - 1ms = -1ms (1ms에 도착하여 0ms에 CPU를 할당받았으므로 대기 시간은 0)
• P3: 12ms - 2ms = 10ms
• P4: 4ms - 3ms = 1ms

평균 대기 시간 (4 + 0 + 10 + 1) / 4 3.75ms

FCFS의 8.75ms보다 훨씬 향상된 것을 확인할 수 있습니다.

4. SRT (Shortest Remaining Time) 스케줄링

SRT 스케줄링은 SJF 스케줄링의 선점형 버전입니다. 즉, 현재 실행 중인 프로세스의 남은 CPU burst time과 새로 도착하는 프로세스의 CPU burst time을 비교하여, 남은 시간이 더 짧은 프로세스에게 CPU를 할당합니다.

1) 동작 방식

SRT는 프로세스가 CPU를 사용하고 있는 동안에도, 새로운 프로세스가 도착하거나 현재 프로세스의 남은 CPU burst time이 변경될 때마다 CPU 할당을 갱신합니다. 매 시점마다 남은 CPU burst time이 가장 짧은 프로세스에게 CPU를 할당합니다.

2) 장점과 단점

• 장점:

  • SJF보다 더욱 효과적으로 평균 대기 시간을 줄일 수 있습니다.
  • 응답 시간(response time)을 개선할 수 있습니다. 짧은 작업이 빠르게 처리되도록 보장합니다.

• 단점:

  • CPU burst time 예측의 정확성이 매우 중요합니다. CPU burst time 예측이 부정확하면 성능이 크게 저하될 수 있습니다.
  • 문맥 교환(context switch) overhead가 큽니다. 프로세스의 CPU burst time이 짧게 남아있을 때마다 다른 프로세스로 교체될 수 있으므로, 문맥 교환 횟수가 증가하고, 이로 인해 오버헤드가 발생합니다.
  • Starvation 문제가 여전히 발생할 수 있습니다. 긴 CPU burst time을 가진 프로세스는 짧은 프로세스에 의해 계속 밀려날 수 있습니다.

3) 예시

동일한 프로세스들에 SRT 스케줄링을 적용해 봅시다.

SRT 스케줄링을 적용하면 다음과 같은 방식으로 CPU가 할당됩니다.

1. 0ms에 P1이 도착합니다.
2. 1ms에 P2가 도착합니다. P2의 CPU burst time이 P1의 남은 시간보다 짧으므로, P2가 실행됩니다.
3. 5ms에 P4가 도착합니다. P4의 CPU burst time이 P1의 남은 시간보다 짧으므로, P4가 실행됩니다.
4. 10ms에 P1이 다시 실행됩니다.
5. 15ms에 P3이 실행됩니다.

이를 간트 차트로 나타내면 다음과 같습니다.

각 프로세스의 대기 시간과 평균 대기 시간을 계산해 봅시다.

• P1: (0-0) + (10-5) = 5ms
• P2: 1-1 = 0ms
• P3: 15-2 = 13ms
• P4: 5-3 = 2ms

평균 대기 시간 (5 + 0 + 13 + 2) / 4 5ms

SRT는 SJF보다 평균 대기 시간 측면에서는 개선되었지만, 문맥 교환이 더 자주 발생하므로 오버헤드 측면에서는 불리할 수 있습니다.

5. 알고리즘 비교 및 고려 사항

FCFS, SJF, SRT 스케줄링 알고리즘을 비교하면 다음과 같습니다.

어떤 스케줄링 알고리즘을 선택할지는 시스템의 특성과 요구 사항에 따라 다릅니다.

• 응답 시간이 중요한 시스템(예: 대화형 시스템)에서는 SRT 또는 SJF와 같은 짧은 작업을 우선시하는 알고리즘이 적합합니다.
• CPU burst time 예측이 어려운 환경에서는 FCFS를 고려할 수 있습니다.
• Starvation 문제를 해결하기 위해, aging 기법(오랫동안 대기하는 프로세스의 우선순위를 높이는 방법)과 같은 기법을 함께 사용할 수 있습니다.

스케줄링은 운영체제 설계의 중요한 부분이며, 시스템의 성능과 사용자 경험에 직접적인 영향을 미칩니다. 각 알고리즘의 장단점을 이해하고, 시스템의 특성에 맞는 알고리즘을 선택하는 것이 중요합니다.