Round Robin planningsalgoritme met voorbeeld

Door: Nathaniel Brooks Nathaniel Brooks
Hours Bijgewerkt

⚡ Slimme samenvatting

Round-Robin Scheduling is het oudste en eenvoudigste preemptieve CPU-algoritme, waarbij elk gereed proces een vaste tijdsduur krijgt in een cyclische wachtrij. Dit zorgt voor een eerlijke uitvoering zonder uithongering bij multitasking.

  • 🔄 Definitie: Elke gereedstaande taak wordt om de beurt uitgevoerd gedurende een vast tijdsinterval.
  • ​ Tijdkwantum: De CPU schakelt na een vast interval, het tijdskwantum, tussen processen.
  • ​ Eerlijkheid: Elk proces krijgt evenveel CPU-tijd, waardoor uithongering wordt voorkomen.
  • 🧮 Preventief: Een onderbroken proces wordt naar het einde van de wachtrij verplaatst.
  • ✅ Voordelen: Eerlijke toewijzing, geen konvooi-effect, voorspelbare reactietijd.
  • ⚠️ Nadelen: De prestaties zijn afhankelijk van het tijdskwantum en er komt overhead bij als gevolg van contextwisselingen.
Meer informatie

Round Robin-planningsalgoritme

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 gereedstaande taak om de beurt uitgevoerd in een cyclische wachtrij, gedurende een beperkte tijdsperiode. Dit algoritme biedt ook de mogelijkheid om processen niet uit te hongeren.

Kenmerken van Round-Robin-planning

Dit zijn de belangrijke kenmerken van Round-Robin Scheduling:

  • Round robin is een preemptief algoritme.
  • De CPU schakelt na een vast tijdsinterval, dat een tijdquantum of tijdssegment wordt genoemd, over naar het volgende proces.
  • Het proces dat wordt onderdrukt, wordt aan het einde van de wachtrij toegevoegd.
  • Round robin is een hybride model dat klokgestuurd is.
  • De tijdsduur moet minimaal zijn en wordt toegewezen aan een specifieke taak die verwerkt moet worden. Deze kan echter per besturingssysteem verschillen.
  • Het is een realtime-algoritme dat binnen een bepaalde tijdslimiet op de gebeurtenis reageert.
  • Round robin is een van de oudste, eerlijkste en eenvoudigste algoritmes.
  • Het is een veelgebruikte planningsmethode in traditionele besturingssystemen.

Voorbeeld van Round Robin-planning

Beschouw de volgende 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 t = 2 wordt P1 aan het einde van de wachtrij toegevoegd en begint P2 met de uitvoering.

Round-robin-planning

GERELATEERDE ARTIKELEN

Stap 3) Op tijdstip t = 4 wordt P2 onderbroken en aan het einde van de wachtrij toegevoegd. P3 begint met de uitvoering.

Round-robin-planning

Stap 4) Op tijdstip t = 6 wordt P3 onderbroken en aan het einde van de wachtrij toegevoegd. P1 begint met de uitvoering.

Round-robin-planning

Stap 5) Op tijdstip t = 8 heeft P1 een bursttijd van 4. De uitvoering is voltooid. P2 begint met de uitvoering.

Round-robin-planning

Stap 6) P2 heeft een bursttijd van 3. Het heeft al 2 intervallen uitgevoerd. Op tijdstip 9 is de uitvoering van P2 voltooid. Daarna begint P3 met de uitvoering totdat deze is voltooid.

Round-robin-planning

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

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

Voordelen van round-robin planning

Hieronder volgen de voordelen van de round-robin-planningsmethode:

  • Het kent geen problemen zoals hongersnood of het effect van konvooien.
  • Alle banen krijgen een eerlijke toewijzing van CPU.
  • Het behandelt alle processen zonder 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 bursttijd. Daarom is deze eenvoudig te implementeren in 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 contextwisselmethode gebruiken om de status van onderbroken processen op te slaan.
  • Het geeft de beste prestaties in termen van gemiddelde responstijd.

Nadelen van Round Robin-planning

Hieronder volgen de nadelen van het gebruik van round-robin-planning:

  • Als de slice-tijd van het besturingssysteem laag is, zal de processoroutput lager zijn.
  • Deze methode besteedt meer tijd aan het wisselen tussen contexten.
  • De prestaties ervan zijn sterk afhankelijk van het tijdkwantum.
  • Er kunnen geen prioriteiten worden gesteld aan de processen.
  • Bij round-robin-planning worden belangrijkere taken niet extra prioriteit gegeven.
  • Het vermindert het begrip.
  • Een lagere tijdskwantumwaarde resulteert in hogere overheadkosten voor contextwisseling in het systeem.
  • Het vinden van het juiste tijdquantum is in dit systeem een ​​behoorlijk lastige opgave.

Latentie in het slechtste geval

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

  • dt = Geeft de detectietijd aan waarop een taak aan de lijst wordt toegevoegd.
  • st = Geeft de overschakeltijd 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
tISR = sum of all execution times

Veelgestelde vragen

Een tijdquantum, of tijdsslot, is de vaste CPU-tijd die elk proces gebruikt voordat het wordt onderbroken. Een te groot tijdquantum gedraagt ​​zich als FCFS (First Come, First Served); een te klein tijdquantum zorgt voor aanzienlijke overhead door contextwisselingen.

FCFS voert elk proces in volgorde van binnenkomst volledig uit en is niet-preëmptief. Round Robin is preëmptief: het geeft elk proces een vaste tijdsslot en doorloopt de wachtrij in een cyclus, waardoor de responstijd verbetert en lange taken andere taken niet blokkeren.

Omdat elk proces in een cyclische wachtrij wordt geplaatst en om de beurt een vast tijdslot krijgt toegewezen. Geen enkel proces wordt overgeslagen of voor onbepaalde tijd uitgesteld, waardoor elk proces uiteindelijk CPU-tijd krijgt, ongeacht de lengte of de volgorde van binnenkomst.

AI en machine learning kunnen procesgedrag en werkbelastingspatronen voorspellen om planningsbeslissingen in realtime te optimaliseren. In plaats van een vast beleid kan het systeem prioriteiten en tijdvakken dynamisch aanpassen, waardoor het CPU-gebruik, de doorvoer en de responstijd verbeteren.

Ja. AI-modellen kunnen eerdere piektijden en systeembelasting analyseren om een ​​optimale tijdsduur voor te stellen en deze aan te passen aan veranderende omstandigheden. Dit zorgt voor een betere balans tussen de overhead van contextwisselingen en de reactietijd dan een enkele vaste waarde.

Vat dit bericht samen met: