Lühim töö enne (SJF): ennetav, mitteennetav näide

Põhimõtteliselt on kahte tüüpi SJF-meetodeid:

• Mitteennetav SJF
• Ennetav SJF

SJF ajakava omadused

• See on seotud iga tööga täitmiseks kuluva ajaühikuna.
• See algoritmimeetod on abiks pakett-tüüpi töötlemisel, kus tööde lõpetamise ootamine pole kriitiline.
• See võib parandada protsessi läbilaskevõimet, tagades, et kõigepealt täidetakse lühemad tööd ja seega võib nende tööaeg olla lühike.
• See parandab töötulemusi, pakkudes lühemaid töid, mis tuleks esmalt teostada ja mille tööaeg on enamasti lühem.

Mitteennetav SJF

Kui protsessori tsükkel on protsessi jaoks eraldatud, hoiab protsess seda mitteennetava ajastamise korral, kuni see jõuab ooteolekusse või lõpetatakse.

Mõelge järgmisele viiele protsessile, millel on oma kordumatu sarivõtte aeg ja saabumisaeg.

Protsessi järjekord	Purskeaeg	Saabumise aeg
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 0) Kell = 0, saabub P4 ja alustab täitmist.

Step 1) Kell = 1, saabub protsess P3. Kuid P4 vajab lõpuleviimiseks siiski 2 täitmisüksust. See jätkab täitmist.

Step 2) Ajahetkel =2 saabub protsess P1 ja lisatakse ootejärjekorda. P4 jätkab täitmist.

Step 3) Aeg = 3 lõpetab protsess P4 täitmise. Võrreldakse P3 ja P1 katkestusaega. Protsess P1 käivitatakse, kuna selle sarivõtte aeg on võrreldes P3-ga lühem.

Step 4) Kell = 4, saabub protsess P5 ja lisatakse ootejärjekorda. P1 jätkab täitmist.

Step 5) Kell = 5, saabub protsess P2 ja lisatakse ootejärjekorda. P1 jätkab täitmist.

Step 6) Kell = 9, lõpetab protsess P1 täitmise. Võrreldakse P3, P5 ja P2 katkestusaega. Protsess P2 käivitatakse, kuna selle sarivõtte aeg on madalaim.

Step 7) Kellaajal = 10, P2 töötab ning P3 ja P5 on ootejärjekorras.

Step 8) Aeg = 11 lõpetab protsess P2 täitmise. Võrreldakse P3 ja P5 katkestusaega. Protsess P5 käivitatakse, kuna selle sarivõtte aeg on väiksem.

Step 9) Aeg = 15 lõpetab protsess P5 täitmise.

Step 10) Aeg = 23 lõpetab protsess P3 täitmise.

Step 11) Arvutame ülaltoodud näite keskmise ooteaja.

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

Ennetav SJF

Ennetavas SJF-ajastamises pannakse tööd saabumisel valmisjärjekorda. Käivitatakse lühima sarivõtteajaga protsess. Kui saabub isegi lühema sarivõtte ajaga protsess, siis praegune protsess eemaldatakse või tühistatakse täitmisest ning lühemale tööle eraldatakse protsessori tsükkel.

Kaaluge järgmist viit protsessi:

Protsessi järjekord	Purskeaeg	Saabumise aeg
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 0) Kell = 0, saabub P4 ja alustab täitmist.

Protsessi järjekord	Purskeaeg	Saabumise aeg
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 1) Kell = 1, saabub protsess P3. Kuid P4-l on lühem sarivõtteaeg. See jätkab täitmist.

Step 2) Ajahetkel = 2, saabub protsess P1 sarivõtte ajaga = 6. Purskeaeg on pikem kui P4 oma. Seega jätkab P4 täitmist.

Step 3) Aeg = 3 lõpetab protsess P4 täitmise. Võrreldakse P3 ja P1 katkestusaega. Protsess P1 käivitatakse, kuna selle sarivõtte aeg on väiksem.

Step 4) Kell = 4, saabub protsess P5. Võrreldakse P3, P5 ja P1 katkestusaega. Protsess P5 käivitatakse, kuna selle sarivõtte aeg on madalaim. Protsess P1 on ennetatud.

Protsessi järjekord	Purskeaeg	Saabumise aeg
P1	5 6-st on jäänud	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 5) Kell = 5, saabub protsess P2. Võrreldakse P1, P2, P3 ja P5 katkestusaega. Protsess P2 käivitatakse, kuna selle sarivõtte aeg on kõige väiksem. Protsess P5 on ennetatud.

