Cel mai scurt loc de muncă mai întâi (SJF): exemplu preventiv, non-preemptiv

Există în esență două tipuri de metode SJF:

• SJF non-preemptive
• SJF preventivă

Caracteristicile programării SJF

• Este asociat fiecărei lucrări ca unitate de timp de finalizat.
• Această metodă de algoritm este utilă pentru procesarea de tip lot, unde așteptarea finalizării lucrărilor nu este critică.
• Poate îmbunătăți debitul procesului, asigurându-se că lucrările mai scurte sunt executate mai întâi, prin urmare, posibil să aibă un timp de executie scurt.
• Îmbunătățește producția de lucrări prin oferirea de lucrări mai scurte, care ar trebui executate mai întâi, care au în mare parte un timp de realizare mai scurt.

SJF non-preemptive

În programarea non-preemptivă, odată ce ciclul CPU este alocat procesului, procesul îl menține până când ajunge într-o stare de așteptare sau se încheie.

Luați în considerare următoarele cinci procese, fiecare având propriul său timp de explozie și timpul de sosire unic.

Coada de procesare	Timp de explozie	Timpul sosirii
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Pas 0) La ora=0, sosește P4 și începe execuția.

Pas 1) La ora= 1, vine Procesul P3. Dar, P4 mai are nevoie de 2 unități de execuție pentru a finaliza. Se va continua executarea.

Pas 2) La momentul =2, procesul P1 sosește și este adăugat la coada de așteptare. P4 va continua execuția.

Pas 3) La momentul = 3, procesul P4 își va termina execuția. Se compară timpul de explozie a lui P3 și P1. Procesul P1 este executat deoarece timpul său de explozie este mai mic comparativ cu P3.

Pas 4) La ora = 4, procesul P5 sosește și este adăugat la coada de așteptare. P1 va continua execuția.

Pas 5) La ora = 5, procesul P2 sosește și este adăugat la coada de așteptare. P1 va continua execuția.

Pas 6) La momentul = 9, procesul P1 își va termina execuția. Se compară timpul de explozie a lui P3, P5 și P2. Procesul P2 este executat deoarece timpul său de explozie este cel mai mic.

Pas 7) La ora=10, P2 se execută și P3 și P5 sunt în coada de așteptare.

Pas 8) La momentul = 11, procesul P2 își va termina execuția. Se compară timpul de explozie a lui P3 și P5. Procesul P5 este executat deoarece timpul său de explozie este mai mic.

Pas 9) La momentul = 15, procesul P5 își va termina execuția.

Pas 10) La momentul = 23, procesul P3 își va termina execuția.

Pas 11) Să calculăm timpul mediu de așteptare pentru exemplul de mai sus.

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

SJF preventivă

În programarea preventivă SJF, lucrările sunt puse în coada de așteptare pe măsură ce apar. Un proces cu cel mai scurt timp de explozie începe execuția. Dacă sosește un proces cu un timp de explozie chiar mai scurt, procesul curent este eliminat sau preemptat de la execuție, iar jobul mai scurt este alocat ciclului CPU.

Luați în considerare următoarele cinci procese:

Coada de procesare	Timp de explozie	Timpul sosirii
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Pas 0) La ora=0, sosește P4 și începe execuția.

Coada de procesare	Timp de explozie	Timpul sosirii
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Pas 1) La ora= 1, vine Procesul P3. Dar, P4 are un timp de explozie mai scurt. Se va continua executarea.

Pas 2) La timp = 2, procesul P1 ajunge cu timpul de explozie = 6. Timpul de explozie este mai mare decât cel al lui P4. Prin urmare, P4 va continua execuția.

Pas 3) La momentul = 3, procesul P4 își va termina execuția. Se compară timpul de explozie a lui P3 și P1. Procesul P1 este executat deoarece timpul său de explozie este mai mic.

Pas 4) La ora = 4, va sosi procesul P5. Se compară timpul de explozie a lui P3, P5 și P1. Procesul P5 este executat deoarece timpul său de explozie este cel mai mic. Procesul P1 este anticipat.

Coada de procesare	Timp de explozie	Timpul sosirii
P1	5 din 6 au mai rămas	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Pas 5) La timp = 5, va sosi procesul P2. Se compară timpul de explozie a lui P1, P2, P3 și P5. Procesul P2 este executat deoarece timpul său de explozie este cel mai mic. Procesul P5 este anticipat.

