Round Robin-planleggingsalgoritme med eksempel

Kjennetegn ved Round-Robin-planlegging

Her er de viktige egenskapene til Round-Robin-planlegging:

• Round robin er en forebyggende algoritme
• CPU-en flyttes til neste prosess etter fast intervalltid, som kalles tidskvante/tidssnitt.
• Prosessen som er forhåndsaktivert, legges til på slutten av køen.
• Round robin er en hybridmodell som er klokkedrevet
• Tidsstykket skal være minimum, som er tildelt for en spesifikk oppgave som må behandles. Det kan imidlertid variere fra OS til OS.
• Det er en sanntidsalgoritme som reagerer på hendelsen innenfor en bestemt tidsgrense.
• Round robin er en av de eldste, mest rettferdige og enkleste algoritmene.
• Mye brukt planleggingsmetode i tradisjonelle OS.

Eksempel på Round-robin-planlegging

Vurder dette etter tre prosesser

Prosesskø	Sprengtid
P1	4
P2	3
P3	5

Trinn 1) Utførelsen starter med prosess P1, som har bruddtid 4. Her kjøres hver prosess i 2 sekunder. P2 og P3 står fortsatt i ventekø.

Trinn 2) Ved tiden =2 legges P1 til på slutten av køen og P2 begynner å kjøre

Trinn 3) Ved time=4 er P2 forhåndsaktivert og legg til på slutten av køen. P3 begynner å kjøre.

Trinn 4) Ved time=6 er P3 forhåndsaktivert og legg til på slutten av køen. P1 begynner å kjøre.

Trinn 5) Ved tid=8 har P1 en bruddtid på 4. Den har fullført utførelse. P2 starter utførelse

Trinn 6) P2 har en serietid på 3. Den har allerede utført for 2 intervaller. Ved tid=9 fullfører P2 utførelsen. Deretter starter P3 kjøringen til den er fullført.

Trinn 7) La oss beregne gjennomsnittlig ventetid for eksempelet ovenfor.

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

Fordel med Round-robin-planlegging

Her er fordeler/fordeler med Round-robin-planleggingsmetoden:

• Den møter ikke problemene med sult eller konvoieffekt.
• Alle jobbene får en rettferdig fordeling av CPU.
• Den tar for seg alle prosesser uten prioritet
• Hvis du vet det totale antallet prosesser i kjørekøen, kan du også anta den verste responstiden for samme prosess.
• Denne planleggingsmetoden er ikke avhengig av bruddtid. Det er derfor det er enkelt å implementere på systemet.
• Når en prosess er utført for et spesifikt sett av perioden, blir prosessen foreskrevet, og en annen prosess kjøres for den gitte tidsperioden.
• Lar OS bruke kontekstbyttemetoden for å lagre tilstander for forhåndsaktiverte prosesser.
• Det gir best ytelse når det gjelder gjennomsnittlig responstid.

Ulemper med Round-robin-planlegging

Her er ulemper/ulemper ved å bruke Round-robin-planlegging:

• Hvis skjæretiden for OS er lav, vil prosessoreffekten reduseres.
• Denne metoden bruker mer tid på kontekstbytte
• Ytelsen avhenger sterkt av tidskvante.
• Det kan ikke prioriteres for prosessene.
• Round-robin-planlegging gir ikke særlig prioritet til viktigere oppgaver.
• Reduserer forståelsen
• Lavere tidskvante resulterer i høyere kontekstsvitsjeoverhead i systemet.
• Å finne et riktig tidskvante er en ganske vanskelig oppgave i dette systemet.

Worst Case Latency

Dette begrepet brukes for maksimal tid det tar å utføre alle oppgavene.

• dt = Angir deteksjonstid når en oppgave bringes inn i listen
• st = Angir byttetid fra en oppgave til en annen
• et = Angi oppgaveutførelsestid

Formel:

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

Sammendrag

• Navnet på denne algoritmen kommer fra round-robin-prinsippet, der hver person får en lik del av noe etter tur.
• Round robin er en av de eldste, mest rettferdige og enkleste algoritmene og mye brukte planleggingsmetoder i tradisjonelle OS.
• Round robin er en forebyggende algoritme
• Den største fordelen med round-robin-planleggingsmetoden er at hvis du vet det totale antallet prosesser i kjøringskøen, kan du også anta den verste responstiden for samme prosess.
• Denne metoden bruker mer tid på kontekstbytte
• Worst-case latency er et begrep som brukes for maksimal tid det tar å utføre alle oppgavene.