Kas yra trumpiausias pirmojo darbo planavimas?
Trumpiausias darbas pirmiausia (SJF) yra algoritmas, kuriame kitam vykdymui pasirenkamas mažiausiai vykdymo laiką turintis procesas. Šis planavimo metodas gali būti prevencinis arba neprognozuojantis. Tai žymiai sumažina kitų procesų, laukiančių vykdymo, vidutinę laukimo laiką. Visa SJF forma yra „Trumpiausias darbas pirmiausia“.
Iš esmės yra dviejų tipų SJF metodai:
- Nepreitinguojantis SJF
- Prevencinis SJF
Šioje operacinės sistemos pamokoje sužinosite:
- Kas yra trumpiausias pirmojo darbo planavimas?
- SJF planavimo ypatybės
- Nepreitinguojantis SJF
- Prevencinis SJF
- SJF pranašumai
- SJF trūkumai / trūkumai
SJF planavimo ypatybės
- Jis susietas su kiekvienu darbu kaip laiko vienetas, kurį reikia atlikti.
- Šis algoritmo metodas yra naudingas paketinio tipo apdorojimui, kai laukti, kol darbai bus baigti, nėra kritiška.
- Tai gali pagerinti procesų našumą užtikrindama, kad pirmiausia būtų atliekami trumpesni darbai, taigi galbūt trumpas darbo laikas.
- Tai pagerina darbo našumą siūlant trumpesnes darbo vietas, kurios turėtų būti vykdomos pirmiausia, o jų darbo laikas dažniausiai yra trumpesnis.
Nepreitinguojantis SJF
Neiš anksto planuojant planavimą, kai procesoriaus ciklas yra paskirtas procesui, procesas jį laiko tol, kol pasiekia laukimo būseną arba baigiasi.
Apsvarstykite šiuos penkis procesus, kurių kiekvienas turi savo unikalų serijos laiką ir atvykimo laiką.
| Proceso eilė | Sprogo laikas | Atvykimo laikas |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
0 žingsnis) Tuo metu, kai = 0, ateina P4 ir pradeda vykdyti.
1 žingsnis) Tuo metu, kai = 1, ateina procesas P3. Tačiau P4 vis tiek reikia 2 vykdymo vienetų, kad būtų galima užbaigti. Jis tęs vykdymą.
2 žingsnis) Tuo metu, kai = 2, ateina procesas P1 ir įtraukiamas į laukimo eilę. P4 tęs vykdymą.
3 žingsnis) Tuo metu, kai laikas = 3, procesas P4 bus baigtas. Palyginamas P3 ir P1 sprogimo laikas. Procesas P1 vykdomas, nes jo serijos laikas yra mažesnis, palyginti su P3.
4 žingsnis) Tuo metu, kai = 4, ateina procesas P5 ir įtraukiamas į laukimo eilę. P1 tęs vykdymą.
5 žingsnis) Tuo metu, kai laikas yra 5, atkeliauja procesas P2 ir įtraukiamas į laukimo eilę. P1 tęs vykdymą.
6 žingsnis) Tuo metu, kai = 9, procesas P1 užbaigs jo vykdymą. Palyginamas P3, P5 ir P2 sprogimo laikas. Procesas P2 vykdomas, nes jo serijos laikas yra mažiausias.
7 žingsnis) Tuo metu, kai = 10, P2 vykdo, o P3 ir P5 yra laukimo eilėje.
8 žingsnis) Tuo metu, kai = 11, procesas P2 užbaigs jo vykdymą. Palyginamas P3 ir P5 sprogimo laikas. Procesas P5 vykdomas, nes jo serijos laikas yra mažesnis.
9 žingsnis) Tuo metu, kai 15, procesas P5 bus baigtas.
10 žingsnis) Tuo metu = 23, procesas P3 bus baigtas.
11 žingsnis) Apskaičiuokime aukščiau pateikto pavyzdžio vidutinę laukimo laiką.
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
Prevencinis SJF
Taikant „Preemptive SJF Scheduling“, darbai atidedami į eilę. Procesas su trumpiausiu serijos laiku pradedamas vykdyti. Jei ateina procesas su net trumpesniu serijos laiku, dabartinis procesas pašalinamas arba jam neleidžiama vykdyti, o trumpesniam darbui priskiriamas procesoriaus ciklas.
Apsvarstykite šiuos penkis procesus:
| Proceso eilė | Sprogo laikas | Atvykimo laikas |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
0 žingsnis) Tuo metu, kai = 0, ateina P4 ir pradeda vykdyti.
| Proceso eilė | Sprogo laikas | Atvykimo laikas |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
1 žingsnis) Tuo metu, kai = 1, ateina procesas P3. Tačiau P4 serijos laikas yra trumpesnis. Jis tęs vykdymą.
2 žingsnis) Tuo metu, kai laikas = 2, procesas P1 ateina su serijos laiku = 6. Sprogo laikas yra didesnis nei P4. Taigi P4 tęs vykdymą.
3 žingsnis) Tuo metu, kai laikas = 3, procesas P4 bus baigtas. Palyginamas P3 ir P1 sprogimo laikas. Procesas P1 vykdomas, nes jo serijos laikas yra mažesnis.
4 žingsnis) Tuo metu, kai = 4, atvyks procesas P5. Palyginamas P3, P5 ir P1 sprogimo laikas. Procesas P5 vykdomas, nes jo serijos laikas yra mažiausias. Procesas P1 yra užkerta kelią.
| Proceso eilė | Sprogo laikas | Atvykimo laikas |
| P1 | Liko 5 iš 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
5 žingsnis) Kai laikas = 5, atvyks procesas P2. Palyginamas P1, P2, P3 ir P5 sprogimo laikas. Procesas P2 vykdomas, nes jo sprogimo laikas yra mažiausias. Procesas P5 yra užkerta kelią.
| Proceso eilė | Sprogo laikas | Atvykimo laikas |
| P1 | Liko 5 iš 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Liko 3 iš 4 | 4 |
6 žingsnis) Tuo metu, kai = 6, P2 vykdo.
7 žingsnis) Tuo metu, kai = 7, P2 baigia vykdyti. Palyginamas P1, P3 ir P5 sprogimo laikas. Procesas P5 vykdomas, nes jo serijos laikas yra mažesnis.
| Proceso eilė | Sprogo laikas | Atvykimo laikas |
| P1 | Liko 5 iš 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Liko 3 iš 4 | 4 |
8 žingsnis) Kai laikas = 10, P5 baigs vykdyti. Palyginamas P1 ir P3 sprogimo laikas. Procesas P1 vykdomas, nes jo serijos laikas yra trumpesnis.
9 žingsnis) Tuo metu, kai = 15, P1 baigia vykdyti. P3 yra vienintelis likęs procesas. Tai pradės vykdyti.
10 žingsnis) Laiku = 23, P3 baigia vykdyti.
11 žingsnis) Apskaičiuokime aukščiau pateikto pavyzdžio vidutinę laukimo laiką.
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 pranašumai
Štai SJF metodo naudojimo pranašumai / pliusai:
- SJF dažnai naudojamas ilgalaikiam planavimui.
- Tai sumažina vidutinį laukimo laiką per FIFO („First in First Out“) algoritmą.
- SJF metodas suteikia mažiausią vidutinį laukimo laiką konkrečiam procesų rinkiniui.
- Tai tinka užduotims, vykdomoms paketais, kur vykdymo laikas yra žinomas iš anksto.
- Ilgalaikio planavimo paketinei sistemai serijos laiko įvertinimą galima gauti iš pareigybės aprašymo.
- Trumpalaikiam planavimui turime numatyti kito serijos laiko vertę.
- Tikriausiai optimalus atsižvelgiant į vidutinį apsisukimo laiką.
SJF trūkumai / trūkumai
Štai keletas SJF algoritmo trūkumų / trūkumų:
- Darbo laikas turi būti žinomas anksčiau, tačiau sunku nuspėti.
- Jis dažnai naudojamas paketinėje sistemoje ilgalaikiam planavimui.
- SJF negalima įgyvendinti planuojant procesorių trumpam laikotarpiui. Taip yra todėl, kad nėra konkretaus metodo numatyti būsimo procesoriaus sprogimo trukmę.
- Šis algoritmas gali sukelti labai ilgą apsisukimo laiką ar badą.
- Reikalingos žinios, kiek laiko truks procesas ar darbas.
- Tai sukelia badą, kuris nesumažina vidutinio apsisukimo laiko.
- Sunku žinoti būsimo procesoriaus užklausos trukmę.
- Turėtų būti užregistruotas praėjęs laikas, o tai padidina procesoriaus pridėtines išlaidas.
Santrauka
- SJF yra algoritmas, kuriame kitam vykdymui pasirenkamas mažiausiai vykdymo laiką turintis procesas.
- SJF planavimas yra susietas su kiekvienu darbu kaip laiko vienetas, kurį reikia atlikti.
- Šis algoritmo metodas yra naudingas paketinio tipo apdorojimui, kai laukti, kol darbai bus baigti, nėra kritiška.
- Iš esmės yra dviejų tipų SJF metodai: 1) Neapsaugotas SJF ir 2) Preemptyvinis SJF.
- Neiš anksto planuojant planavimą, kai procesoriaus ciklas priskiriamas procesui, procesas jį laiko tol, kol pasiekia laukimo būseną arba baigiasi.
- Taikant „Preemptive SJF Scheduling“, darbai atidedami į eilę.
- Nors prasideda procesas su trumpu serijos laiku, dabartinis procesas pašalinamas arba jam neleidžiama vykdyti, o trumpesnė užduotis atliekama 1-ąja.
- SJF dažnai naudojamas ilgalaikiam planavimui.
- Tai sumažina vidutinį laukimo laiką per FIFO („First in First Out“) algoritmą.
- Planuojant SJF, darbo pabaigos laikas turi būti žinomas anksčiau, tačiau sunku nuspėti.
- SJF negalima įgyvendinti planuojant procesorių trumpam laikotarpiui. Taip yra todėl, kad nėra konkretaus metodo numatyti būsimo procesoriaus sprogimo trukmę.
