Round Robin -aikataulutusalgoritmi esimerkin kanssa

⚡ Älykäs yhteenveto

Round-Robin Scheduling on vanhin ja yksinkertaisin preemptiivinen CPU-algoritmi, jossa jokainen valmis prosessi suoritetaan kiinteän aikaviipaleen ajan syklisessä jonossa, mikä varmistaa oikeudenmukaisen ja nälkiintymättömän suorituksen moniajoa varten.

🔄 Määritelmä: Jokainen valmis tehtävä suoritetaan vuorotellen kiinteän aikasuunnassa.
⏱️ Aikakvantti: CPU vaihtaa prosesseja tietyn aikavälin, aikakvantin, jälkeen.
🇧🇷 oikeudenmukaisuus: Jokainen prosessi saa yhtä paljon suorittimen käyttöaikaa, mikä estää nälkiintymisen.
🧮 Ennaltaehkäisevä: Ennakoitu prosessi siirtyy jonon loppuun.
✅ edut: Oikeudenmukainen kohdentaminen, ei saattuevaikutusta, ennustettava vasteaika.
⚠️ Haittoja: Suorituskyky riippuu aikakvantista ja lisää kontekstikytkimen aiheuttamaa lisätyötä.

Lue lisää

Mikä on Round-Robin-aikataulutus?

Tämän algoritmin nimi tulee round-robin-periaatteesta, jossa jokainen saa vuorotellen yhtä suuren osuuden jostakin. Se on vanhin, yksinkertaisin ajoitusalgoritmi, jota käytetään enimmäkseen moniajoon.

Round-robin-ajoituksessa jokainen valmis tehtävä suoritetaan vuorotellen syklisessä jonossa rajoitetun ajan. Tämä algoritmi tarjoaa myös prosessien suorittamisen ilman nälkiintymistä.

Round-Robin-aikataulutuksen ominaisuudet

Tässä ovat Round-Robin-aikataulutuksen tärkeät ominaisuudet:

Round robin on ennaltaehkäisevä algoritmi.
CPU siirtyy seuraavaan prosessiin tietyn ajan kuluttua, jota kutsutaan aikakvantiksi/aikaviipaleeksi.
Prosessi, joka on ennalta määrätty, lisätään jonon loppuun.
Round robin on hybridimalli, joka toimii kelloajoittain.
Aikaviipaleen tulisi olla lyhin mahdollinen, ja se on varattu tietylle käsiteltävälle tehtävälle. Se voi kuitenkin vaihdella käyttöjärjestelmästä toiseen.
Se on reaaliaikainen algoritmi, joka reagoi tapahtumaan tietyn aikarajan sisällä.
Round robin on yksi vanhimmista, oikeudenmukaisimmista ja helpoimmista algoritmeista.
Se on laajalti käytetty ajoitusmenetelmä perinteisissä käyttöjärjestelmissä.

Esimerkki Round-robin-aikataulusta

Tarkastellaan seuraavia kolmea prosessia:

Prosessin jono	Räjähdysaika
P1	4
P2	3
P3	5

Vaihe 1) Suoritus alkaa prosessilla P1, jonka purskeaika on 4. Tässä jokainen prosessi suoritetaan 2 sekuntia. P2 ja P3 ovat edelleen odotusjonossa.

Vaihe 2) Ajanhetkellä 2 P1 lisätään jonon loppuun ja P2 alkaa suorituksen.

Vaihe 3) Ajanhetkellä 4 P2:n suoritus varataan ja se lisätään jonon loppuun. P3:n suoritus alkaa.

Vaihe 4) Ajanhetkellä 6 P3:n suoritus varataan ja se lisätään jonon loppuun. P1:n suoritus alkaa.

Vaihe 5) Ajanhetkellä 8 P1:n purskeaika on 4. Suoritus on päättynyt. P2 aloittaa suorituksen.

Vaihe 6) P2:n purskeaika on 3. Se on jo suoritettu kahden aikavälin ajan. Ajanhetkellä 9 P2 suorittaa suorituksen loppuun. Sitten P3 jatkaa suoritusta, kunnes se on valmis.

Vaihe 7) Lasketaanpa keskimääräinen odotusaika yllä olevalle esimerkille.

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

Round-robin-aikataulutuksen edut

