# Early Deadline First (EDF) scheduling in real-time systems feasibility test proof

I am trying to prove Theorem 6.2 on page 127 of the book Real-Time Systems by Jane W. S. Liu: http://www.cse.hcmut.edu.vn/~thai/books/2000%20_%20Liu-%20Real%20Time%20Systems.pdf

It is based on Early Deadline First(EDF) scheduling.

It says the proof is similar to the proof for Theorem 6.1 on page 124-126. However, I am still stuck.

Here is what I have so far:

Density of task $$T_j:\ \delta_j=\frac{e_j}{\min{\left(D_j,p_j\right)}}$$

Density of the system: $$∆=\sum_{j=1}^{n}\delta_j=\sum_{j=1}^{n}\frac{e_j}{\min{\left(D_j,p_j\right)}}$$

$$e_j$$ is the execution time for task $$T_j$$

$$D_j$$ is the deadline for task $$T_j$$

$$p_j$$ is the period for task $$T_j$$

$$\emptyset_j$$ is the phase for task $$T_j$$

$$r_{j,b}$$ is the release time for task $$T_j$$ at period $$b$$

$$J_{j,b}$$ is the job for task $$T_j$$ at period $$b$$

$$\emptyset_j=r_{j,1}$$

$$r_{j,b}+p_j=r_{j,b+1}$$

THEOREM 6.2. A system $$T$$ of independent, preemptable tasks can be feasibly scheduled on one processor if its density is equal to or less than $$1$$.

If $$D_j for some $$j$$, then $$∆=\sum_{j=1}^{n}\frac{e_j}{\min{\left(D_j,p_j\right)}}\le1$$ is only a sufficient condition so we can only say that the system may not be schedulable when the condition is not satisfied.

I try to prove the contrapositive just as Theorem 6.1 on page 124-126. So what I try to prove is that if according to an EDF schedule, the system fails to meet some deadlines, then its density is larger than $$1$$.

Suppose that the system begins to execute at time $$0$$. And at time $$t$$, the job $$J_{i,c}$$ of task $$T_i$$ misses its deadline. Assume the case that the current period of every task begins at or after $$r_{i,c}$$, the release time of the job that misses its deadline. We use $$t$$ to divide two types of task besides task $$T_i$$ as in below figure: 1) tasks with deadline happens before $$t$$ in the current period just like $$T_f$$, 2) tasks with deadline happens after $$t$$ in the current period just like $$T_k$$. $$J_{i,c}$$ misses its deadline at $$t$$ tells us that any current job whose deadline is after $$t$$ is not given any processor time to execute before $$t$$ and that the total processor time required to complete $$J_{i,c}$$ and all the jobs with deadlines at or before $$t$$ exceeds the total available time $$t$$. So we have

$$t<\left\lceil\frac{\left(t-\emptyset_i\right)}{p_i}\right\rceil e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{\left\lceil\frac{\left(t-\emptyset_f\right)}{p_f}\right\rceil e}_f$$

then

$$t<\left\lfloor\frac{\left(t-\emptyset_i\right)}{p_i}\right\rfloor e_i+e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset_f\right)}{p_f}\right\rfloor e}_f+\sum_{f\neq i,f\neq k}\ e_f}$$

And it is

$$=\left\lfloor\frac{\left(t-\emptyset_i\right)}{p_i}\right\rfloor e_i+\sum_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset_k\right)}{p_k}\right\rfloor e}_k+\sum_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset_f\right)}{p_f}\right\rfloor e}_f+\sum_{f\neq k}\ e_f}$$

$$\le \left(\frac{t}{p_i}\right)e_i+\sum_{k\neq i,k\neq f}{\left(\frac{t}{p_k}\right)e}_k+\sum_{f\neq i,f\neq k}{{\left(\frac{t}{p_f}\right)e}_f+\sum_{f\neq k}\ e_f}$$

$$=t\sum_{h=1}^{n}\frac{e_h}{p_h}+\sum_{f\neq k}\ e_f$$

$$\le t\sum_{h=1}^{n}\frac{e_h}{\min{\left(D_h,p_h\right)}}+\sum_{f\neq k}\ e_f$$

$$=t∆+\sum_{f\neq k}\ e_f$$

So I prove up to $$t

but I cannot prove $$∆>1$$

I might be too focus on the algebra. I believe I only need to argue or proof a scenario that would give the least density of the system that will fail to meet a deadline. As shown in the figure below, all tasks start at the same time with same period and deadline. For each of period, each task only have time slot D=D1=D2=...=Dn to execute. In other words, they share exactly the same time slot to execute. If density > 1 then obviously schedule will fail. If the below system has a density of $$1^+$$(greater than 1 by the smallest amount), then any changes on Di or Pi will only increase the density of the system or make the system feasible. 