logo

Korteste job først (SJF) planlægning

Indtil nu planlagde vi processerne i henhold til deres ankomsttidspunkt (i FCFS-planlægning). SJF planlægningsalgoritme planlægger dog processerne i henhold til deres bursttid.

I SJF-planlægning vil processen med den laveste bursttid blandt listen over tilgængelige processer i klarkøen blive planlagt næste gang.

Det er imidlertid meget vanskeligt at forudsige den nødvendige bursttid for en proces, og derfor er denne algoritme meget vanskelig at implementere i systemet.

Fordele ved SJF

  1. Maksimal gennemstrømning
  2. Minimum gennemsnitlig vente- og ekspeditionstid

Ulemper ved SJF

  1. Kan lide af problemet med sult
  2. Det er ikke implementerbart, fordi den nøjagtige Burst-tid for en proces ikke kan kendes på forhånd.

Der er forskellige teknikker til rådighed, hvorved processens CPU-bursttid kan bestemmes. Vi vil diskutere dem senere i detaljer.

Eksempel

I det følgende eksempel er der fem job navngivet som P1, P2, P3, P4 og P5. Deres ankomsttid og eksplosionstid er angivet i tabellen nedenfor.

PID Ankomsttid Burst Time Afslutningstid Vendetid Ventetid
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 enogtyve 12 4

Da ingen proces ankommer til tidspunktet 0 derfor; der vil være en tom plads i Gantt kort fra tid 0 til 1 (det tidspunkt, hvor den første proces ankommer).

Ifølge algoritmen planlægger OS den proces, der har den laveste bursttid blandt de tilgængelige processer i klarkøen.

Indtil nu har vi kun én proces i klarkøen, så planlæggeren vil planlægge dette til processoren, uanset hvad dens burst-tid er.

Dette vil blive udført indtil 8 tidsenheder. Indtil da har vi yderligere tre processer ankommet i klarkøen, så planlæggeren vil vælge processen med den laveste bursttid.

Blandt de processer, der er angivet i tabellen, vil P3 blive udført som det næste, da det har den laveste bursttid blandt alle de tilgængelige processer.

Så det er sådan proceduren vil fortsætte ind korteste job først (SJF) planlægningsalgoritme.

os SJF planlægningsalgoritme

Gennemsnitlig ventetid = 27/5