Coada de procesare	Timp de explozie	Timpul sosirii
P1	5 din 6 au mai rămas	2
P2	2	5
P3	8	1
P4	3	0
P5	3 din 4 au mai rămas	4

Pas 6) La momentul =6, P2 se execută.

Pas 7) La momentul =7, P2 își încheie execuția. Se compară timpul de explozie a lui P1, P3 și P5. Procesul P5 este executat deoarece timpul său de explozie este mai mic.

Coada de procesare	Timp de explozie	Timpul sosirii
P1	5 din 6 au mai rămas	2
P2	2	5
P3	8	1
P4	3	0
P5	3 din 4 au mai rămas	4

Pas 8) La momentul =10, P5 își va termina execuția. Se compară timpul de explozie a lui P1 și P3. Procesul P1 este executat deoarece timpul său de explozie este mai mic.

Pas 9) La momentul =15, P1 își încheie execuția. P3 este singurul proces rămas. Va începe execuția.

Pas 10) La momentul =23, P3 își încheie execuția.

Pas 11) Să calculăm timpul mediu de așteptare pentru exemplul de mai sus.

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

Avantajele SJF

Iată care sunt beneficiile/avantajele utilizării metodei SJF:

• SJF este frecvent utilizat pentru programarea pe termen lung.
• Reduce timpul mediu de așteptare prin algoritmul FIFO (First in First Out).
• Metoda SJF oferă cel mai mic timp mediu de așteptare pentru un anumit set de procese.
• Este potrivit pentru joburile care rulează în lot, în care timpii de rulare sunt cunoscuți dinainte.
• Pentru sistemul batch de programare pe termen lung, o estimare a timpului de explozie poate fi obținută din fișa postului.
• Pentru programarea pe termen scurt, trebuie să anticipăm valoarea următoarei ore de explozie.
• Probabil optim în ceea ce privește timpul mediu de răspuns.

Dezavantajele/Dezavantajele SJF

Iată câteva dezavantaje/contra ale algoritmului SJF:

• Timpul de finalizare a postului trebuie cunoscut mai devreme, dar este greu de prezis.
• Este adesea folosit într-un sistem batch pentru programarea pe termen lung.
• SJF nu poate fi implementat pentru programarea procesorului pe termen scurt. Acest lucru se datorează faptului că nu există o metodă specifică pentru a prezice durata viitoarei explozii CPU.
• Acest algoritm poate cauza timpi foarte mari de răspuns sau înfometare.
• Necesită cunoștințe despre cât timp va rula un proces sau un job.
• Aceasta duce la foamete care nu reduce timpul mediu de răspuns.
• Este greu de știut lungimea viitoarei solicitări CPU.
• Timpul scurs trebuie înregistrat, ceea ce duce la o supraîncărcare mai mare pentru procesor.

Rezumat

• SJF este un algoritm în care procesul care are cel mai mic timp de execuție este ales pentru următoarea execuție.
• SJF Scheduling este asociat cu fiecare job ca o unitate de timp de finalizat.
• Această metodă de algoritm este utilă pentru procesarea de tip lot, unde așteptarea finalizării lucrărilor nu este critică.
• Practic, există două tipuri de metode SJF: 1) SJF non-preemptive și 2) SJF preventivă.
• În programarea non-preemptivă, odată ce ciclul CPU este alocat procesului, procesul îl menține până când ajunge într-o stare de așteptare sau se încheie.
• În programarea preventivă SJF, lucrările sunt puse în coada de așteptare pe măsură ce apar.
• Deși începe un proces cu timp de explozie scurt, procesul curent este eliminat sau preemptat de la execuție, iar jobul care este mai scurt este executat primul.
• SJF este frecvent utilizat pentru programarea pe termen lung.
• Reduce timpul mediu de așteptare prin algoritmul FIFO (First in First Out).
• În programarea SJF, timpul de finalizare a lucrării trebuie cunoscut mai devreme, dar este greu de prezis.
• SJF nu poate fi implementat pentru programarea CPU pe termen scurt. Acest lucru se datorează faptului că nu există o metodă specifică pentru a prezice durata viitoarei explozii CPU.