Što je prvo planiranje najkraćeg posla?
Najkraći posao prvo (SJF) algoritam je u kojem se postupak koji ima najmanje vrijeme izvršenja bira za sljedeće izvršavanje. Ova metoda raspoređivanja može biti preventivna ili nepreventivna. Značajno smanjuje prosječno vrijeme čekanja za ostale procese koji čekaju izvršenje. Puni oblik SJF-a je Najkraći posao prvo.
U osnovi postoje dvije vrste SJF metoda:
- Nepreventivni SJF
- Preventivni SJF
U ovom vodiču za operativni sustav naučit ćete:
- Što je prvo planiranje najkraćeg posla?
- Karakteristike SJF zakazivanja
- Nepreventivni SJF
- Preventivni SJF
- Prednosti SJF-a
- Mane / nedostaci SJF-a
Karakteristike SJF zakazivanja
- Uz svaki je posao povezan kao jedinica vremena koju treba dovršiti.
- Ova metoda algoritma korisna je za skupnu obradu, gdje čekanje završetka poslova nije kritično.
- Može poboljšati protok procesa osiguravajući da se najprije izvršavaju kraći poslovi, stoga možda ima kratko vrijeme obrade.
- Poboljšava izlaznu ponudu nudeći kraće poslove, koje bi prvo trebalo izvršiti, a koji uglavnom imaju kraće vrijeme obrade.
Nepreventivni SJF
U ne-preventivnom planiranju, nakon što se procesorski ciklus dodijeli procesu, proces ga zadržava dok ne dosegne stanje čekanja ili se prekine.
Razmotrite sljedećih pet procesa od kojih svaki ima svoje jedinstveno vrijeme izbijanja i vrijeme dolaska.
| Red č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 stiže i započinje izvršenje.
Korak 1) U vrijeme = 1, dolazi proces P3. Ali, P4 i dalje trebaju dvije izvršne jedinice za dovršetak. Nastavit će se izvršenje.
Korak 2) U vrijeme = 2, dolazi proces P1 koji se dodaje u red čekanja. P4 će nastaviti izvršenje.
Korak 3) U trenutku = 3, postupak P4 će završiti svoje izvršavanje. Uspoređuje se vrijeme pucanja P3 i P1. Proces P1 se izvršava jer je njegovo vrijeme pucanja manje u odnosu na P3.
Korak 4) U vrijeme = 4, dolazi proces P5 koji se dodaje u red čekanja. P1 će nastaviti izvršenje.
Korak 5) U vrijeme = 5, dolazi proces P2 koji se dodaje u red čekanja. P1 će nastaviti izvršenje.
Korak 6) U vrijeme = 9, postupak P1 će završiti svoje izvršavanje. Uspoređuje se vrijeme pucanja P3, P5 i P2. Proces P2 se izvršava jer je njegovo vrijeme pucanja najniže.
Korak 7) U vrijeme = 10, P2 se izvršava, a P3 i P5 su u redu čekanja.
Korak 8) U vrijeme = 11, postupak P2 će završiti svoje izvršavanje. Uspoređuje se vrijeme pucanja P3 i P5. Proces P5 se izvodi jer je njegovo vrijeme pucanja kraće.
Korak 9) U vrijeme = 15, postupak P5 će završiti svoje izvršavanje.
Korak 10) U vrijeme = 23, postupak P3 će završiti svoje izvršavanje.
Korak 11) Izračunajmo prosječno vrijeme čekanja za gornji primjer.
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
Preventivni SJF
U preventivnom SJF raspoređivanju, poslovi se stavljaju u red spremnosti čim dođu. Proces s najkraćim vremenom pucanja započinje s izvršenjem. Ako stigne proces s čak kraćim vremenom burst-a, trenutni se postupak uklanja ili sprečava iz izvršavanja, a kraći posao dodjeljuje se ciklusu procesora.
Razmotrimo sljedećih pet procesa:
| Red č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 stiže i započinje izvršenje.
| Red čekanja | Vrijeme praska | Vrijeme dolaska |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Korak 1) U vrijeme = 1, dolazi proces P3. Ali, P4 ima kraće vrijeme pucanja. Nastavit će se izvršenje.
Korak 2) U vrijeme = 2, proces P1 dolazi s vremenom pucanja = 6. Vrijeme pucanja je više od vremena P4. Stoga će P4 nastaviti izvršenje.
Korak 3) U trenutku = 3, postupak P4 će završiti svoje izvršavanje. Uspoređuje se vrijeme pucanja P3 i P1. Proces P1 se izvodi jer je njegovo vrijeme pucanja kraće.
Korak 4) U vrijeme = 4, stići će postupak P5. Uspoređuje se vrijeme pucanja P3, P5 i P1. Proces P5 se izvršava jer je njegovo vrijeme pucanja najniže. Proces P1 je preduhitren.
| Red č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 vrijeme = 5, stići će postupak P2. Uspoređuje se vrijeme pucanja P1, P2, P3 i P5. Proces P2 se izvršava jer je njegovo vrijeme pucanja najmanje. Proces P5 je preduhitren.
| Red čekanja | Vrijeme praska | Vrijeme dolaska |
| P1 | Preostalo je 5 od 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Preostala su 3 od 4 | 4 |
Korak 6) U trenutku = 6, izvršava se P2.
Korak 7) U trenutku = 7, P2 završava svoje izvršavanje. Uspoređuje se vrijeme pucanja P1, P3 i P5. Proces P5 se izvršava jer je vrijeme pucanja kraće.
| Red čekanja | Vrijeme praska | Vrijeme dolaska |
| P1 | Preostalo je 5 od 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Preostala su 3 od 4 | 4 |
Korak 8) U vrijeme = 10, P5 će završiti svoje izvršavanje. Uspoređuje se vrijeme pucanja P1 i P3. Postupak P1 se izvršava jer je vrijeme pucanja kraće.
Korak 9) U vrijeme = 15, P1 završava svoje izvršavanje. P3 je jedini preostali postupak. Započet će izvršenje.
Korak 10) U vrijeme = 23, P3 završava svoje izvršavanje.
Korak 11) Izračunajmo prosječno vrijeme čekanja za gornji primjer.
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
Prednosti SJF-a
Evo prednosti / prednosti upotrebe SJF metode:
- SJF se često koristi za dugoročno raspoređivanje.
- 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.
- Prikladno je za poslove koji se izvode u šarži, gdje su vremena izvođenja unaprijed poznata.
- Za paketni sustav dugoročnog rasporeda, iz opisa posla može se dobiti procjena vremena pucanja.
- Za kratkoročno zakazivanje moramo predvidjeti vrijednost sljedećeg vremena snimanja.
- Vjerojatno optimalno s obzirom na prosječno vrijeme obrade.
Mane / nedostaci SJF-a
Evo nekoliko nedostataka / nedostataka SJF algoritma:
- Vrijeme završetka posla mora se znati ranije, ali teško je predvidjeti.
- Često se koristi u paketnom sustavu za dugoročno raspoređivanje.
- SJF se ne može kratkoročno implementirati za planiranje CPU-a. To je zato što ne postoji posebna metoda za predviđanje duljine nadolazećeg CPU-a.
- Ovaj algoritam može prouzročiti vrlo dugo vrijeme obrta ili izgladnjivanje.
- Zahtijeva znanje o tome koliko će dugo trajati proces ili posao.
- Dovodi do gladovanja koje ne smanjuje prosječno vrijeme obrade.
- Teško je znati duljinu nadolazećeg zahtjeva za procesor.
- Treba zabilježiti proteklo vrijeme, što rezultira većim troškovima na procesoru.
Sažetak
- SJF je algoritam u kojem se za sljedeće izvršavanje bira proces koji ima najmanje vrijeme izvršenja.
- SJF planiranje povezano je sa svakim poslom kao vremenska jedinica.
- Ova metoda algoritma korisna je za skupnu obradu, gdje čekanje završetka poslova nije kritično.
- U osnovi postoje dvije vrste SJF metoda 1) Nepreventivni SJF i 2) Preemptive SJF.
- U ne-preventivnom planiranju, nakon što se procesorski ciklus dodijeli procesu, proces ga zadržava dok ne dosegne stanje čekanja ili se prekine.
- U preventivnom SJF raspoređivanju, poslovi se stavljaju u red spremnosti čim dođu.
- Iako započinje postupak s kratkim vremenom burst-a, trenutni se postupak uklanja ili sprečava iz izvršavanja, a posao koji je kraći izvršava se 1..
- SJF se često koristi za dugoročno raspoređivanje.
- Smanjuje prosječno vrijeme čekanja preko FIFO (First in First Out) algoritma.
- U SJF rasporedu, vrijeme završetka posla mora se znati ranije, ali teško je predvidjeti.
- SJF se ne može kratkoročno implementirati za planiranje CPU-a. To je zato što ne postoji posebna metoda za predviđanje duljine nadolazećeg CPU-a.