@RR(Round Robin) scheduling adalah suatu algorithma penjadwalan yang termasuk ke dalam kelompok penjadwalan Preemptive pada akhir irisan waktu(time slice) atau akhir waktu quantum . Algorithma Round Robin sederhana dan mudah diimplementasikan. 

Nama Round Robin berasal dari prinsip yang dikenal sebagai Round Robin dimana setiap orang mengambil bagian yang sama dari sesuatu pada gilirannya.

@Algorithme Round Robin merupakan salah satu algorithma yang tertua paling sederhana, algoritma paling adil dan paling banyak digunakan adalah Round Robin (RR).

@Tujuan dasar dari algoritma penjadwalan Round Robin adalah untuk mendukung sistem pembagian waktu (Time Sharing).Oleh karena itu Round Robin efektif dalam lingkungan time-sharing di mana sistem perlu menjamin waktu respon yang wajar bagi pengguna interaktif.

@Di satu sisi Algoritma Round Robin mirip dengan algoritma FIFO yakni proses yang dilayani  di dalam antrian Ready dan proses yang duluan tiba adalah proses yang duluan dilayani.
Pada RR Proses yang dilayani berada dalam antrian Ready melingkar disebut cyclic executive.

Perbedaannya dengan FIFO bahwa pada penjadwalan Round Robin ada pemberian jatah waktu layanan maksimal tertentu yang  sama untuk semua proses dalam 1 kali layanan.Jatah waktu layanan tertentu dalam satu kali layanan disebut waktu Quantum atau irisan waktu(time slice). Sehingga sistem pemberian jatah waktu layanan pada Round Robin disebut Time Slice(Irisan waktu) atau dikenal sebagai waktu Quantum

@Waktu kuantum umumnya 10 s/d 100 ms

@Dalam algorithme Round Robin untuk menyelesaikan suatu proses boleh saja mengalami layanan lebih dari 1 kali waktu kuantum yaitu terjadi pada proses yang BTnya lebih besar atau jauh lebih besar dari waktu Quantum. 

Pada kronologis layanan setiap set timer menunjuk habisnya waktu Quantum akan menyebabkan interupsi pada Sistem Operasi maka layanan terhadap suatu proses dihentikan(ditunda) dan scheduller menetapkan layanan diberikan pada proses urutan berikutnya pada antrian Ready. Proses yang ditunda tersebut akan ditempatkan posisinya di ujung akhir antrian Ready dan akan dilayani dilain waktu jika telah tiba gilirannya untuk dilayani lagi. 


Suatu proses yang ditunda layanannya dapat disebabkan karena telah tiba batas kuantum atau karena mendapatkan blokir atau karena suatu operasi I / O ketika dalam waktu kuantum. 


Perpindahan proses dari posisi antrian Ready depan ke ujug akhir antrian Ready disebut Overhead. Proses pengalihan layanan dari proses Running(dilayani)  ke kondisi Ready(bersiap untuk dilayani) di dalam antrian proses Ready dan mekanisme kebalikannya seolah tiada terputus disebut Konteks Switching. 

Jika suatu proses selesai dilayani sebelum habis masa waktu kuantum maka proses mengalami Terminated (dihentikan layanan terhadapnya) kemudian proses keluar dari sistem. Selanjutnya layanan akan diberikan sebesar waktu Quantum ke proses yang berada pada urutan berikutnya dari antrian Ready.
Demikian seterusnya hingga semua proses selesai dilayani.

@Biasanya waktu yang diperlukan konteks switching adalah kurang dari 10 microsecond; dengan demikian, waktu konteks switch adalah sebagian kecil dari waktu quantum.
Perlu mempertimbangkan pengaruh konteks switching pada kinerja penjadwalan RR,mekanisme memindahkan layanan dari satu proses  ke proses yang lain  membutuhkan sejumlah waktu tertentu untuk melakukan administration saving dan memuat register dan peta memori, memperbarui berbagai tabel dan daftar, pembilasan dan reload cache memori, dll.

Pada contoh diagram di bawah ini memperlihatkan mekanisme overhead,switching pada proses A yang memiliki BT lebih besar dari waktu quantum sehingga proses A butuh dilayani lebih dari 1 kali kuantum. Setelah layanan tahap 1 sebesar waktu quantum  maka proses A mengalami switching dan overhead ke ujung akhir antrian Ready. Proses A akan dilayani lagi setelah waktu giliran proses A kembali posisinya di ujung awal antrian. Jika proses A belum juga selesai ketika waktu quantum tahap ke 2 habis maka proses A akan switching dan overhead ke ujung akhir lagi dan bersiap akan dilayani jika sudah tiba lagi posisinya di ujung awal antrian.Demikian mekanisme RR-nya hingga proses A selesai dan akhirnya keluar dari sistem.

