Mi a legrövidebb munka első ütemezése?
A Shortest Job First (SJF) egy olyan algoritmus, amelyben a legkisebb végrehajtási idővel rendelkező folyamatot választják ki a következő végrehajtásra. Ez az ütemezési módszer lehet megelőző vagy nem megelőző. Jelentősen lecsökkenti az egyéb végrehajtásra váró folyamatok átlagos várakozási idejét. Az SJF teljes formája a Legrövidebb munka.
Alapvetően kétféle SJF módszer létezik:
- Nem megelőző SJF
- Megelőző SJF
Ebben az operációs rendszer bemutatóban megtudhatja:
- Mi a legrövidebb munka első ütemezése?
- Az SJF ütemezés jellemzői
- Nem megelőző SJF
- Megelőző SJF
- Az SJF előnyei
- Az SJF hátrányai / hátrányai
Az SJF ütemezés jellemzői
- Minden munkához a teljesítés időegységeként kapcsolódik.
- Ez az algoritmus módszer hasznos a kötegelt típusú feldolgozásnál, ahol a munkák befejezésére való várakozás nem kritikus.
- Javíthatja a folyamat áteresztőképességét azáltal, hogy gondoskodik arról, hogy először rövidebb feladatokat hajtsanak végre, és ezáltal rövid átfutási idővel bírjon.
- Javítja a munka eredményét azáltal, hogy rövidebb állásokat kínál, amelyeket először végre kell hajtani, amelyek többnyire rövidebb átfutási idővel rendelkeznek.
Nem megelőző SJF
A nem megelőző ütemezésben, amint a CPU-ciklust kiosztják a folyamathoz, a folyamat addig tartja, amíg várakozási állapotba nem kerül vagy le nem áll.
Vegye figyelembe a következő öt folyamatot, amelyek mindegyikének megvan a maga egyedi sorozatfelvételi ideje és érkezési ideje.
| Folyamat sor | Burst time | Érkezési idő |
| P1 | 6. | 2 |
| P2 | 2 | 5. |
| P3 | 8. | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
0. lépés: A = 0 időpontban megérkezik a P4, és elindítja a végrehajtást.
1. lépés : Időben = 1 érkezik a P3 folyamat. De a P4 befejezéséhez még mindig 2 végrehajtási egységre van szükség. Folytatja a végrehajtást.
2. lépés: A = 2 időpontban megérkezik a P1 folyamat, és hozzáadódik a várakozási sorhoz. A P4 folytatja a végrehajtást.
3. lépés: A = 3 időpontban a P4 folyamat befejezi a végrehajtását. Összehasonlítjuk a P3 és a P1 törésidejét. A P1 folyamatot azért hajtják végre, mert annak tört ideje rövidebb a P3-hoz képest.
4. lépés: A = 4 időpontban megérkezik a P5 folyamat, és hozzáadódik a várakozási sorhoz. A P1 folytatja a végrehajtást.
5. lépés: Az időpontban = 5 a P2 folyamat megérkezik, és hozzáadódik a várakozási sorhoz. A P1 folytatja a végrehajtást.
6. lépés: A = 9 időpontban a P1 folyamat befejezi a végrehajtását. Összehasonlítjuk a P3, P5 és P2 törésidejét. A P2 folyamatot azért hajtják végre, mert annak tört ideje a legkisebb.
7. lépés: A = 10 időpontban P2 végrehajt, P3 és P5 pedig várakozási sorban van.
8. lépés: A 11 = időpontban a P2 folyamat befejezi a végrehajtását. Összehasonlítjuk a P3 és a P5 törésidejét. A P5 folyamatot azért hajtják végre, mert annak tört ideje alacsonyabb.
9. lépés: A = 15 időpontban a P5 folyamat befejezi a végrehajtását.
10. lépés: A = 23 időpontban a P3 folyamat befejezi a végrehajtását.
11. lépés) Számítsuk ki a fenti példa átlagos várakozási idejét.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Megelőző SJF
A megelőző SJF-ütemezésben a munkák kész állapotba kerülnek, amint jönnek. A legrövidebb sorozatidővel rendelkező folyamat megkezdi a végrehajtást. Ha még rövidebb sorozatidővel rendelkező folyamat is megérkezik, az aktuális folyamat eltávolításra kerül, vagy előbbre kerül a végrehajtás, és a rövidebb feladat CPU-ciklust kap.
Vegye figyelembe a következő öt folyamatot:
| Folyamat sor | Burst time | Érkezési idő |
| P1 | 6. | 2 |
| P2 | 2 | 5. |
| P3 | 8. | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
0. lépés: A = 0 időpontban megérkezik a P4, és elindítja a végrehajtást.
| Folyamat sor | Burst time | Érkezési idő |
| P1 | 6. | 2 |
| P2 | 2 | 5. |
| P3 | 8. | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
1. lépés : Időben = 1 érkezik a P3 folyamat. De a P4 rövidebb sorozatidővel rendelkezik. Folytatja a végrehajtást.
2. lépés: A 2-es időpontban a P1 folyamat = 6-os sorozatidővel érkezik. A sorozatidő meghaladja a P4-esét. Ezért a P4 folytatja a végrehajtást.
3. lépés: A = 3 időpontban a P4 folyamat befejezi a végrehajtását. Összehasonlítjuk a P3 és a P1 törésidejét. A P1 folyamatot azért hajtják végre, mert annak tört ideje alacsonyabb.
4. lépés: A = 4 időpontban megérkezik a P5 folyamat. Összehasonlítjuk a P3, P5 és P1 törésidejét. A P5 folyamatot azért hajtják végre, mert annak sorozatideje a legalacsonyabb. A P1 folyamat meg van előzve.
| Folyamat sor | Burst time | Érkezési idő |
| P1 | 6-ból 5 maradt | 2 |
| P2 | 2 | 5. |
| P3 | 8. | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
5. lépés: 5-ös időpontban megérkezik a P2 folyamat. A P1, P2, P3 és P5 törésidejét összehasonlítjuk. A P2 folyamatot azért hajtják végre, mert annak tört ideje legkevesebb. A P5 folyamat meg van előzve.
| Folyamat sor | Burst time | Érkezési idő |
| P1 | 6-ból 5 maradt | 2 |
| P2 | 2 | 5. |
| P3 | 8. | 1 |
| P4 | 3 | 0 |
| P5 | 4-ből 3 maradt | 4 |
6. lépés: A = 2 időpontban a P2 végrehajtja.
7. lépés) A = 2 időpontban a P2 befejezi a végrehajtását. Összehasonlítjuk a P1, P3 és P5 törésidejét. A P5 folyamatot azért hajtják végre, mert annak tört ideje rövidebb.
| Folyamat sor | Burst time | Érkezési idő |
| P1 | 6-ból 5 maradt | 2 |
| P2 | 2 | 5. |
| P3 | 8. | 1 |
| P4 | 3 | 0 |
| P5 | 4-ből 3 maradt | 4 |
8. lépés: A = 5 időpontban a P5 befejezi a végrehajtását. Összehasonlítjuk a P1 és P3 törésidejét. A P1 folyamatot azért hajtják végre, mert annak tört ideje kevesebb.
9. lépés) A = 15 időpontban a P1 befejezi a végrehajtását. A P3 az egyetlen folyamat maradt. Megkezdi a végrehajtást.
10. lépés: A = 23 időpontban a P3 befejezi a végrehajtását.
11. lépés) Számítsuk ki a fenti példa átlagos várakozási idejét.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 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 / 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) algoritmus felett.
- Az SJF módszer a legalacsonyabb átlagos várakozási időt adja meg egy adott folyamatkészlethez.
- Megfelelő azok a kötegelt futtatású munkák, amelyeknél a futási idő előre ismert.
- A hosszú távú ütemezés kötegelt rendszeréhez a sorozatidő becslése beszerezhető a munkaköri leírásból.
- A rövid távú ütemezéshez meg kell jósolnunk a következő sorozatfelvétel idejét.
- Valószínűleg optimális az átlagos átfutási idő szempontjából.
Az SJF hátrányai / hátrányai
Íme néhány hátrány / hátrány az SJF algoritmus számára:
- A munka befejezési idejét korábban kell tudni, de nehéz megjósolni.
- Gyakran kötegelt rendszerben használják hosszú távú ütemezéshez.
- Az SJF rövid távon nem valósítható meg a CPU ütemezéséhez. Azért van, 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őket vagy éhezést okozhat.
- Szükség van ismeretekre, hogy egy folyamat vagy munka mennyi ideig fog futni.
- Az éhezéshez vezet, amely nem csökkenti az átlagos átfutási időt.
- Nehéz megtudni a közelgő CPU-kérés hosszát.
- Az eltelt időt rögzíteni kell, ami több processzort jelent.
Összegzés
- Az SJF egy olyan algoritmus, amelyben a legkisebb végrehajtási idővel rendelkező folyamatot választják ki a következő végrehajtásra.
- Az SJF ütemezése az egyes munkákhoz időegységként társul.
- Ez az algoritmus módszer hasznos a kötegelt típusú feldolgozásnál, ahol a munkák 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) megelőző SJF.
- A nem megelőző ütemezésben, amint a CPU-ciklust kiosztják a folyamathoz, a folyamat addig tartja, amíg várakozási állapotba nem kerül vagy le nem áll.
- A megelőző SJF-ütemezésben a munkák kész állapotba kerülnek, amint jönnek.
- Bár egy rövid sorozatidővel rendelkező folyamat megkezdődik, az aktuális folyamat eltávolításra kerül vagy megakadályozásra kerül, és a rövidebb feladatot az 1. végrehajtja.
- 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) algoritmus felett.
- Az SJF ütemezésében a munka befejezési idejét korábban kell tudni, de nehéz megjósolni.
- Az SJF rövid távon nem valósítható meg a CPU ütemezéséhez. Azért van, mert nincs konkrét módszer a közelgő CPU-burst hosszának előrejelzésére.