Prvo najkraći posao (SJF): Preemptivni, nepreemptivni primjer
Nathaniel Brooks
Što je najkraći raspored prvog posla?
Najkraći posao prvi (SJF) je algoritam u kojem se za sljedeće izvršenje bira proces koji ima najmanje vrijeme izvršenja. Ova metoda raspoređivanja može biti preventivna ili nepreventivna. Značajno smanjuje prosječno vrijeme čekanja za druge procese koji čekaju na izvršenje. Puni oblik SJF-a je najkraći posao.
U osnovi postoje dvije vrste SJF metoda:
- Nepreemptivni SJF
- Preemptivni SJF
Karakteristike SJF rasporeda
- Povezan je sa svakim poslom kao jedinica vremena koje treba izvršiti.
- Ova algoritamska metoda korisna je za serijsku obradu, gdje čekanje da se poslovi završe nije kritično.
- Može poboljšati propusnost procesa osiguravajući da se prvi izvrše kraći poslovi, stoga vjerojatno imaju kratko vrijeme obrade.
- Poboljšava učinak posla nudeći kraće poslove, koji bi se trebali izvršiti prvi, a koji uglavnom imaju kraće vrijeme obrade.
Nepreemptivni SJF
U raspoređivanju bez prioriteta, nakon što je CPU ciklus dodijeljen procesu, proces ga zadržava dok ne dosegne stanje čekanja ili dok se ne prekine.
Razmotrite sljedećih pet procesa, od kojih svaki ima svoje jedinstveno vrijeme praska i vrijeme dolaska.
| Proces čekanja | Vrijeme praska | Vrijeme dolaska |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Korak 0) U vrijeme = 0, P4 dolazi i počinje izvršavanje.
Korak 1) U trenutku = 1 dolazi proces P3. No, P4 još uvijek treba 2 izvršne jedinice za dovršetak. Nastavit će s izvršenjem.
Korak 2) U trenutku =2 dolazi proces P1 i dodaje se u red čekanja. P4 će nastaviti s izvršenjem.
Korak 3) U trenutku = 3, proces P4 će završiti svoje izvršenje. Uspoređuje se vrijeme praska P3 i P1. Proces P1 se izvršava jer je njegovo vrijeme pražnjenja kraće u usporedbi s P3.
Korak 4) U trenutku = 4, proces P5 dolazi i dodaje se u red čekanja. P1 će nastaviti s izvršenjem.
Korak 5) U trenutku = 5, proces P2 dolazi i dodaje se u red čekanja. P1 će nastaviti s izvršenjem.
Korak 6) U trenutku = 9, proces P1 će završiti svoje izvršenje. Uspoređuje se vrijeme praska P3, P5 i P2. Proces P2 se izvršava jer je njegovo vrijeme praska najniže.
Korak 7) U trenutku=10, P2 se izvršava, a P3 i P5 su u redu čekanja.
Korak 8) U trenutku = 11, proces P2 će završiti svoje izvršenje. Uspoređuje se vrijeme praska P3 i P5. Proces P5 se izvršava jer je njegovo vrijeme praska niže.
Korak 9) U trenutku = 15, proces P5 će završiti svoje izvršenje.
Korak 10) U trenutku = 23, proces P3 će završiti svoje izvršenje.
Korak 11) Izračunajmo prosječno vrijeme čekanja za gornji primjer.
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
Preemptivni SJF
U Preemptive SJF Scheduling, poslovi se stavljaju u red čekanja čim dođu. Proces s najkraćim vremenom praska počinje s izvršenjem. Ako stigne proces s čak i kraćim vremenom pražnjenja, trenutni proces se uklanja ili izbacuje iz izvršenja, a kraćem poslu dodjeljuje se CPU ciklus.
Razmotrite sljedećih pet procesa:
| Proces čekanja | Vrijeme praska | Vrijeme dolaska |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Korak 0) U vrijeme = 0, P4 dolazi i počinje izvršavanje.
| Proces čekanja | Vrijeme praska | Vrijeme dolaska |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Korak 1) U trenutku = 1 dolazi proces P3. Ali P4 ima kraće vrijeme praska. Nastavit će s izvršenjem.
Korak 2) U trenutku = 2, proces P1 dolazi s burst time = 6. Burst time je više od vremena P4. Stoga će P4 nastaviti s izvršenjem.
Korak 3) U trenutku = 3, proces P4 će završiti svoje izvršenje. Uspoređuje se vrijeme praska P3 i P1. Proces P1 se izvršava jer je njegovo vrijeme praska niže.
Korak 4) U trenutku = 4 dolazi proces P5. Uspoređuje se vrijeme praska P3, P5 i P1. Proces P5 se izvršava jer je njegovo vrijeme praska najniže. Proces P1 ima prednost.
| Proces čekanja | Vrijeme praska | Vrijeme dolaska |
|---|---|---|
| P1 | Preostalo je 5 od 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Korak 5) U trenutku = 5 dolazi proces P2. Uspoređuje se vrijeme praska P1, P2, P3 i P5. Proces P2 se izvršava jer je njegovo vrijeme praska najmanje. Proces P5 ima prednost.
| Proces čekanja | Vrijeme praska | Vrijeme dolaska |
|---|---|---|
| P1 | Preostalo je 5 od 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Preostalo je 3 od 4 | 4 |
Korak 6) U trenutku =6, P2 se izvršava.
Korak 7) U trenutku =7, P2 završava svoje izvršenje. Uspoređuje se vrijeme praska P1, P3 i P5. Proces P5 se izvršava jer je njegovo vrijeme praska kraće.
| Proces čekanja | Vrijeme praska | Vrijeme dolaska |
|---|---|---|
| P1 | Preostalo je 5 od 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Preostalo je 3 od 4 | 4 |
Korak 8) U trenutku =10, P5 će završiti svoje izvršenje. Uspoređuje se vrijeme praska P1 i P3. Proces P1 se izvršava jer je njegovo vrijeme praska kraće.
Korak 9) U trenutku =15, P1 završava svoje izvršenje. P3 je jedini preostali proces. Pokrenut će izvršenje.
Korak 10) U trenutku =23, P3 završava svoje izvršenje.
Korak 11) Izračunajmo prosječno vrijeme čekanja za gornji primjer.
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
Prednosti SJF-a
Evo prednosti/prednosti korištenja SJF metode:
- SJF se često koristi za dugoročno planiranje.
- Smanjuje prosječno vrijeme čekanja preko FIFO (First in First Out) algoritma.
- SJF metoda daje najniže prosječno vrijeme čekanja za određeni skup procesa.
- Prikladan je za poslove koji se izvode u serijama, gdje su vremena izvođenja unaprijed poznata.
- Za paketni sustav dugoročnog raspoređivanja, procjena vremena praska može se dobiti iz opisa posla.
- Za kratkoročno planiranje, moramo predvidjeti vrijednost sljedećeg vremena praska.
- Vjerojatno optimalno s obzirom na prosječno vrijeme obrade.
Nedostaci/protiv SJF
Evo nekoliko nedostataka/protivnosti SJF algoritma:
- Vrijeme završetka posla mora se znati ranije, ali ga je teško predvidjeti.
- Često se koristi u paketnom sustavu za dugoročno planiranje.
- SJF se ne može implementirati za CPU raspoređivanje na kratak rok. To je zato što ne postoji specifična metoda za predviđanje duljine nadolazećeg CPU bursta.
- Ovaj algoritam može uzrokovati vrlo duga vremena obrade ili izgladnjivanje.
- Zahtijeva znanje o tome koliko dugo će proces ili posao trajati.
- To dovodi do gladovanja koje ne smanjuje prosječno vrijeme obrade.
- Teško je znati duljinu nadolazećeg CPU zahtjeva.
- Proteklo vrijeme treba biti zabilježeno, što rezultira većim opterećenjem procesora.
rezime
- SJF je algoritam u kojem se za sljedeće izvršenje bira proces koji ima najmanje vrijeme izvršenja.
- SJF planiranje povezano je sa svakim poslom kao jedinica vremena koje treba izvršiti.
- Ova algoritamska metoda korisna je za serijsku obradu, gdje čekanje da se poslovi završe nije kritično.
- U osnovi postoje dvije vrste SJF metoda 1) Nepreemptivni SJF i 2) Preemptivni SJF.
- U raspoređivanju bez prioriteta, nakon što je CPU ciklus dodijeljen procesu, proces ga zadržava dok ne dosegne stanje čekanja ili dok se ne prekine.
- U Preemptive SJF Scheduling, poslovi se stavljaju u red čekanja čim dođu.
- Iako započinje proces s kratkim vremenom praska, trenutni proces se uklanja ili izbacuje iz izvršenja, a posao koji je kraći izvršava se prvi.
- SJF se često koristi za dugoročno planiranje.
- Smanjuje prosječno vrijeme čekanja preko FIFO (First in First Out) algoritma.
- U SJF planiranju, vrijeme završetka posla mora biti poznato ranije, ali ga je teško predvidjeti.
- SJF se ne može implementirati za kratkoročno raspoređivanje procesora. To je zato što ne postoji specifična metoda za predviđanje duljine nadolazećeg CPU bursta.
