Kas ir īsākais darba plānošana vispirms?
Īsākais darbs vispirms (SJF) ir algoritms, kurā nākamajai izpildei tiek izvēlēts process ar vismazāko izpildes laiku. Šī plānošanas metode var būt preventīva vai nepieļauta. Tas ievērojami samazina vidējo gaidīšanas laiku citiem procesiem, kas gaida izpildi. Pilna SJF forma ir Īsākais darbs vispirms.
Būtībā ir divu veidu SJF metodes:
- Nepreferatīvs SJF
- Preventīvs SJF
Šajā operētājsistēmas apmācībā jūs uzzināsiet:
- Kas ir īsākais darba plānošana vispirms?
- SJF plānošanas raksturojums
- Nepreferatīvs SJF
- Preventīvs SJF
- SJF priekšrocības
- SJF trūkumi / mīnusi
SJF plānošanas raksturojums
- Tas ir saistīts ar katru darbu kā laika vienību, kas jāpaveic.
- Šī algoritma metode ir noderīga sērijveida apstrādei, kur darbu pabeigšanas gaidīšana nav kritiska.
- Tas var uzlabot procesa caurlaidspēju, pārliecinoties, ka vispirms tiek izpildīti īsāki darbi, līdz ar to, iespējams, īss darba laiks.
- Tas uzlabo darba piedāvājumu, piedāvājot īsākus darbus, kuri būtu jāizpilda vispirms, kuriem pārsvarā ir īsāks darba laiks.
Nepreferatīvs SJF
Nepieļaujot plānošanu, kad CPU cikls ir piešķirts procesam, process to tur, līdz tas sasniedz gaidīšanas stāvokli vai tiek pārtraukts.
Apsveriet šādus piecus procesus, kuriem katram ir savs unikālais pārraides laiks un ierašanās laiks.
| Procesa rinda | Sprādziena laiks | Ierašanās laiks |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
0. solis) Laikā = 0, P4 pienāk un sāk izpildi.
1. solis) Laikā = 1, pienāk process P3. Bet P4 pabeigšanai joprojām ir vajadzīgas 2 izpildes vienības. Tas turpinās izpildi.
2. solis. Laikā = 2 pienāk process P1 un tiek pievienots gaidīšanas rindai. P4 turpinās izpildi.
3. solis. Laikā = 3 process P4 pabeigs tā izpildi. Salīdzina P3 un P1 sprādziena laiku. Process P1 tiek izpildīts, jo tā sprādziena laiks ir mazāks nekā P3.
4. solis. Laikā = 4, pienāk process P5, kas tiek pievienots gaidīšanas rindai. P1 turpinās izpildi.
5. solis. Laikā = 5, pienāk process P2 un tiek pievienots gaidīšanas rindai. P1 turpinās izpildi.
6. solis) Laikā = 9 process P1 pabeigs tā izpildi. Salīdzina P3, P5 un P2 eksplozijas laiku. Process P2 tiek izpildīts, jo tā sprādziena laiks ir mazākais.
7. solis) Laikā = 10, P2 izpilda, un P3 un P5 ir gaidīšanas rindā.
8. solis. Laikā = 11 process P2 pabeigs tā izpildi. Salīdzina P3 un P5 sprādziena laiku. Process P5 tiek izpildīts, jo tā sprādziena laiks ir mazāks.
9. solis) Laikā = 15 process P5 pabeigs tā izpildi.
10. solis. Laikā = 23 process P3 izpildīs.
11. solis. Aprēķināsim vidējo gaidīšanas laiku iepriekš minētajam piemēram.
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
Preventīvs SJF
Izmantojot Preemptive SJF Scheduling, darbavietas tiek ievietotas gatavajā rindā, tiklīdz tās nāk. Tiek uzsākts process ar īsāko sērijas laiku. Ja pienāk process ar vēl īsāku sērijas laiku, pašreizējais process tiek noņemts vai izpildīts, un īsākajam darbam tiek piešķirts CPU cikls.
Apsveriet šādus piecus procesus:
| Procesa rinda | Sprādziena laiks | Ierašanās laiks |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
0. solis) Laikā = 0, P4 pienāk un sāk izpildi.
| Procesa rinda | Sprādziena laiks | Ierašanās laiks |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
1. solis) Laikā = 1, pienāk process P3. Bet, P4 ir īsāks sērijas laiks. Tas turpinās izpildi.
2. solis. Laikā = 2, process P1 pienāk ar sērijas laiku = 6. Pārraušanas laiks ir lielāks nekā P4. Tādējādi P4 turpinās izpildi.
3. solis. Laikā = 3 process P4 pabeigs tā izpildi. Salīdzina P3 un P1 sprādziena laiku. Process P1 tiek izpildīts, jo tā sprādziena laiks ir mazāks.
4. solis. Laikā = 4 pienāks process P5. Salīdzina P3, P5 un P1 sprādziena laiku. Process P5 tiek izpildīts, jo tā sprādziena laiks ir viszemākais. Process P1 ir nepieļauts.
| Procesa rinda | Sprādziena laiks | Ierašanās laiks |
| P1 | 5 no 6 ir palikuši | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
5. solis) Laikā = 5, pienāks process P2. Salīdzina P1, P2, P3 un P5 eksplozijas laiku. Process P2 tiek izpildīts, jo tā sprādziena laiks ir mazākais. Process P5 ir nepieļauts.
| Procesa rinda | Sprādziena laiks | Ierašanās laiks |
| P1 | 5 no 6 ir palikuši | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Atlikušas 3 no 4 | 4 |
6. solis) Laikā = 6, izpilda P2.
7. solis) Laikā = 7, P2 pabeidz izpildi. Salīdzina P1, P3 un P5 eksplozijas laiku. Process P5 tiek izpildīts, jo tā sprādziena laiks ir mazāks.
| Procesa rinda | Sprādziena laiks | Ierašanās laiks |
| P1 | 5 no 6 ir palikuši | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Atlikušas 3 no 4 | 4 |
8. solis) Laikā = 10, P5 pabeigs izpildi. Salīdzina P1 un P3 sprādziena laiku. Process P1 tiek izpildīts, jo tā sprādziena laiks ir mazāks.
9. solis) Laikā = 15, P1 pabeidz izpildi. P3 ir vienīgais atlikušais process. Tas sāks izpildi.
10. solis) Laikā = 23, P3 pabeidz izpildi.
11. solis. Aprēķināsim vidējo gaidīšanas laiku iepriekš minētajam piemēram.
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
SJF priekšrocības
Šeit ir SJF metodes izmantošanas priekšrocības / plusi:
- SJF bieži izmanto ilgtermiņa plānošanai.
- Tas samazina vidējo gaidīšanas laiku, salīdzinot ar FIFO (First in First Out) algoritmu.
- SJF metode dod zemāko vidējo gaidīšanas laiku konkrētam procesu kopumam.
- Tas ir piemērots darbiem, kas darbojas paketēs, kur izpildes laiki ir zināmi iepriekš.
- Ilgtermiņa plānošanas sērijveida sistēmai sērijas laika aprēķinu var iegūt no darba apraksta.
- Īstermiņa plānošanai mums jāparedz nākamā sērijas laika vērtība.
- Iespējams, optimāls attiecībā uz vidējo apgrozījuma laiku.
SJF trūkumi / mīnusi
Šeit ir daži SJF algoritma trūkumi / trūkumi:
- Darba pabeigšanas laiks ir jāzina agrāk, taču to ir grūti paredzēt.
- To bieži izmanto pakešu sistēmā ilgtermiņa plānošanai.
- SJF nevar ieviest CPU plānošanai īstermiņā. Tas ir tāpēc, ka nav īpašas metodes gaidāmā CPU pārsprāgt ilguma prognozēšanai.
- Šis algoritms var izraisīt ļoti ilgu apgrozījuma laiku vai badu.
- Nepieciešamas zināšanas par procesa vai darba ilgumu.
- Tas noved pie bada, kas nesamazina vidējo apgrozījuma laiku.
- Ir grūti zināt gaidāmā procesora pieprasījuma ilgumu.
- Būtu jāreģistrē pagājušais laiks, tādējādi palielinot procesora izmaksas.
Kopsavilkums
- SJF ir algoritms, kurā nākamajai izpildei tiek izvēlēts process ar vismazāko izpildes laiku.
- SJF plānošana ir saistīta ar katru darbu kā laika vienību, kas jāpaveic.
- Šī algoritma metode ir noderīga sērijveida apstrādei, kur darbu pabeigšanas gaidīšana nav kritiska.
- Būtībā pastāv divu veidu SJF metodes: 1) Nepreferenciāla SJF un 2) Preemptive SJF.
- Nepieļaujot plānošanu, kad CPU cikls ir piešķirts procesam, process to tur, līdz tas sasniedz gaidīšanas stāvokli vai tiek pārtraukts.
- Izmantojot Preemptive SJF Scheduling, darbavietas tiek ievietotas gatavajā rindā, tiklīdz tās nāk.
- Neskatoties uz to, ka sākas process ar īsu sērijas laiku, pašreizējais process tiek noņemts vai izpildīts, un īsāks darbs tiek izpildīts 1. vietā.
- SJF bieži izmanto ilgtermiņa plānošanai.
- Tas samazina vidējo gaidīšanas laiku, salīdzinot ar FIFO (First in First Out) algoritmu.
- SJF plānošanā darba izpildes laiks ir jāzina agrāk, taču to ir grūti paredzēt.
- SJF nevar ieviest CPU plānošanai īstermiņā. Tas ir tāpēc, ka nav īpašas metodes gaidāmā CPU pārsprāgt ilguma prognozēšanai.