2-5. Priority 및 Round Robin 스케줄링

1. Priority 스케줄링

운영체제에서 여러 프로세스들이 동시에 실행될 때, 어떤 프로세스에게 CPU를 할당할지는 매우 중요한 문제입니다. 이를 결정하는 알고리즘을 스케줄링 알고리즘이라고 합니다. Priority 스케줄링은 각 프로세스에 우선순위를 부여하여, 우선순위가 높은 프로세스에게 CPU를 먼저 할당하는 방식입니다. 이는 CPU 사용의 효율성을 높이고, 시스템의 응답성을 개선하는 데 기여합니다.

1) 개념 및 배경

Priority 스케줄링의 기본 아이디어는 간단합니다. 각 프로세스는 숫자 값을 가진 우선순위를 할당받습니다. 이 숫자는 프로세스의 중요성, 요구되는 자원의 양, 혹은 사용자의 선호도 등을 반영할 수 있습니다. 운영체제는 CPU를 할당할 때, 가장 높은 우선순위를 가진 프로세스를 선택합니다. 우선순위가 같은 프로세스들 사이에서는 FCFS (First-Come, First-Served) 방식이나 Round Robin 방식을 적용하여 CPU를 할당할 수 있습니다.

이러한 방식은 몇 가지 장점을 가집니다. 예를 들어, 중요도가 높은 프로세스, 즉 긴급한 작업을 처리해야 하는 프로세스 (예: 실시간 시스템에서 센서 데이터 처리)를 빠르게 실행할 수 있도록 보장할 수 있습니다. 또한, 사용자들은 자신의 작업을 중요도에 따라 분류하여 시스템 자원을 효율적으로 사용할 수 있습니다.

2) 동작 원리

Priority 스케줄링은 크게 두 가지 유형으로 나눌 수 있습니다.

• 비선점형 (Non-preemptive) 스케줄링: 프로세스가 CPU를 할당받으면, 해당 프로세스가 종료되거나 I/O 요청으로 인해 대기 상태가 될 때까지 CPU를 계속 사용합니다. 우선순위가 더 높은 프로세스가 준비 상태가 되더라도 현재 실행 중인 프로세스는 CPU를 양보하지 않습니다.

• 선점형 (Preemptive) 스케줄링: 프로세스가 CPU를 사용하던 중, 더 높은 우선순위의 프로세스가 준비 상태가 되면, 현재 실행 중인 프로세스를 중단하고 CPU를 더 높은 우선순위의 프로세스에 할당합니다.

선점형 Priority 스케줄링은 더욱 유연하고 응답성이 뛰어나지만, 문맥 교환 (Context Switch)에 따른 오버헤드가 발생할 수 있습니다.

3) 장단점

Priority 스케줄링은 다음과 같은 장점과 단점을 가집니다.

장점:

• 중요 프로세스 우선 처리: 우선순위를 통해 중요한 프로세스를 빠르게 처리할 수 있습니다.
• 유연성: 다양한 우선순위 할당 방식을 통해 시스템의 요구사항을 반영할 수 있습니다.
• 응답성 향상: 높은 우선순위의 프로세스가 즉시 실행되므로 응답성이 향상됩니다.

단점:

• 기아 현상 (Starvation): 낮은 우선순위의 프로세스가 CPU를 전혀 할당받지 못하는 상황이 발생할 수 있습니다.
• 우선순위 역전 (Priority Inversion): 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스가 필요로 하는 자원을 먼저 획득하고, 해당 자원을 반환하지 못해 높은 우선순위의 프로세스가 블록되는 현상.
• 우선순위 결정의 어려움: 적절한 우선순위를 결정하는 것은 시스템의 성능에 매우 큰 영향을 미치며, 프로세스의 특성을 정확히 파악해야 합니다.

4) 기아 현상 해결 방안

기아 현상을 해결하기 위한 몇 가지 방법이 있습니다.

• 에이징 (Aging): 일정 시간 동안 대기하는 프로세스의 우선순위를 점진적으로 높여줍니다.
• 우선순위 변경 불가능 설정: 일부 프로세스의 우선순위를 시스템에 의해 변경되지 않도록 설정합니다.
• 상대적 우선순위 기반 스케줄링: 프로세스의 현재 상태와 관계없이, 상대적인 우선순위를 기반으로 CPU를 할당합니다.

5) 예시

