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

⚡ Rezumat inteligent

Shortest Job First (SJF) este un algoritm de planificare a procesorului care selectează procesul cu cel mai mic timp de execuție pentru a fi executat în continuare. Poate fi preemptiv sau non-preemptiv și reduce semnificativ timpul mediu de așteptare pentru procese.

⏱️ Definiție: Procesul cu cel mai scurt timp de rafală este ales pentru următoarea execuție.
🔀 Două tipuri: SJF poate fi non-preemptiv sau preemptiv (Shortest Remaining Time First - Cel mai scurt timp rămas primul).
📉 Beneficiu cheie: Oferă cel mai mic timp mediu de așteptare pentru un set dat de procese.
🏭 Cea mai bună utilizare: Ideal pentru sistemele de tip batch în care timpii de execuție a lucrărilor sunt cunoscuți în avans.
❓ Principala limitare: Timpul de explozie trebuie cunoscut dinainte, ceea ce este greu de prezis.
⚠️ Risc: Procesele lungi pot fi în pericol de înfometare dacă continuă să apară joburi scurte.

Citește mai mult

Ce este cea mai scurtă programare pentru primul loc de muncă?

Cel mai scurt job mai întâi (SJF) este un algoritm în care procesul care are cel mai mic timp de execuție este ales pentru următoarea execuție. Această metodă de planificare poate fi preventivă sau non-preemptivă. Reduce semnificativ timpul mediu de așteptare pentru alte procese care așteaptă execuția. Forma completă a SJF este Shortest Job First.

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 randamentul procesului asigurându-se că joburile mai scurte sunt executate primele, având astfel un timp de execuție scurt.
Îmbunătățește randamentul lucrărilor prin oferirea de lucrări mai scurte, care ar trebui executate primele și care au, în mare parte, un timp de execuție mai scurt.

SJF non-preemptive

În planificarea non-preemptivă, odată ce ciclul CPU este alocat unui proces, procesul îl reține până când ajunge într-o stare de așteptare sau este terminat.

Luați în considerare următoarele cinci procese, fiecare având propriul timp de explozie și propriul timp 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 momentul = 0, P4 sosește și începe execuția.

Pas 1) La momentul = 1, procesul P3 sosește. Dar P4 mai are nevoie de 2 unități de execuție pentru a se finaliza. Acesta va continua execuția.

Pas 2) La ora = 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 momentul = 10, P2 se execută, iar P3 și P5 se află î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 planificarea SJF preemptivă, joburile sunt puse în coada de așteptare pe măsură ce sosesc. Un proces cu cel mai scurt timp de execuție începe execuția. Dacă sosește un proces cu un timp de execuție și mai scurt, procesul curent este eliminat sau preemptat de la execuție, iar jobului mai scurt i se alocă un ciclu 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 momentul = 0, P4 sosește ș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 momentul = 1, procesul P3 sosește. Dar P4 are un timp de rafală mai scurt. Acesta va continua execuția.

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 momentul = 5, va sosi procesul P2. Se compară timpul de rafală al lui P1, P2, P3 și P5. Procesul P2 este executat deoarece timpul său de rafală este cel mai mic. Procesul P5 este preemptat.

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 termină execuția. Se compară timpul de rafală al lui P1, P3 și P5. Procesul P5 este executat deoarece timpul său de rafală 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 rafală al lui P1 și P3. Procesul P1 este executat deoarece timpul său de rafală este mai mic.

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

Pas 10) La momentul = 23, P3 își termină 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ă 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 set specific 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 este optim în ceea ce privește timpul mediu de execuție.

Dezavantajele/Dezavantajele SJF

Iată câteva dezavantaje/dezavantaje 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.
Duce la înfometare care nu reduce timpul mediu de răspuns.
Este greu de știut lungimea viitoarei solicitări CPU.
Timpul scurs ar trebui înregistrat, ceea ce duce la o suprasolicitare mai mare pentru procesor.

Întrebări frecvente

SRTF (Shortest Remaining Time First - Timp rămas mai scurt) este pur și simplu versiunea preemptivă a SJF. În SJF, un job care rulează se termină înainte de alegerea următorului. În SRTF, un job nou sosit cu un timp rămas mai scurt poate preempționa procesul care rulează.

SJF favorizează întotdeauna jobul cel mai scurt. Dacă procesele scurte continuă să sosească, un proces lung s-ar putea să nu obțină niciodată CPU-ul și să aștepte la nesfârșit. Aceasta este o priză la viață. Îmbătrânirea, care crește lent prioritatea unui job în așteptare, este utilizată pentru a preveni acest lucru.

Da. SJF este demonstrabil optimă deoarece produce timpul mediu de așteptare minim posibil pentru un set dat de procese. Totuși, acest lucru este adevărat numai dacă timpii de explozie sunt cunoscuți în avans, ceea ce este rareori posibil în practică.

Inteligența artificială și învățarea automată pot analiza istoricul unui proces, caracteristicile codului și rulările anterioare pentru a estima timpul de procesare în rafale al procesorului. Predicțiile mai bune fac SJF mai precis, reducând timpul de așteptare în comparație cu estimările tradiționale cu mediere exponențială.

Potențial. SJF se confruntă cu dificultăți în planificarea pe termen scurt deoarece timpii de rafale sunt necunoscuți. Inteligența artificială care prezice rafale în timp real ar putea face SJF utilizabil, dar costurile generale de predicție și erorile trebuie să rămână suficient de scăzute pentru ca decizia de planificare să fie utilă.