Round Robin planningsalgoritme met voorbeeld

Wat is Round-Robin-planning?

De naam van dit algoritme komt van het round-robin-principe, waarbij elke persoon om de beurt een gelijk deel van iets krijgt. Het is het oudste, eenvoudigste planningsalgoritme, dat vooral wordt gebruikt voor multitasking.

Bij Round-Robin-planning wordt elke voltooide taak beurt voor beurt uitgevoerd in een cyclische wachtrij gedurende een beperkte tijdsperiode. Dit algoritme biedt ook een hongervrije uitvoering van processen.

Kenmerken van Round-Robin-planning

Dit zijn de belangrijke kenmerken van Round-Robin Scheduling:

  • Round Robin is een preventief algoritme
  • De CPU is shiftnaar het volgende proces na een vaste intervaltijd, wat tijdkwantum/tijdplak wordt genoemd.
  • Het proces dat wordt onderdrukt, wordt aan het einde van de wachtrij toegevoegd.
  • Round Robin is een hybride model dat klokgestuurd is
  • Het tijdsdeel moet minimaal zijn, wat wordt toegewezen aan een specifieke taak die moet worden verwerkt. Het kan echter van besturingssysteem tot besturingssysteem verschillen.
  • Het is een real-time algoritme dat binnen een specifieke tijdslimiet op de gebeurtenis reageert.
  • Round Robin is een van de oudste, eerlijkste en gemakkelijkste algoritmen.
  • Veelgebruikte planningsmethode in traditionele besturingssystemen.

Voorbeeld van Round Robin-planning

Denk eens aan dit vervolgwing drie processen

Wachtrij verwerken Burst-tijd
P1 4
P2 3
P3 5

Round-robin-planning

Stap 1) De uitvoering begint met proces P1, dat burst-tijd 4 heeft. Hier wordt elk proces gedurende 2 seconden uitgevoerd. P2 en P3 staan ​​nog in de wachtrij.

Round-robin-planning

Stap 2) Op tijdstip =2 wordt P1 toegevoegd aan het einde van de wachtrij en begint P2 met uitvoeren

Round-robin-planning


Stap 3) Op tijdstip=4 wordt P2 voorrang gegeven en aan het einde van de wachtrij toegevoegd. P3 begint met uitvoeren.

Round-robin-planning

Stap 4) Op tijdstip=6 wordt P3 voorrang gegeven en aan het einde van de wachtrij toegevoegd. P1 begint met uitvoeren.

Round-robin-planning

Stap 5) Op tijdstip=8 heeft P1 een burst-tijd van 4. De uitvoering is voltooid. P2 start de uitvoering

Round-robin-planning

Stap 6) P2 heeft een burst-tijd van 3. Het is al gedurende 2 intervallen uitgevoerd. Op tijdstip=9 voltooit P2 de uitvoering. Vervolgens begint P3 met de uitvoering totdat deze is voltooid.

Round-robin-planning

Stap 7) Laten we de gemiddelde wachttijd voor bovenstaand voorbeeld berekenen.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

Voordeel van Round Robin-planning

Hier volgen de voor- en nadelen van de Round-robin-planningsmethode:

  • Het land wordt niet geconfronteerd met de problemen van hongersnood of konvooi-effect.
  • Alle banen krijgen een eerlijke toewijzing van CPU.
  • Het behandelt alle processen zonder enige prioriteit
  • Als u het totale aantal processen in de wachtrij kent, kunt u ook uitgaan van de slechtste responstijd voor hetzelfde proces.
  • Deze planningsmethode is niet afhankelijk van de burst-tijd. Daarom is het eenvoudig te implementeren op het systeem.
  • Zodra een proces voor een specifieke set van de periode is uitgevoerd, wordt het proces voorrang gegeven en wordt een ander proces gedurende die bepaalde periode uitgevoerd.
  • Hiermee kan het besturingssysteem de contextomschakelingsmethode gebruiken om de status van gepreëmpteerde processen op te slaan.
  • Het geeft de beste prestaties in termen van gemiddelde responstijd.

Nadelen van Round Robin-planning

Hier volgen de nadelen/nadelen van het gebruik van Round-robin-planning:

  • Als de snijtijd van het besturingssysteem laag is, wordt de processoruitvoer verminderd.
  • Deze methode besteedt meer tijd aan het wisselen van context
  • De prestaties ervan zijn sterk afhankelijk van het tijdkwantum.
  • Er kunnen geen prioriteiten worden gesteld aan de processen.
  • Round-robin-planning geeft geen speciale prioriteit aan belangrijkere taken.
  • Vermindert het begrip
  • Een lager tijdkwantum resulteert in een hogere contextomschakelingsoverhead in het systeem.
  • Het vinden van een correct tijdkwantum is een behoorlijk moeilijke taak in dit systeem.

Latentie in het slechtste geval

Deze term wordt gebruikt voor de maximale tijd die nodig is voor het uitvoeren van alle taken.

  • dt = Geeft detectietijd aan wanneer een taak in de lijst wordt geplaatst
  • st = Geeft de schakeltijd van de ene taak naar de andere aan
  • et = Geeft de uitvoeringstijd van de taak aan

Formule:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR	
t,SR = sum of all execution times

Samengevat

  • De naam van dit algoritme komt van het round-robin-principe, waarbij elke persoon om de beurt een gelijk deel van iets krijgt.
  • Round Robin is een van de oudste, eerlijkste en gemakkelijkste algorithms en veelgebruikte planningsmethoden in traditioneel OS.
  • Round Robin is een preventief algoritme
  • Het grootste voordeel van de round-robin-planningsmethode is dat als u het totale aantal processen in de wachtrij kent, u ook kunt uitgaan van de responstijd in het slechtste geval voor hetzelfde proces.
  • Deze methode besteedt meer tijd aan het wisselen van context
  • Worst-case latentie is een term die wordt gebruikt voor de maximale tijd die nodig is voor de uitvoering van alle taken.