Kortste baan eerst (SJF): preventief, niet-preventief voorbeeld

Wat is Shortest Job First Scheduling?

Kortste baan eerst (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 Shortest Job First.

Er zijn in principe twee soorten SJF-methoden:

  • Niet-preventieve SJF
  • Preventieve SJF

In deze zelfstudie over het besturingssysteem leert u:

Kenmerken van SJF-planning

  • Het is gekoppeld aan elke taak als een tijdseenheid die moet worden voltooid.
  • Deze algoritmemethode is handig voor batchverwerking, waarbij wachten op het voltooien van taken niet essentieel is.
  • Het kan de procesdoorvoer verbeteren door ervoor te zorgen dat kortere opdrachten eerst worden uitgevoerd, en dus mogelijk een korte doorlooptijd hebben.
  • Het verbetert de joboutput 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 aan het proces, houdt het proces deze vast totdat deze een wachtstatus bereikt of wordt beëindigd.

Beschouw de volgende vijf processen die elk hun eigen unieke burst-tijd en aankomsttijd hebben.

Wachtrij verwerkenBurst-tijdAankomsttijd
P162
P225
P381
P430
P544

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 tijdstip =2 arriveert proces P1 en wordt toegevoegd aan de wachtrij. P4 zal doorgaan met de uitvoering.

Stap 3) Op tijd = 3 zal proces P4 zijn uitvoering voltooien. 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 tijdstip = 4 arriveert proces P5 en wordt toegevoegd aan de wachtrij. P1 gaat door met de uitvoering.

Stap 5) Op tijdstip = 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 voltooien. De burst-tijd van P3, P5 en P2 wordt vergeleken. Proces P2 wordt uitgevoerd omdat zijn burst-tijd het laagst 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 voltooien. De burst-tijd van P3 en P5 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd ervan lager is.

Stap 9) Op tijd = 15 zal proces P5 zijn uitvoering voltooien.

Stap 10) Op tijd = 23 zal proces P3 zijn uitvoering voltooien.

Stap 11) Laten we de gemiddelde wachttijd voor het bovenstaande voorbeeld berekenen. |__+_| |__+_|

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 uitgesloten van uitvoering en krijgt de kortere taak een CPU-cyclus toegewezen.

Overweeg de volgende vijf processen:

Wachtrij verwerkenBurst-tijdAankomsttijd
P162
P225
P381
P430
P544

Stap 0) Op tijd=0 arriveert P4 en begint de uitvoering.

Wachtrij verwerkenBurst-tijdAankomsttijd
P162
P225
P381
P430
P544

Stap 1) Op tijd = 1 arriveert proces P3. Maar P4 heeft een kortere burst-tijd. Het zal doorgaan met de uitvoering.

Stap 2) Op tijdstip = 2 arriveert proces P1 met bursttijd = 6. De bursttijd is langer dan die van P4. Daarom zal P4 doorgaan met de uitvoering.

Stap 3) Op tijd = 3 zal proces P4 zijn uitvoering voltooien. De burst-tijd van P3 en P1 wordt vergeleken. Proces P1 wordt uitgevoerd omdat zijn burst-tijd lager 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 zijn burst-tijd het laagst is. Proces P1 wordt ontkracht.

Wachtrij verwerkenBurst-tijdAankomsttijd
P15 van de 6 is overgebleven2
P225
P381
P430
P544

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 ontkracht.

Wachtrij verwerkenBurst-tijdAankomsttijd
P15 van de 6 is overgebleven2
P225
P381
P430
P53 van de 4 is overgebleven4

Stap 6) Op tijdstip =6 wordt P2 uitgevoerd.

Stap 7) Op tijdstip =7 voltooit P2 zijn uitvoering. De burst-tijd van P1, P3 en P5 wordt vergeleken. Proces P5 wordt uitgevoerd omdat de burst-tijd korter is.

Wachtrij verwerkenBurst-tijdAankomsttijd
P15 van de 6 is overgebleven2
P225
P381
P430
P53 van de 4 is overgebleven4

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 tijdstip =15 voltooit P1 zijn uitvoering. P3 is het enige proces dat nog over is. Het zal beginnen met de uitvoering.

Stap 10) Op tijdstip =23 voltooit P3 de uitvoering ervan.

Stap 11) Laten we de gemiddelde wachttijd voor het bovenstaande voorbeeld berekenen. |__+_| |__+_|

Voordelen van SJF

Hier zijn de voordelen / voordelen van het gebruik van de SJF-methode:

  • SJF wordt vaak gebruikt voor planning op lange termijn.
  • Het vermindert de gemiddelde wachttijd via 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 bursttijd worden verkregen uit de functiebeschrijving.
  • Voor kortetermijnplanning moeten we de waarde van de volgende burst-tijd voorspellen.
  • Waarschijnlijk optimaal gezien de gemiddelde doorlooptijd.

Nadelen/nadelen van SJF

Hier zijn enkele nadelen/nadelen van het SJF-algoritme:

  • De voltooiingstijd van de taak moet eerder bekend zijn, maar is moeilijk te voorspellen.
  • Het wordt vaak gebruikt in een batchsysteem voor planning op lange termijn.
  • 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 aanstaande CPU-burst te voorspellen.
  • Dit algoritme kan zeer lange doorlooptijden of hongersnood veroorzaken.
  • Vereist kennis van hoe lang een proces of taak zal duren.
  • Het leidt tot hongersnood die de gemiddelde doorlooptijd niet verkort.
  • Het is moeilijk om de lengte van het aanstaande CPU-verzoek te kennen.
  • Verstreken tijd moet worden geregistreerd, dat resulteert in meer overhead op de processor.

Samenvatting

  • SJF is een algoritme waarbij het proces met de kleinste uitvoeringstijd wordt gekozen voor de volgende uitvoering.
  • SJF Scheduling is gekoppeld aan elke taak als een tijdseenheid die moet worden voltooid.
  • Deze algoritmemethode is handig voor batchverwerking, waarbij wachten op het voltooien van taken niet essentieel 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 aan het proces, houdt het proces deze vast totdat deze een wachtstatus 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 uitgesloten van uitvoering, en wordt de kortere taak als eerste uitgevoerd.
  • SJF wordt vaak gebruikt voor planning op lange termijn.
  • Het vermindert de gemiddelde wachttijd via 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 aanstaande CPU-burst te voorspellen.