Kaj je najkrajše načrtovanje za prvo delovno mesto?
Najkrajše delo najprej (SJF) je algoritem, pri katerem je postopek z najmanjšim časom izvedbe izbran za naslednjo izvedbo. Ta metoda razporejanja je lahko preventivna ali nepreventivna. Znatno skrajša povprečno čakalno dobo za druge procese, ki čakajo na izvedbo. Celotna oblika SJF je najkrajša zaposlitev najprej.
V osnovi obstajata dve vrsti metod SJF:
- Nepreventivni SJF
- Preventivni SJF
V tej vadnici o operacijskem sistemu boste izvedeli:
- Kaj je najkrajše načrtovanje za prvo delovno mesto?
- Značilnosti razporejanja SJF
- Nepreventivni SJF
- Preventivni SJF
- Prednosti SJF
- Slabosti / slabosti SJF
Značilnosti razporejanja SJF
- Z vsakim opravilom je povezan kot enota časa za dokončanje.
- Ta algoritemska metoda je koristna za paketno obdelavo, kjer čakanje na dokončanje opravil ni kritično.
- Lahko izboljša pretočnost postopka, tako da poskrbi, da se najprej izvedejo krajša opravila, s čimer je morda kratek čas obrata.
- Izboljša izhodne naloge tako, da ponuja krajše naloge, ki bi jih bilo treba najprej izvesti, ki imajo večinoma krajši čas obnove.
Nepreventivni SJF
Pri nepredvidljivem razporejanju, ko je cikel procesorja dodeljen procesu, ga postopek zadrži, dokler ne pride v čakalno stanje ali se konča.
Razmislite o naslednjih petih procesih, ki imajo vsak svoj edinstveni čas porušitve in čas prihoda.
| Čakalna vrsta procesa | Čas porušitve | Čas prihoda |
| P1 | 6. | 2. |
| P2 | 2. | 5. |
| P3 | 8. | 1. |
| P4 | 3. | 0 |
| P5 | 4. | 4. |
Korak 0) Ob času = 0 prispe P4 in začne izvajanje.
Korak 1) Ob času = 1 prispe proces P3. Toda P4 še vedno potrebuje dve izvršilni enoti. Izvedba se bo nadaljevala.
Korak 2) Ob času = 2 prispe postopek P1 in se doda v čakalno vrsto. P4 bo nadaljeval izvajanje.
Korak 3) Ob času = 3 bo postopek P4 zaključil svoje izvajanje. Primerja se čas porušitve P3 in P1. Proces P1 se izvede, ker je njegov čas porušitve krajši v primerjavi s P3.
Korak 4) Ob času = 4 prispe postopek P5 in se doda v čakalno vrsto. P1 bo nadaljeval izvajanje.
5. korak) Ob času = 5 prispe proces P2 in se doda v čakalno vrsto. P1 bo nadaljeval izvajanje.
Korak 6) V času = 9 bo postopek P1 zaključil svoje izvajanje. Primerja se čas porušitve P3, P5 in P2. Proces P2 se izvede, ker je njegov čas porušitve najnižji.
Korak 7) V času = 10 se izvaja P2 in P3 in P5 sta v čakalni vrsti.
Korak 8) V času = 11 bo postopek P2 zaključil svoje izvajanje. Primerja se čas razpoka P3 in P5. Proces P5 se izvede, ker je njegov čas porušitve krajši.
Korak 9) Ob času = 15 bo postopek P5 zaključil svoje izvajanje.
Korak 10) V času = 23 bo postopek P3 zaključil svoje izvajanje.
Korak 11) Izračunajmo povprečno čakalno dobo za zgornji primer.
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
V preventivnem načrtovanju SJF so delovna mesta postavljena v pripravljeno vrsto, ko pridejo. Postopek z najkrajšim časom porušitve se začne izvajati. Če prispe postopek s še krajšim časom porušitve, se trenutni postopek odstrani ali izvzame iz izvedbe, krajši opravi pa se dodeli cikel procesorja.
Razmislite o naslednjih petih postopkih:
| Čakalna vrsta procesa | Čas porušitve | Čas prihoda |
| P1 | 6. | 2. |
| P2 | 2. | 5. |
| P3 | 8. | 1. |
| P4 | 3. | 0 |
| P5 | 4. | 4. |
Korak 0) Ob času = 0 prispe P4 in začne izvajanje.
| Čakalna vrsta procesa | Čas porušitve | Čas prihoda |
| P1 | 6. | 2. |
| P2 | 2. | 5. |
| P3 | 8. | 1. |
| P4 | 3. | 0 |
| P5 | 4. | 4. |
Korak 1) Ob času = 1 prispe proces P3. Toda P4 ima krajši čas porušitve. Izvedba se bo nadaljevala.
Korak 2) Ob času = 2 pride postopek P1 s časom porušitve = 6. Čas porušitve je daljši od časa P4. Zato bo P4 nadaljeval izvajanje.
Korak 3) Ob času = 3 bo postopek P4 zaključil svoje izvajanje. Primerja se čas porušitve P3 in P1. Proces P1 se izvede, ker je njegov čas porušitve krajši.
Korak 4) Ob času = 4 bo prispel postopek P5. Primerja se čas porušitve P3, P5 in P1. Proces P5 se izvede, ker je njegov čas porušitve najnižji. Proces P1 je predviden.
| Čakalna vrsta procesa | Čas porušitve | Čas prihoda |
| P1 | Preostane še 5 od 6 | 2. |
| P2 | 2. | 5. |
| P3 | 8. | 1. |
| P4 | 3. | 0 |
| P5 | 4. | 4. |
5. korak) Ob času = 5 bo prispel postopek P2. Primerja se čas porušitve P1, P2, P3 in P5. Proces P2 se izvede, ker je njegov čas porušitve najmanjši. Proces P5 je predviden.
| Čakalna vrsta procesa | Čas porušitve | Čas prihoda |
| P1 | Preostane še 5 od 6 | 2. |
| P2 | 2. | 5. |
| P3 | 8. | 1. |
| P4 | 3. | 0 |
| P5 | Preostali so 3 od 4 | 4. |
Korak 6) V času = 6 se izvaja P2.
Korak 7) V času = 7 P2 zaključi svoje izvajanje. Primerja se čas porušitve P1, P3 in P5. Proces P5 se izvede, ker je njegov čas porušitve krajši.
| Čakalna vrsta procesa | Čas porušitve | Čas prihoda |
| P1 | Preostane še 5 od 6 | 2. |
| P2 | 2. | 5. |
| P3 | 8. | 1. |
| P4 | 3. | 0 |
| P5 | Preostali so 3 od 4 | 4. |
Korak 8) V času = 10 bo P5 zaključil svoje izvajanje. Primerja se čas porušitve P1 in P3. Proces P1 se izvede, ker je njegov čas porušitve krajši.
Korak 9) V času = 15, P1 zaključi svoje izvajanje. P3 je edini preostali postopek. Začelo se bo izvrševanje.
Korak 10) V času = 23, P3 zaključi svoje izvajanje.
Korak 11) Izračunajmo povprečno čakalno dobo za zgornji primer.
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
Tu so prednosti / prednosti uporabe metode SJF:
- SJF se pogosto uporablja za dolgoročno načrtovanje.
- Zmanjša povprečno čakalno dobo v algoritmu FIFO (First in First Out).
- SJF metoda daje najnižjo povprečno čakalno dobo za določen nabor procesov.
- Primerno je za dela, ki se izvajajo v paketu, kjer so časi izvajanja vnaprej znani.
- Za paketni sistem dolgoročnega načrtovanja lahko iz opisa dela dobite oceno časa razpoka.
- Za kratkoročno razporejanje moramo predvideti vrednost naslednjega časa rafala.
- Verjetno optimalno glede na povprečni čas obrata.
Slabosti / slabosti SJF
Tu je nekaj pomanjkljivosti / slabosti algoritma SJF:
- Čas zaključka dela mora biti znan že prej, vendar je težko napovedati.
- Pogosto se uporablja v paketnem sistemu za dolgoročno razporejanje.
- SJF za kratkoročno načrtovanje CPU ni mogoče uporabiti. Ker ni posebne metode za napovedovanje dolžine prihajajočega CPU-ja.
- Ta algoritem lahko povzroči zelo dolge čase obnove ali stradanje.
- Zahteva znanje o tem, kako dolgo bo potekal postopek ali delo.
- Privede do stradanja, ki ne zmanjša povprečnega časa obračanja.
- Težko je poznati dolžino prihajajoče zahteve za CPU.
- Zabeleženi pretečeni čas je treba zabeležiti, kar povzroči več dodatnih stroškov na procesorju.
Povzetek
- SJF je algoritem, pri katerem je postopek z najmanjšim časom izvedbe izbran za naslednjo izvedbo.
- Razporejanje SJF je povezano z vsakim opravilom kot enota časa za dokončanje.
- Ta algoritemska metoda je koristna za paketno obdelavo, kjer čakanje na dokončanje opravil ni kritično.
- V osnovi obstajata dve vrsti metod SJF 1) Nepreventivni SJF in 2) Preventivni SJF.
- Pri nepredvidljivem razporejanju, ko je cikel procesorja dodeljen procesu, ga postopek zadrži, dokler ne pride v čakalno stanje ali se konča.
- V preventivnem načrtovanju SJF so delovna mesta postavljena v pripravljeno vrsto, ko pridejo.
- Čeprav se začne postopek s kratkim časom porušitve, je trenutni postopek odstranjen ali izvzet iz izvajanja, krajše opravilo pa 1..
- SJF se pogosto uporablja za dolgoročno načrtovanje.
- Zmanjša povprečno čakalno dobo v algoritmu FIFO (First in First Out).
- Pri razporejanju SJF je treba čas dokončanja opravila poznati že prej, vendar je težko napovedati.
- SJF za kratkoročno načrtovanje CPU ni mogoče uporabiti. Ker ni posebne metode za napovedovanje dolžine prihajajočega CPU-ja.