@Rata-rata Waiting Time  dalam Round Robin scheduling panjang.
@Secara umum, waktu penyelesaian rata-rata dapat ditingkatkan jika sebagian besar proses memiliki Burst Time selesai dalam waktu kuantum hanya satu kali.

Kelemahan  dan masalah pada Round Robin Scheduling :
1. Jika waktu kuantum terlalu kecil akan menyebabkan  terjadinya 
   banyak overhead untuk konteks switching yang sering memperburuk 
   efisiensi kinerja.  Misalnya 1 ms,  pendekatan  RR disebut 
   Sharing Prosesor dan menciptakan penampilan yang masing-masing n
   proses memiliki prosesor sendiri berjalan pada 1/n kecepatan 
   prosesor yang nyata.


2. Rata-rata waktu tunggu cukup panjang ketika Burst Time proses 
   yang terlibat  sama panjang nya.

3. Jika  waktu kuantum  terlalu besar dapat menyebabkan minim 
   respon untuk permintaan layanan proses interaktif singkat
   yaitu saat pekerjaan panjang  adalah identik dengan menunggu,
   jika terjadi demikian bahkan algorithme FIFO lebih baik.
   Jika  kuantum terlalu besar maka RR berubah menjadi FIFO,  
   

Hubungan Overhead  dengan context switch dapat dinyatakan sebagai
overhead konteks switch  = C / (Q + C)
di mana Q adalah panjang waktu kuantum dan C adalah waktu konteks switching.
Peningkatan Q meningkatkan efisiensi tetapi mengurangi waktu respon rata-rata.

