A legrövidebb munka először (SJF): Megelőző, nem megelőző példa

Alapvetően kétféle SJF módszer létezik:

• Nem megelőző SJF
• Megelőző SJF

Az SJF ütemezés jellemzői

• Az egyes munkákhoz a befejezéshez szükséges időegységként van társítva.
• Ez az algoritmus-módszer hasznos a kötegelt típusú feldolgozáshoz, ahol a feladatok befejezésére való várakozás nem kritikus.
• Javíthatja a folyamat átviteli sebességét azáltal, hogy először rövidebb feladatokat hajtanak végre, így rövid átfutási idővel.
• Javítja a feladatok teljesítményét azáltal, hogy rövidebb munkákat kínál, amelyeket először végre kell hajtani, és amelyek többnyire rövidebb átfutási idővel rendelkeznek.

Nem megelőző SJF

A nem megelőző ütemezésben, ha a processzorciklust lefoglalták a folyamat számára, a folyamat addig tartja, amíg el nem éri a várakozási állapotot vagy le nem fejeződik.

Tekintsük a következő öt folyamatot, amelyek mindegyikének saját egyedi sorozatfelvételi ideje és érkezési ideje van.

Feldolgozási sor	Burst time	Érkezési idő
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 0) A 0 időpontban P4 érkezik és megkezdi a végrehajtást.

Step 1) Az időpont= 1, megérkezik a P3 folyamat. De a P4-nek még 2 végrehajtási egységre van szüksége a befejezéshez. Folytatja a végrehajtást.

Step 2) A =2 időpontban a P1 folyamat megérkezik, és hozzáadódik a várakozási sorhoz. A P4 folytatja a végrehajtást.

Step 3) A 3 időpontban a P4 folyamat befejezi a végrehajtást. A P3 és P1 burst idejét összehasonlítjuk. A P1 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje rövidebb a P3-hoz képest.

Step 4) Amikor az időpont = 4, a P5 folyamat megérkezik, és hozzáadódik a várakozási sorhoz. A P1 folytatja a végrehajtást.

Step 5) Amikor az időpont = 5, a P2 folyamat megérkezik, és hozzáadódik a várakozási sorhoz. A P1 folytatja a végrehajtást.

Step 6) A 9 időpontban a P1 folyamat befejezi a végrehajtást. A P3, P5 és P2 burst idejét összehasonlítjuk. A P2 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje a legalacsonyabb.

Step 7) A time=10 időpontban a P2 végrehajt, a P3 és P5 pedig a várakozási sorban vannak.

Step 8) A 11 időpontban a P2 folyamat befejezi a végrehajtást. A P3 és P5 burst idejét összehasonlítjuk. A P5 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje alacsonyabb.

Step 9) A 15 időpontban a P5 folyamat befejezi a végrehajtást.

Step 10) A 23 időpontban a P3 folyamat befejezi a végrehajtást.

Step 11) Számítsuk ki a fenti példa átlagos várakozási idejét.

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

Megelőző SJF

A Preemptive SJF ütemezésben a jobok a készenléti sorba kerülnek, ahogy jönnek. A legrövidebb sorozatfelvételi idejű folyamat végrehajtása megkezdődik. Ha egy még rövidebb burst idejű folyamat érkezik, akkor az aktuális folyamatot eltávolítják, vagy megelőzik a végrehajtást, és a rövidebb jobhoz rendelik a CPU ciklust.

Fontolja meg a következő öt folyamatot:

Feldolgozási sor	Burst time	Érkezési idő
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 0) A 0 időpontban P4 érkezik és megkezdi a végrehajtást.

Feldolgozási sor	Burst time	Érkezési idő
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 1) Az időpont= 1, megérkezik a P3 folyamat. A P4-nek azonban rövidebb a sorozatfelvételi ideje. Folytatja a végrehajtást.

Step 2) Az időpont = 2, a P1 folyamat 6 burst idővel érkezik. A burst ideje hosszabb, mint a P4-é. Ezért a P4 folytatja a végrehajtást.

Step 3) A 3 időpontban a P4 folyamat befejezi a végrehajtást. A P3 és P1 burst idejét összehasonlítjuk. A P1 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje alacsonyabb.

Step 4) Az időpont = 4, a P5 folyamat megérkezik. A P3, P5 és P1 sorozatfelvételi idejét összehasonlítjuk. A P5 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje a legalacsonyabb. A P1 folyamat megelőzve van.

