고급 실시간 스케줄링 알고리즘은 실시간 시스템에서 다양한 스케줄링 요구사항을 충족하기 위해 설계된 고급 기법들로 구성되어 있다. 이 장에서는 다양한 고급 스케줄링 알고리즘을 다루며, 각 알고리즘의 동작 원리와 특징, 그리고 이들이 실시간 시스템에서 어떻게 사용되는지를 설명한다.

EDF (Earliest Deadline First)

Earliest Deadline First(EDF) 알고리즘은 가장 빠른 데드라인을 가진 작업을 우선적으로 스케줄링하는 방식이다. 이는 작업의 데드라인을 기준으로 우선순위를 정하기 때문에, 항상 가장 급한 작업이 먼저 실행된다. EDF 알고리즘의 주요 특징은 다음과 같다:

• 동적 우선순위: 작업의 도착 시간에 따라 우선순위가 변경된다.
• 최적성: 단일 프로세서 환경에서 EDF는 데드라인을 만족하는 작업 세트를 스케줄링할 수 있는 최적의 알고리즘이다.
• 복잡도: 우선순위 큐를 유지하는 데 필요한 시간 복잡도는 O(log n)이다.

LLF (Least Laxity First)

Least Laxity First(LLF) 알고리즘은 작업의 여유 시간을 기준으로 스케줄링한다. 여유 시간(Laxity)은 작업의 데드라인과 남은 실행 시간의 차이로 정의된다. LLF 알고리즘의 주요 특징은 다음과 같다:

• 동적 우선순위: 여유 시간이 실시간으로 계산되므로 우선순위가 계속 변경된다.
• 긴급성: 여유 시간이 가장 적은 작업이 가장 긴급하게 처리된다.
• 복잡도: 여유 시간을 계산하는 데 필요한 시간 복잡도는 O(n)이다.

RM (Rate Monotonic)

Rate Monotonic(RM) 알고리즘은 주기적 작업의 우선순위를 주기의 역수에 따라 정하는 정적 우선순위 알고리즘이다. 주기가 짧은 작업일수록 높은 우선순위를 갖는다. RM 알고리즘의 주요 특징은 다음과 같다:

• 정적 우선순위: 작업의 우선순위는 시스템 설계 시 결정되며 실행 중에는 변경되지 않는다.
• 주기적 작업: 주기가 명확하게 정의된 주기적 작업에 적합한다.
• 최적성: 단일 프로세서 환경에서 주기적 작업을 스케줄링하는 데 있어서 최적의 성능을 보장한다.

DM (Deadline Monotonic)

Deadline Monotonic(DM) 알고리즘은 작업의 상대적 데드라인을 기준으로 우선순위를 정하는 정적 우선순위 알고리즘이다. 상대적 데드라인이 짧은 작업일수록 높은 우선순위를 갖는다. DM 알고리즘의 주요 특징은 다음과 같다:

• 정적 우선순위: 상대적 데드라인에 따라 우선순위가 결정되며 실행 중에는 변경되지 않는다.
• 실시간 작업: 데드라인이 명확하게 정의된 실시간 작업에 적합한다.
• 최적성: 주기적 작업을 스케줄링하는 데 있어서 최적의 성능을 보장하지는 않지만, 특정 조건에서 매우 효율적이다.

CBS (Constant Bandwidth Server)

Constant Bandwidth Server(CBS)는 서버 기반 스케줄링 알고리즘으로, 각 작업에게 일정한 CPU 대역폭을 할당한다. CBS 알고리즘의 주요 특징은 다음과 같다:

• 자원 예약: 각 작업은 고정된 대역폭을 가지며, 이 대역폭 내에서 실행된다.
• 유연성: 실시간과 비실시간 작업이 혼합된 환경에서 유연하게 사용할 수 있다.
• 복잡도: 자원 예약과 할당을 관리하는 복잡도는 상대적으로 높다.

G-EDF (Global Earliest Deadline First)

Global Earliest Deadline First(G-EDF) 알고리즘은 멀티프로세서 환경에서 EDF 알고리즘을 확장하여 사용하는 방식이다. 모든 작업을 글로벌 큐에서 관리하며, 각 프로세서는 가장 빠른 데드라인을 가진 작업을 선택하여 실행한다. G-EDF 알고리즘의 주요 특징은 다음과 같다:

• 글로벌 큐: 모든 프로세서가 하나의 글로벌 큐를 공유한다.
• 동적 우선순위: 작업의 도착 시간에 따라 우선순위가 변경된다.
• 복잡도: 글로벌 큐를 유지하는 데 필요한 시간 복잡도는 O(log n)이다.

