Mis on kõige lühem töö esimese planeerimine?
Lühim töö kõigepealt (SJF) on algoritm, milles järgmise täitmise jaoks valitakse protsess, millel on kõige väiksem täitmisaeg. See ajastamismeetod võib olla ennetav või mitte. See vähendab oluliselt teiste täitmist ootavate protsesside keskmist ooteaega. SJF-i täielik vorm on kõigepealt lühim töö.
Põhimõtteliselt on kahte tüüpi SJF-i meetodeid:
- Mitteeelistav SJF
- Ennetav SJF
Selles opsüsteemi õpetuses saate teada:
- Mis on kõige lühem töö esimese planeerimine?
- SJF-i kavandamise omadused
- Mitteeelistav SJF
- Ennetav SJF
- SJF-i eelised
- SJF-i puudused / miinused
SJF-i kavandamise omadused
- See on seotud iga tööga ajaühikuna.
- See algoritmimeetod on abiks pakett-tüüpi töötlemisel, kus tööde lõpuleviimise ootamine pole kriitiline.
- See võib parandada protsessi läbilaskvust, veendudes, et kõigepealt täidetakse lühemad tööd, seega võib nende lühike tööaeg.
- See parandab töökohtade väljundit, pakkudes lühemaid töökohti, mis tuleks täita kõigepealt ja millel on enamasti lühem tööaeg.
Mitteeelistav SJF
Mitte-ennetava ajastamise korral hoiab protsessor pärast protsessori tsükli eraldamist protsessis seda kuni ooteseisundini jõudmiseni või lõpetamiseni.
Mõelge järgmisele viiel protsessil, millel on oma ainulaadne purskeaeg ja saabumisaeg.
| Protsessi järjekord | Plahvatuse aeg | Saabumise aeg |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Samm 0) Ajal = 0 saabub P4 ja alustab täitmist.
Samm 1) Ajal = 1 saabub protsess P3. Kuid P4 vajab veel 2 täitmisüksust. See jätkab hukkamist.
Samm 2) Ajal = 2 saabub protsess P1 ja see lisatakse ootejärjekorda. P4 jätkab täitmist.
Samm 3) Ajal = 3 lõpetab protsess P4 selle käivitamise. Võrreldakse P3 ja P1 purskeaega. Protsess P1 viiakse läbi, kuna selle purskeaeg on väiksem kui P3.
Samm 4) Ajal = 4 saabub protsess P5 ja see lisatakse ootejärjekorda. P1 jätkab täitmist.
Samm 5) Ajal = 5 saabub protsess P2 ja see lisatakse ootejärjekorda. P1 jätkab täitmist.
Samm 6) Ajal = 9 lõpetab protsess P1 selle käivitamise. Võrreldakse P3, P5 ja P2 purskeaega. Protsess P2 käivitatakse, kuna selle purskeaeg on kõige väiksem.
Samm 7) Ajahetkel = 10 teostab P2 ning P3 ja P5 on ootejärjekorras.
8. samm. Ajal = 11 lõpetab protsess P2 selle täitmise. Võrreldakse P3 ja P5 purskeaega. Protsess P5 käivitatakse, kuna selle purskeaeg on väiksem.
Samm 9) Ajal = 15 lõpetab protsess P5 selle käivitamise.
Samm 10) Ajal = 23 lõpetab protsess P3 selle käivitamise.
Samm 11) Arvutame ülaltoodud näite keskmise ooteaja.
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
Ennetav SJF
Ennetavas SJF-i ajastamises pannakse töökohad nende saabumisel valmis järjekorda. Lühima purskeajaga protsess algab käivitamisega. Kui saabub isegi lühema plahvatusajaga protsess, eemaldatakse praegune protsess või keelatakse see käivitada ja lühema töö jaoks määratakse protsessori tsükkel.
Vaatleme järgmist viit protsessi:
| Protsessi järjekord | Plahvatuse aeg | Saabumise aeg |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Samm 0) Ajal = 0 saabub P4 ja alustab täitmist.
| Protsessi järjekord | Plahvatuse aeg | Saabumise aeg |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Samm 1) Ajal = 1 saabub protsess P3. Kuid P4-l on lühem sarivõte. See jätkab hukkamist.
Samm 2) Ajal = 2 saabub protsess P1 sarivõtmisajaga = 6. Sarivõtte aeg on pikem kui P4-l. Seega jätkab P4 täitmist.
Samm 3) Ajal = 3 lõpetab protsess P4 selle käivitamise. Võrreldakse P3 ja P1 purskeaega. Protsess P1 viiakse läbi, kuna selle purskeaeg on väiksem.
Samm 4) Ajal = 4 saabub protsess P5. Võrreldakse P3, P5 ja P1 purskeaega. Protsess P5 käivitatakse, kuna selle purskeaeg on kõige madalam. Protsess P1 on ennetatud.
| Protsessi järjekord | Plahvatuse aeg | Saabumise aeg |
| P1 | 5-st 6-st on alles | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Samm 5) Ajal = 5 saabub protsess P2. Võrreldakse P1, P2, P3 ja P5 purskeaega. Protsess P2 käivitatakse, kuna selle purskeaeg on kõige väiksem. Protsess P5 on ennetatud.
| Protsessi järjekord | Plahvatuse aeg | Saabumise aeg |
| P1 | 5-st 6-st on alles | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3-st 4-st on alles | 4 |
Samm 6) Ajahetkel = 6 täidab P2.
Samm 7) Ajahetkel = 7 lõpetab P2 selle täitmise. Võrreldakse P1, P3 ja P5 purskeaega. Protsess P5 käivitatakse, kuna selle purskeaeg on väiksem.
| Protsessi järjekord | Plahvatuse aeg | Saabumise aeg |
| P1 | 5-st 6-st on alles | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3-st 4-st on alles | 4 |
8. samm. Ajal = 10 lõpetab P5 selle täitmise. Võrreldakse P1 ja P3 purskeaega. Protsess P1 käivitatakse, kuna selle purskeaeg on lühem.
9. samm) ajahetkel = 15 lõpetab P1 selle täitmise. P3 on ainus järelejäänud protsess. See alustab täitmist.
10. samm) ajahetkel = 23 lõpetab P3 selle täitmise.
Samm 11) Arvutame ülaltoodud näite keskmise ooteaja.
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
SJF-i eelised
Siin on SJF-meetodi kasutamise eelised / plussid:
- SJF-i kasutatakse sageli pikaajaliseks planeerimiseks.
- See vähendab keskmist ooteaega üle FIFO (First in First Out) algoritmi.
- SJF-meetod annab konkreetse protsesside komplekti jaoks madalaima keskmise ooteaja.
- See on sobiv pakkide kaupa töötavate tööde jaoks, kus tööajad on eelnevalt teada.
- Pikaajalise ajastamise partiisüsteemi jaoks saab purskeaja hinnangu saada ametijuhendist.
- Lühiajalise ajastamise jaoks peame ennustama järgmise purskeaja väärtust.
- Tõenäoliselt optimaalne keskmise pöördeaja suhtes.
SJF-i puudused / miinused
Siin on mõned SJF-i algoritmi puudused / miinused:
- Töö lõpetamise aeg peab olema teada varem, kuid seda on raske ennustada.
- Sageli kasutatakse seda pikaajalises plaanis partiisüsteemis.
- SJF-i ei saa protsessori lühiajaliseks ajastamiseks rakendada. Sellepärast, et eelseisva protsessori purske pikkuse ennustamiseks pole konkreetset meetodit.
- See algoritm võib põhjustada väga pikki pöördeaegu või nälga.
- Nõuab teadmisi selle kohta, kui kaua protsess või töö kestab.
- See viib nälga, mis ei vähenda keskmist pööranguaega.
- Tulevase protsessori päringu pikkust on raske teada.
- Möödunud aeg tuleks registreerida, see toob protsessorile rohkem lisakulusid.
Kokkuvõte
- SJF on algoritm, mille järgmiseks täitmiseks valitakse protsess, millel on kõige väiksem täitmisaeg.
- SJF-i ajastamine on seotud iga tööga ajaühikuna.
- See algoritmimeetod on abiks pakett-tüüpi töötlemisel, kus tööde lõpuleviimise ootamine pole kriitiline.
- Põhimõtteliselt on kahte tüüpi SJF-i meetodeid: 1) mittepreemptive SJF ja 2) ennetav SJF.
- Mitte-ennetava ajastamise korral hoiab protsessor pärast protsessori tsükli eraldamist protsessis seda kuni ooteseisundini jõudmiseni või lõpetamiseni.
- Ennetavas SJF-i ajastamises pannakse töökohad nende saabumisel valmis järjekorda.
- Kuigi algab lühikese purskeajaga protsess, eemaldatakse praegune protsess või keelatakse see käivitada ja lühem töö täidetakse 1. kohal.
- SJF-i kasutatakse sageli pikaajaliseks planeerimiseks.
- See vähendab keskmist ooteaega üle FIFO (First in First Out) algoritmi.
- SJF-i ajastamisel peab töö lõpetamise aeg olema varem teada, kuid seda on raske ennustada.
- SJF-i ei saa protsessori lühiajaliseks ajastamiseks rakendada. Sellepärast, et eelseisva protsessori purske pikkuse ennustamiseks pole konkreetset meetodit.