Care este cea mai scurtă programare la locul de muncă?
Shortest Job First (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-preventivă. Reduce semnificativ timpul mediu de așteptare pentru alte procese care așteaptă executarea. Forma completă a SJF este cel mai scurt loc de muncă mai întâi.
În principiu, există două tipuri de metode SJF:
- SJF nepreventiv
- SJF preventiv
În acest tutorial privind sistemul de operare, veți afla:
- Care este cea mai scurtă programare la locul de muncă?
- Caracteristicile programării SJF
- SJF nepreventiv
- SJF preventiv
- Avantajele SJF
- Dezavantaje / dezavantaje ale SJF
Caracteristicile programării SJF
- Este asociat fiecărei lucrări ca o unitate de timp de finalizat.
- Această metodă algoritmică este utilă pentru procesarea de tip batch, unde așteptarea finalizării lucrărilor nu este critică.
- Poate îmbunătăți randamentul procesului asigurându-se că sunt executate mai întâi lucrări mai scurte, deci este posibil să aibă un timp de răspuns scurt.
- Îmbunătățește producția de locuri de muncă oferind locuri de muncă mai scurte, care ar trebui executate mai întâi, care au cea mai mare parte un timp de răspuns mai scurt.
SJF nepreventiv
În programarea non-preventivă, odată ce ciclul procesorului este alocat procesului, procesul îl menține până ajunge la o stare de așteptare sau se termină.
Luați în considerare următoarele cinci procese, fiecare având propriul său moment de rafală și ora de sosire.
| Coadă de proces | Timp de rafală | Timpul sosirii |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Pasul 0) La momentul = 0, P4 ajunge și începe executarea.
Pasul 1) La momentul = 1, ajunge procesul P3. Dar, P4 are încă nevoie de 2 unități de execuție pentru a finaliza. Va continua execuția.
Pasul 2) La momentul = 2, procesul P1 ajunge și este adăugat la coada de așteptare. P4 va continua execuția.
Pasul 3) La momentul = 3, procesul P4 își va termina execuția. Se compară timpul de explozie al P3 și P1. Procesul P1 este executat deoarece timpul său de rafală este mai mic în comparație cu P3.
Pasul 4) La momentul = 4, procesul P5 ajunge și este adăugat la coada de așteptare. P1 va continua execuția.
Pasul 5) La ora = 5, procesul P2 ajunge și este adăugat la coada de așteptare. P1 va continua execuția.
Pasul 6) La momentul = 9, procesul P1 își va termina execuția. Se compară timpul de explozie al P3, P5 și P2. Procesul P2 este executat deoarece timpul său de rafală este cel mai mic.
Pasul 7) La ora = 10, P2 se execută și P3 și P5 sunt în coada de așteptare.
Pasul 8) La momentul = 11, procesul P2 își va termina execuția. Se compară timpul de explozie al P3 și P5. Procesul P5 este executat deoarece timpul său de explozie este mai mic.
Pasul 9) La momentul = 15, procesul P5 își va termina execuția.
Pasul 10) La ora = 23, procesul P3 își va termina execuția.
Pasul 11) Să calculăm timpul mediu de așteptare pentru exemplul de mai sus.
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
SJF preventiv
În programarea SJF preventivă, joburile sunt puse în coada pregătită pe măsură ce vin. Un proces cu cel mai scurt timp de explozie începe executarea. Dacă ajunge un proces cu un timp de rafală chiar mai scurt, procesul curent este eliminat sau împiedicat de la execuție, iar sarcina mai scurtă este alocată ciclului CPU.
Luați în considerare următoarele cinci procese:
| Coadă de proces | Timp de rafală | Timpul sosirii |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Pasul 0) La momentul = 0, P4 ajunge și începe executarea.
| Coadă de proces | Timp de rafală | Timpul sosirii |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Pasul 1) La momentul = 1, ajunge procesul P3. Dar, P4 are un timp de explozie mai scurt. Va continua execuția.
Pasul 2) La momentul = 2, procesul P1 ajunge cu timpul de rafală = 6. Timpul de rafală este mai mare decât cel al lui P4. Prin urmare, P4 va continua execuția.
Pasul 3) La momentul = 3, procesul P4 își va termina execuția. Se compară timpul de explozie al P3 și P1. Procesul P1 este executat deoarece timpul său de explozie este mai mic.
Pasul 4) La ora = 4, va ajunge procesul P5. Se compară timpul de explozie al P3, P5 și P1. Procesul P5 este executat deoarece timpul său de explozie este cel mai mic. Procesul P1 este oprit.
| Coadă de proces | Timp de rafală | Timpul sosirii |
| P1 | 5 din 6 rămâne | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Pasul 5) La ora = 5, va ajunge procesul P2. Se compară timpul de explozie al P1, P2, P3 și P5. Procesul P2 este executat deoarece timpul său de explozie este cel mai mic. Procesul P5 este prevenit.
| Coadă de proces | Timp de rafală | Timpul sosirii |
| P1 | 5 din 6 rămâne | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 din 4 rămâne | 4 |
Pasul 6) La momentul = 6, P2 se execută.
Pasul 7) La momentul = 7, P2 își termină execuția. Se compară timpul de explozie al P1, P3 și P5. Procesul P5 este executat deoarece timpul său de rafală este mai mic.
| Coadă de proces | Timp de rafală | Timpul sosirii |
| P1 | 5 din 6 rămâne | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 din 4 rămâne | 4 |
Pasul 8) La momentul = 10, P5 își va termina execuția. Se compară timpul de explozie al P1 și P3. Procesul P1 este executat deoarece timpul său de explozie este mai mic.
Pasul 9) La momentul = 15, P1 își termină execuția. P3 este singurul proces rămas. Va începe executarea.
Pasul 10) La momentul = 23, P3 își termină execuția.
Pasul 11) Să calculăm timpul mediu de așteptare pentru exemplul de mai sus.
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
Avantajele SJF
Iată avantajele / avantajele utilizării metodei SJF:
- SJF este frecvent utilizat pentru programarea pe termen lung.
- Reduce timpul mediu de așteptare peste algoritmul FIFO (First in First Out).
- Metoda SJF oferă cel mai mic timp mediu de așteptare pentru un set specific de procese.
- Este adecvat pentru lucrările care rulează în lot, unde timpii de rulare sunt cunoscuți în prealabil.
- Pentru sistemul discontinuu 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ă prezicem valoarea următoarei perioade de explozie.
- Probabil optim în ceea ce privește timpul mediu de răspuns.
Dezavantaje / dezavantaje ale SJF
Iată câteva dezavantaje / dezavantaje ale algoritmului SJF:
- Timpul de finalizare a locului de muncă trebuie cunoscut mai devreme, dar este greu de prezis.
- Este adesea folosit într-un sistem discontinuu 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 rafale de CPU.
- Acest algoritm poate provoca timpi de răspuns foarte lungi sau foamete.
- Necesită cunoștințe despre cât timp va rula un proces sau un job.
- Aceasta duce la înfometarea care nu reduce timpul mediu de răspuns.
- Este greu de știut durata viitoarei cereri de procesor.
- Timpul scurs ar trebui să fie înregistrat, ceea ce duce la mai multe cheltuieli generale asupra procesorului.
rezumat
- SJF este un algoritm în care procesul care are cel mai mic timp de execuție este ales pentru următoarea execuție.
- Programarea SJF este asociată fiecărei lucrări ca o unitate de timp pentru finalizare.
- Această metodă algoritmică este utilă pentru procesarea de tip batch, unde așteptarea finalizării lucrărilor nu este critică.
- Există practic două tipuri de metode SJF 1) SJF non-preventiv și 2) SJF preventiv.
- În programarea non-preventivă, odată ce ciclul procesorului este alocat procesului, procesul îl menține până ajunge la o stare de așteptare sau se termină.
- În programarea SJF preventivă, joburile sunt puse în coada pregătită pe măsură ce vin.
- Deși începe un proces cu timp scurt de explozie, procesul curent este eliminat sau împiedicat de executare, iar lucrarea care este mai scurtă este executată pe primul loc.
- SJF este frecvent utilizat pentru programarea pe termen lung.
- Reduce timpul mediu de așteptare peste algoritmul FIFO (First in First Out).
- În programarea SJF, timpul de finalizare a lucrărilor trebuie cunoscut mai devreme, dar este greu de prezis.
- 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 rafale de CPU.