A legrövidebb munka először (SJF): Megelőző, nem megelőző példa
Nathaniel Brooks
⚡ Okos összefoglaló
A Shortest Job First (SJF) egy CPU-ütemező algoritmus, amely a legrövidebb futási idejű folyamatot választja ki következő futtatásra. Lehet preemptív vagy nem preemptív, és jelentősen csökkenti a folyamatok átlagos várakozási idejét.
Mi a legrövidebb munka első ütemezése?
Először a legrövidebb munka (SJF) egy olyan algoritmus, amelyben a legkisebb végrehajtási idejű folyamatot választjuk a következő végrehajtáshoz. Ez az ütemezési módszer lehet preemptív vagy nem megelőző. Jelentősen csökkenti a végrehajtásra váró többi folyamat átlagos várakozási idejét. Az SJF teljes formája a Shortest Job First.
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 folyamatok áteresztőképességét azáltal, hogy biztosítja, hogy a rövidebb feladatok először végrehajtásra kerüljenek, így valószínűleg rövidebb átfutási idővel járnak.
- Javítja a munkateljesítményt azáltal, hogy rövidebb munkákat kínál, amelyeket először végre kell hajtani, és amelyeknek többnyire rövidebb az átfutási idejük.
Nem megelőző SJF
A nem megelőző ütemezés során, miután a CPU-ciklust lefoglalták egy folyamathoz, a folyamat addig tartja azt, amíg el nem éri a várakozási állapotot, vagy le nem áll.
Tekintsük a következő öt folyamatot, amelyek mindegyikének megvan a saját egyedi burst ideje és érkezési ideje.
| 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őpillanatban megérkezik a P4 és megkezdi a végrehajtást.
Step 1) Az 1-es időpontban megérkezik a P3 folyamat. De a P4-nek még 2 végrehajtási egységre van szüksége a befejezéshez. A végrehajtás folytatódik.
Step 2) Amikor az időpont = 2, 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 10-es időpontban a P2 végrehajtás alatt áll, a P3 és a P5 pedig a várakozó sorban áll.
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 az átlagos várakozási időt a fenti példára.
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 preemptív SJF ütemezés során a feladatok a érkezésekor kerülnek a készenléti várólistába. A legrövidebb burst idejű folyamat kezdi meg a végrehajtást. Ha egy még rövidebb burst idejű folyamat érkezik, az aktuális folyamatot eltávolítják vagy felfüggesztik a végrehajtásból, és a rövidebb feladat kap egy CPU-ciklust.
Vegyük figyelembe 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őpillanatban megérkezik a P4 é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 1 időpillanatban megérkezik a P3 folyamat. De a P4-nek rövidebb a burst 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 5-ös időpontban a P2 folyamat megérkezik. A P1, P2, P3 és P5 löketidőit összehasonlítjuk. A P2 folyamatot azért hajtjuk végre, mert ennek a legrövidebb a löketideje. A P5 folyamatot előzetesen végrehajtjuk.
| 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-os időpontban a P2 fut.
Step 7) A 7-es időpontban a P2 befejezi a végrehajtását. A P1, P3 és P5 löketidőit összehasonlítjuk. A P5 folyamatot azért hajtjuk végre, mert a löketideje 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-es időpontban a P5 folyamat befejezi a végrehajtását. A P1 és a P3 burst idejét összehasonlítjuk. A P1 folyamat végrehajtásra kerül, mivel a burst ideje rövidebb.
Step 9) 15-ös időpontban a P1 befejezi a végrehajtását. A P3 az egyetlen folyamat, ami maradt. Ez fogja elindítani a végrehajtást.
Step 10) 23 időpontban a P3 befejezi a végrehajtását.
Step 11) Számítsuk ki az átlagos várakozási időt a fenti példára.
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/kedvezőtlenségei:
- Az SJF-et gyakran használják hosszú távú ütemezéshez.
- Csökkenti az átlagos várakozási időt a FIFO (elsőként be, elsőként ki) algoritmushoz képest.
- Az SJF módszer a legalacsonyabb átlagos várakozási időt adja meg egy adott folyamatkészlethez.
- 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 ez az 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 implementálható a következőhöz: 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.
- Éhezéshez vezet, ami nem csökkenti az átlagos fordulási időt.
- Nehéz megmondani a közelgő CPU-kérés hosszát.
- Az eltelt időt rögzíteni kell, ami nagyobb terhelést jelent a processzor számára.
