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í.

Nepreemptivní SJF

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í.

Nepreemptivní SJF

Krok 2) V čase =2 dorazí proces P1 a přidá se do čekající fronty. P4 bude pokračovat v provádění.

Nepreemptivní SJF

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.

Nepreemptivní SJF

Krok 4) V čase = 4 dorazí proces P5 a přidá se do čekající fronty. P1 bude pokračovat v provádění.

Nepreemptivní SJF

Krok 5) V čase = 5 dorazí proces P2 a přidá se do čekající fronty. P1 bude pokračovat v provádění.

Nepreemptivní SJF

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žší.

Nepreemptivní SJF

Krok 7) V čase=10 se P2 provádí a P3 a P5 jsou ve frontě čekajících.

Nepreemptivní SJF

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ší.

Nepreemptivní SJF

Krok 9) V čase = 15 proces P5 dokončí své provádění.

Nepreemptivní SJF

Krok 10) V čase = 23 proces P3 dokončí své provádění.

Nepreemptivní SJF

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

Preemptivní SJF

Krok 1) V čase = 1 přichází proces P3. Ale P4 má kratší dobu prasknutí. Bude pokračovat v provádění.

Preemptivní SJF

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í.

Preemptivní SJF

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ší.

Preemptivní SJF

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

Preemptivní SJF

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

Preemptivní SJF

Krok 6) V čase =6 se provádí P2.

Preemptivní SJF

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

Preemptivní SJF

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ší.

Preemptivní SJF

Krok 9) V čase =15 P1 dokončí své provádění. P3 je jediný proces, který zbývá. Zahájí se provádění.

Preemptivní SJF

Krok 10) V čase =23 ukončí P3 své provádění.

Preemptivní SJF

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.