BI-PI.21-14 SRC
- Časové plánování úloh
- Testy plánovatelnosti a algoritmy plánování:
- Statické
- Dynamické
- Se statickou prioritou
- Dynamickou prioritou
- Preemptivní
- Nepreemptivní.
- Typy plánovačů a jejich vlastnosti:
- RMS (Rate Monotonic)
- EDF (Earliest-Deadline First)
- LL (Least-Laxity).
Testy plánovatelnosti
- Plánování je alokace prostředků, aby byly naplněny všechny časové požadavky
- Testují zda je množina připravených úloh plánovatelná tak aby všechny dávky splnily svůj deadline
- Exaktní testy - testují zda se dají úlohy naplánovat, říká ANO, NE
- Dostačující testy
- Řekne pouze že úlohy naplánovat lze
- Negativní neříká že to nutně nejde
- Nezbytné testy
- Řekne pouze že úlohy nelze naplánovat
- Negativní neříká že naplánovat jdou
Algoritmy plánování
- Statické
- Planují úlohy před spuštěním systému
- Offline jsou řízené hodinami, neplánuje se za běhu
- Plán garantuje splnění všech úloh
- Existence je dostatečný test plánovatelnosti
- Dynamické
- Reaguje na události za běhu
- Rozhoduje za běhu
- založený na prioritách běží dávka s nejvyšší prioritou
- Priority
- Statické - Lin Laylandův limit
- Určuje počet bezpečně plánovatelných úloh na jednom procesoru
- Dynamická - mez využití 100%
- Statické - Lin Laylandův limit
- Preemptivní
- Dávce může být během jejího vykonávání odebrán procesor
- Každá událost vyvolá přerušení
- Po přerušení znovu vyhodnotí která dávka se provádí
- Minimalizuje odezvu na dávku
- Nepreemptivní
- Dávka má přidělený procesor až do jejího dokončení
- Plánování běží až po skončení dávky
- Vhodné pro systémy, kde je WCET podobný WCAO
- Může vést k vyhladovění
- Jednodušší na implementaci
- Exkluzivní přístup ke zdrojům, nevyžaduje synchronizaci
Typy plánovačů a jejich vlastnosti
- Statický plánovač
- Statický rozvrh je spouštěný časem
- Časem je rozdělen na základní jednotky - úseky
- Přerušení jen od časovače - periodické
- Každá transakce je periodická s délkou periody rovné plánovacímu úseku
- Během překladu jsou uloženy plánovací rozhodnutí do tabulky
- Při běhu se plánuje dle tabulky
- Dynamické plánovače
- Není možné vytvořit dynamický plánovač, pokud existují vzájemná vyloučení mezi periodickým a sporadickým taskem
- Lin-Laylandův limit
- Postačují ale pesimistický test plánovatelnosti
- Teoretická mez plánovatelnosti pro n-úloh
- Faktor využití n-úloh s periodami p musí být menší než tato mez aby byly úlohy plánovatelné
- RMS (Rate Monotonic)
- Dynamický preemptivní se statickými prioritami
- Předpoklady
- Požadavky na HARD úlohy jsou periodické
- Úlohy jsou nezávyslé
- Relativní deadline = perioda
- WCET je konstantní a známý
- WCAO je zanedbatelný
- Periodičtější úlohy mají vyšší prioritu
- Musí platit Lin-Laylandův limit
- EDF (Earliest-Deadline First)
- Dynamický, Preemptivní, Dynamické priority
- Předpoklady shodné s RMS
- Faktor využití roste k 1
- Po události se plánuje úloha s nejbližším deadlinem
- Nejpoužívanější i pro nepreemptivní plánovač
- Větší overhead proti RMS
- LL (Least-Laxity)
- Dynamické priority
- Rozvrhování nezávislých úloh
- Úlohy s nejmenší Laxitou mají nejvyšší prioritu
- Optimální pro single core CPU
- podobné EDF
- DMS(Deadline Monotonic)
- Pro případ že deadline < plánovací perioda
- kratší relativní deadline => vyšší priorita
- pokud relativní deadline == perioda => stejné jako RMS
- statické priority
- preemptivní
Vytvořeno: 29. 5. 2026, 16:42
Poslední aktualizace: 16. 6. 2026, 22:38