[03] Uniprocessor Real-Time Scheduling

Set of tasks가 deadline과 함께 주어지면, real-time scheduling을 통해 policy에 따라 computing 자원에 task를 할당하게 된다. 목표는 deadline을 최대한 충족하는 것이다.

 

스케쥴링 알고리즘을 제안할 수도, 스케쥴 가능성(schedulability)을 분석할 수도 있다. Schedulability란 real-time 시스템이 모든 task의 deadline을 충족시킬 수 있는 지를 의미한다. 이를 만족하기 위해 스케쥴링을 통해 task의 실행 순서를 결정한다.

 

1. Priority-based 스케쥴링

• Task-level fixed-priority (TFP) 스케쥴링 : 각 task에 고정된 priority 부여
• Job-level fixed-priority (JFP) 스케쥴링 : 각 job에 고정된 priority 부여

TFP < JFP

 

일반적으로 real-time embedded system은 uniprocessor 환경이다. 이때 preemptive priority-based scheduler는 다음과 같다. Optimal의 의미는, 해당 스케쥴링이 안되면 다른 친구들 모두 안된다는 의미이다.

• Optimal TFP : RM
• Optimal JFP : EDF

 

2. RM (Rate Monotonic)

가장 짧은 주기를 가지는 task의 priority를 높게 측정하는 방법이다. 당연히 deadline miss가 발생할 수 있으며, 이를 파악하기 위해 response time 개념이 사용된다.

• Response time : finished time - released time

 

어떤 task의 maximum response time을 구해, 이것이 period보다 작은지 확인하는 방식으로 RM이 사용 가능한 지 확인할 수 있다. Maximum response time을 구하는 식은 다음과 같다.

 

그래서 만약 모든 task i에 대해서 $r_i < p_i$면 해당  real-time system은 RM에 의해 스케쥴링 가능하다고 본다.

 

또 다른 방식으로는 utilization을 사용할 수 있다. 아래의 부등식을 만족하면, 해당 시스템은 RM으로 스케쥴링 가능하다.

 

가령 T(4,1), T(5,1), T(10,1)이면 $\sum U_i = 0.55$이고 n=3이므로 우항은 0.78이 된다. 따라서 tasks가 RM에 의해 스케쥴링 가능함을 알 수 있다. 우항의 특성상 다음과 같은 bound를 가지고 있다.

 

3. EDF (Earliest Deadline First)

가장 빠른 deadline의 task를 우선적으로 수행하는 방법이다. EDF의 실행 가능성을 보기 위해서 사용되는 것은 Demand Bound Function, dbf(t)이다. dbf(t)는 주어진 간격 t 동안 시스템이 처리해야 할 최대 workload를 의미한다.

 

그래서 만약 모든 interval t에 대해서 dbf(t) < t이면, 해당 시스템은 EDF로 스케쥴링할 수 있다.

 

EDF 역시 utilization으로도 schedulability를 확인할 수 있다. $\sum U_i \leq 1$이면 된다. 다른 말로 하면, EDF를 사용할 시 utilization을 1로 뽑아 낼 수 있음을 의미하며 성능적인 면에서도 optimal임을 보여준다.

 

EDF의 단점 중 하나는 domino effect에 의한 연속적인 deadline miss이다.

 

4. 정리

RM	EDF
Simple implementation (timing constraint 신경 안씀) Highest priority task는 predictability를 보여줌	Full processor utilization Misbehavior during overload conditions