Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment

느낀점

이 논문은 실시간 시스템 이론의 초석이 된 고전으로, 이 논문이 출판된 이래로 이 내용은 수많은 실시간 스케줄링 알고리즘의 기반이 되었다. 특히 Rate-Monotonic과 Deadline-Driven Scheduling은 오늘날에도 널리 사용되고 있다. 

증명 내용 단계 단계가 간단명료하고 직관적이어서 이해하기에 어렵지 않았다. 잘 쓴 논문이란 이런 것인가 하는 생각과 더불어 도대체 이런 아이디어는 어떻게 생각해내는지 궁금하다. 

Problem Statement

본 논문은 Hard Real-Time Environment에서 단일 프로세서 위에서 동작하는 Multi Programming Task들의 Scheduling 문제를 다룬다. 이 환경에서 모든 Task들이 정해진 Deadline 내에 반드시 완료되어야 하며, 그 기한을 지키지 못하면 시스템에 치명적인 문제가 발생할 수 있음을 전제한다. 목표는 Deadline을 만족시키면서 최대한 높은 프로세서의 활용률을 달성하는 Scheduling Algorithm을 설계하는 것이다. 

좀 더 세분화해서 살펴보면, 

Hard Real-Time Environment에서 Scheduling Algorithm의 주요 목표와 과제는 다음과 같다. 

주요 목표

1. 서비스 보장 (Guaranteed Service): 제어 또는 모니터링되는 장비 내 event 또는 다른 Task 내 event에 대한 응답으로 실행되는 각 Task는 요청 발생 후에 정해진 시간(Deadline) 내에 완료되어야 한다. 즉 모든 Task는 정해진 마감 시간(Deadline) 내에 완료되어야 하며, 응답 시간(Response Time)이 보장되어야 한다. 

2. 오버플로우 방지 (Preventing Overflow): Scheduling Algorithm은 Deadline이 초과된(unfulfilled) 요청이 발생하지 않도록 Task를 Scheduling해야 한다. 이러한 상황을 Overflow라고 한다. Scheduling Algorithm이 Deadline을 준수하며 Overflow가 발생하지 않도록 Task를 Scheduling할 수 있다면, '실행 가능(feasible)'하다고 말한다. 

3. 프로세서 활용 극대화(Maximizing Processor Utilization): 제한된 프로세서 자원을 효율적으로 사용하여 가능한 한 높은 활용률을 달성하는 것이 중요하다.

• Fixed Priority Scheduling의 경우, Processor 활용률의 Upper Bound가 대규모 Task Set에 대해 70%까지 낮아질 수 있다.
• Dynamic Priority Scheduling의 경우, Processor 활용률을 100%까지 달성할 수 있다. 

주요 과제

1. 최적의 우선순위 할당 (Optimum Priority Assignment): Task에 우선순위를 할당하는 방법이 Scheduling 성공에 매우 중요하다.

• Static/Fixed Priority Assignment: 우선순위가 한 번 할당되면 변경되지 않는다.
  • Rate-Monotonic Scheduling: Rate(요청률, 주기의 역수)가 높은 Task에 더 높은 우선순위를 할당하는 방식. 이는 모든 Fixed Priority Scheduling Algorithm 중에서 Optimum으로 간주된다. 
  • 과제는 Fixed Priority Scheduler가 대규모 Task Set의 경우에, 프로세서 활용률의 Upper Bound가 약 70%까지 낮아질 수 있다는 점이다. 
• Dynamic Priority Assignment: Task의 우선순위가 요청마다 변경될 수 있다. 
  • Deadline-Driven Scheduling: 현재 요청의 Deadline이 가장 가까운 Task에 가장 높은 우선순위를 할당한다. 이 방법은 어떤 우선순위 할당으로 Scheduling될 수 있는 Task set이 있다면, 이 방법으로도 Scheduling할 수 있다는 점에서 Globally 최적이며, 100%의 프로세서 활용률을 달성할 수 있다.
• Mixed Scheduling: Fixed Priority Scheduling과 Deadline 중심 Scheduling의 조합이다. 이는 현재 컴퓨터의 하드웨어 인터럽트가 Fixed Priority Scheduler처럼 작동하고, 느린 Task를 위한 소프트웨어 Scheduler는 Deadline 중심 방식으로 구현하는 것이 효율적일 수 있기 때문에 연구되었다. 이 방식도 100% 활용률은 보편적으로 달성하기 어렵지만, Fixed Priority 방식보다는 덜 제한적일 수 있다. 

2. 현실적인 환경 제약 조건 고려 (Considering Realistic Environmental Constraints): 분석 결과를 얻기 위해 특정 가정이 필요하며, 이러한 가정을 완화할 때의 영향도 고려해야 한다. 

