Round-robin (informatikk)

Turnstilen er en algoritme for planlegging som er vanlig i operativsystemer, og er egnet for systemer som jobber i delt tid.

En liten tidsenhet, kalt kvantum av tid, er definert. Køen administreres som en sirkulær kø. Planleggeren går gjennom denne køen og tildeler prosessortid til hver av prosessene for et tidsintervall av størrelsen på ett kvantum på det meste.

Utførelsen av round-robin avhenger sterkt av valget av basekvantum.

Turnstile system

Turnstile- systemet henter sitt navn fra lekeparken for barn. Bildet for algoritmen er at hver prosess sitter på turnstilen, og hver i sin tur bare går forbi prosessoren i en begrenset periode.

Formelt har vi:

en ny prosess legges til på slutten av listen (for ikke å duplisere allerede eksisterende prosesser, noe som kan skape en mulighet for sult );
bruken av prosessoren av prosessoren kan ikke overstige et visst tidsmengde som forsikrer oss igjen om at det ikke vil være sult;
maksimal ventetid er gitt ved multiplikasjonen av antall kjørende prosesser multiplisert med kvantetiden gitt til hver prosess (NB: Hver prosess har samme tidsmengde som de andre);
en prosess som nettopp er ferdig med å bruke prosessoren (forløpt kvante) er plassert på slutten av listen;
en prosess som har fullført arbeidet, blir fjernet fra listen, derfor reduseres ventetiden for andre prosesser.

Tar vi eksemplet som er foreslått i den engelske versjonen av leksikonet: 6 oppgaver med forskjellige begynnelser og utførelsestider og en tidsmengde fast på 1 ms, finner du overfor behandlingsdiagrammet til en forebyggende planlegger ved hjelp av turneringsmetoden. Således vil en prosess i et gitt kvantum av tid vente hvor det er antall venteprosesser, for å få tilgang til prosessoren. $q$ $n \ ganger q$ $ikke$

Når prosessoren velger en ny prosess for å behandle og laster den, tar det tid. Vi må derfor finne den rette balansen mellom:

En kort kvante: regelmessige prosessendringer derfor tap av effektivitet ( overhead ) fordi kontekstbytte vil forekomme oftere.
En lang kvante: responstiden vil bli forlenget og på grensen (uendelig kvante) blir den en FIFO ( først inn først ut ) algoritme først kommer først ut.

Generelt er tidskvanten definert i henhold til prosessens statistiske oppførsel. Ideen er å sette et kvantum av tid som får prosesser til å fullføre 80% av CPU-bruken før slutten av kvantetiden. Så det er lite tap av effektivitet.

Problematisk eksempel

Hvis kvanten er 4 ms og det tar 1 ms å endre prosessen, mister vi derfor 1 / (4 + 1) = 20% av endringstiden (eksempel på et kvante for kort sammenlignet med lastetiden).

Hvis kvanten er 4 ms og prosessen tar 2 ms å utføre, mister vi 2 / (4 + 2) = 33% av tiden (eksempel på et kvante for lenge sammenlignet med utførelsestiden).

Nettverk

En turné ( round robin på engelsk) er en belastningsfordeling ( lastbalansering ) som er likeverdig mellom servere i en datagård ( klynge ). Hver server behandler det samme antall forespørsler. Dette krever en homogen serverfarm i prosesseringskapasitet. Denne lastbalanseringen kan utføres av DNS-serveren ( Domain Name System ) som knytter flere IP-adresser til et domenenavn . Dette kalles DNS Round Robin .