Round Robin-planlægningsalgoritme med eksempel

Hvad er Round-Robin-planlægning?

Navnet på denne algoritme kommer fra round-robin-princippet, hvor hver person får en lige del af noget på skift. Det er den ældste, enkleste planlægningsalgoritme, som mest bruges til multitasking.

I Round-robin-planlægning kører hver færdig opgave kun tur for tur i en cyklisk kø i et begrænset tidsinterval. Denne algoritme tilbyder også udførelse af processer uden behov for sult.

Karakteristika for Round-Robin-planlægning

Her er de vigtige egenskaber ved Round-Robin-planlægning:

• Round robin er en præemptiv algoritme.
• CPU'en skifter til den næste proces efter et fast tidsinterval, som kaldes tidskvante/tidsskive.
• Processen, der er foregrebet, tilføjes til slutningen af ​​køen.
• Round robin er en hybridmodel, der er urdrevet.
• Tidsintervallet skal være minimum og tildeles til en specifik opgave, der skal behandles. Det kan dog variere fra operativsystem til operativsystem.
• Det er en realtidsalgoritme, der reagerer på hændelser inden for en bestemt tidsfrist.
• Round robin er en af ​​de ældste, mest retfærdige og nemmeste algoritmer.
• Det er en udbredt planlægningsmetode i traditionelle operativsystemer.

Eksempel på Round-robin-planlægning

Overvej følgende tre processer:

Trin 1) Udførelsen begynder med proces P1, som har burst tid 4. Her udføres hver proces i 2 sekunder. P2 og P3 står stadig i ventekøen.

Trin 2) Ved tidspunktet = 2 tilføjes P1 til slutningen af ​​køen, og P2 begynder at udføre.

Trin 3) Ved tidspunktet 4 er P2 forudindtaget og tilføjet i slutningen af ​​køen. P3 begynder at udføre.

Trin 4) Ved tidspunktet 6 er P3 forudindtaget og tilføjet i slutningen af ​​køen. P1 begynder at udføre.

Trin 5) Ved tidspunktet 8 har P1 en burst-tid på 4. Den har fuldført udførelsen. P2 starter udførelsen.

Trin 6) P2 har en burst-tid på 3. Den har allerede udført i 2 intervaller. Ved tidspunktet = 9 fuldfører P2 udførelsen. Derefter starter P3 udførelsen, indtil den er færdig.

Trin 7) Lad os beregne den gennemsnitlige ventetid for ovenstående eksempel.

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

Fordele ved Round-robin-planlægning

Her er fordelene ved Round-robin-planlægningsmetoden:

• Den står ikke over for problemerne med sult eller konvojeffekt.
• Alle jobs får en rimelig fordeling af CPU.
• Den håndterer alle processer uden prioritering.
• Hvis du kender det samlede antal processer i kørselskøen, så kan du også antage den worst-case responstid for den samme proces.
• Denne planlægningsmetode afhænger ikke af burst-tid. Derfor er den let at implementere i systemet.
• Når først en proces er eksekveret i et bestemt sæt af perioden, er processen foregrebet, og en anden proces udføres for den givne tidsperiode.
• Tillader operativsystemet at bruge kontekstskiftningsmetoden til at gemme tilstande for forudindtagede processer.
• Det giver den bedste ydeevne i forhold til gennemsnitlig responstid.

Ulemper ved Round-robin-planlægning

Her er ulemperne/ulemperne ved at bruge Round-robin-planlægning:

• Hvis operativsystemets slicing-tid er lav, vil processorens output blive reduceret.
• Denne metode bruger mere tid på kontekstskift.
• Dens ydeevne afhænger stærkt af tidskvante.
• Der kan ikke prioriteres for processerne.
• Round-robin-planlægning prioriterer ikke vigtigere opgaver særligt.
• Det mindsker forståelsen.
• Et lavere tidskvante resulterer i højere kontekstskiftningsoverhead i systemet.
• Det er en ret vanskelig opgave at finde et korrekt tidskvante i dette system.

Worst Case Latency

Dette udtryk bruges for den maksimale tid, det tager at udføre alle opgaverne.

• dt = Angiver detektionstidspunktet, når en opgave bringes på listen
• st = Angiver skiftetid fra én opgave til en anden
• et = Angiver opgavens udførelsestid

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

Ofte Stillede Spørgsmål