2
$\begingroup$

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<p_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$.

enter image description here

$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<t∆+\sum_{f\neq k}\ e_f$

but I cannot prove $∆>1$

$\endgroup$
0
0
$\begingroup$

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.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.