Round Robin Algoritam rasporeda s primjerom

Što je Round-Robin raspored?

Naziv ovog algoritma dolazi od kružnog principa, gdje svaka osoba dobiva jednaki udio nečega naizmjenično. To je najstariji, najjednostavniji algoritam za raspoređivanje, koji se uglavnom koristi za multitasking.

U kružnom raspoređivanju, svaki spreman zadatak izvršava se redom samo u cikličkom redu čekanja tijekom ograničenog vremenskog intervala. Ovaj algoritam također nudi izvršavanje procesa bez gladovanja.

Karakteristike Round-Robin rasporeda

Evo važnih karakteristika Round-Robin rasporeda:

• Kružni rad je preemptivni algoritam.
• CPU se prebacuje na sljedeći proces nakon fiksnog vremenskog intervala, koji se naziva vremenski kvant/vremenski odsječak.
• Proces koji ima prednost dodaje se na kraj reda čekanja.
• Kružni sistem je hibridni model koji se pokreće satnim rasporedom.
• Vremenski isječak trebao bi biti minimalan, što je dodijeljeno za određeni zadatak koji treba obraditi. Međutim, može se razlikovati od operativnog sustava do operativnog sustava.
• To je algoritam u stvarnom vremenu koji reagira na događaj unutar određenog vremenskog ograničenja.
• Kružni rad je jedan od najstarijih, najpravednijih i najlakših algoritama.
• To je široko korištena metoda raspoređivanja u tradicionalnim OS-ima.

Primjer Round-robin rasporeda

Razmotrite sljedeća tri procesa:

Korak 1) Izvršenje počinje s procesom P1, koji ima vrijeme praska 4. Ovdje se svaki proces izvršava 2 sekunde. P2 i P3 su još uvijek u redu čekanja.

Korak 2) U trenutku = 2, P1 se dodaje na kraj reda čekanja i P2 počinje s izvršavanjem.

Korak 3) U trenutku = 4, P2 se preemptira i dodaje na kraj reda. P3 počinje s izvršavanjem.

Korak 4) U trenutku = 6, P3 se preemptira i dodaje na kraj reda. P1 počinje s izvršavanjem.

Korak 5) U vremenu = 8, P1 ima vrijeme neprekidnog niza od 4. Izvršenje je završeno. P2 započinje izvršavanje.

Korak 6) P2 ima vrijeme izvršavanja od 3. Već se izvršavao u 2 intervala. U vremenu = 9, P2 završava izvršavanje. Zatim, P3 započinje izvršavanje dok se ne završi.

Korak 7) Izračunajmo prosječno vrijeme čekanja za gornji primjer.

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

Prednosti kružnog raspoređivanja

Evo prednosti/koristi metode kružnog raspoređivanja:

• Ne suočava se s problemima gladi ili efekta konvoja.
• Svi poslovi dobivaju poštenu raspodjelu CPU-a.
• Bavi se svim procesima bez ikakvog prioriteta.
• Ako znate ukupan broj procesa u redu čekanja, tada također možete pretpostaviti najgore moguće vrijeme odgovora za isti proces.
• Ova metoda raspoređivanja ne ovisi o vremenu rafala. Zato se lako implementira u sustav.
• Nakon što se proces izvrši za određeni skup razdoblja, proces se isključuje, a drugi se proces izvršava za to određeno vremensko razdoblje.
• Omogućuje OS-u korištenje metode promjene konteksta za spremanje stanja preemptiranih procesa.
• Daje najbolje performanse u smislu prosječnog vremena odziva.

Nedostaci Round-robin rasporeda

Evo nedostataka/nedostataka korištenja kružnog raspoređivanja:

• Ako je vrijeme rezanja OS-a nisko, izlaz procesora će se smanjiti.
• Ova metoda troši više vremena na promjenu konteksta.
• Njegova izvedba uvelike ovisi o kvantumu vremena.
• Prioriteti se ne mogu postaviti za procese.
• Kružno raspoređivanje ne daje poseban prioritet važnijim zadacima.
• Smanjuje razumijevanje.
• Niži vremenski kvant rezultira većim opterećenjem promjene konteksta u sustavu.
• Pronalaženje ispravnog vremenskog kvanta prilično je težak zadatak u ovom sustavu.

Latencija u najgorem slučaju

Ovaj izraz se koristi za maksimalno vrijeme potrebno za izvršenje svih zadataka.

• dt = Označava vrijeme detekcije kada je zadatak dodan na popis
• st = Označava vrijeme prebacivanja s jednog zadatka na drugi
• et = Označava vrijeme izvršavanja zadatka

formula:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

Pitanja i odgovori