Nejkratší práce jako první (SJF): Preemptivní, nepreemptivní příklad
Co je to nejkratší plánování práce?
Nejkratší práce jako první (SJF) je algoritmus, ve kterém je pro další spuštění vybrán proces s nejmenší dobou provádění. Tato metoda plánování může být preemptivní nebo nepreemptivní. Výrazně snižuje průměrnou dobu čekání na další procesy čekající na provedení. Plná forma SJF je Shortest Job First.
V zásadě existují dva typy metod SJF:
- Nepreemptivní SJF
- Preemptivní SJF
Charakteristika rozvrhu 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í, aby byly nejprve provedeny kratší úlohy, a proto mohou mít krátkou dobu obratu.
- Zlepšuje výstup úloh tím, že nabízí kratší úlohy, které by měly být provedeny jako první, které mají většinou kratší dobu obratu.
Nepreemptivní SJF
V nepreemptivním plánování, jakmile je proces CPU přidělen, proces jej podrží, dokud nedosáhne stavu čekání nebo není ukončen.
Zvažte následujících pět procesů, z nichž každý má svůj vlastní jedinečný čas shluku a čas příchodu.
Fronta procesů | Č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 dorazí P4 a spustí provádění.
Krok 1) V čase = 1 přichází proces P3. Ale P4 stále potřebuje k dokončení 2 prováděcí jednotky. Bude pokračovat v provádění.
Krok 2) V čase =2 dorazí proces P1 a přidá se 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á se doba burstu P3 a P1. Proces P1 se provede, protože jeho doba shluku je kratší ve srovnání s procesem P3.
Krok 4) V čase = 4 dorazí proces P5 a přidá se do čekající fronty. P1 bude pokračovat v provádění.
Krok 5) V čase = 5 dorazí proces P2 a přidá se do čekající fronty. P1 bude pokračovat v provádění.
Krok 6) V čase = 9 proces P1 dokončí své provádění. Porovná se doba burstu P3, P5 a P2. Proces P2 se provede, protože jeho doba burstu je nejnižší.
Krok 7) V čase=10 se P2 provádí a P3 a P5 jsou ve frontě čekajících.
Krok 8) V čase = 11 proces P2 dokončí své provádění. Porovná se doba burstu P3 a P5. Proces P5 se provede, protože jeho doba burstu je kratší.
Krok 9) V čase = 15 proces P5 dokončí své provádění.
Krok 10) V čase = 23 proces P3 dokončí své provádění.
Krok 11) Vypočítejme průměrnou dobu čekání pro výše uvedený příklad.
Wait time P4= 0-0=0 P1= 3-2=1 P2= 9-5=4 P5= 11-4=7 P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Preemptivní SJF
V Preemptive SJF Scheduling jsou úlohy zařazovány do fronty připravené tak, jak přicházejí. Proces s nejkratší dobou shluku se spustí. Pokud přijde proces s ještě kratší dobou shluku, aktuální proces je odstraněn nebo vyřazen z provádění a kratší úloha je přidělena cyklu CPU.
Zvažte následujících pět procesů:
Fronta procesů | Č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 dorazí P4 a spustí provádění.
Fronta procesů | Č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 přichází proces P3. Ale P4 má kratší dobu prasknutí. Bude pokračovat v provádění.
Krok 2) V čase = 2 přichází proces P1 s dobou shluku = 6. Doba shluku je delší 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á se doba burstu P3 a P1. Proces P1 se provede, protože jeho doba burstu je kratší.
Krok 4) V čase = 4 dorazí proces P5. Porovná se doba burstu P3, P5 a P1. Proces P5 se provede, protože jeho doba burstu je nejnižší. Proces P1 je vyloučen.
Fronta procesů | Č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á se doba burstu P1, P2, P3 a P5. Proces P2 je proveden, protože jeho doba shluku je nejmenší. Proces P5 je vyloučen.
Fronta procesů | Čas prasknutí | Čas příjezdu |
---|---|---|
P1 | Zbývá 5 ze 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | Zbývá 3 ze 4 | 4 |
Krok 6) V čase =6 se provádí P2.
Krok 7) V čase =7 ukončí P2 své provádění. Porovná se doba burstu P1, P3 a P5. Proces P5 se provede, protože jeho doba burstu je kratší.
Fronta procesů | Čas prasknutí | Čas příjezdu |
---|---|---|
P1 | Zbývá 5 ze 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | Zbývá 3 ze 4 | 4 |
Krok 8) V čase =10 P5 dokončí své provádění. Porovná se doba burstu P1 a P3. Proces P1 se provede, protože jeho doba burstu je kratší.
Krok 9) V čase =15 P1 dokončí své provádění. P3 je jediný proces, který zbývá. Zahájí se provádění.
Krok 10) V čase =23 ukončí P3 své provádění.
Krok 11) Vypočítejme průměrnou dobu čekání pro výše uvedený příklad.
Wait time P4= 0-0=0 P1= (3-2) + 6 =7 P2= 5-5 = 0 P5= 4-4+2 =2 P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Výhody SJF
Zde jsou výhody/klady používání metody SJF:
- SJF se často používá pro dlouhodobé plánování.
- Snižuje průměrnou čekací dobu oproti algoritmu FIFO (First in First Out).
- Metoda SJF udává nejnižší průměrnou čekací dobu pro konkrétní sadu procesů.
- Je vhodný pro úlohy běžící v dávce, kde jsou předem známy doby běhu.
- Pro dávkový systém dlouhodobého plánování lze odhad doby shluku získat z popisu práce.
- Pro krátkodobé plánování potřebujeme předpovědět hodnotu příštího burst time.
- Asi optimální s ohledem na průměrnou dobu obratu.
Nevýhody/nevýhody SJF
Zde jsou některé nevýhody / nevýhody algoritmu SJF:
- Čas dokončení úkolu 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 implementovat plánování CPU krátkodobě. Je to proto, že neexistuje žádná konkrétní metoda, jak předpovědět délku nadcházejícího shluku CPU.
- Tento algoritmus může způsobit velmi dlouhé doby obratu nebo hladovění.
- Vyžaduje znalost toho, jak dlouho bude proces nebo úloha probíhat.
- Vede to k hladovění, které nezkracuje průměrnou dobu obratu.
- Je těžké znát 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.
Shrnutí
- SJF je algoritmus, ve kterém je pro další spuštění vybrán proces s nejmenší dobou provádění.
- Plánování SJF je spojeno 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é.
- V zásadě existují dva typy metod SJF 1) Nepreemptivní SJF a 2) Preemptivní SJF.
- V nepreemptivním plánování, jakmile je proces CPU přidělen, proces jej podrží, dokud nedosáhne stavu čekání nebo není ukončen.
- V Preemptive SJF Scheduling jsou úlohy zařazovány do fronty připravené tak, jak přicházejí.
- I když se spustí proces s krátkou dobou shluku, aktuální proces je odstraněn nebo vyřazen z provádění a úloha, která je kratší, se provede jako první.
- SJF se často používá pro dlouhodobé plánování.
- Snižuje průměrnou čekací dobu oproti algoritmu FIFO (First in First Out).
- Při plánování SJF musí být čas dokončení úlohy znám dříve, ale je těžké to předvídat.
- SJF nelze krátkodobě implementovat pro plánování CPU. Je to proto, že neexistuje žádná konkrétní metoda, jak předpovědět délku nadcházejícího shluku CPU.