Round Robin Algoritam rasporeda s primjerom

By: Nathaniel Brooks Nathaniel Brooks
Hours Ažurirano

Š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 Round-robin raspoređivanju, svaki spremni zadatak izvodi se redom samo u cikličkom redu čekanja u ograničenom vremenskom odsječku. Ovaj algoritam također nudi izvođenje procesa bez izgladnjivanja.

Karakteristike Round-Robin rasporeda

Evo važnih karakteristika Round-Robin rasporeda:

  • Round robin je preventivni algoritam
  • CPU se prebacuje na sljedeći proces nakon fiksnog vremenskog intervala, koji se naziva vremenski kvantum/vremenski odsječak.
  • Proces koji ima prednost dodaje se na kraj reda čekanja.
  • Round robin je hibridni model koji pokreće sat
  • Vremenski odsječak treba biti minimalan, koji je dodijeljen za određeni zadatak koji treba obraditi. Međutim, može se razlikovati od OS do OS-a.
  • To je algoritam u stvarnom vremenu koji odgovara na događaj unutar određenog vremenskog ograničenja.
  • Round robin je jedan od najstarijih, najpravednijih i najlakših algoritama.
  • Često korištena metoda raspoređivanja u tradicionalnom OS-u.

Primjer Round-robin rasporeda

Razmotrite ovo kroz tri procesa

Proces čekanja Vrijeme praska
P1 4
P2 3
P3 5

Round-robin raspored

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.

Round-robin raspored

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

Round-robin raspored

POVEZANI ČLANCI


Korak 3) U vrijeme = 4, P2 se iskorištava i dodaje na kraj reda čekanja. P3 počinje s izvršavanjem.

Round-robin raspored

Korak 4) U vrijeme = 6, P3 se iskorištava i dodaje na kraj reda čekanja. P1 počinje s izvršavanjem.

Round-robin raspored

Korak 5) U trenutku=8, P1 ima vrijeme praska od 4. Završio je izvršenje. P2 započinje izvršenje

Round-robin raspored

Korak 6) P2 ima vrijeme praska od 3. Već je izvršen u intervalu od 2. U trenutku = 9, P2 dovršava izvršenje. Zatim P3 počinje s izvođenjem dok ne završi.

Round-robin raspored

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

Prednost Round-robin rasporeda

Ovdje su prednosti/prednosti Round-robin metode raspoređivanja:

  • Ne suočava se s problemima gladovanja 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 praska. Zato ga je lako implementirati 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 prebacivanja konteksta za spremanje stanja unaprijed izuzetih procesa.
  • Daje najbolje performanse u smislu prosječnog vremena odziva.

Nedostaci Round-robin rasporeda

Ovdje su nedostaci/protiv upotrebe Round-robin rasporeda:

  • Ako je vrijeme rezanja OS-a malo, 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.
  • Round-robin raspoređivanje ne daje poseban prioritet važnijim zadacima.
  • Smanjuje razumijevanje
  • Niži vremenski kvantum rezultira višim opterećenjem prebacivanja konteksta u sustavu.
  • Pronalaženje točnog vremenskog kvantuma 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 se zadatak unese na popis
  • st = Označava vrijeme prebacivanja s jednog zadatka na drugi
  • et = Označava vrijeme izvršenja zadatka

formula:

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

rezime

  • Naziv ovog algoritma dolazi od kružnog principa, gdje svaka osoba dobiva jednaki udio nečega naizmjenično.
  • Round robin jedan je od najstarijih, najpravednijih i najlakših algoritama i naširoko korištenih metoda raspoređivanja u tradicionalnim OS.
  • Round robin je preventivni algoritam
  • Najveća prednost kružne metode raspoređivanja je u tome što, ako znate ukupan broj procesa u redu čekanja, možete pretpostaviti najgore moguće vrijeme odgovora za isti proces.
  • Ova metoda troši više vremena na promjenu konteksta
  • Latencija u najgorem slučaju je termin koji se koristi za maksimalno vrijeme potrebno za izvršenje svih zadataka.

Možda ti se svidi: