Co je plánování nejkratší práce?
Shortest Job First (SJF) je algoritmus, ve kterém je pro další provedení zvolen proces s nejmenší dobou provedení. Tato metoda plánování může být preventivní i nepřekonatelná. Výrazně snižuje průměrnou čekací dobu na další procesy čekající na provedení. Plná forma SJF je Shortest Job First.
V zásadě existují dva typy metod SJF:
- Nepreventivní SJF
- Preventivní SJF
V tomto kurzu operačního systému se naučíte:
- Co je plánování nejkratší práce?
- Charakteristika plánování SJF
- Nepreventivní SJF
- Preventivní SJF
- Výhody SJF
- Nevýhody / nevýhody SJF
Charakteristika plánování SJF
- Je spojena s každou úlohou jako jednotka času k dokončení.
- Tato metoda algoritmu je užitečná pro dávkové zpracování, kde čekání na dokončení úloh není kritické.
- Může zlepšit propustnost procesu tím, že zajistí, že se nejprve provedou kratší úlohy, a proto možná budou mít krátkou dobu zpracování.
- Zlepšuje výstup úlohy tím, že nabízí kratší úlohy, které by měly být provedeny jako první, které většinou mají kratší dobu zpracování.
Nepreventivní SJF
V nepreventivním plánování, jakmile je cyklus CPU přidělen procesu, proces ho drží, dokud nedosáhne stavu čekání nebo nebude ukončen.
Zvažte následujících pět procesů, z nichž každý má svůj vlastní jedinečný čas roztržení a čas příjezdu.
| Procesní fronta | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 0) V čase = 0 přijde P4 a zahájí provádění.
Krok 1) V čase = 1 dorazí proces P3. K dokončení však P4 stále potřebuje 2 popravní jednotky. Bude pokračovat v provádění.
Krok 2) V čase = 2 dorazí proces P1 a je přidán do čekající fronty. P4 bude pokračovat v provádění.
Krok 3) V čase = 3 proces P4 dokončí své provádění. Porovnává se doba roztržení P3 a P1. Proces P1 je proveden, protože jeho doba roztržení je kratší ve srovnání s P3.
Krok 4) V čase = 4 dorazí proces P5 a je přidán do čekající fronty. P1 bude pokračovat v provádění.
Krok 5) V čase = 5 dorazí proces P2 a je přidán do čekající fronty. P1 bude pokračovat v provádění.
Krok 6) V čase = 9 proces P1 dokončí své provádění. Srovnává se doba roztržení P3, P5 a P2. Proces P2 je spuštěn, protože jeho doba roztržení je nejnižší.
Krok 7) V čase = 10 se provádí P2 a P3 a P5 jsou ve frontě čekání.
Krok 8) V čase = 11 dokončí proces P2 proces P2. Srovnává se doba roztržení P3 a P5. Proces P5 je spuštěn, protože jeho doba roztržení je nižší.
Krok 9) V čase = 15 dokončí proces P5 jeho provádění.
Krok 10) V čase = 23 dokončí proces P3 jeho provádění.
Krok 11) Vypočítáme průměrnou čekací dobu pro výše uvedený příklad.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Preventivní SJF
V preventivním plánování SJF jsou úlohy zařazeny do připravené fronty hned, jak přijdou. Spustí se proces s nejkratší dobou shluku. Pokud přijde proces s ještě kratším časem shluku, aktuální proces je odebrán nebo předcházet provedení a kratší úloze je přidělen cyklus CPU.
Zvažte následujících pět procesů:
| Procesní fronta | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 0) V čase = 0 přijde P4 a zahájí provádění.
| Procesní fronta | Čas prasknutí | Čas příjezdu |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 1) V čase = 1 dorazí proces P3. Ale P4 má kratší čas roztržení. Bude pokračovat v provádění.
Krok 2) V čase = 2 přijde proces P1 s časem roztržení = 6. Čas roztržení je více než u P4. Proto bude P4 pokračovat v provádění.
Krok 3) V čase = 3 proces P4 dokončí své provádění. Porovnává se doba roztržení P3 a P1. Proces P1 je spuštěn, protože jeho doba roztržení je nižší.
Krok 4) V čase = 4 dorazí proces P5. Srovnává se doba roztržení P3, P5 a P1. Proces P5 je spuštěn, protože jeho doba roztržení je nejnižší. Proces P1 je preempted.
| Procesní fronta | Čas prasknutí | Čas příjezdu |
| P1 | Zbývá 5 ze 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 5) V čase = 5 dorazí proces P2. Porovnává se doba roztržení P1, P2, P3 a P5. Proces P2 je spuštěn, protože jeho doba roztržení je nejméně. Proces P5 je preempted.
| Procesní fronta | Čas prasknutí | Čas příjezdu |
| P1 | Zbývá 5 ze 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Zbývají 3 ze 4 | 4 |
Krok 6) V čase = 6 se provádí P2.
Krok 7) V čase = 7 dokončí P2 svoji realizaci. Srovnává se doba roztržení P1, P3 a P5. Proces P5 je spuštěn, protože jeho doba roztržení je kratší.
| Procesní fronta | Čas prasknutí | Čas příjezdu |
| P1 | Zbývá 5 ze 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Zbývají 3 ze 4 | 4 |
Krok 8) V čase = 10 dokončí P5 provádění. Srovnává se doba roztržení P1 a P3. Proces P1 je proveden, protože jeho doba roztržení je kratší.
Krok 9) V čase = 15 P1 dokončí své provádění. P3 je jediný zbývající proces. Spustí se provádění.
Krok 10) V čase = 23 P3 dokončí své provádění.
Krok 11) Vypočítáme průměrnou čekací dobu pro výše uvedený příklad.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Výhody SJF
Zde jsou výhody / výhody použití metody SJF:
- SJF se často používá pro dlouhodobé plánování.
- Snižuje průměrnou čekací dobu při použití algoritmu FIFO (First in First Out).
- Metoda SJF poskytuje nejnižší průměrnou čekací dobu pro konkrétní sadu procesů.
- Je vhodný pro úlohy spuštěné v dávce, kde jsou časy běhu známy předem.
- U dávkového systému dlouhodobého plánování lze odhad doby shluku získat z popisu úlohy.
- Pro krátkodobé plánování potřebujeme předpovědět hodnotu příštího dávkového času.
- Pravděpodobně optimální s ohledem na průměrnou dobu zpracování.
Nevýhody / nevýhody SJF
Zde jsou některé nevýhody / nevýhody algoritmu SJF:
- Čas dokončení úlohy musí být znám dříve, ale je těžké ho předvídat.
- Často se používá v dávkovém systému pro dlouhodobé plánování.
- SJF nelze krátkodobě implementovat pro plánování CPU. Je to proto, že neexistuje žádná konkrétní metoda k předpovědi délky nadcházejícího výbuchu CPU.
- Tento algoritmus může způsobit velmi dlouhé doby obratu nebo hladovění.
- Vyžaduje znalost toho, jak dlouho proces nebo úloha poběží.
- Vede k hladovění, které nesnižuje průměrnou dobu obratu.
- Je těžké zjistit délku nadcházejícího požadavku CPU.
- Uplynulý čas by měl být zaznamenán, což má za následek větší režii procesoru.
souhrn
- SJF je algoritmus, ve kterém je pro další provedení zvolen proces s nejmenší dobou provedení.
- Plánování SJF je spojeno s každou úlohou jako jednotka času na dokončení.
- Tato metoda algoritmu je užitečná pro dávkové zpracování, kde čekání na dokončení úloh není kritické.
- V zásadě existují dva typy metod SJF 1) Preemptivní SJF a 2) Preemptivní SJF.
- V nepreventivním plánování, jakmile je cyklus CPU přidělen procesu, proces ho drží, dokud nedosáhne stavu čekání nebo nebude ukončen.
- V preventivním plánování SJF jsou úlohy zařazeny do připravené fronty hned, jak přijdou.
- I když začíná proces s krátkou dobou shluku, aktuální proces je odebrán nebo je mu zabráněno v provedení a úloha, která je kratší, je provedena jako první.
- SJF se často používá pro dlouhodobé plánování.
- Snižuje průměrnou čekací dobu při použití algoritmu FIFO (First in First Out).
- V plánování SJF musí být čas dokončení úlohy znám dříve, ale je těžké ho předpovědět.
- SJF nelze krátkodobě implementovat pro plánování CPU. Je to proto, že neexistuje žádná konkrétní metoda k předpovědi délky nadcházejícího výbuchu CPU.