Feldolgozási sor	Burst time	Érkezési idő
P1	5-ból 6 maradt	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 5) Az időpont = 5, a P2 folyamat érkezik. A P1, P2, P3 és P5 burst idejét összehasonlítjuk. A P2 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje a legkevesebb. A P5 folyamat megelőzve van.

Feldolgozási sor	Burst time	Érkezési idő
P1	5-ból 6 maradt	2
P2	2	5
P3	8	1
P4	3	0
P5	3-ból 4 maradt	4

Step 6) A =6 időpontban P2 fut.

Step 7) A =7 időpontban P2 befejezi a végrehajtást. A P1, P3 és P5 burst idejét összehasonlítjuk. A P5 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje rövidebb.

Feldolgozási sor	Burst time	Érkezési idő
P1	5-ból 6 maradt	2
P2	2	5
P3	8	1
P4	3	0
P5	3-ból 4 maradt	4

Step 8) =10 időpontban a P5 befejezi a végrehajtást. A P1 és P3 burst idejét összehasonlítjuk. A P1 folyamat végrehajtásra kerül, mert a sorozatfelvételi ideje rövidebb.

Step 9) A =15 időpontban P1 befejezi a végrehajtást. A P3 az egyetlen folyamat. Megkezdi a végrehajtást.

Step 10) A =23 időpontban a P3 befejezi a végrehajtást.

Step 11) Számítsuk ki a fenti példa átlagos várakozási idejét.

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

Az SJF előnyei

Íme az SJF módszer használatának előnyei:

• Az SJF-et gyakran használják hosszú távú ütemezéshez.
• Csökkenti az átlagos várakozási időt a FIFO (First in First Out) algoritmuson keresztül.
• Az SJF módszer a legalacsonyabb átlagos várakozási időt adja meg egy adott folyamatcsoporthoz.
• Alkalmas a kötegelt munkákhoz, ahol a futási idők előre ismertek.
• A hosszú távú ütemezés kötegelt rendszeréhez a sorozatfelvételi idő becslése a munkaleírásból szerezhető be.
• A rövid távú ütemezéshez meg kell jósolnunk a következő sorozatidő értékét.
• Valószínűleg optimális az átlagos átfutási idő tekintetében.

Az SJF hátrányai/hátrányai

Íme néhány hátránya/hátránya az SJF algoritmusnak:

• A munka befejezésének idejét korábban tudni kell, de nehéz megjósolni.
• Gyakran használják kötegelt rendszerben hosszú távú ütemezéshez.
• Az SJF nem hajtható végre CPU ütemezés rövid távra. Ez azért van így, mert nincs konkrét módszer a közelgő CPU burst hosszának előrejelzésére.
• Ez az algoritmus nagyon hosszú átfutási időt vagy éhezést okozhat.
• Ismerni kell, hogy egy folyamat vagy feladat mennyi ideig fog futni.
• Ez éhezéshez vezet, ami nem csökkenti az átlagos átfutási időt.
• Nehéz megmondani a közelgő CPU-kérés hosszát.
• Az eltelt időt fel kell jegyezni, ami több terhelést eredményez a processzoron.

Összegzésként

• Az SJF egy olyan algoritmus, amelyben a legkisebb végrehajtási idejű folyamatot választják a következő végrehajtáshoz.
• Az SJF ütemezés minden egyes feladathoz a befejezés időegységeként van társítva.
• Ez az algoritmus-módszer hasznos a kötegelt típusú feldolgozáshoz, ahol a feladatok befejezésére való várakozás nem kritikus.
• Alapvetően kétféle SJF módszer létezik: 1) Nem megelőző SJF és 2) Preemptív SJF.
• A nem megelőző ütemezésben, ha a processzorciklust lefoglalták a folyamat számára, a folyamat addig tartja, amíg el nem éri a várakozási állapotot vagy le nem fejeződik.
• A megelőző SJF-ütemezésben a jobok érkezéskor a készenléti sorba kerülnek.
• Bár egy rövid sorozatidejű folyamat elindul, az aktuális folyamatot eltávolítják vagy megelőzik a végrehajtástól, és a rövidebb feladat kerül végrehajtásra elsőként.
• Az SJF-et gyakran használják hosszú távú ütemezéshez.
• Csökkenti az átlagos várakozási időt a FIFO (First in First Out) algoritmuson keresztül.
• Az SJF ütemezésben a Munka befejezési idejét korábban tudni kell, de nehéz megjósolni.
• Az SJF nem implementálható a CPU rövid távú ütemezéséhez. Ez azért van így, mert nincs konkrét módszer a közelgő CPU burst hosszának előrejelzésére.