logo

Plánování nejkratší práce nejdříve (SJF).

Doposud jsme procesy plánovali podle času jejich příchodu (v plánování FCFS). Plánovací algoritmus SJF však naplánuje procesy podle jejich doby shluku.

věk dharmendry

V plánování SJF se jako další naplánuje proces s nejnižší dobou shluku ze seznamu dostupných procesů ve frontě připravenosti.

Je však velmi obtížné předpovědět dobu shluku potřebnou pro proces, a proto je velmi obtížné tento algoritmus implementovat do systému.

Výhody SJF

  1. Maximální propustnost
  2. Minimální průměrná doba čekání a obrátky

Nevýhody SJF

  1. Může trpět problémem hladovění
  2. Není to implementovatelné, protože přesný čas burstu pro proces nelze předem znát.

Existují různé dostupné techniky, pomocí kterých lze určit dobu shluku CPU procesu. Podrobně je probereme později.

Příklad

V následujícím příkladu je pět úloh pojmenovaných jako P1, P2, P3, P4 a P5. Jejich čas příjezdu a čas burstu jsou uvedeny v tabulce níže.

PID Čas příjezdu Burst Time Čas dokončení Turn Around Time Čekací doba
1 1 7 8 7 0
2 3 3 13 10 7
3 6 2 10 4 2
4 7 10 31 24 14
5 9 8 dvacet jedna 12 4

Protože žádný proces nedorazí v čase 0, tedy; v něm bude prázdný slot Ganttův diagram od času 0 do 1 (čas, kdy dorazí první proces).

Podle algoritmu OS naplánuje proces, který má nejnižší dobu burstu mezi dostupnými procesy ve frontě připravenosti.

Doposud máme ve frontě připraven pouze jeden proces, takže plánovač to naplánuje procesoru bez ohledu na to, jaká je doba jeho shluku.

Toto bude provedeno do 8 jednotek času. Do té doby máme ve frontě připravené tři další procesy, takže plánovač vybere proces s nejnižší dobou shluku.

Mezi procesy uvedenými v tabulce se jako další provede P3, protože má nejnižší dobu burstu ze všech dostupných procesů.

Takže takto bude postup pokračovat nejdříve nejkratší práce (SJF) rozvrhovací algoritmus.

os SJF plánovací algoritmus

Průměrná čekací doba = 27/5