Mikä on Round Robin -aikataulutus?
Algoritmin nimi tulee round-robin -periaatteesta, jossa jokainen saa vuorotellen yhtä suuren osan jostakin. Se on vanhin ja yksinkertaisin aikataulutusalgoritmi, jota käytetään useimmiten monitehtävässä.
Round-robin-aikataulutuksessa jokainen valmis tehtävä suoritetaan vuorotellen vain syklisessä jonossa rajoitetun ajanjakson ajan. Tämä algoritmi tarjoaa myös prosessien nälkävapaan suorituksen.
Tässä käyttöjärjestelmäoppaassa opit:
- Mikä on Round-Robin Scheduling?
- Round-Robin Schedulingin ominaisuudet
- Esimerkki Round-robin Schedulingista
- Round-robin Schedulingin etu
- Round-robin Schedulingin haitat
- Worst Case Latency (pahimman tapauksen latenssi)
Round-Robin Schedulingin ominaisuudet
Näissä kerrotaan Round-Robin Schedulingin tärkeät ominaisuudet:
- Round robin on preemptive-algoritmi
- Suorittimen käyttö siirtyy seuraavalle prosessille kiinteän aikaväliajan jälkeen, jota kutsutaan aikakvantiksi/aikasiivuksi.
- Prosessi, joka on preemptoitu, lisätään jonon loppuun.
- Round robin on hybridimalli, joka on kello-ohjattu
- Aikaviipaleen tulisi olla minimaalinen, joka osoitetaan tietylle tehtävälle, joka on käsiteltävä. Se voi kuitenkin vaihdella käyttöjärjestelmäkohtaisesti.
- Se on reaaliaikainen algoritmi, joka reagoi tapahtumaan tietyn aikarajan sisällä.
- Round robin on yksi vanhimmista, oikeudenmukaisimmista ja helpoimmista algoritmeista.
- Laajasti käytetty aikataulutusmenetelmä perinteisissä käyttöjärjestelmissä.
Esimerkki Round- Robinista.robin Scheduling
Tarkastellaan seuraavia kolmea prosessia
| Prosessijono | Burst time |
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
Vaihe 1) Suoritus alkaa prosessilla P1, jolla on burst-aika 4. Tässä jokainen prosessi suorittaa 2 sekuntia. P2 ja P3 ovat edelleen odotusjonossa.
Vaihe 2) Ajankohtana =2 P1 lisätään jonon loppuun ja P2 aloittaa suorituksen
Vaihe 3) Ajankohtana =4 P2 ennakoidaan ja lisätään jonon loppuun. P3 alkaa suorittaa.
Vaihe 4) Ajankohtana=6 , P3 preemptoidaan ja lisätään jonon loppuun. P1 aloittaa suorituksen.
Vaihe 5) Ajankohtana=8 , P1:n purskeaika on 4. Se on suorittanut suorituksen loppuun. P2 aloittaa suorituksen
Vaihe 6) P2:lla on purskeaika 3. Se on jo suorittanut 2 välin ajan. Ajankohtana = 9 P2 suorittaa suorituksen loppuun. Sen jälkeen P3 aloittaa suorituksen, kunnes se on valmis.
Vaihe 7) Lasketaan keskimääräinen odotusaika edellä mainitulle esimerkille.
Wait time P1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7
Round-robin-aikataulun edut
Tässä ovat Round-robin-aikataulumenetelmän edut/edut:
- Se ei kohtaa nälänhädän tai saattueilmiön ongelmia.
- Kaikki työt saavat oikeudenmukaisen jaon suorittimesta.
- Se käsittelee kaikkia prosesseja ilman prioriteetteja.
- Jos tiedät prosessien kokonaismäärän suoritusjonossa, voit myös olettaa huonoimman tapauksen vasteajan samalle prosessille.
- Tämä ajoitusmenetelmä ei ole riippuvainen purskeajasta. Siksi se on helposti toteutettavissa järjestelmässä.
- Kun prosessi on suoritettu tietyn ajanjakson ajan, prosessi otetaan ennakkoon ja toinen prosessi suoritetaan kyseisen ajanjakson ajan.
- Sallii käyttöjärjestelmän käyttää kontekstinvaihtomenetelmää (Context switching) ennakkoon otettujen prosessien tilojen tallentamiseen.
- Se antaa parhaan suorituskyvyn keskimääräisen vasteajan suhteen.
Round-robin schedulingin haitat
Tässä ovat Round-robin schedulingin käytön haitat/haitat:
- Jos käyttöjärjestelmän viipalointiaika on pieni, prosessoriteho vähenee.
- Tämä menetelmä käyttää enemmän aikaa kontekstinvaihtoon
- Suorituskyky riippuu voimakkaasti aikakvantista.
- Prosesseille ei voi asettaa prioriteetteja.
- Round-robin -aikataulutus ei anna erityistä prioriteettia tärkeämmille tehtäville.
- Vähentää ymmärrettävyyttä
- Matalampi aikakvantti johtaa suurempaan kontekstinvaihdon yleiskustannukseen järjestelmässä.
- Oikein aikakvantin löytäminen on melko vaikea tehtävä tässä järjestelmässä.
Worst Case Latency
Tällä termillä tarkoitetaan kaikkien tehtävien suorittamiseen kuluvaa enimmäisaikaa.
- dt = Merkitään havaintoaikaa, kun tehtävä tuodaan listalle
- st = Merkitään siirtymisaikaa tehtävästä toiseen
- et = Merkitään tehtävän suoritusaikaa
Formula:
Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISRt,SR = sum of all execution times
Yhteenveto:
- Tämän algoritmin nimi tulee round robin -periaatteesta, jossa jokainen saa vuorotellen yhtä suuren osuuden jostakin asiasta.
- Round robin on yksi vanhimmista, oikeudenmukaisimmista ja helpoimmista algoritmeista ja laajalti käytetyistä aikataulutusmenetelmistä perinteisessä käyttöjärjestelmässä.
- Round robin on pre-emptive-algoritmi
- Round robin -aikataulutusmenetelmän suurin etu on se, että Jos tiedetään ajojonossa olevien prosessien kokonaismäärä, voidaan myös olettaa saman prosessin pahimman tapauksen vasteaika.
- Tämä menetelmä kuluttaa enemmän aikaa kontekstinvaihtoon
- Pahimman tapauksen viive on termi, jota käytetään kaikkien tehtävien suorittamiseen kuluvasta enimmäisajasta.
Kontekstinvaihtoon käytetään enemmän aikaa.