• Periodic Requests: 모든 Task의 요청이 주기적이며 요청 간 간격이 일정하다는 가정은 순수 프로세스 제어에는 유효하지만, 항상 현실적이지는 않을 수 있다. 
• Constant Run-Time: 각 Task의 실행 시간이 일정하다는 가정도 실제 환경에서는 변동될 수 있다.
• 이러한 가정이 유효하지 않을 경우, 프로세서 활용률에 심각한 제약이 가해질 수 있으며, 분석 자업의 유효성이 사라질 수 있다. 

3. 테스크 독립성 (Task Independence): 특정 Task의 요청이 다른 Task의 시작이나 완료에 의존하지 않는다는 가정은 중요한 단순화이며, 실제 시스템에서는 Task 간의 의존성이 존재할 수 있다. 

결론적으로 Hard Real Time 환경의 Scheduling은 모든 Task가 정해진 Deadline 내에 완료되도록 서비스를 보장하면서 프로세서 활용을 최적화하는 것을 목표로 한다. 이를 위해 Fixed/ Dynamic Priority Scheduling 방식의 장단점을 고려하고, 실제 환경의 비주기성 및 가변 실행 시간과 같은 복잡성을 다루는 것이 중요한 과제다. 

Contribution

1. Fixed Priority Scheduling에서의 최대 프로세서 활용률을 수학적으로 규명:

• 최대 활용률은 $ U=m(2^(1/m)-1),m\to \infty $ 일 때, 약 69.3%
• Rate-monotonic Scheduling이 최적의 Fixed Priority Scheduling 방식임을 증명

2. Dynamic Scheduling의 제안 및 최적성 증명:

• Deadline Driven Scheduling은 Task의 현재 Deadline을 기준으로 Priority를 부여
• 이 방식은 이론적으로 100% 프로세서 활용률을 달성 할 수 있음을 보임

3. 혼합 스케줄링(Mixed Scheduling) 전략 제시:

• 일부 높은 빈도의 Task는 Fixed Priority로, 나머지는 Dynamic으로 Scheduling
• 하드웨어 호환성과 높은 활용률을 동시에 달성하는 현실적 절충안 제시

Key Ideas

1. Rate-Monotonic Priority Assignment: 요청 주기가 짧을수록 높은 Priority를 부여, 이는 모든 Fixed Priority Scheduling 중 최적
2. Critical Instant & Time Zone: 가장 나쁜 경우의 Task 요청 시점에서 시스템의 수행 가능성을 분석
3. Processor Utilization Bound: Fixed Priority Scheduling에서의 최악의 활용률 상한을 수학적으로 계산
4. Deadline Driven Algorithm: Deadline이 가까운 Task에 높은 Priority를 주어 수행하며, 가능한 경우 항상 Deadline을 만족할 수 있음
5. Mixed Strategy: 현실적 제약을 고려하여 Fixed & Dynamic Priority를 병행 적용하는 Hybrid 모델

Mathematics View

Theorem 1 - Critical Instant Theorem

A critical instant for any task occurs whenever the task is requested simultaneously with requests for all higher-priority tasks

Critical instant는 Task가 최악의 응답시간(Worst Case Response Time)을 갖는 요청 시점을 할한다. 이 정리는 "자기보다 Priority가 높은 Task들이 동시에 도착했을 때"가 그 최악의 시점임을 나타낸다.

수학적 증명

• Task 집합: $\tau_1, \tau_2,...,\tau_m$, 우선순위는 $\tau_1 > \tau_2 > ... > \tau_m$
• $\tau_m$은 최하위 Priority Task
• $t_1:\tau_m$의 요청 시점
• 다른 모든 상위 Task $\tau_i, i < m$은 $t_2$부터 실행 

주장: 상위 작업이 $t_1$에 동시에 도착하면 $\tau_m$의 응답시간이 가장 길다

논리: 

• 만약 상위 Task들이 $t_1$보다 나중에 도착하면, 그만큼 $\tau_m$은 더 빨리 실행될 수 있다 -> 응답시간이 더 짧음
• 그러므로 상위 Task들과 동시에 요청될 때, $\tau_m$의 응답시간이 최대가 됨

따라서: 최악 응답시간 분석은 모든 상위 Task이 동시에 도착하는 경우만 고려하면 된다

 

Theorem 2 - RMS Optimality

If a fixed-priority assignment exists for a task set, then the rate-monotonic (RM) priority assignment is also feasible

• RM은 주기가 짧은 Task에 높은 Priority를 줌
• $\tau_1, \tau_2$에 대해, 주기가 $T_1 < T_2$라고 하자
• 두 가지 Priority 배치를 비교:
  • Case 1: $\tau_1 > \tau_2$
  • Case 2: $\tau_2 > \tau_1$