간단한 Priority 스케줄링 예시를 살펴보겠습니다. 5개의 프로세스가 있고, 각 프로세스의 우선순위와 CPU 사용 시간은 다음과 같습니다. (낮은 숫자가 높은 우선순위를 의미)

비선점형 Priority 스케줄링을 사용한다면, 다음과 같은 순서로 프로세스가 실행됩니다.

1. P2 (우선순위 1)가 가장 먼저 실행됩니다. (4ms)
2. P5 (우선순위 2)가 실행됩니다. (3ms)
3. P1 (우선순위 3)이 실행됩니다. (8ms)
4. P3 (우선순위 4)이 실행됩니다. (9ms)
5. P4 (우선순위 5)가 실행됩니다. (5ms)

선점형 Priority 스케줄링을 사용한다면, 프로세스가 실행되는 동안 더 높은 우선순위의 프로세스가 도착하면 CPU를 빼앗길 수 있습니다. 이 경우, 문맥 교환으로 인한 오버헤드가 발생하지만, 시스템의 응답성은 더욱 향상될 것입니다.

2. Round Robin 스케줄링

Round Robin (RR) 스케줄링은 시분할 시스템에서 널리 사용되는 스케줄링 알고리즘입니다. 각 프로세스에 CPU 사용 시간을 일정하게 할당하여, 모든 프로세스가 공정하게 CPU를 사용할 수 있도록 합니다.

1) 개념 및 배경

Round Robin 스케줄링은 "공정성"을 최우선 목표로 합니다. 각 프로세스는 CPU를 사용할 수 있는 시간 할당량(time quantum, time slice)을 할당받습니다. 프로세스가 time quantum 내에 작업을 완료하지 못하면, 해당 프로세스는 CPU를 반납하고 ready queue의 뒤로 이동합니다. 그 후, 다음 프로세스가 CPU를 할당받아 실행됩니다. 이러한 방식으로 모든 프로세스에게 CPU가 차례로 할당됩니다.

2) 동작 원리

Round Robin 스케줄링은 다음과 같은 방식으로 작동합니다.

1. 준비 큐(ready queue)에 있는 프로세스들을 순서대로 CPU에 할당합니다.
2. 각 프로세스는 정해진 시간 할당량(time quantum, 일반적으로 10-100ms)만큼 CPU를 사용합니다.
3. time quantum이 만료되면, 현재 실행 중인 프로세스는 중단되고 ready queue의 마지막으로 이동합니다.
4. ready queue의 다음 프로세스가 CPU를 할당받아 실행됩니다.
5. 모든 프로세스가 종료될 때까지 1-4단계를 반복합니다.

3) Time Quantum의 중요성

Round Robin 스케줄링의 성능은 time quantum의 크기에 크게 의존합니다.

• Time quantum이 너무 작을 경우: 잦은 문맥 교환으로 인한 오버헤드가 증가하여, 시스템의 성능이 저하될 수 있습니다. (CPU 사용률 감소)

• Time quantum이 너무 클 경우: Round Robin 스케줄링의 장점인 공정성이 감소하고, FCFS (First-Come, First-Served) 스케줄링과 유사해집니다.

따라서, 적절한 time quantum의 크기를 선택하는 것이 중요합니다. 일반적으로, time quantum은 문맥 교환 시간보다 약간 큰 값으로 설정합니다.

4) 장단점

Round Robin 스케줄링은 다음과 같은 장점과 단점을 가집니다.

장점:

• 공정성: 모든 프로세스에게 CPU 사용 기회를 균등하게 제공합니다.
• 응답 시간 예측 가능: 각 프로세스가 CPU를 얻는 데 걸리는 시간을 비교적 예측할 수 있습니다.
• 단순성: 구현이 비교적 쉽습니다.

단점:

• 문맥 교환 오버헤드: time quantum이 작을 경우, 잦은 문맥 교환으로 인한 오버헤드가 발생할 수 있습니다.
• 성능 저하 가능성: I/O를 많이 사용하는 프로세스의 경우, time quantum을 모두 사용하지 못하고 CPU를 반납하는 경우가 많아, CPU의 효율적인 사용을 방해할 수 있습니다.
• time quantum 설정의 어려움: 적절한 time quantum을 설정하는 것은 시스템의 특성에 따라 어려울 수 있습니다.

5) 예시

