Round Robin Scheduling Algorithm with Example

In deze besturingssysteem tutorial, zul je leren:

• Wat is Round-Robin Scheduling?
• Kenmerken van Round-Robin Scheduling
• Voorbeeld van Round-robin Scheduling
• Voordeel van Round-robin Scheduling
• Nadelen van Round-robin Scheduling
• Worst Case Latency

Kenmerken van Round-Robin Scheduling

Hier zijn de belangrijke kenmerken van Round-Robin Scheduling:

• Round robin is een preventief algoritme
• De CPU wordt verschoven naar het volgende proces na vaste intervaltijd, die tijdkwantum/tijdsplit wordt genoemd.
• Het proces dat wordt gepreempt wordt toegevoegd aan het einde van de wachtrij.
• Round robin is een hybride model dat klok-gedreven is
• Time slice moet minimaal zijn, die wordt toegewezen voor een specifieke taak die moet worden verwerkt. Het kan echter OS tot OS verschillen.
• Het is een real-time algoritme dat op de gebeurtenis binnen een specifieke tijdslimiet reageert.
• Round robin is een van de oudste, eerlijkste, en gemakkelijkste algoritme.
• Wijd gebruikte planningsmethode in traditionele OS.

Voorbeeld van Round-robin Scheduling

Beschouw de volgende drie processen

Process Queue	Burst time
P1	4
P2	3
P3	5

Step 1) De uitvoering begint met proces P1, dat burst-tijd 4 heeft. Hier voert elk proces 2 seconden uit. P2 en P3 staan nog in de wachtrij.

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

Stap 3) Op tijd=4 wordt P2 gepreempt en aan het eind van de wachtrij toegevoegd. P3 begint met uitvoeren.

Step 4) Op tijdstip=6 , wordt P3 gepreempt en aan het einde van de wachtrij toegevoegd. P1 begint met uitvoeren.

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

Step 6) P2 heeft een burst-tijd van 3. Het heeft al 2 intervallen uitgevoerd. Op tijd=9, voltooit P2 de uitvoering. Dan begint P3 met de uitvoering tot hij voltooid is.

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

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

Voordeel van Round-robin scheduling

Hier volgen de voordelen van Round-robin scheduling methode:

• Het wordt niet geconfronteerd met de problemen van verhongering of konvooi-effect.
• Alle taken krijgen een eerlijke toewijzing van CPU.
• Het behandelt alle processen zonder enige prioriteit
• Als je het totale aantal processen op de run wachtrij weet, dan kun je ook uitgaan van de worst-case responstijd voor hetzelfde proces.
• Deze scheduling methode is niet afhankelijk van burst-tijd. Daarom is ze gemakkelijk op het systeem te implementeren.
• Als een proces eenmaal voor een bepaalde tijd is uitgevoerd, wordt het proces gepreempt, en een ander proces wordt voor die bepaalde tijd uitgevoerd.
• Het OS kan de Context switching methode gebruiken om toestanden van gepreempt processen op te slaan.
• Het geeft de beste prestaties in termen van gemiddelde responstijd.

Nadelen van Round-robin scheduling

Hierna volgen de nadelen van het gebruik van Round-robin scheduling:

• Als de slicing tijd van het OS laag is, zal de processor output verminderen.
• Deze methode besteedt meer tijd aan context switching
• De prestaties zijn sterk afhankelijk van de hoeveelheid tijd.
• Prioriteiten kunnen niet worden ingesteld voor de processen.
• Round-robin scheduling geeft geen speciale prioriteit aan belangrijkere taken.
• Vermindert begrip
• Lager tijdkwantum resulteert in hogere context switching overhead in het systeem.
• Het vinden van een juist tijdkwantum is een vrij moeilijke taak in dit systeem.

Worst Case Latency

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

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

Formule:

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

Samenvatting:

• De naam van dit algoritme komt van het round-robin principe, waarbij iedereen om de beurt een gelijk deel van iets krijgt.
• Round robin is een van de oudste, eerlijkste en eenvoudigste algoritmen en veelgebruikte scheduling methoden in traditionele OS.
• Round robin is een pre-emptive algoritme
• Het grootste voordeel van de round-robin scheduling methode is dat Als je het totale aantal processen op de run queue weet, dan kun je ook uitgaan van de worst-case responstijd voor datzelfde proces.
• Deze methode besteedt meer tijd aan context switching
• Worst-case latency is een term die wordt gebruikt voor de maximale tijd die nodig is voor de uitvoering van alle taken.