이때 Case 1이 가능한 경우라면, RM 할당도 가능한 것으로 나타남. 따라서 순서를 하나씩 교체하면서 RM 형태로 변환 가능

 

Theorem 3 - Utilization Bound (2 tasks)

최대 사용률

$$U=\frac{C_1}{T_1}+\frac{C_2}{T_2}\leq 2(2^{1/2}-1)\approx 0.828$$

증명

• $\tau_1$은 높은 Priority, $\tau_2$는 낮음
• $\tau_2$의 Deadline은 $T_2$
• $\tau_2$가 요청될 때, $\tau_1$은 $\left \lfloor \frac{T_2}{T_1}\right \rfloor$ 번 실행됨
• $\tau_2$가 Deadline을 지키려면:

$$\left \lfloor \frac{T_2}{T_1}\right \rfloor\cdot C_1+C_2\leq T_2$$

이 관계로부터 Processor Utilization:

$$U=\frac{C_1}{T_1}+\frac{C_2}{T_2}$$

를 최소화 조건으로 유도 -> 위의 수치가 최대 상한

 

Theorem 4 - Utilization Bound for m tasks (T_i + 1/T_i < 2)

$$U\leq m(2^{1/m}-1)$$

아이디어

• 모든 Task 주기가 서로 2배 이내라면 worst-case bound가 위 수식에 의해 주어진다.
• 증명은 유도화된 일반화 recurrence relation을 최소화하면서 얻어진다.
• m-> infinity일 때 이 값은 $ln(2)\approx 0.693$로 수렴

 

Theorem 5 - General Case (no period restriction)

The same bound $m(2^{1/m}-1)$ holds even when there is no restriction on period ratios

• 임의의 Task Set에서 가장 나쁜 경우를 조정해서, period ratio < 2인 Set으로 변형 가능
• 해당 Bound는 여전히 유효함을 보임

 

Theorem 6 - No Idle Before Overflow (Deadline Scheduling)

Deadline-driven Scheduling에서는 overflow 직전까지 CPU는 idle하지 않음

• overflow 시점 $t$ 이전에 idle 시간이 있었다면, Request들을 $t$ 직후로 옮겨도 동일한 overflow 발생
• 하지만 그렇게 옮기면 idle 시간은 사라짐 -> 모순
• 따라서 overflow 직전까지는 항상 CPU가 바쁨

 

Theorem 7 - Deadline Scheduling Feasibility

$$\sum_{i=1}^{m}\frac{C_i}{T_i}\leq 1 \Leftrightarrow feasible$$

• $T = LCM(T_1,...,T_m)
• 시간 $\left [ 0, T \right ]$동안 실행 시간 총합은:

$$\sum_{i=1}^{m}(\frac{T}{T_i}\cdot C_i)=T\cdot \sum_{i=1}^{m}\frac{C_i}{T_i}$$

• 이것이 $T$를 초과하면 불가능, 조건이 만족되면 deadline-driven 알고리즘으로 항상 만족 가능

 

Theorem 8 - No Idle in Mixed Scheduling

• 정적(RMS)과 동적(Deadline)을 혼합했을 때도 overflow 직전엔 idle하지 않음
• Theorem 6과 같은 증명 논리 사용

 

Theorem 9 - Feasibility Condition for Mixed Scheduling

$$ \sum_{i=k+1}^{m}\left \lfloor \frac{t}{T_i}\right \rfloor C_i\leq a_{k}(t) $$

• $a_{k}(t)$: RMS에 의해 사용되지 않고 남은 시간
• 모든 $t$에 대해 위 조건이 성립하면, deadline-driven Task들도 실행 가능

 

Limitations

1. 이상적인 가정에 의존:

• Task는 항상 주기적으로 요청된
• 실행 시간은 변하지 않음
• Task간의 의존성이 없음
• 이러한 가정들은 실제 시스템에서는 자주 위반될 수 있으며, 분석이 무효화될 가능성이 있음

2. Scheduling 복잡도:

• Dynamic Scheduling은 이론적으로는 최적이지만, 실행 중 계산 복잡도 및 구현 비용이 클 수 있음

3. Mixed Scheduling에 대한 Upper Bound 부재:

• 고정과 동적을 혼합한 경우의 최대 활용률에 대한 일반적인 해석 불가능
• 제한적인 조건 하에서만 충분조건을 도출할 수 있으며 일반화가 어려움

 

Reference

[1] C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," *Journal of the ACM (JACM)*, vol. 20, no. 1, pp. 46–61, Jan. 1973, doi: 10.1145/321738.321743.