Protsessi järjekord	Purskeaeg	Saabumise aeg
P1	5 6-st on jäänud	2
P2	2	5
P3	8	1
P4	3	0
P5	3 4-st on jäänud	4

Step 6) Ajahetkel =6, P2 töötab.

Step 7) Ajahetkel =7 lõpetab P2 täitmise. Võrreldakse P1, P3 ja P5 katkestusaega. Protsess P5 käivitatakse, kuna selle sarivõtte aeg on lühem.

Protsessi järjekord	Purskeaeg	Saabumise aeg
P1	5 6-st on jäänud	2
P2	2	5
P3	8	1
P4	3	0
P5	3 4-st on jäänud	4

Step 8) Ajahetkel =10 lõpetab P5 täitmise. Võrreldakse P1 ja P3 katkestusaega. Protsess P1 käivitatakse, kuna selle sarivõtte aeg on lühem.

Step 9) Ajahetkel =15 lõpetab P1 täitmise. P3 on ainus protsess. See alustab täitmist.

Step 10) Ajahetkel =23 lõpetab P3 täitmise.

Step 11) Arvutame ülaltoodud näite keskmise ooteaja.

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

SJF eelised

Siin on SJF-meetodi kasutamise eelised/plussid:

• SJF-i kasutatakse sageli pikaajaliseks planeerimiseks.
• See vähendab FIFO (First in First Out) algoritmi keskmist ooteaega.
• SJF-meetod annab madalaima keskmise ooteaja konkreetse protsesside komplekti jaoks.
• See sobib partiidena töötavate tööde jaoks, kus tööajad on ette teada.
• Pikaajalise ajakava pakettsüsteemi jaoks saab sarivõtte aja hinnangu saada ametijuhendist.
• Lühiajalise ajastamise jaoks peame ennustama järgmise sarivõtte aja väärtust.
• Arvatavasti optimaalne, arvestades keskmist tööaega.

SJF-i miinused/miinused

Siin on mõned SJF-algoritmi puudused/miinused:

• Töö valmimise aeg peab olema varem teada, kuid seda on raske ennustada.
• Seda kasutatakse sageli pikaajaliste ajakavade koostamiseks partiisüsteemis.
• SJF-i ei saa rakendada CPU ajakava lühiajaliselt. Põhjus on selles, et eelseisva CPU-purske pikkuse ennustamiseks pole konkreetset meetodit.
• See algoritm võib põhjustada väga pikki töötlemisaegu või nälgimist.
• Nõuab teadmisi selle kohta, kui kaua protsess või töö kestab.
• See viib nälgimiseni, mis ei vähenda keskmist tööaega.
• Eelseisva CPU päringu pikkust on raske teada.
• Kulunud aeg tuleks registreerida, see toob protsessorile rohkem üldkulusid.

kokkuvõte

• SJF on algoritm, milles järgmiseks täitmiseks valitakse kõige väiksema täitmisajaga protsess.
• SJF-i ajakava seostatakse iga tööga täitmiseks kuluva ajaühikuna.
• See algoritmimeetod on abiks pakett-tüüpi töötlemisel, kus tööde lõpetamise ootamine pole kriitiline.
• Põhimõtteliselt on kahte tüüpi SJF meetodeid: 1) mitteennetav SJF ja 2) ennetav SJF.
• Kui protsessori tsükkel on protsessi jaoks eraldatud, hoiab protsess seda mitteennetava ajastamise korral, kuni see jõuab ooteolekusse või lõpetatakse.
• Ennetavas SJF-ajastamises pannakse tööd saabumisel valmisjärjekorda.
• Kuigi algab lühikese sarivõtte ajaga protsess, eemaldatakse või tühistatakse praegune protsess ja lühem töö täidetakse esimesena.
• SJF-i kasutatakse sageli pikaajaliseks planeerimiseks.
• See vähendab FIFO (First in First Out) algoritmi keskmist ooteaega.
• SJF ajakava koostamisel peab töö lõpetamise aeg olema teada varem, kuid seda on raske ennustada.
• SJF-i ei saa CPU lühiajaliseks planeerimiseks rakendada. Põhjus on selles, et eelseisva CPU-purske pikkuse ennustamiseks pole konkreetset meetodit.