Priority-Driven Scheduling of Periodic Tasks (Dynamic Priority) - 2

EDF with Practical Environment

 

 EDF with deadlines less than the periods

$$D_i<p_i$$

$$\sum_{j=1}^{n}\frac{e_j+p_j-D_j}{p_j}\leq 1\,\,increase\,\,execution\,\,time$$

$$\sum_{j=1}^{n}\frac{e_j}{D_j}\leq 1\,\,\,decrease\,\,period$$

 

EDF with Non-preemptable Code Section

Low Priority의 NPS(Non-preemptable code section)은 High Priority Task를 Block한다.

$$b_i=max_{j=i+1}^{n}NPS\,\,\,D_i<D_k\,\,\,\,if\,\,\,\, i<k$$

1. $\sum_{j=1}^{n}\frac{e_j}{p_j}+\frac{b_i}{p_i}\leq 1 $ task by task check (only for task i)

2. $\sum_{j=1}^{n}\frac{e_j}{p_j}+max_{j=1}^{n}\frac{b_j}{p_j}\leq 1 $ single check (for all tasks)

 

EDF with Earlier Deadline and NPS

 

1. $\sum_{j=1}^{n}\frac{e_j}{min(D_j,p_j)}+\frac{b_i}{min(D_i,p_i)}\leq 1$ task by task check (only for task i)

2. $\sum_{j=1}^{n}\frac{e_j}{min(D_j,p_j)}+max_{j=1}^{n}\frac{b_i}{min(D_i,p_i)}\leq 1$ single check (for all tasks)

 

Precedence Constraints

• 선행 Job이 수행되어야지만, 다음 Job이 수행되는 관계
• 기본적으로 , 선행 관계가 있는 경우, 후행 작업은 선행 작업을 Preempt할 수 없다.

위와 같은 관계를 가진 Task Set이 있다고 하자. 

$J_i=[r_i,d_i],e_i$:   $r$: Release tiem, $d$: Deadline, $e$: Execution time

Effective Release Times

$r_b^*=max(r_b,r_a+C_a)$

Effective Deadlines

$d_a^*=min(d_a,d_b-C_b)$

위와 같이 Effective Release Time, Deadline으로 변경하면 선행 조건이 있더라도 EDF 하에서 Optimal하다.

Optimality of Effective EDF under Precedence Constraints 

If there exists a feasible schedule(meet all release times, deadlines, precedence constraints), effective EDF schedule(EDF schedule with effective release tiems and deadlines) is also feasible

1. Effective EDF does not care about precedence constraints

• 실제 스케줄링 단계에서 precedence 제약은 고려하지 않음
• 대신 effective release time과 effective deadline을 조정함으로써 간접적 제약을 반영함

2. To show effective EDF Schedule is feasible

• 단순히 EDF로 스케줄했다고 해서 항상 feasible한 건 아님
• feasibility를 증명하려면, 모든 시간 조건과 의존성 관계가 충족됨을 보여야 한다.