목차
CPU 스케줄링
CPU 스케줄링은 여러 프로세스 사이에서 CPU 시간을 어떻게 분배할지 결정하는 메커니즘입니다.
스케줄링의 목표는 크게 다음과 같이 분류할 수 있습니다
1.
처리량 : 단위 시간당 처리할 수 있는 작업의 양을 최대화하는 것입니다. 이는 시스템이 효율적으로 작동하고 있음을 나타냅니다.
2.
응답 시간 : 사용자가 요청을 보낸 후 시스템이 응답을 최소화 합니다.
3.
대기 시간 : 프로세스가 CPU를 할당받기 위해 대기하는 시간의 총합을 최소화하는 것입니다. 이는 자원을 공정하게 분배하는데 중점을 둡니다.
4.
공정성 : 모든 프로세스가 공평한 CPU 시간을 할당받아야 합니다. 이는 특정 프로세스가 다른 프로세스에 비해 과도하게 더 많이 또는 덜 실행되지 않도록 보장합니다.
위에서 언급한 목표에 대한 자세한 설명은 아래에서, 기본 스케줄링 알고리즘의 단점을 설명하면서 추가로 설명하겠습니다.
CPU 스케줄링 기본 알고리즘
큐 스케줄링
•
FIFO : 이 알고리즘은 가장 단순한 형태의 스케줄링으로, 먼저 도착한 프로세스를 먼저 처리합니다. 프로세스들은 도착한 순서대로 큐에 배치되고, CPU는 큐의 앞에서부터 순서대로 프로세스를 실행합니다.
•
단점 : 이 방식은 구현이 간단하고 공정하지만, 평균 대기 시간이 길어질 수 있으며, 특히 CPU 사용 시간이 긴 작업에 의해 다른 작업들이 오랜 시간 대기할 수 있습니다.
큐 스케줄링 단점 예시
예를 들어, 4개의 프로세스 A, B, C, D가 있고, 각각의 실행 시간이 아래와 같다고 가정해 보겠습니다.
•
A : 20초
•
B : 3초
•
C : 4초
•
D : 5초
이 프로세스들이 시스템에 도착한 순서대로 A, B, C, D 순서로 CPU를 요청하고, 시스템이 FIFO 스케줄링 알고리즘을 사용한다고 가정하겠습니다.
스케줄링 순서와 대기 시간 계산
•
A는 바로 실행되므로 대기 시간은 0초입니다.
•
B는 A가 완료된 후 실행될 수 있으므로, B의 대기 시간은 A의 실행 시간인 20초입니다.
•
C는 A와 B가 완료된 후 실행될 수 있으므로, C의 대기 시간은 A와 B의 실행 시간의 합인 23초입니다.
•
D는 A, B, C가 완료된 후 실행될 수 있으므로, D의 대기 시간은 A, B, C의 실행 시간의 합인 27초입니다.
이제 평균 대기 시간을 계산해 보겠습니다.
평균 대기 시간 = (0+20+23+27) / 4 = 70 / 4 =17.5초
이 예에서 볼 수 있듯이, 긴 작업(A)이 먼저 도착하면 이후에 도착하는 짧은 작업들(B, C, D)은 긴 작업이 완료될 때까지 대기해야 합니다.
이로 인해 짧은 작업들의 대기 시간이 불필요하게 길어지고, 전체적인 평균 대기 시간이 증가합니다
우선순위 큐 스케줄링
•
우선순위 기반 스케줄링 : 이 알고리즘은 각 프로세스에 우선순위를 할당하고, 가장 높은 우선순위를 가진 프로세스부터 CPU 시간을 할당합니다. 우선순위는 프로세스의 중요도, 메모리 요구사항, CPU 시간 요구사항, 입출력 요구사항 등 다양한 기준에 따라 결정될 수 있습니다.
•
단점 : 우선순위 스케줄링은 실시간 시스템에서 중요한 작업을 우선적으로 처리해야 할 때 유용하지만, 낮은 우선순위의 프로세스가 무한히 대기하는 기아상태 문제를 초래할 수 있습니다.
우선순위 큐 단점 예시
예를 들어, 다음과 같은 상황을 가정해봅시다
•
프로세스 P1, P2, P3가 있으며, 각각의 우선순위는 다음과 같습니다
◦
P1: 우선순위 3 (가장 낮음)
◦
P2: 우선순위 2
◦
P3: 우선순위 1 (가장 높음)
•
모든 프로세스가 거의 동시에 도착했다고 가정합니다.
•
우선순위가 높은 프로세스부터 CPU가 할당됩니다.
초기 상태에서 P3가 가장 높은 우선순위를 가지고 있기 때문에 CPU를 먼저 할당받습니다.
P3의 실행이 끝나면 P2가 다음으로 CPU를 할당받습니다.
이 시점까지는 정상적인 우선순위에 따른 스케줄링입니다.
그러나 이후 시간에 걸쳐 새로운 프로세스들이 시스템에 도착한다고 가정해 봅시다.
이 새로운 프로세스들은 모두 P1보다 높은 우선순위(2 이상)를 가집니다.
•
새로운 프로세스 P4(우선순위 2), P5(우선순위 1)가 도착합니다.
•
P5가 가장 높은 우선순위로 CPU를 먼저 할당받고, 이후 P4가 할당받습니다.
•
이러한 상황이 계속 반복되면, P1은 계속해서 실행될 기회를 얻지 못하고 대기 상태에 머물게 됩니다. 이를 기아 상태라고 합니다.
최단 작업 우선 스케줄링
•
SJF : 이 알고리즘은 다음에 실행될 프로세스 중에서 실행 시간이 가장 짧은 프로세스를 선택합니다.
•
단점 : SJF는 평균 대기 시간을 최소화하는데 효과적이지만, 실행 시간을 정확히 예측하기 어렵고, 긴 작업이 기아 상태에 빠질 수 있다는 단점이 있습니다.
최단 작업 우선 스케줄링 단점 예시
우선순위 큐의 단점과 마찬가지로, 최단 작업 우선 스케줄링에서도 기아 상태가 발생할 수 있습니다.
예시를 들어보겠습니다
•
4개의 프로세스 A, B, C, D가 시스템에 도착하였고, 각각의 예상 실행 시간은 다음과 같다고 가정합니다.
◦
A: 10초 (먼저 도착)
◦
B: 2초
◦
C: 1초
◦
D: 5초
•
SJF 스케줄링 규칙에 따라, 시스템은 가장 짧은 실행 시간을 가진 프로세스부터 CPU를 할당합니다.
초기 상태에서 A가 먼저 도착했으나, 이후 B, C, D가 도착하면, SJF 알고리즘에 의해 A는 대기해야 합니다. 우선 순위는 다음과 같이 변경됩니다:
1.
C (1초)가 가장 짧으므로 먼저 실행됩니다.
2.
이후 B (2초)가 실행됩니다.
3.
다음으로 D (5초)가 실행됩니다.
4.
마지막으로 A (10초)가 실행됩니다.
만약 이 상황에서 계속해서 1초, 2초, 3초 등의 짧은 실행 시간을 가진 새로운 프로세스들이 시스템에 도착한다면, 원래 있던 A 프로세스는 계속해서 실행을 기다려야 할 것입니다.
이러한 방식으로, A와 같은 긴 실행 시간을 가진 프로세스는 계속해서 뒤로 밀리게 되고, 결국 기아 상태에 빠질 수 있습니다.
CPU 스케줄링 고도화 알고리즘
라운드 로빈 스케줄링
라운드 로빈 스케줄링은 시분할 시스템에서 널리 사용되는 방법으로, 각 프로세스에 동일한 크기의 시간 할당량(타임 퀀텀 또는 타임 슬라이스라고 함)을 주고, 준비 큐에 있는 모든 프로세스들이 순환적으로 CPU를 할당받는 방식입니다.
이 알고리즘의 핵심은 모든 프로세스가 동일한 시간 동안 CPU를 사용할 기회를 가집니다.
여기서 중요한 점은 타임 퀀텀을 관리하는 것이 중요합니다. 만약 타임 퀀텀이 너무 크다면 응답 시간과 대기 시간이 길어질 수 있습니다.
예를 들어, 타임 퀀텀이 100초라면 큐 알고리즘과 별반 차이가 없는 상황이 발생합니다.
그러나 타임 퀀텀이 너무 짧으면, 콘텍스트 스위칭이 지나치게 자주 발생하여 프로세스 처리 시간보다 콘텍스트 스위칭 처리 시간이 더 길어질 수 있습니다. 이 경우, 처리량이 감소할 수 있습니다.
그렇기에 라운드 로빈 스케줄링에선 타인 퀀텀을 적절히 선택하는 것이 중요합니다.
라운드 로빈 스케줄링 예시
라운드 로빈 스케줄링의 예를 들어보겠습니다.
여기서, 각 프로세스에 할당된 타임 퀀텀 4초라고 가정합니다.
•
프로세스 A : 필요 실행 시간 8초
•
프로세스 B : 필요 실행 시간 4초
•
프로세스 C : 필요 실행 시간 9초
•
프로세스 D : 필요 실행 시간 5초
프로세스들은 A, B, C, D의 순서로 시스템에 도착했다고 가정하며, 모두 준비 상태입니다.
라운드 로빈 스케줄링에 따라, 각 프로세스는 4초 동안 CPU를 사용한 후, 준비 큐의 끝으로 이동합니다.
모든 프로세스가 실행을 완료할 때까지 이 과정이 반복됩니다.
스케줄링 순서는 다음과 같습니다.
1.
A가 처음 4초 동안 실행됩니다 (남은 시간 4초).
2.
B가 다음 4초 동안 실행됩니다 (완료).
3.
C가 그 다음 4초 동안 실행됩니다 (남은 시간 5초).
4.
D가 이어서 4초 동안 실행됩니다 (남은 시간 1초).
5.
A가 다시 4초 동안 실행됩니다 (완료).
6.
C는 다시 실행되며, 이번에는 4초 중 4초만 필요합니다 (남은 시간 1초).
7.
D는 1초 동안 실행된 후 완료됩니다 (남은 시간 0초, 완료).
8.
C는 마지막으로 1초 동안 실행되어 완료됩니다.
멀티레벨 피드백 큐 스케줄링
멀티레벨 피드백 큐 스케줄링은 복잡한 시스템을 위해 설계된 매우 유연한 스케줄링 방법입니다. 여러 개의 큐를 사용하고, 각 큐는 다른 우선순위 레벨을 가집니다.
프로세스는 특정 기준에 따라 다른 큐 사이를 이동할 수 있습니다.
이 시스템은 프로세스가 실행될 때마다 그 행동을 기반으로 동적으로 우선순위를 조정합니다.
예를 들어, CPU를 많이 사용하는 프로세스는 낮은 우선순위 큐로 이동할 수 있으며, 입출력 요청이 많은 프로세스는 높은 우선순위 큐로 승격될 수 있습니다. 이 방식은 시스템의 효율성을 최대화하고 다양한 유형의 프로세스 요구를 만족시킬 수 있는 유연성을 제공합니다.
멀티레벨 피드백 큐 스케줄링 예시
다음은 멀티레벨 피드백 큐 스케줄링의 예시입니다.
•
3개의 큐가 있으며, 각각의 타임 퀀텀은 다음과 같습니다:
◦
큐 1: 타임 퀀텀 4초 (가장 높은 우선순위)
◦
큐 2: 타임 퀀텀 8초
◦
큐 3: 타임 퀀텀 12초 (가장 낮은 우선순위)
•
프로세스 정보:
◦
프로세스 A: 필요 실행 시간 24초
◦
프로세스 B: 필요 실행 시간 3초
◦
프로세스 C: 필요 실행 시간 3초
프로세스 A, B, C가 거의 동시에 도착했다고 가정합니다.
초기에 모든 프로세스는 가장 높은 우선순위 큐인 큐 1에 배치됩니다.
1.
프로세스 A가 먼저 CPU를 할당받고 4초 동안 실행됩니다.
타임 퀀텀이 완료되면, 프로세스 A는 큐 2로 이동합니다.
2.
그 다음, 프로세스 B가 4초 타임 퀀텀을 가진 큐 1에서 실행됩니다.
프로세스 B는 3초 만에 종료되므로, 추가 이동 없이 완료됩니다.
3.
프로세스 C도 동일하게 큐 1에서 실행되어 3초 만에 종료됩니다.
4.
이제 큐 1은 비어 있고, 큐 2에는 프로세스 A만 남아 있습니다.
프로세스 A는 이제 8초 동안 실행됩니다.
하지만 프로세스 A는 총 24초가 필요하므로, 8초 후에는 여전히 더 실행할 시간이 필요합니다. 따라서 큐 3으로 이동합니다.
5.
큐 3에서 프로세스 A는 남은 시간 동안 실행될 수 있습니다.
이 예시에서 멀티레벨 피드백 큐 스케줄링의 주요 특징을 볼 수 있습니다
•
프로세스는 다른 타임 퀀텀을 가진 여러 큐 사이를 이동할 수 있습니다.
•
짧은 작업은 빠르게 완료되어 시스템의 반응성을 향상시킵니다.
•
프로세스가 더 많은 CPU 시간을 요구할수록 점점 낮은 우선순위 큐로 이동하여, 다양한 프로세스의 요구를 동시에 만족시킬 수 있는 유연성을 제공합니다.
저는 마지막으로 MLFQ 알고리즘에 대해 설명했지만, 모든 운영체제가 해당 알고리즘을 사용하는 것은 아닙니다. 현대의 운영체제는 MLFQ를 채택하고 있지만, 그 외에도 훨씬 더 복잡한 알고리즘을 사용하여 CPU 스케줄링을 관리합니다.