P-EDF (Partitioned Earliest Deadline First)

Partitioned Earliest Deadline First(P-EDF) 알고리즘은 멀티프로세서 환경에서 각 프로세서가 독립적으로 EDF 스케줄링을 수행하는 방식이다. 작업은 처음에 각 프로세서에 할당되고, 이후 프로세서 내에서만 스케줄링된다. P-EDF 알고리즘의 주요 특징은 다음과 같다:

• 파티셔닝: 작업은 시스템 초기화 시 각 프로세서에 고정적으로 할당된다.
• 독립적 스케줄링: 각 프로세서가 독립적으로 EDF 알고리즘을 실행한다.
• 복잡도: 각 프로세서의 작업 수에 따라 다르며, 일반적으로 O(log n)이다.

G-RM (Global Rate Monotonic)

Global Rate Monotonic(G-RM) 알고리즘은 멀티프로세서 환경에서 RM 알고리즘을 확장하여 사용하는 방식이다. 모든 작업을 글로벌 큐에서 관리하며, 각 프로세서는 가장 높은 우선순위를 가진 작업을 선택하여 실행한다. G-RM 알고리즘의 주요 특징은 다음과 같다:

• 글로벌 큐: 모든 프로세서가 하나의 글로벌 큐를 공유한다.
• 정적 우선순위: 작업의 주기에 따라 우선순위가 결정되며, 실행 중에는 변경되지 않는다.
• 복잡도: 글로벌 큐를 유지하는 데 필요한 시간 복잡도는 O(log n)이다.

P-RM (Partitioned Rate Monotonic)

Partitioned Rate Monotonic(P-RM) 알고리즘은 멀티프로세서 환경에서 각 프로세서가 독립적으로 RM 스케줄링을 수행하는 방식이다. 작업은 처음에 각 프로세서에 할당되고, 이후 프로세서 내에서만 스케줄링된다. P-RM 알고리즘의 주요 특징은 다음과 같다:

• 파티셔닝: 작업은 시스템 초기화 시 각 프로세서에 고정적으로 할당된다.
• 독립적 스케줄링: 각 프로세서가 독립적으로 RM 알고리즘을 실행한다.
• 복잡도: 각 프로세서의 작업 수에 따라 다르며, 일반적으로 O(log n)이다.

Pfair (Proportionate Fair)

Proportionate Fair(Pfair) 알고리즘은 멀티프로세서 환경에서 각 작업이 할당된 자원의 비율을 정확하게 반영하도록 스케줄링하는 방식이다. 작업의 실행 시간을 작은 조각으로 나누어, 각 프로세서가 공정하게 자원을 분배받도록 한다. Pfair 알고리즘의 주요 특징은 다음과 같다:

• 공정성: 모든 작업이 할당된 자원 비율에 따라 공정하게 스케줄링된다.
• 작은 조각: 작업의 실행 시간을 작은 조각으로 나누어 스케줄링한다.
• 복잡도: 작업의 조각을 관리하는 데 필요한 시간 복잡도는 상대적으로 높다.

LST (Least Slack Time)

Least Slack Time(LST) 알고리즘은 작업의 슬랙 타임(Slack Time)을 기준으로 스케줄링하는 방식이다. 슬랙 타임은 데드라인과 남은 실행 시간, 그리고 현재 시간을 고려하여 계산된다. LST 알고리즘의 주요 특징은 다음과 같다:

• 동적 우선순위: 슬랙 타임에 따라 우선순위가 실시간으로 변경된다.
• 긴급성: 슬랙 타임이 가장 적은 작업이 가장 긴급하게 처리된다.
• 복잡도: 슬랙 타임을 계산하는 데 필요한 시간 복잡도는 O(n)이다.

활용 사례

고급 스케줄링 알고리즘들은 다양한 실시간 시스템에서 사용된다. 예를 들어, EDF 알고리즘은 임베디드 시스템과 같은 제한된 자원 환경에서 자주 사용되며, CBS 알고리즘은 멀티미디어 스트리밍과 같은 동적 환경에서 유용하다. 또한, Pfair 알고리즘은 멀티코어 프로세서에서 공정한 자원 분배를 필요로 하는 응용 프로그램에 적합한다.

이 장에서는 고급 스케줄링 알고리즘의 다양한 특징과 활용 사례를 다루었으며, 실시간 시스템에서 이들이 어떻게 적용될 수 있는지에 대해 설명하였다. 다음 장에서는 이러한 알고리즘의 성능 평가와 최적화 방법에 대해 다룰 것이다.