Round-robin (tietojenkäsittelytiede)

Kääntöportti on käyttöjärjestelmissä yleinen aikataulutuksen algoritmi , ja se soveltuu järjestelmille, jotka työskentelevät jaetussa ajassa.

Pieni aikayksikkö, jota kutsutaan ajan kvantiksi, on määritelty. Jonoa hallitaan pyöreänä jonona. Ajastin kulkee tämän jonon läpi ja allokoi prosessorin ajan kullekin prosessille enintään yhden kvantin suuruiselle aikavälille.

Round-robin-suorituskyky riippuu voimakkaasti peruskvantin valinnasta.

Kääntöporttijärjestelmä

Portti järjestelmä on saanut nimensä siitä leikkipuistossa lapsille. Algoritmin kuva on, että kukin prosessi istuu kääntöportilla ja jokainen vuorostaan vain kävelee prosessorin ohi rajallisen ajan.

Virallisesti meillä on:

uusi prosessi lisätään luettelon loppuun (jotta ei päällekkäistä jo olemassa olevia prosesseja, mikä voisi luoda mahdollisuuden nälkään );
prosessorin käyttö prosessorissa ei voi ylittää tiettyä aikamäärää, mikä vakuuttaa meille jälleen, että nälkää ei tule;
suurin odotusaika saadaan kertomalla käynnissä olevien prosessien määrä kerrottuna kullekin prosessille myönnetyllä ajan kvantilla (Huom. Jokaisella prosessilla on sama ajan kvantti kuin muilla);
prosessori (juuri kulunut kvantti) on juuri päättynyt prosessi sijoitetaan luettelon loppuun;
työnsä suorittanut prosessi poistetaan luettelosta, minkä vuoksi muiden prosessien odotusaika lyhenee.

Ottaen tietosanakirjan englanninkielisessä versiossa ehdotetun esimerkin: 6 tehtävää, joilla on eri alku- ja toteutusajat ja ajan kvantti, joka on vahvistettu 1 ms: ksi, löydät vastakohtana ennaltaehkäisevän ajoittajan prosessikaavion, joka käyttää kiristysmenetelmää. Siten tietyn kvantti aikaa , prosessi odottaa korkeintaan jossa on määrä odottamassa prosesseista, käyttää prosessorin. $q$ $n \ kertaa q$ $ei$

Kun prosessori valitsee uuden prosessin prosessoitavaksi ja lataa sen, se vie aikaa. Siksi meidän on löydettävä oikea tasapaino:

Lyhyt kvantti: säännöllinen prosessimuutos muuttaa tehokkuuden menetystä ( yleiskustannuksia ), koska kontekstivaihto tapahtuu useammin.
Pitkä kvantti: vasteaikaa pidennetään ja rajalla (ääretön kvantti) siitä tulee FIFO- algoritmi ( ensin sisään ensin ulos ).

Yleensä aikakvantti määritetään prosessien tilastollisen käyttäytymisen mukaan. Ajatuksena on asettaa aikakvantti, joka saa prosessit lopettamaan 80% prosessorin käytöstä ennen ajan kvantin loppua. Joten tehokkuuden menetys on vähäinen.

Ongelmallinen esimerkki

Jos kvantti on 4 ms ja prosessin muuttaminen vie 1 ms , menetämme siis 1 / (4 + 1) = 20% muutosajasta (esimerkki kvantista, joka on liian lyhyt verrattuna latausaikaan).

Jos kvantti on 4 ms ja prosessin suorittaminen vie 2 ms , menetämme 2 / (4 + 2) = 33% ajasta (esimerkki kvantista liian pitkä verrattuna suoritusaikaan).

Verkko

Puristusside ( round robin Englanti) on kuorman jakautuminen ( kuormantasaus ) kohtuullinen palvelimien välillä on tietokoneen tilan ( klusteri ). Jokainen palvelin käsittelee saman määrän pyyntöjä. Tämä edellyttää homogeenista palvelintilaa prosessointikapasiteetissa. Tämä kuormantasaus voidaan suorittaa DNS ( Domain Name System ) palvelimen , joka liittää useita IP-osoitteita , joiden verkkotunnus . Tätä kutsutaan DNS Round Robiniksi .