Tässä ovat Round-robin-ajoitusmenetelmän edut/hyödyt:

Se ei kohtaa nälänhädän tai saattuevaikutuksen ongelmia.
Kaikki työpaikat saavat oikeudenmukaisen prosessorin.
Se käsittelee kaikkia prosesseja ilman prioriteettia.
Jos tiedät ajojonossa olevien prosessien kokonaismäärän, voit myös olettaa pahimman tapauksen vasteajan samalle prosessille.
Tämä ajoitusmenetelmä ei ole riippuvainen purskeajasta. Siksi se on helppo toteuttaa järjestelmässä.
Kun prosessi on suoritettu tietyn ajanjakson aikana, prosessi estetään ja toinen prosessi suoritetaan kyseisen ajanjakson ajan.
Sallii käyttöjärjestelmän käyttää kontekstinvaihtomenetelmää ennalta määritettyjen prosessien tilojen tallentamiseen.
Se tarjoaa parhaan suorituskyvyn keskimääräisen vasteajan suhteen.

Round-robin-aikataulutuksen haitat

Tässä ovat Round-robin-ajoituksen haitat/haitat:

Jos käyttöjärjestelmän viipalointiaika on hidas, prosessorin teho pienenee.
Tämä menetelmä käyttää enemmän aikaa kontekstin vaihtamiseen.
Sen suorituskyky riippuu suuresti aikakvantista.
Prosesseille ei voi asettaa prioriteetteja.
Round-robin-ajoitus ei anna erityistä prioriteettia tärkeämmille tehtäville.
Se vähentää ymmärrystä.
Pienempi aikakvantti johtaa suurempaan kontekstin vaihtamisen lisäkuormaan järjestelmässä.
Oikean aikamäärän löytäminen on tässä järjestelmässä melko vaikea tehtävä.

Pahimmassa tapauksessa latenssi

Tätä termiä käytetään kaikkien tehtävien suorittamiseen käytettävän enimmäisajan osalta.

dt = Ilmaisee havaitsemisaikaa, kun tehtävä tuodaan listaan
st = Ilmaisee siirtymisaikaa tehtävästä toiseen
et = Ilmaisee tehtävän suoritusaikaa

kaava:

^T_worst = {(dt_i+ st_i+ et_i ), + (dt_i+ st_i+ et_i )₂ +...+ (dt_i+ st_i + et_i )_N., + (dt_i+ st_i + et_i  + et_i) N} + t_ISR
t_ISR = sum of all execution times

UKK

Aikakvantti eli aikaviipale on kiinteä suorittimen aika, jonka kukin prosessi suorittaa ennen kuin se estetään. Liian suuri aikakvantti käyttäytyy kuten FCFS; liian pieni aikakvantti lisää raskasta kontekstinvaihtotyötä.

FCFS suorittaa jokaisen prosessin loppuun saapumisjärjestyksessä eikä ole preemptiivinen. Round Robin on preemptiivinen: se antaa jokaiselle prosessille kiinteän aikaviipaleen ja käy jonon läpi parantaen vasteaikaa ja estäen pitkiä töitä estämästä muita.

Koska jokainen prosessi sijoitetaan sykliseen jonoon ja saa vuorollaan kiinteän aikaviipaleen, yhtäkään prosessia ei ohiteta tai viivytetä loputtomiin, joten jokainen prosessi saa lopulta suorittimen aikaa pituudestaan tai saapumisjärjestyksestään riippumatta.

Tekoäly ja koneoppiminen voivat ennustaa prosessien käyttäytymistä ja työmäärämalleja aikataulutuspäätösten hienosäätämiseksi reaaliajassa. Kiinteän käytännön sijaan järjestelmä voi mukauttaa prioriteetteja ja aikaviipaleita dynaamisesti, mikä parantaa suorittimen käyttöastetta, läpimenoaikaa ja vasteaikaa.

Kyllä. Tekoälymallit voivat analysoida aiempia purskeaikoja ja järjestelmän kuormitusta ehdottaakseen optimaalista aikamäärää ja säätää sitä olosuhteiden muuttuessa. Tämä tasapainottaa kontekstivaihdon aiheuttamaa lisäkuormitusta vasteaikaan nähden paremmin kuin yksi kiinteä arvo.