Chetto-Silly-Bouchentouf (prec → nezávislé, pak EDF)
Z mapy slidu 27 ([L5.7] EDD a Hornův algoritmus) zbývá poslední polynomiální řádek: $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$ — „transformation to independent task set and then solved EDF“. Precedence (hrana $T_j \to T_k$ = „$T_k$ smí začít až po dokončení $T_j$“) znáš z [L5.2] Precedence a temporální omezení; dnes je nebudeme kreslit do grafu temporálních omezení, ale přepočítáme kvůli nim $r_j$ a $\tilde{d}_j$.
Co se pokazí, když EDF pustíš rovnou
Pracovní instance (vlastní mini-instance — přiznáno): čtyři preemptivní úlohy na jednom stroji, $r = (0, 1, 0, 2)$, $p = (2, 2, 3, 1)$, $d = \tilde{d} = (10, 4, 9, 12)$, precedence $T_1 \to T_3$, $T_2 \to T_3$, $T_2 \to T_4$:
Zkus sám: zapomeň na chvíli na precedence a pusť na instanci čisté EDF z [L5.7] („v každém okamžiku ready úloha s nejmenším deadlinem“). Co se rozbije hned v čase $t = 0$?
V $t = 0$ jsou ready $T_1$ ($\tilde{d}_1 = 10$) a $T_3$ ($r_3 = 0$, $\tilde{d}_3 = 9$). EDF vybere $T_3$ — následníka, jehož předchůdci $T_1$ a $T_2$ ještě ani nezačali. Porušení precedence. EDF je na precedence slepé: kouká jen na $r$ a $\tilde{d}$. Trik CSB: přepiš $r$ a $\tilde{d}$ tak, aby precedence „byly vidět“ už v časových parametrech — pak EDF nic porušit nemůže.
Zabuduj precedence do $r$ a $\tilde{d}$
Zkus sám: hrana $T_h \to T_j$ říká, že $T_j$ smí začít až po dokončení $T_h$. Před jaký čas se start $T_j$ reálně nikdy nedostane? Odvoď nové $r_j'$ — a rozmysli, jestli do vzorce patří původní $r_h$, nebo už upravené $r_h'$.
$T_h$ nemůže skončit dřív než v $r_h + p_h$ — takže $T_j$ nemá smysl uvolňovat před $\max\{r_j,\ r_h + p_h\}$ přes všechny bezprostřední předchůdce. Jenže $T_h$ může být sám zdržen svými předchůdci, takže správně je $r_h' + p_h$ s už upravenou hodnotou: $r_j' = \max\{r_j,\ \max\{r_h' + p_h\}\}$. Proto se DAG prochází dopředně v topologickém pořadí — úloha přijde na řadu, až když mají upravené $r'$ všichni její bezprostřední předchůdci.
Zkus sám: a symetricky — hrana $T_j \to T_k$ s deadlinem $\tilde{d}_k$ následníka. Do kdy nejpozději musí být hotová $T_j$, aby $T_k$ vůbec mohla stihnout svůj deadline? Odvoď $\tilde{d}_j'$.
$T_k$ potřebuje po dokončení $T_j$ ještě aspoň $p_k$ času, takže $T_j$ musí skončit do $\tilde{d}_k' - p_k$ (zase s upravenou hodnotou — $T_k$ může být přitlačen svými následníky). Přes všechny bezprostřední následníky: $\tilde{d}_j' = \min\{\tilde{d}_j,\ \min\{\tilde{d}_k' - p_k\}\}$ — zpětný průchod od úloh bez následníků. Pozor na častou chybu: odečítá se $p_k$ následníka, ne vlastní $p_j$.
Slide 35 (EN 1:1) — Problem $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$“Chetto, Silly, Bouchentouf algorithm transforms set $\mathcal{T}$ of dependent tasks into $\mathcal{T}'$ of independent tasks by modification of timing parameters:
- modification of the release dates
- For any task without predecessors set $r_j' = r_j$.
- Select task $T_j$ such that its release date has not been modified but the release dates of all immediate predecessors $T_h$ have been modified. If no such task exists, exit.
- Set $r_j' = \max\{r_j,\ \max\{r_h' + p_h \mid T_h \text{ is immediate predecessor of } T_j\}\}$ and jump to step 2.
- modification of deadlines
- For any task without successors set $\tilde{d}_j' = \tilde{d}_j$.
- Select a task $T_j$ such that its deadline has not been modified but the deadlines of all immediate successors $T_k$ have been modified. If no such task exists, exit.
- Set $\tilde{d}_j' = \min\{\tilde{d}_j,\ \min\{\tilde{d}_k' - p_k \mid T_k \text{ is immediate successor of } T_j\}\}$ and jump to step 2.
- EDF is executed on independent tasks in $\mathcal{T}'$”
Běh transformace na pracovní instanci
Projdi si oba průchody krok za krokem (čísla pod uzly = právě spočtené $r'$ a $\tilde{d}'$):
Pak už jen EDF
Na transformované instanci $\mathcal{T}'$: $r' = (0, 1, 3, 3)$, $p = (2, 2, 3, 1)$, $\tilde{d}' = (6, 4, 9, 12)$ — bez precedencí — běží Hornův algoritmus/EDF přesně podle pseudokódu z [L5.7]:
Zkus sám: zkontroluj ve výsledném rozvrhu všechny tři precedence. A najdi okamžik, kde by EDF s původním $\tilde{d}_1 = 10$ pořadí rozbilo.
$C_1 = 4 \le s_3 = 4$ ✓, $C_2 = 3 \le s_3 = 4$ ✓, $C_2 = 3 \le s_4 = 7$ ✓ — všechny precedence drží, ač o nich EDF „neví“. Kritický okamžik je $t = 3$: ready jsou rozdělaná $T_1$ a čerstvě uvolněné $T_3$, $T_4$. Díky zpřísnění $\tilde{d}_1' = 6 < \tilde{d}_3' = 9$ vyhraje předchůdce $T_1$; s původním $\tilde{d}_1 = 10 > 9$ by EDF pustilo následníka $T_3$ před nedokončeného předchůdce.
Proč je to korektní
Zkus sám: dvě obavy. (1) Nezahodí zpřísnění $r' \ge r$, $\tilde{d}' \le \tilde{d}$ nějaký dobrý rozvrh? (2) Proč EDF na $\mathcal{T}'$ nikdy nespustí následníka před dokončením předchůdce? (Nápověda k (2): porovnej $\tilde{d}_j'$ a $\tilde{d}_k'$ pro $T_j \to T_k$ — ostře?)
(1) Zpřísněné meze jsme odvodili z precedencí: žádný rozvrh respektující precedence stejně nemůže začít $T_j$ před $r_j'$ ani dokončit po $\tilde{d}_j'$ (jinak by následníci nestihli). Takže množina přípustných rozvrhů se nezmenšila — jen jsme ji popsali časovými okny. A obráceně: kdo stihne přísnější okna, stihne i původní. (2) Pro hranu $T_j \to T_k$ platí $\tilde{d}_j' \le \tilde{d}_k' - p_k < \tilde{d}_k'$ ostře (protože $p_k > 0$) — dokud je předchůdce nedokončený a ready, EDF ho vždy upřednostní; a díky $r_k' \ge r_j' + p_j$ se následník ani neuvolní, dokud předchůdce nemohl doběhnout.
Slide 36 (EN 1:1) — No problem constraints are violated by Chetto, Silly, Bouchentouf algorithm- “$r_j' \ge r_j$ and $\tilde{d}_j' \le \tilde{d}_j$, therefore, the schedulability of $\mathcal{T}'$ with respect to the timing constraints (release dates and deadlines) implies also schedulability of $\mathcal{T}$ with respect to the timing constraints
- due to the structure of Horn's alg. (consider a set of released tasks and choose the one with smallest deadline) and modification of the timing constraints the scheduled tasks of $\mathcal{T}'$ are ordered in the same way as given by the precedence constraints, therefore, precedence constraints of $\mathcal{T}$ are not violated”
Celé to tedy je polynomiální recept na $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$: dva průchody DAGem + EDF; optimalita EDF z [L5.7] se přenáší a EDF na $\mathcal{T}'$ pořád rozhoduje schedulabilitu ($L_{\max} \le 0$ ⟺ existuje přípustný rozvrh — teď i vůči precedencím). Pro více procesorů tahle transformace nestačí: feasibilitu $P\,|\,\mathrm{pmtn}, r_j, \tilde{d}_j\,|$ řeší toky v [L5.0], $P\,|\,\mathrm{pmtn}, \mathrm{prec}\,|\,C_{max}$ Muntz & Coffman [L5.10]; nepreemptivní jednostrojový případ s deadliny řeší Bratleyho B&B [L5.9].
Nebezpečné polopravdy① „Stačí dosadit původní hodnoty sousedů.“ Ne — průchody jdou v topologickém pořadí a používají už upravené hodnoty: $r_h' + p_h$ (ne $r_h + p_h$), $\tilde{d}_k' - p_k$ (ne $\tilde{d}_k - p_k$). Krok 2 pseudokódu to vynucuje („…all immediate predecessors have been modified“). ② Čí $p$ se přičítá/odečítá? U release přičítáš $p_h$ předchůdce, u deadline odečítáš $p_k$ následníka — nikdy vlastní $p_j$. ③ EDF běží na $r', \tilde{d}'$, ale $L_{\max}$ vyhodnoť proti původním $d_j$ — $\tilde{d}'$ je jen pracovní nástroj transformace ($\tilde{d}_j' \le \tilde{d}_j$, takže s $\tilde{d}'$ by sis výsledek uměle zhoršil). ④ Jen jeden stroj. CSB stojí na tom, že EDF na jednom stroji s ostře menším $\tilde{d}'$ předchůdce nikdy nepředběhne — na více procesorech běží úlohy vedle sebe a argument padá (tam Muntz & Coffman [L5.10]).
Key takeaways — L5.8- CSB = transformace na nezávislé úlohy + EDF pro $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$ (polynomiální).
- Dopředný průchod: $r_j' = \max\{r_j,\ \max_{T_h \to T_j}\{r_h' + p_h\}\}$ — od úloh bez předchůdců, s už upravenými $r_h'$.
- Zpětný průchod: $\tilde{d}_j' = \min\{\tilde{d}_j,\ \min_{T_j \to T_k}\{\tilde{d}_k' - p_k\}\}$ — od úloh bez následníků, odečítá se $p$ následníka.
- Korektnost: $r_j' \ge r_j$, $\tilde{d}_j' \le \tilde{d}_j$ ⟹ schedulabilita $\mathcal{T}'$ implikuje schedulabilitu $\mathcal{T}$; EDF předchůdce nikdy nepředběhne ($\tilde{d}_j' < \tilde{d}_k'$ ostře), takže precedence drží samy.
- Vyhodnocení: $L_{\max} = \max_j(C_j - d_j)$ proti původním due datům; $L_{\max} \le 0$ ⟺ existuje přípustný rozvrh (EDF rozhoduje schedulabilitu i s precedencemi).
“a) Using Chetto, Silly, Bouchentouf algorithm solve the following instance of mono-processor scheduling of preemptive tasks with precedence relations, release dates and due-dates equal to deadlines while minimizing the maximum lateness. Indicate values of main variables in separate steps of the algorithm. Draw the Gantt chart.
$$r = (0, 3, 2, 6, 3)$$ $$p = (2, 3, 2, 2, 3)$$ $$\tilde{d} = d = (3, 7, 13, 9, 13)$$
Precedence graph (edge list, source $T_1$ on the left, sink $T_5$ on the right): $T_1 \to T_2$, $T_1 \to T_3$, $T_2 \to T_4$, $T_2 \to T_5$, $T_3 \to T_5$, $T_4 \to T_5$.
b) Calculate the $L_{\max}$ value of the optimal solution.”
a) Co je v zadání?
Pět preemptivních úloh na jednom stroji s release times, deadliny rovnými due datům a precedencemi (DAG se zdrojem $T_1$ a stokem $T_5$). Máme spustit CSB: oba průchody s vypsanými mezivýpočty („values of main variables in separate steps“), pak EDF, Gantt a $L_{\max}$.
b) Co k tomu budeme potřebovat?
- Tato lekce — vzorce obou průchodů a topologické pořadí (takeaways).
- [L5.7] EDD a Hornův algoritmus — běh EDF (rozhodovací body, $\delta$, preempce).
- [L5.1] Grahamova notace — čtení $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$.
c) Jak nad úlohou uvažovat?
Nejdřív dopředný průchod od $T_1$ (jediná bez předchůdců), pak zpětný od $T_5$ (jediná bez následníků) — u každé úlohy vypiš celý $\max$/$\min$ se všemi bezprostředními sousedy, to jsou ty „main variables in separate steps“. Pak zahoď hrany a vede tabulka iterací EDF jako v [L5.7]: $t_1$, $t_2$, ready množina s $\tilde{d}'$, vítěz, $\delta$. Nakonec $L_j = C_j - d_j$ proti původním due datům.
d) Úplné řešení (hodnoty $r'$, $\tilde{d}'$, Gantt i $L_{\max}$ dle slidu 37)
Dopředný průchod (release dates), topologicky $T_1, T_2, T_3, T_4, T_5$:
| $T_j$ | bezpr. předchůdci | $r_j' = \max\{r_j,\ \max\{r_h' + p_h\}\}$ | $r_j'$ |
|---|---|---|---|
| $T_1$ | — | $r_1' = r_1$ | $0$ |
| $T_2$ | $T_1$ | $\max\{3,\ 0 + 2\}$ | $3$ |
| $T_3$ | $T_1$ | $\max\{2,\ 0 + 2\}$ | $2$ |
| $T_4$ | $T_2$ | $\max\{6,\ 3 + 3\}$ | $6$ |
| $T_5$ | $T_2, T_3, T_4$ | $\max\{3,\ 3 + 3,\ 2 + 2,\ 6 + 2\}$ | $8$ |
Zpětný průchod (deadliny), topologicky $T_5, T_4, T_3, T_2, T_1$:
| $T_j$ | bezpr. následníci | $\tilde{d}_j' = \min\{\tilde{d}_j,\ \min\{\tilde{d}_k' - p_k\}\}$ | $\tilde{d}_j'$ |
|---|---|---|---|
| $T_5$ | — | $\tilde{d}_5' = \tilde{d}_5$ | $13$ |
| $T_4$ | $T_5$ | $\min\{9,\ 13 - 3\}$ | $9$ |
| $T_3$ | $T_5$ | $\min\{13,\ 13 - 3\}$ | $10$ |
| $T_2$ | $T_4, T_5$ | $\min\{7,\ 9 - 2,\ 13 - 3\}$ | $7$ |
| $T_1$ | $T_2, T_3$ | $\min\{3,\ 7 - 3,\ 10 - 2\}$ | $3$ |
Shodně se slidem 37: $r' = (0, 3, 2, 6, 8)$, $\tilde{d}' = (3, 7, 10, 9, 13)$.
EDF na nezávislých úlohách $\mathcal{T}'$ (vítěz tučně, $\tilde{d}'$ v závorkách):
| # | $t_1$ | $t_2$ | $T'$ (ready) | $\delta$ | naplánováno | po kroku |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | $\mathbf{T_1}(3)$ | $\min\{2, 2\} = 2$ | $T_1\ \langle 0, 2)$ | $T_1$ hotová, $C_1 = 2$ |
| 2 | 2 | 3 | $\mathbf{T_3}(10)$ | $\min\{2, 1\} = 1$ | $T_3\ \langle 2, 3)$ | $p_3 := 1$ (preempce) |
| 3 | 3 | 6 | $T_3(10),\ \mathbf{T_2}(7)$ | $\min\{3, 3\} = 3$ | $T_2\ \langle 3, 6)$ | $T_2$ hotová, $C_2 = 6$ |
| 4 | 6 | 8 | $T_3(10),\ \mathbf{T_4}(9)$ | $\min\{2, 2\} = 2$ | $T_4\ \langle 6, 8)$ | $T_4$ hotová, $C_4 = 8$ |
| 5 | 8 | $\infty$ | $\mathbf{T_3}(10),\ T_5(13)$ | $\min\{1, \infty\} = 1$ | $T_3\ \langle 8, 9)$ | $T_3$ hotová, $C_3 = 9$ |
| 6 | 9 | $\infty$ | $\mathbf{T_5}(13)$ | $\min\{3, \infty\} = 3$ | $T_5\ \langle 9, 12)$ | $T_5$ hotová, $C_5 = 12$ |
Všimni si role transformace: v iteraci 2 je $T_3$ preemptována releasem naléhavější $T_2$; v iteraci 4 vyhrává $T_4$ nad $T_3$ díky zpřísněnému $\tilde{d}_3' = 10$; a $T_5$ se díky $r_5' = 8$ vůbec neuvolní, dokud nemohli doběhnout všichni její předchůdci.
Lateness proti původním $d = (3, 7, 13, 9, 13)$: $L_1 = 2 - 3 = -1$, $L_2 = 6 - 7 = -1$, $L_3 = 9 - 13 = -4$, $L_4 = 8 - 9 = -1$, $L_5 = 12 - 13 = -1$.
$$L_{\max} = -1.$$
b) CSB + EDF je pro $1\,|\,\mathrm{pmtn}, \mathrm{prec}, r_j, d_j = \tilde{d}_j\,|\,L_{\max}$ optimální (slide 27 + optimalita EDF z [L5.7] + korektnost transformace, slide 36), takže $L_{\max}$ optimálního řešení je přímo hodnota z bodu a): $L_{\max}^* = -1$ — vše stíháme s rezervou 1.
Pozn. k podkladům (přiznáno): textový přepis obrázku slidu 37 vyjmenovává jen hrany $T_1 \to T_2$, $T_1 \to T_3$, $T_2 \to T_4$, $T_2 \to T_5$, $T_3 \to T_5$ — bez $T_4 \to T_5$. Obě zkoušková zadání (21. 6. 2021 i 2023) a banka #39 hranu $T_4 \to T_5$ uvádějí a vlastní řešení slidu ji potvrzuje: $r_5' = 8 = r_4' + p_4$ vyjde jen s ní. Počítáme tedy se všemi šesti hranami.
Using the Chetto, Silly, Bouchentouf algorithm solve the following instance of mono-processor scheduling of preemptive tasks with precedence relations, release dates and due-dates equal to deadlines:
$$r = (0, 0, 1, 0), \qquad p = (1, 2, 2, 2), \qquad \tilde{d} = d = (9, 3, 8, 6),$$
precedence constraints $T_1 \to T_2$, $T_1 \to T_3$, $T_3 \to T_4$.
(i) Compute the modified release dates $r'$ and modified deadlines $\tilde{d}'$.
(ii) Run EDF on the transformed independent-task instance, draw the Gantt chart and compute $L_{\max}$.
(iii) Does a feasible schedule (meeting all deadlines) exist for this instance? Justify your answer.
a) Co je v zadání?
Čtyři preemptivní úlohy, jeden stroj, precedence tvoří vidličku s řetízkem ($T_1$ před vším, $T_3$ před $T_4$). Část (iii) chce verdikt feasibility — vzpomeň si, co EDF rozhoduje.
b) Co k tomu budeme potřebovat?
- Tato lekce — oba průchody + korektnost (takeaways).
- [L5.7] — EDF rozhoduje schedulabilitu ($L_{\max} \le 0$ ⟺ feasible).
c) Jak nad úlohou uvažovat?
Pozor na dvě místa, kde se meze opravdu mění: $\tilde{d}_3$ stlačí následník $T_4$ (i když $\tilde{d}_4 < \tilde{d}_3$ — právě proto!) a $\tilde{d}_1$ stlačí oba následníci. U (iii) nehádej: výsledné $L_{\max}$ je sám o sobě certifikát — ale rozmysli si, kterým směrem implikace platí a proč je tu i opačná (optimalita EDF).
d) Úplné řešení (vlastní — přiznáno)
(i) Dopředný průchod ($T_1$ bez předchůdců): $r_1' = 0$; $r_2' = \max\{0,\ 0 + 1\} = 1$; $r_3' = \max\{1,\ 0 + 1\} = 1$; $r_4' = \max\{0,\ r_3' + p_3 = 1 + 2\} = 3$. Tedy $r' = (0, 1, 1, 3)$.
Zpětný průchod ($T_2$, $T_4$ bez následníků): $\tilde{d}_2' = 3$; $\tilde{d}_4' = 6$; $\tilde{d}_3' = \min\{8,\ \tilde{d}_4' - p_4 = 6 - 2\} = 4$; $\tilde{d}_1' = \min\{9,\ \tilde{d}_2' - p_2 = 3 - 2,\ \tilde{d}_3' - p_3 = 4 - 2\} = 1$. Tedy $\tilde{d}' = (1, 3, 4, 6)$ — všimni si, jak řetízek $T_3 \to T_4$ propadl až do $\tilde{d}_1'$.
(ii) EDF na $r' = (0, 1, 1, 3)$, $\tilde{d}' = (1, 3, 4, 6)$:
| # | $t_1$ | $t_2$ | $T'$ (ready) | $\delta$ | naplánováno |
|---|---|---|---|---|---|
| 1 | 0 | 1 | $\mathbf{T_1}(1)$ | $\min\{1, 1\} = 1$ | $T_1\ \langle 0, 1)$, $C_1 = 1$ |
| 2 | 1 | 3 | $\mathbf{T_2}(3),\ T_3(4)$ | $\min\{2, 2\} = 2$ | $T_2\ \langle 1, 3)$, $C_2 = 3$ |
| 3 | 3 | $\infty$ | $\mathbf{T_3}(4),\ T_4(6)$ | $\min\{2, \infty\} = 2$ | $T_3\ \langle 3, 5)$, $C_3 = 5$ |
| 4 | 5 | $\infty$ | $\mathbf{T_4}(6)$ | $\min\{2, \infty\} = 2$ | $T_4\ \langle 5, 7)$, $C_4 = 7$ |
Lateness proti původním $d = (9, 3, 8, 6)$: $L_1 = 1 - 9 = -8$, $L_2 = 3 - 3 = 0$, $L_3 = 5 - 8 = -3$, $L_4 = 7 - 6 = 1$, tedy $$L_{\max} = 1 \quad (\text{určuje } T_4).$$
(iii) Ne, přípustný rozvrh neexistuje. CSB + EDF minimalizuje $L_{\max}$, takže $L_{\max}^* = 1 > 0$ znamená, že žádný rozvrh všechny deadliny nestihne (EDF rozhoduje schedulabilitu, [L5.7]). Ručně to lze nahlédnout i bez věty: celková práce je $\sum p_j = 7$, takže úloha dokončená jako poslední má $C \ge 7$; poslední přitom může být jen $T_2$, nebo $T_4$ (předchůdce nikdy nekončí po svém následníkovi: $C_1 < C_2$ a $C_3 < C_4$). Skončí-li poslední $T_2$: $L_2 \ge 7 - 3 = 4$; skončí-li $T_4$: $L_4 \ge 7 - 6 = 1$. V každém případě $L_{\max} \ge 1$ — a EDF hodnoty $1$ dosáhlo, je tedy optimální a verdikt je definitivní.