Čo je prvé plánovanie najkratšej práce?
Najkratšia práca ako prvá (SJF) je algoritmus, v ktorom sa pre ďalšie vykonávanie zvolí proces s najmenším časom vykonania. Táto metóda plánovania môže byť preventívna aj nepreventívna. Výrazne znižuje priemernú dobu čakania na ďalšie procesy čakajúce na vykonanie. Plná forma SJF je Najkratšia práca ako prvá.
V zásade existujú dva typy metód SJF:
- Nepreventívne SJF
- Preventívne SJF
V tomto výučbe operačného systému sa dozviete:
- Čo je prvé plánovanie najkratšej práce?
- Charakteristika plánovania SJF
- Nepreventívne SJF
- Preventívne SJF
- Výhody SJF
- Nevýhody / nevýhody SJF
Charakteristika plánovania SJF
- Je spojená s každou úlohou ako jednotka času na dokončenie.
- Táto metóda algoritmu je užitočná pri dávkovom spracovaní, kde čakanie na dokončenie úloh nie je kritické.
- Môže zlepšiť priepustnosť procesu tým, že zabezpečí, že sa najskôr vykonajú kratšie úlohy, a preto budú mať pravdepodobne krátky čas na vybavenie.
- Zlepšuje produkciu úloh tým, že ponúka kratšie úlohy, ktoré by sa mali vykonať najskôr, ktoré majú väčšinou kratšiu dobu spracovania.
Nepreventívne SJF
V nepreventívnom plánovaní, akonáhle je cyklus CPU pridelený procesu, proces ho drží, kým nedosiahne stav čakania alebo sa neukončí.
Zvážte nasledujúcich päť procesov, z ktorých každý má svoj vlastný jedinečný čas roztrhnutia a čas príchodu.
| Procesný front | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 0) V čase = 0 dorazí P4 a začne vykonávanie.
Krok 1) V čase = 1 dorazí proces P3. Na dokončenie však P4 stále potrebuje 2 exekučné jednotky. Bude pokračovať v exekúcii.
Krok 2) V čase = 2 prichádza proces P1 a je pridaný do čakacieho radu. P4 bude pokračovať v exekúcii.
Krok 3) V čase = 3 proces P4 dokončí svoje vykonávanie. Porovnáva sa čas roztrhnutia P3 a P1. Proces P1 sa vykoná, pretože jeho čas roztrhnutia je menší v porovnaní s P3.
Krok 4) V čase = 4 dorazí proces P5 a je pridaný do čakacieho radu. P1 bude pokračovať v exekúcii.
Krok 5) V čase = 5 dorazí proces P2 a je pridaný do čakacieho radu. P1 bude pokračovať v exekúcii.
Krok 6) V čase = 9 proces P1 ukončí svoje vykonávanie. Porovnáva sa čas roztrhnutia P3, P5 a P2. Proces P2 sa vykoná, pretože jeho čas roztrhnutia je najnižší.
Krok 7) V čase = 10 sa vykonáva P2 a P3 a P5 sú v čakacej rade.
Krok 8) V čase = 11 proces P2 ukončí svoje vykonávanie. Porovnáva sa čas roztrhnutia P3 a P5. Proces P5 sa vykoná, pretože jeho čas roztrhnutia je nižší.
Krok 9) V čase = 15 proces P5 ukončí svoje vykonávanie.
Krok 10) V čase = 23 proces P3 dokončí svoje vykonávanie.
Krok 11) Vypočítajme priemernú dobu čakania pre vyššie uvedený príklad.
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ívne SJF
V preventívnom plánovaní SJF sa úlohy zaraďujú do poradia hneď, ako prídu. Spustí sa proces s najkratšou dobou prasknutia. Ak dorazí proces s ešte kratšou dobou zhluku, aktuálny proces sa odstráni alebo sa mu zabráni v vykonaní a kratšej úlohe sa pridelí cyklus CPU.
Zvážte nasledujúcich päť procesov:
| Procesný front | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 0) V čase = 0 dorazí P4 a začne vykonávanie.
| Procesný front | Čas prasknutia | Čas príchodu |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 1) V čase = 1 dorazí proces P3. Ale P4 má kratší čas prasknutia. Bude pokračovať v exekúcii.
Krok 2) V čase = 2 prichádza proces P1 s časom roztrhnutia = 6. Čas roztrhnutia je viac ako v prípade P4. Preto bude P4 pokračovať v realizácii.
Krok 3) V čase = 3 proces P4 dokončí svoje vykonávanie. Porovnáva sa čas roztrhnutia P3 a P1. Proces P1 sa vykoná, pretože jeho čas roztrhnutia je nižší.
Krok 4) V čase = 4 dorazí proces P5. Porovnáva sa čas roztrhnutia P3, P5 a P1. Proces P5 sa vykoná, pretože jeho čas roztrhnutia je najnižší. Proces P1 je zabránený.
| Procesný front | Čas prasknutia | Čas príchodu |
| P1 | Zostáva 5 zo 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 5) V čase = 5 dorazí proces P2. Porovnáva sa čas roztrhnutia P1, P2, P3 a P5. Proces P2 sa vykoná, pretože jeho čas roztrhnutia je najmenší. Proces P5 je zabránený.
| Procesný front | Čas prasknutia | Čas príchodu |
| P1 | Zostáva 5 zo 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 zo 4 zostávajú | 4 |
Krok 6) V čase = 6 sa vykonáva P2.
Krok 7) V čase = 7, P2 dokončí svoje vykonávanie. Porovnáva sa čas roztrhnutia P1, P3 a P5. Proces P5 sa vykoná, pretože jeho čas roztrhnutia je menší.
| Procesný front | Čas prasknutia | Čas príchodu |
| P1 | Zostáva 5 zo 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 zo 4 zostávajú | 4 |
Krok 8) V čase = 10 P5 ukončí svoje vykonávanie. Porovnáva sa čas roztrhnutia P1 a P3. Proces P1 sa vykoná, pretože jeho čas roztrhnutia je kratší.
Krok 9) V čase = 15 P1 dokončí svoje vykonávanie. P3 je jediný zostávajúci proces. Začne sa s popravou.
Krok 10) V čase = 23 P3 dokončí svoje vykonávanie.
Krok 11) Vypočítajme priemernú dobu čakania pre vyššie uvedený príklad.
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
Výhody SJF
Tu sú výhody / výhody použitia metódy SJF:
- SJF sa často používa na dlhodobé plánovanie.
- Znižuje priemernú dobu čakania pri použití algoritmu FIFO (First in First Out).
- Metóda SJF poskytuje najnižšiu priemernú dobu čakania na konkrétny súbor procesov.
- Je to vhodné pre úlohy bežiace v dávkach, kde sú časy behu známe vopred.
- Pre dávkový systém dlhodobého plánovania je možné z opisu úlohy získať odhad doby prasknutia.
- V prípade krátkodobého plánovania musíme predpovedať hodnotu nasledujúceho sériového času.
- Pravdepodobne optimálne z hľadiska priemerného času na vybavenie.
Nevýhody / nevýhody SJF
Tu sú niektoré nevýhody / nevýhody algoritmu SJF:
- Čas dokončenia práce musí byť známy skôr, ale je ťažké ho predpovedať.
- Často sa používa v dávkovom systéme na dlhodobé plánovanie.
- SJF nie je možné z krátkodobého hľadiska implementovať na plánovanie CPU. Je to preto, že neexistuje žiadna konkrétna metóda na predpovedanie dĺžky nadchádzajúceho výbuchu CPU.
- Tento algoritmus môže spôsobiť veľmi dlhé časy spracovania alebo hladovanie.
- Vyžaduje znalosť toho, ako dlho bude proces alebo úloha prebiehať.
- Vedie k hladu, ktorý neznižuje priemerný čas obratu.
- Je ťažké poznať dĺžku nadchádzajúcej požiadavky CPU.
- Uplynutý čas by sa mal zaznamenávať, čo má za následok vyššiu réžiu procesora.
Zhrnutie
- SJF je algoritmus, v ktorom je pre ďalšie vykonávanie zvolený proces s najmenším časom vykonania.
- Plánovanie SJF je spojené s každou úlohou ako jednotka času na dokončenie.
- Táto metóda algoritmu je užitočná pri dávkovom spracovaní, kde čakanie na dokončenie úloh nie je kritické.
- V zásade existujú dva typy metód SJF 1) Preventívny SJF a 2) Preventívny SJF.
- V nepreventívnom plánovaní, akonáhle je cyklus CPU pridelený procesu, proces ho drží, kým nedosiahne stav čakania alebo sa neukončí.
- V preventívnom plánovaní SJF sa úlohy zaraďujú do poradia hneď, ako prídu.
- Aj keď sa začína proces s krátkym časom zhluku, aktuálny proces sa odstráni alebo sa mu zabráni v vykonaní a úloha, ktorá je kratšia, sa vykoná ako prvá.
- SJF sa často používa na dlhodobé plánovanie.
- Znižuje priemernú dobu čakania pri použití algoritmu FIFO (First in First Out).
- Pri plánovaní SJF musí byť čas dokončenia úlohy známy skôr, ale je ťažké ho predvídať.
- SJF nie je možné z krátkodobého hľadiska implementovať na plánovanie CPU. Je to preto, že neexistuje žiadna konkrétna metóda na predpovedanie dĺžky nadchádzajúceho výbuchu CPU.