Round Robin Schemaläggning Algoritm med exempel

Vad är Round-Robin-schemaläggning?

Namnet på denna algoritm kommer från round-robin-principen, där varje person får en lika stor del av något i tur och ordning. Det är den äldsta, enklaste schemaläggningsalgoritmen, som mestadels används för multitasking.

I Round-robin-schemaläggning körs varje färdig uppgift tur för tur i en cyklisk kö under en begränsad tidsperiod. Denna algoritm erbjuder också svältfri exekvering av processer.

Kännetecken för Round-Robin-schemaläggning

Här är de viktiga egenskaperna hos Round-Robin Scheduling:

• Round robin är en förebyggande algoritm.
• CPU:n skiftas till nästa process efter ett fast tidsintervall, vilket kallas tidskvantum/tidsskiva.
• Processen som förebyggs läggs till i slutet av kön.
• Round robin är en hybridmodell som är klockdriven.
• Tidsintervallet bör vara minimalt och tilldelas en specifik uppgift som behöver bearbetas. Det kan dock variera från operativsystem till operativsystem.
• Det är en realtidsalgoritm som reagerar på händelser inom en viss tidsgräns.
• Round robin är en av de äldsta, rättvisaste och enklaste algoritmerna.
• Det är en vanligt förekommande schemaläggningsmetod i traditionella operativsystem.

Exempel på Round-robin-schemaläggning

Betrakta följande tre processer:

Steg 1) Exekveringen börjar med process P1, som har bursttid 4. Här körs varje process i 2 sekunder. P2 och P3 står fortfarande i väntekön.

Steg 2) Vid tidpunkten 2 läggs P1 till i slutet av kön och P2 börjar köras.

Steg 3) Vid tidpunkten 4 preemptas P2 och läggs till i slutet av kön. P3 börjar exekveras.

Steg 4) Vid tidpunkten 6 preemptas P3 och läggs till i slutet av kön. P1 börjar exekveras.

Steg 5) Vid tidpunkten 8 har P1 en bursttid på 4. Den har slutfört exekveringen. P2 startar exekveringen.

Steg 6) P2 har en bursttid på 3. Den har redan exekverats i 2 intervaller. Vid tidpunkten 9 slutför P2 exekveringen. Sedan börjar P3 exekveringen tills den är klar.

Steg 7) Låt oss beräkna den genomsnittliga väntetiden för exemplet ovan.

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

Fördelar med Round-robin-schemaläggning

Här är fördelarna/nyttorna med Round-robin-schemaläggningsmetoden:

• Den står inte inför problemen med svält eller konvojeffekt.
• Alla jobb får en rättvis fördelning av CPU.
• Den hanterar alla processer utan prioritering.
• Om du vet det totala antalet processer i körkön kan du också anta den värsta svarstiden för samma process.
• Denna schemaläggningsmetod är inte beroende av bursttid. Det är därför den är lätt att implementera i systemet.
• När väl en process exekveras för en specifik uppsättning av perioden, är processen förebyggd, och en annan process körs för den givna tidsperioden.
• Tillåter operativsystemet att använda kontextväxlingsmetoden för att spara tillstånd för förberedda processer.
• Det ger den bästa prestandan när det gäller genomsnittlig svarstid.

Nackdelar med Round-robin Scheduling

Här är nackdelarna/nackdelarna med att använda Round-robin-schemaläggning:

• Om operativsystemets slicingtid är låg kommer processorns utdata att minska.
• Den här metoden lägger mer tid på kontextväxling.
• Dess prestanda beror mycket på tidskvantum.
• Det går inte att prioritera processerna.
• Round-robin-schemaläggning prioriterar inte viktigare uppgifter särskilt.
• Det minskar förståelsen.
• En lägre tidskvantitet resulterar i högre kontextväxlingsoverhead i systemet.
• Att hitta ett korrekt tidskvantum är en ganska svår uppgift i detta system.

Värsta fall latens

Denna term används för den maximala tiden det tar för att utföra alla uppgifter.

• dt = Anger detekteringstid när en uppgift tas med i listan
• st = Anger växlingstid från en uppgift till en annan
• et = Anger uppgiftens körningstid

Formel:

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

Vanliga frågor