Sebagai contoh, misalkan ada sepuluh proses siap dijalankan, Q = 100 ms, dan C = 5 ms. Proses A (di kepala antrian run, daftar proses yang dalam keadaan Ready) mendapat giliran layanan segera. Proses B dapat berjalan hanya setelah  kuantum proses A berakhir (100 ms) dan context switch terjadi (5 ms), sehingga mulai berjalan pada 105 ms. Demikian juga, proses B dapat dilayani hanya 105 ms. Kita bisa menghitung jumlah waktu setiap proses yang akan ditunda dan membandingkan penundaan antara kuantum kecil (10 ms) dan kuantum panjang (100 ms.

Kelebihan Round Robin:
1.secara dramatis dapat meningkatkan rata-rata waktu respon rata-
rata.
2.Alokasi layanan adil ,tidak terjadi Starvation karena tidak ada proses dibiarkan menunggu giliran untuk dieksekusi oleh CPU.
3.Rata-rata Waktu Tunggu  rendah ketika ukuran Burst Time proses yang terlibat dalam layanan ukurannya bervariasi

Perhitungan yang biasa di dalam algorithme RR seperti perhitungan pada algorithme FIFO dan SJF yang telah penulis postingkan di waktu lalu .

Contoh1. Round Robin Scheduling:

Waktu Quantum = 1 ms
Pada contoh 1 ini penulis tidak mengulas perhitungan hanya menjelaskan step by step kronologis algorithme RR-nya. Waktu Quantum = 1 ms artinya setiap proses mendapat jatah layanan sebesar 1 ms . Dari paparan di bawah ini dapat dilihat bahwa P1 dilayani 5 kali, P2 dilayani 3 kali, P3 dilayani 2 kali. Dengan urutan layanan proses ada 4 rangkaian seperti yang penulis istilahkan di bawah ini sebagai 4 Trip yaitu Trip 1, Trip 2, Trip 3, dan Trip 4.

Kronologi proses dalam algorithma Round Robin-nya dapat digambarkan 
pada Gantt Chart sbb:

--------------------------------------------------------------------------------------------------------------------------


Contoh 2. Round Robin
Pada contoh ini bahasan RR bersama contoh perhitungan di dalamnya.
Data Contoh 2 ini penulis ambil dari suatu web, yang Gantt Chartnya penulis koreksi karena yang asalnya mungkin ada kesilapan dalam menuliskan Gantt Chartnya.Tetapi perhitungan Waiting Timenya dengan cara perhitungan bertahap melalui pembacaan t pada  Gantt Chartnya 
benar. 
Baiklah sahabat on line kita lanjut ulasan ini...
  

Waktu quantum = 2 ms

*Gantt Chart
Gantt Chart Contoh 2 Round Robin:

Pada akhir Gantt Chart P1 boleh tidak digambarkan sebanyak 2 kali karena P1 adalah proses yang terakhir dilayani dalam 2 kali quantum hingga selesai.Cukup dengan menuliskan t selesainya saja 17


*Perhitungan Waiting Time Round Robin 
Perhitungan Waiting Time pada Round Robin dapat dilakukan melalui pembacaan t pada Gantt Chartnya. Tetapi sedikit berbeda dibandingkan dengan pembacaan Waiting Time melalui Gantt Chart pada FIFO dan SJF yang juga telah penulis ulas pada waktu yang lalu,  hal itu karena dalam algorithme RR layanan proses yang ukuran BTnya lebih besar dari ukuran waktu Quantum,layanan dialokasikan dalam tahapan-tahapan oleh quantum.  Jadi pembacaan Waiting Time melalui Gantt Chart RR selalu dibarengi dengan perhitungan akumulasi waiting time dalam layanan hingga suatu proses itu selesai di layani.

Penulis mencoba terjemahkan ke dalam rumus perhitungan   WT yang membarengi pembacaan WT pada Gantt Chart.

Waiting Time = wt1 +( wt2 - ct1)+ (wt3 - ct2) +... (wtn - ctn-1)

wt1 =waiting time tahap1(awal)
wt2 =waiting time tahap2 
wt3 =waiting time tahap3
wtn =waiting time tahapke n
ct1 =completion time tahap1 (waktu selesai tahap1)
ct2 =completion time tahap2
ctn =completion time tahap ke n-1

Waiting Time (WT) untuk contoh 2 RR ini adalah sbb:
WT P1 = 0 + (6-2) + (10-8) + (13-12) = 7 ms

WT P2 = 2+ (8-4) + (12-10) = 8 ms
WT P3 = 4 ms , selesai dalam 1 kali Quantum
Jika dihitung rata-rata WT-nya  maka ,WT = (7+8+4)/3 = 6.33 

Bagaimana jika WT kita hitung menggunakan rumus perhitungan WT seperti yang juga telah saya postingkan pada Penjadwalan Proses di waktu yang lalu.

WT = CT - BT - AT
maka ;
WT P1 = CTP1 - BTP1 - AT1
WT P1 = 17 - 10 - 0 = 7 ms
WT P2 = 13 - 5 - 0 = 8 ms
WT P3 = 4 ms
hasilnya....sama juga.
Rata - Rata Waiting Time = (7 + 8 + 4 )/3 = 6,33

*Perhitungan Turn Around Time
Kita cukup menggunakan rumus 
TAT = WT + BT
sehingga;
TAT P1 = 7 + 10 =17 ms
TAT P2 = 8 + 5  =13 ms
TAT P3 = 4 + 2  = 6 ms

atau
boleh menggunakan rumus lain yaitu
TAT = CT - AT
sehingga ;
TAT P1=  CTP1 - ATP1
karena AT = 0, maka dalam hal ini TAT = CT
sehingga;
TAT P1= CTP1 -ATP1
      = 17 -0 =17 ms
TAT P2= 13 ms
TAT P3= 6 ms ....lihat t nya pada Gantt Chart   
hasilnya juga sama dengan hasil perhitungan rumus TAT di atas....

Rata-rata Turn Around Time = (17 + 13 + 6)/3 = 8,67 ms
----------------------------------------------------------------

Contoh 3. Round Robin
Hitunglah Rata-rata Turn Around dari layanan proses di bawah ini:
Quantum = 4 ms

*Perhitungan Turn Around Time
Kita cukup menggunakan rumus yang ada komponen rumusnya di tabel yaitu:
TAT = WT + BT
TAT D1 = 15 + 17 =32 ms
TAT D2 = 12 + 5  =17 ms
TAT D3 = 17 + 10 =27 mssehingga Rata-rata TAT-nya didapat
TAT = (30 + 17 + 27)/3 = 74/3 =24.67  ms

*Bagaimana Gantt Chart contoh 3 di atas?
Gantt Chart contoh 3 adalah :

*Bagaimana cara mencari Waiting Timenya?

WT  D1 = 0 + (12-4) + (21-16)  + (27-25)

              = 0  +     8      +     5        +      2     = 15

WT  D2 = 4  + (16-8)

              = 4  +     8   = 12

WT  D3 = 8  +(17-12) + (25-21)

              = 8  +     5       +    4     =17

Demikianlah informasi perihal algorithma Round Robin yang dapat penulis sampaikan di sini, semoga bermanfaat ...
Alhamdulillah  terima kasih. Thanks For........

Daftar Referensi

http://javahungry.blogspot.com/2013/09/round-robin-scheduling-algorithm-with-example-java-program-code.html
http://physinfo.ulb.ac.be/cit_courseware/opsys/os02.htm
http://siber.cankaya.edu.tr/OperatingSystems/ceng328/node125.html

http://web.cse.ohio-state.edu/~agrawal/660/Slides/jan18.pdf

https://www.cs.rutgers.edu/~pxk/416/notes/07-scheduling.html

http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/roundRobinSchedule.htm
Pasaribu.M.2015.Sistem Operasi.

Yang,Junfeng.W4118.http://www.cs.columbia.edu/~junfeng/10sp-w4118/lectures/l13-sched.pdf