Round Robini ajastamisalgoritm koos näitega

⚡ Nutikas kokkuvõte

Round-Robin Scheduling on vanim ja lihtsaim ennetav protsessori algoritm, kus iga valmis protsessor töötab tsüklilises järjekorras fikseeritud aja jooksul, tagades õiglase ja nälgimisevaba täitmise mitme ülesande korraga täitmiseks.

🔄 Määratlus: Iga valmisülesanne töötab kordamööda kindla ajavahemiku jooksul.
️ Ajakvant: Protsessor lülitab protsesse pärast kindlat intervalli, ajakvanti.
🇧🇷 Õiglus: Iga protsess saab võrdse protsessoriaja, vältides nälgimist.
🧮 Ennetav: Eelnevalt valitud protsess liigub järjekorra lõppu.
✅ Plussid: Õiglane jaotus, konvoiefekti puudumine, prognoositav reageerimisaeg.
⚠️ Puudusi: Jõudlus sõltub ajakvantist ja lisab kontekstivahetuse lisakulusid.

Loe rohkem

Mis on Round-Robini ajakava?

Selle algoritmi nimi tuleneb round-robin põhimõttest, kus iga inimene saab kordamööda millestki võrdse osa. See on vanim ja lihtsaim ajastamisalgoritm, mida kasutatakse enamasti multitegumtööks.

Ring-robin ajastamise puhul töötab iga valmis ülesanne piiratud aja jooksul tsüklilises järjekorras kordamööda. See algoritm pakub ka protsesside nälgimisevaba täitmist.

Round-Robini ajakava omadused

Siin on Round-Robini ajakava olulised omadused:

Round robin on ennetav algoritm.
Protsessor nihutatakse järgmisele protsessile pärast fikseeritud ajavahemikku, mida nimetatakse ajakvantiks/ajaviiluks.
Eelistatud protsess lisatakse järjekorra lõppu.
Round robin on hübriidmudel, mis töötab kella graafikul.
Ajalõik peaks olema minimaalne, mis on määratud konkreetse töödeldava ülesande jaoks. See võib aga operatsioonisüsteemiti erineda.
See on reaalajas algoritm, mis reageerib sündmusele kindla aja jooksul.
Ringmäng on üks vanimaid, õiglasemaid ja lihtsamaid algoritme.
See on traditsioonilises operatsioonisüsteemis laialdaselt kasutatav ajastamismeetod.

Ring-robini ajakava näide

Mõelge järgmistele kolmele protsessile:

Protsessi järjekord	Purskeaeg
P1	4
P2	3
P3	5

Step 1) Täitmine algab protsessiga P1, mille sarivõtte aeg on 4. Siin käivitub iga protsess 2 sekundit. P2 ja P3 on endiselt ootejärjekorras.

Step 2) Ajahetkel 2 lisatakse P1 järjekorra lõppu ja P2 hakkab käivituma.

Step 3) Ajahetkel 4 tühistatakse käsk P2 ja lisatakse järjekorra lõppu. Käivitub käsk P3.

Step 4) Ajahetkel 6 tühistatakse käsk P3 ja lisatakse järjekorra lõppu. Käivitub käsk P1.

Step 5) Ajahetkel 8 on P1 purskeaeg 4. See on täitmise lõpetanud. P2 alustab täitmist.

Step 6) P2 täitmisaeg on 3. See on juba kaks intervalli täidetud. Ajahetkel 9 lõpetab P2 täitmise. Seejärel alustab P3 täitmist kuni selle lõpetamiseni.

Step 7) Arvutame ülaltoodud näite jaoks keskmise ooteaja.

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

Ringgraafiku koostamise eelised

Siin on ringjada meetodi plussid/eelised:

See ei seisa silmitsi nälja ega konvoiefekti probleemidega.
Kõik töökohad saavad CPU õiglase jaotuse.
See tegeleb kõigi protsessidega ilma prioriteetideta.
Kui teate käivitusjärjekorras olevate protsesside koguarvu, võite eeldada ka sama protsessi halvima reaktsiooniaega.
See ajastamismeetod ei sõltu purskeajast. Seetõttu on see süsteemis hõlpsasti rakendatav.
Kui protsess on teatud perioodi jooksul käivitatud, eelneb protsess ja selle ajaperioodi jooksul käivitub teine protsess.
Võimaldab operatsioonisüsteemil kasutada kontekstivahetuse meetodit eelnevalt aktiveeritud protsesside olekute salvestamiseks.
See annab keskmise reageerimisaja osas parima jõudluse.

Round-robini ajakava puudused

Siin on ringjada ajastamise puudused/miinused:

Kui operatsioonisüsteemi viilutamisaeg on madal, väheneb protsessori väljundvõimsus.
See meetod pühendab konteksti vahetamisele rohkem aega.
Selle jõudlus sõltub suuresti ajakvandist.
Protsessidele ei saa prioriteete seada.
Ringgraafiku koostamine ei anna olulisemaid ülesandeid eraldi prioriteeti.
See vähendab mõistusvõimet.
Väiksem ajakvant põhjustab süsteemis suuremat konteksti vahetamise üldkulu.
Õige ajamahu leidmine on selles süsteemis üsna keeruline ülesanne.

Halvimal juhul latentsus

Seda terminit kasutatakse kõigi ülesannete täitmiseks kuluva maksimaalse aja kohta.

dt = Tähistab ülesande loendisse lisamise tuvastamise aega
st = tähistab ühelt ülesandelt teisele ülemineku aega
et = Tähistab ülesande täitmise aega

Valem:

^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

KKK

Ajakvant ehk ajaviil on fikseeritud protsessori aeg, mille iga protsess enne eelseadistamist töötab. Liiga suur väärtus käitub nagu FCFS; liiga väike väärtus lisab kontekstivahetusega seotud lisakoormust.

FCFS käivitab iga protsessi saabumisjärjekorras lõpuni ja ei ole ennetav. Round Robin on ennetav: see annab igale protsessile fikseeritud ajaviilu ja tsükliliselt läbib järjekorda, parandades reageerimisaega ja takistades pikkadel töödel teisi blokeerida.

Kuna iga protsess paigutatakse tsüklilisse järjekorda ja saab kordamööda fikseeritud ajaviilu, siis ühtegi protsessi ei jäeta vahele ega lükata määramata ajaks edasi, seega saab igaüks lõpuks protsessori aega olenemata selle pikkusest või saabumisjärjekorrast.

Tehisintellekt ja masinõpe suudavad ennustada protsesside käitumist ja töökoormuse mustreid, et ajastamisotsuseid reaalajas häälestada. Fikseeritud poliitika asemel saab süsteem prioriteete ja ajaviilusid dünaamiliselt kohandada, parandades protsessori kasutust, läbilaskevõimet ja reageerimisaega.

Jah. Tehisintellekti mudelid suudavad analüüsida varasemaid pursete aegu ja süsteemi koormust, et pakkuda välja optimaalne ajakvant ning seda vastavalt tingimuste muutumisele kohandada. See tasakaalustab kontekstivahetuse lisakulud reageerimisajaga paremini kui üks fikseeritud väärtus.