Kortste taak eerst (SJF): preventief, niet-preventief voorbeeld
Nathaniel Brooks
⚡ Slimme samenvatting
Shortest Job First (SJF) is een CPU-planningsalgoritme dat het proces met de kortste uitvoeringstijd selecteert om als volgende te worden uitgevoerd. Het kan preemptief of niet-preemptief zijn en verkort de gemiddelde wachttijd voor processen aanzienlijk.
Wat is de kortste taak-eerste planning?
Kortste baan eerst (SJF) is een algoritme waarbij 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 Kortste baan eerst.
Er zijn in principe twee soorten SJF-methoden:
- Niet-preventieve SJF
- Preventieve SJF
Kenmerken van SJF-planning
- Het wordt aan elke taak gekoppeld als een tijdseenheid die moet worden voltooid.
- Deze algoritmemethode is handig voor batchverwerking, waarbij wachten tot taken zijn voltooid niet van cruciaal belang is.
- Het kan de procesdoorvoer verbeteren door ervoor te zorgen dat kortere taken eerst worden uitgevoerd, waardoor de doorlooptijd mogelijk korter wordt.
- Het verbetert de productiviteit door kortere taken aan te bieden, die als eerste moeten worden uitgevoerd en die over het algemeen een kortere doorlooptijd hebben.
Niet-preventieve SJF
Bij niet-preëmptieve scheduling houdt een proces, zodra de CPU-cyclus aan het proces is toegewezen, deze vast totdat het in een wachttoestand terechtkomt of wordt beëindigd.
Beschouw de volgende vijf processen, die elk hun eigen unieke begintijd 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 tijdstip t = 0 arriveert P4 en begint met de uitvoering.
Stap 1) Op tijdstip t = 1 arriveert proces P3. Maar P4 heeft nog 2 uitvoereenheden nodig om te voltooien. Het zal de uitvoering voortzetten.
Stap 2) Op tijdstip = 2 arriveert proces P1 en wordt toegevoegd aan de wachtrij. P4 zal de uitvoering voortzetten.
Stap 3) Op tijdstip = 3 zal proces P4 zijn uitvoering voltooien. De burst-tijd van P3 en P1 wordt vergeleken. Proces P1 wordt uitgevoerd omdat de burst-tijd ervan korter is vergeleken met P3.
Stap 4) Op tijdstip = 4 arriveert proces P5 en wordt toegevoegd aan de wachtrij. P1 zal de uitvoering voortzetten.
Stap 5) Op tijdstip = 5 arriveert proces P2 en wordt toegevoegd aan de wachtrij. P1 zal de uitvoering voortzetten.
Stap 6) Op tijdstip = 9 zal proces P1 zijn uitvoering voltooien. De burst-tijd van P3, P5 en P2 wordt vergeleken. Proces P2 wordt uitgevoerd omdat de burst-tijd het laagst is.
Stap 7) Op tijdstip t=10 is P2 in uitvoering en staan P3 en P5 in de wachtrij.
Stap 8) Op tijdstip = 11 zal proces P2 zijn uitvoering voltooien. De burst-tijd van P3 en P5 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd ervan korter is.
Stap 9) Op tijdstip = 15 zal proces P5 zijn uitvoering voltooien.
Stap 10) Op tijdstip = 23 zal proces P3 zijn uitvoering voltooien.
Stap 11) Laten we de gemiddelde wachttijd voor het bovenstaande voorbeeld berekenen.
Wait time P4 = 0 - 0 = 0 P1 = 3 - 2 = 1 P2 = 9 - 5 = 4 P5 = 11 - 4 = 7 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2
Preventieve SJF
Bij Preemptive SJF Scheduling worden taken in de wachtrij geplaatst zodra ze binnenkomen. Het proces met de kortste uitvoeringstijd begint. Als er een proces met een nog kortere uitvoeringstijd arriveert, wordt het huidige proces verwijderd of onderbroken en krijgt de taak met de kortste uitvoeringstijd een CPU-cyclus toegewezen.
Overweeg 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 tijdstip t = 0 arriveert P4 en begint met 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 tijdstip t = 1 arriveert proces P3. Maar P4 heeft een kortere uitvoeringsduur. Het zal de uitvoering voortzetten.
Stap 2) Op tijdstip = 2 arriveert proces P1 met burst-tijd = 6. De burst-tijd is langer dan die van P4. Daarom zal P4 de uitvoering voortzetten.
Stap 3) Op tijdstip = 3 zal proces P4 zijn uitvoering voltooien. De burst-tijd van P3 en P1 wordt vergeleken. Proces P1 wordt uitgevoerd omdat de burst-tijd ervan korter is.
Stap 4) Op tijdstip = 4 arriveert proces P5. De burst-tijd van P3, P5 en P1 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd het laagst is. Proces P1 wordt voorrang gegeven.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | Er zijn nog 5 van de 6 over | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Stap 5) Op tijdstip t = 5 arriveert proces P2. De bursttijd van P1, P2, P3 en P5 wordt vergeleken. Proces P2 wordt uitgevoerd omdat de bursttijd het kortst is. Proces P5 wordt onderbroken.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | Er zijn nog 5 van de 6 over | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Er zijn nog 3 van de 4 over | 4 |
Stap 6) Op tijdstip t = 6 wordt P2 uitgevoerd.
Stap 7) Op tijdstip t = 7 is P2 klaar met de uitvoering. De bursttijd van P1, P3 en P5 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de bursttijd ervan korter is.
| Wachtrij verwerken | Burst-tijd | Aankomsttijd |
|---|---|---|
| P1 | Er zijn nog 5 van de 6 over | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Er zijn nog 3 van de 4 over | 4 |
Stap 8) Op tijdstip t = 10 zal P5 zijn uitvoering voltooien. De bursttijd van P1 en P3 wordt vergeleken. Proces P1 wordt uitgevoerd omdat de bursttijd ervan korter is.
Stap 9) Op tijdstip t = 15 is P1 klaar met de uitvoering. P3 is het enige proces dat overblijft. Het zal nu beginnen met de uitvoering.
Stap 10) Op tijdstip 23 is de uitvoering van P3 voltooid.
Stap 11) Laten we de gemiddelde wachttijd voor het bovenstaande voorbeeld berekenen.
Wait time P4 = 0 - 0 = 0 P1 = (3 - 2) + 6 = 7 P2 = 5 - 5 = 0 P5 = 4 - 4 + 2 = 2 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6
Voordelen van SJF
Hieronder volgen de voordelen van het gebruik van de SJF-methode:
- SJF wordt vaak gebruikt voor planning op lange termijn.
- Het verkort de gemiddelde wachttijd ten opzichte van het FIFO-algoritme (First In First Out).
- De SJF-methode levert de laagste gemiddelde wachttijd op voor een specifieke set processen.
- Dit is geschikt voor taken die in batch worden uitgevoerd, waarbij de uitvoeringstijden vooraf bekend zijn.
- Voor het batchsysteem voor langetermijnplanning kan een schatting van de burst-tijd worden verkregen uit de taakbeschrijving.
- Voor kortetermijnplanning moeten we de waarde van de volgende burst-tijd voorspellen.
- Het is waarschijnlijk optimaal met betrekking tot de gemiddelde doorlooptijd.
Nadelen/nadelen van SJF
Hieronder volgen enkele nadelen van het SJF-algoritme:
- De voltooiingstijd van een taak moet eerder bekend zijn, maar is moeilijk te voorspellen.
- Het wordt vaak gebruikt in een batchsysteem voor planning op lange termijn.
- SJF kan niet worden geïmplementeerd voor CPU-planning voor de korte termijn. Dit komt omdat er geen specifieke methode is om de lengte van de komende CPU-burst te voorspellen.
- Dit algoritme kan zeer lange doorlooptijden of hongersnood veroorzaken.
- Vereist kennis van hoe lang een proces of taak zal duren.
- Dit leidt tot onderbenutting die de gemiddelde doorlooptijd niet verkort.
- Het is moeilijk om de lengte van het komende CPU-verzoek te kennen.
- De verstreken tijd moet worden geregistreerd, wat extra belasting voor de processor met zich meebrengt.
