Round Robin-planleggingsalgoritme med eksempel

Hva er Round-Robin-planlegging?

Navnet på denne algoritmen kommer fra round-robin-prinsippet, der hver person får en lik del av noe etter tur. Det er den eldste, enkleste planleggingsalgoritmen, som mest brukes til multitasking.

I Round-robin-planlegging kjører hver klare oppgave tur for tur i en syklisk kø i et begrenset tidsintervall. Denne algoritmen tilbyr også utførelse av prosesser uten behov for sult.

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 et fast tidsintervall, som kalles tidskvante/tidsskive.
• Prosessen som er forhåndsaktivert, legges til på slutten av køen.
• Round robin er en hybridmodell som er klokkedrevet.
• Tidsintervallet bør være minimum, og er tildelt for en spesifikk oppgave som må behandles. Det kan imidlertid variere fra operativsystem til operativsystem.
• Det er en sanntidsalgoritme som reagerer på hendelser innen en bestemt tidsfrist.
• Round robin er en av de eldste, mest rettferdige og enkleste algoritmene.
• Det er en mye brukt planleggingsmetode i tradisjonelle operativsystemer.

Eksempel på Round-robin-planlegging

Tenk på følgende tre prosesser:

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 tid = 2 legges P1 til på slutten av køen, og P2 begynner å kjøre.

Trinn 3) Ved tid = 4 blir P2 forhåndsutnyttet og lagt til på slutten av køen. P3 begynner å kjøre.

Trinn 4) Ved tid = 6 blir P3 forhåndsutnyttet og lagt til på slutten av køen. P1 begynner å kjøre.

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

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

Trinn 7) La oss beregne den gjennomsnittlige ventetiden for eksemplet ovenfor.

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

Fordeler med Round-robin-planlegging

Her er fordelene med Round-robin-planleggingsmetoden:

• Den står ikke overfor problemene med sult eller konvoieffekt.
• Alle jobbene får en rettferdig fordeling av CPU.
• Den håndterer alle prosesser uten prioritering.
• 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 burst-tid. Derfor er den enkel å implementere i 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 operativsystemet bruke kontekstbyttemetoden for å lagre tilstander til forhåndsbestemte prosesser.
• Det gir best ytelse når det gjelder gjennomsnittlig responstid.

Ulemper med Round-robin-planlegging

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

• Hvis slicing-tiden til operativsystemet er lav, vil prosessorutgangen reduseres.
• Denne metoden bruker mer tid på kontekstbytte.
• Ytelsen avhenger sterkt av tidskvante.
• Det kan ikke prioriteres for prosessene.
• Round-robin-planlegging prioriterer ikke viktigere oppgaver spesielt.
• Det reduserer forståelsen.
• Et lavere tidskvante resulterer i høyere kontekstbyttekostnader 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 = Betegner byttetid fra én oppgave til en annen
• et = Angir utførelsestid for oppgaven

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

Spørsmål og svar