Wat is de kortste taak eerst-planning?
Shortest Job First (SJF) is een algoritme waarin het proces met de kleinste uitvoeringstijd wordt gekozen voor de volgende uitvoering. Deze planningsmethode kan preventief of niet-preventief zijn. Het vermindert de gemiddelde wachttijd voor andere processen die wachten op uitvoering aanzienlijk. De volledige vorm van SJF is de kortste taak eerst.
Er zijn in principe twee soorten SJF-methoden:
- Niet-preventieve SJF
- Preventieve SJF
In deze handleiding voor het besturingssysteem leert u:
- Wat is de kortste taak eerst-planning?
- Kenmerken van SJF Scheduling
- Niet-preventieve SJF
- Preventieve SJF
- Voordelen van SJF
- Nadelen / nadelen van SJF
Kenmerken van SJF Scheduling
- Het wordt aan elke taak gekoppeld als een te voltooien tijdseenheid.
- Deze algoritmemethode is handig voor verwerking van het batchtype, waarbij wachten tot taken zijn voltooid niet kritisch is.
- Het kan de procesdoorvoer verbeteren door ervoor te zorgen dat kortere taken eerst worden uitgevoerd en dus mogelijk een korte doorlooptijd hebben.
- Het verbetert de job output door kortere jobs aan te bieden, die eerst uitgevoerd moeten worden, die meestal een kortere doorlooptijd hebben.
Niet-preventieve SJF
Bij niet-preventieve planning, zodra de CPU-cyclus is toegewezen om te verwerken, houdt het proces het vast totdat het een wachttoestand bereikt of wordt beëindigd.
Beschouw de volgende vijf processen die elk hun eigen unieke burst-tijd en aankomsttijd hebben.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 0) Op tijd = 0 arriveert P4 en begint de uitvoering.
Stap 1) Op tijd = 1 arriveert proces P3. Maar P4 heeft nog steeds 2 uitvoeringseenheden nodig om te voltooien. Het zal doorgaan met de uitvoering.
Stap 2) Op tijd = 2 arriveert proces P1 en wordt toegevoegd aan de wachtrij. P4 gaat door met de uitvoering.
Stap 3) Op tijd = 3, zal proces P4 zijn uitvoering beëindigen. De burst-tijd van P3 en P1 wordt vergeleken. Proces P1 wordt uitgevoerd omdat de burst-tijd korter is in vergelijking met P3.
Stap 4) Op tijd = 4 arriveert proces P5 en wordt toegevoegd aan de wachtrij. P1 gaat door met de uitvoering.
Stap 5) Op tijd = 5 arriveert proces P2 en wordt toegevoegd aan de wachtrij. P1 gaat door met de uitvoering.
Stap 6) Op tijd = 9, zal proces P1 zijn uitvoering beëindigen. De burst-tijd van P3, P5 en P2 wordt vergeleken. Proces P2 wordt uitgevoerd omdat de burst-tijd de laagste is.
Stap 7) Op tijd = 10, wordt P2 uitgevoerd en staan P3 en P5 in de wachtrij.
Stap 8) Op tijd = 11, zal proces P2 zijn uitvoering beëindigen. De burst-tijd van P3 en P5 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd korter is.
Stap 9) Op tijd = 15 zal proces P5 zijn uitvoering beëindigen.
Stap 10) Op tijd = 23, zal proces P3 zijn uitvoering beëindigen.
Stap 11) Laten we de gemiddelde wachttijd voor bovenstaand voorbeeld berekenen.
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
Preventieve SJF
In Preemptive SJF Scheduling worden taken in de wachtrij geplaatst zodra ze binnenkomen. Een proces met de kortste burst-tijd begint met de uitvoering. Als een proces met een nog kortere burst-tijd arriveert, wordt het huidige proces verwijderd of kan het niet worden uitgevoerd, en krijgt de kortere taak een CPU-cyclus toegewezen.
Beschouw de volgende vijf processen:
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 0) Op tijd = 0 arriveert P4 en begint de uitvoering.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 1) Op tijd = 1 arriveert proces P3. Maar P4 heeft een kortere burst-tijd. Het zal doorgaan met de uitvoering.
Stap 2) Op tijd = 2 arriveert proces P1 met burst-tijd = 6. De burst-tijd is langer dan die van P4. Daarom gaat P4 door met de uitvoering.
Stap 3) Op tijd = 3, zal proces P4 zijn uitvoering beëindigen. De burst-tijd van P3 en P1 wordt vergeleken. Proces P1 wordt uitgevoerd omdat de burst-tijd korter is.
Stap 4) Op tijd = 4 komt proces P5 aan. De burst-tijd van P3, P5 en P1 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd het laagst is. Proces P1 wordt onderdrukt.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
| P1 | 5 van de 6 blijft over | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 5) Op tijd = 5 komt proces P2 aan. De burst-tijd van P1, P2, P3 en P5 wordt vergeleken. Proces P2 wordt uitgevoerd omdat de burst-tijd het kortst is. Proces P5 wordt onderbroken.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
| P1 | 5 van de 6 blijft over | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 van de 4 blijft over | 4 |
Stap 6) Op tijd = 6, wordt P2 uitgevoerd.
Stap 7) Op tijd = 7 voltooit P2 de uitvoering. De burst-tijd van P1, P3 en P5 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd korter is.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
| P1 | 5 van de 6 blijft over | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 van de 4 blijft over | 4 |
Stap 8) Op tijd = 10, zal P5 zijn uitvoering voltooien. De burst-tijd van P1 en P3 wordt vergeleken. Proces P1 wordt uitgevoerd omdat de burst-tijd korter is.
Stap 9) Op tijd = 15 voltooit P1 zijn uitvoering. P3 is het enige proces dat nog over is. Het begint met de uitvoering.
Stap 10) Op tijd = 23, voltooit P3 zijn uitvoering.
Stap 11) Laten we de gemiddelde wachttijd voor bovenstaand voorbeeld berekenen.
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
Voordelen van SJF
Hier zijn de voordelen / voordelen van het gebruik van de SJF-methode:
- SJF wordt vaak gebruikt voor langetermijnplanning.
- Het vermindert de gemiddelde wachttijd ten opzichte van het FIFO-algoritme (First in First Out).
- De SJF-methode geeft de laagste gemiddelde wachttijd voor een specifieke set processen.
- Het is geschikt voor de taken die in batch worden uitgevoerd, waarbij de looptijden van tevoren bekend zijn.
- Voor het batchsysteem van langetermijnplanning kan een schatting van de burst-tijd worden verkregen uit de taakomschrijving.
- Voor korte-termijnplanning moeten we de waarde van de volgende burst-tijd voorspellen.
- Waarschijnlijk optimaal met betrekking tot de gemiddelde doorlooptijd.
Nadelen / nadelen van SJF
Hier zijn enkele nadelen / nadelen van het SJF-algoritme:
- De voltooiingstijd van een taak moet eerder bekend zijn, maar het is moeilijk te voorspellen.
- Het wordt vaak gebruikt in een batch-systeem voor langetermijnplanning.
- SJF kan op korte termijn niet worden geïmplementeerd voor CPU-planning. Het is omdat er geen specifieke methode is om de lengte van de komende CPU-burst te voorspellen.
- Dit algoritme kan zeer lange doorlooptijden of uithongering veroorzaken.
- Vereist kennis van hoe lang een proces of taak zal duren.
- Het leidt tot de honger die de gemiddelde doorlooptijd niet verkort.
- Het is moeilijk om de lengte van het aankomende CPU-verzoek te weten.
- Verstreken tijd moet worden geregistreerd, dat resulteert in meer overhead op de processor.
Overzicht
- SJF is een algoritme waarin het proces met de kleinste uitvoeringstijd wordt gekozen voor de volgende uitvoering.
- SJF Scheduling wordt aan elke taak gekoppeld als een te voltooien tijdseenheid.
- Deze algoritmemethode is handig voor verwerking van het batchtype, waarbij wachten tot taken zijn voltooid niet kritisch is.
- Er zijn in principe twee soorten SJF-methoden: 1) niet-preventieve SJF en 2) preventieve SJF.
- Bij niet-preventieve planning, zodra de CPU-cyclus is toegewezen om te verwerken, houdt het proces het vast totdat het een wachttoestand bereikt of wordt beëindigd.
- In Preemptive SJF Scheduling worden taken in de wachtrij geplaatst zodra ze binnenkomen.
- Hoewel een proces met een korte burst-tijd begint, wordt het huidige proces verwijderd of kan het niet worden uitgevoerd, en wordt de taak die korter is, als eerste uitgevoerd.
- SJF wordt vaak gebruikt voor langetermijnplanning.
- Het vermindert de gemiddelde wachttijd ten opzichte van het FIFO-algoritme (First in First Out).
- Bij SJF-planning moet de voltooiingstijd van de taak eerder bekend zijn, maar het is moeilijk te voorspellen.
- SJF kan op korte termijn niet worden geïmplementeerd voor CPU-planning. Het is omdat er geen specifieke methode is om de lengte van de komende CPU-burst te voorspellen.