Round Robin 스케줄링 예시를 살펴보겠습니다. 3개의 프로세스가 있고, 각 프로세스의 CPU 사용 시간은 다음과 같습니다. time quantum은 2ms로 설정합니다.

Round Robin 스케줄링을 사용하면 다음과 같은 순서로 프로세스가 실행됩니다.

1. P1 (2ms)
2. P2 (2ms)
3. P3 (2ms)
4. P1 (2ms)
5. P2 (1ms)
6. P3 (2ms)
7. P1 (2ms)
8. P3 (2ms)

각 프로세스가 time quantum만큼 CPU를 사용한 후, ready queue의 뒤로 이동하여 다시 CPU를 할당받는 것을 확인할 수 있습니다.

3. Priority와 Round Robin의 결합

Priority 스케줄링과 Round Robin 스케줄링을 결합하여, 두 알고리즘의 장점을 모두 활용할 수 있습니다.

1) 개념

이 방식은 프로세스에 우선순위를 부여하고, 각 우선순위 내에서는 Round Robin 방식으로 CPU를 할당합니다. 즉, 높은 우선순위를 가진 프로세스가 먼저 CPU를 할당받고, 동일한 우선순위를 가진 프로세스들 간에는 Round Robin 방식으로 CPU를 분배합니다.

2) 동작 원리

1. 각 프로세스에 우선순위를 할당합니다.
2. 가장 높은 우선순위를 가진 프로세스 그룹을 선택합니다.
3. 선택된 그룹 내의 프로세스들에게 Round Robin 스케줄링을 적용하여 CPU를 할당합니다.
4. 가장 높은 우선순위 그룹의 모든 프로세스가 완료되면, 다음으로 높은 우선순위 그룹을 선택하여 3단계를 반복합니다.
5. 모든 프로세스가 종료될 때까지 2-4단계를 반복합니다.

3) 장점

• 응답성 향상: 높은 우선순위의 프로세스가 먼저 실행되므로, 중요한 작업의 응답 시간을 개선할 수 있습니다.
• 공정성 보장: 동일한 우선순위 내의 프로세스들에게 Round Robin 방식을 적용하여 공정성을 유지합니다.
• 유연성: 시스템의 요구사항에 따라 우선순위와 time quantum을 조절하여 성능을 최적화할 수 있습니다.

4) 단점

• 복잡성: 순수 Priority 스케줄링이나 Round Robin 스케줄링보다 구현이 복잡합니다.
• 기아 현상 가능성: 낮은 우선순위의 프로세스가 CPU를 할당받지 못하는 기아 현상이 발생할 수 있습니다. 이를 해결하기 위해 에이징 기법 등을 사용할 수 있습니다.
• 매개변수 튜닝 필요: 우선순위와 time quantum을 적절하게 설정해야 시스템의 성능을 최적화할 수 있습니다.

5) 예시

Priority Round Robin 스케줄링 예시를 살펴보겠습니다. 4개의 프로세스가 있고, 각 프로세스의 우선순위, CPU 사용 시간은 다음과 같습니다. time quantum은 2ms로 설정합니다.

이 경우, 다음과 같은 순서로 프로세스가 실행됩니다. (낮은 숫자가 높은 우선순위를 의미)

1. P1 (2ms)
2. P3 (2ms)
3. P1 (2ms)
4. P3 (2ms)
5. P2 (2ms)
6. P2 (1ms)
7. P4 (2ms)

먼저, 우선순위 1인 P1과 P3이 Round Robin 방식으로 실행됩니다. P1과 P3이 모두 완료된 후, 우선순위 2인 P2가 실행되고, 마지막으로 우선순위 3인 P4가 실행됩니다.

4. 결론

Priority 스케줄링과 Round Robin 스케줄링은 운영체제에서 프로세스를 효율적으로 관리하기 위한 핵심적인 알고리즘입니다. Priority 스케줄링은 프로세스의 중요도에 따라 CPU를 할당하여 응답성을 개선하고, Round Robin 스케줄링은 모든 프로세스에게 공정한 CPU 사용 기회를 제공합니다. 두 알고리즘을 결합하여, 시스템의 요구사항에 맞는 유연하고 효율적인 스케줄링을 구현할 수 있습니다. 각 알고리즘의 장단점을 이해하고, 적절한 매개변수를 설정하는 것이 시스템 성능을 최적화하는 데 중요합니다.