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

Mis on lühim töö esimene ajakava?

Lühim töö enne (SJF) on algoritm, milles järgmiseks täitmiseks valitakse kõige väiksema täitmisajaga protsess. See ajastamismeetod võib olla ennetav või mitteennetav. See vähendab oluliselt teiste täitmist ootavate protsesside keskmist ooteaega. SJF-i täisvorm on Shortest Job First.

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 saab parandada protsesside läbilaskevõimet, tagades, et lühemad tööd teostatakse esimesena, mis omakorda võib lühendada teostusaega.
• See parandab töötulemusi, pakkudes lühemaid töid, mis tuleks esimesena teostada ja millel on enamasti lühem teostusaeg.

Mitteennetav SJF

Mitte-ennetavas ajastamises, kui protsessori tsükkel on protsessile eraldatud, hoiab protsess seda seni, kuni see jõuab ooteolekusse või lõpetatakse.

Vaatleme järgmisi viit protsessi, millel kõigil on oma unikaalne purskeaeg 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) Ajahetkel = 0 saabub P4 ja alustab täitmist.

Step 1) Ajahetkel 1 saabub protsess P3. Kuid protsess P4 vajab lõpuleviimiseks veel 2 täitmisüksust. See jätkab täitmist.

Step 2) Kell = 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) Ajahetkel 10 on P2 täitmisel 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 jaoks 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

Preemptiivse SJF-i ajastamise puhul pannakse tööd saabudes valmisolekujärjekorda. Täitmist alustab lühima purskeajaga protsess. Kui saabub veelgi lühema purskeajaga protsess, eemaldatakse praegune protsess või lükatakse see ennetavalt täitmisele ning lühemale tööle eraldatakse protsessori tsükkel.

Mõelge järgmistele viiele protsessile:

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

Step 0) Ajahetkel = 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) Ajahetkel 1 saabub protsess P3. Kuid protsess P4-l on lühem purskeaeg. 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) Ajahetkel 5 saabub protsess P2. Võrreldakse P1, P2, P3 ja P5 purskeaegu. Protsess P2 käivitatakse, kuna selle purskeaeg on lühim. Protsess P5 on eelnevalt lubatud.

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 on P2 täitmisel.

Step 7) Ajahetkel 7 lõpetab P2 oma täitmise. Võrreldakse P1, P3 ja P5 purskeaegu. Protsess P5 täidetakse, kuna selle purskeaeg 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 oma täitmise. P1 ja P3 purskeaega võrreldakse. Protsess P1 käivitatakse, kuna selle purskeaeg on lühem.

Step 9) Ajahetkel 15 lõpetab P1 oma täitmise. Järelejäänud on ainult P3. See alustab täitmist.

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

Step 11) Arvutame ülaltoodud näite jaoks 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 keskmist ooteaega võrreldes FIFO (First In, First Out) algoritmiga.
• SJF-meetod annab konkreetse protsesside komplekti jaoks madalaima keskmise ooteaja.
• 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.
• See on keskmise pöördeaja osas ilmselt optimaalne.

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 lühenda keskmist taastumisaega.
• Eelseisva CPU päringu pikkust on raske teada.
• Möödunud aeg tuleks registreerida, mis suurendab protsessori koormust.

KKK