Round-Robin

Round-Robin Scheduling

Merupakan penjadwalan yang paling tua, sederhana, adil, banyak digunakan algoritmanya dan mudah diimplementasikan. Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwal. Berdasarkan lama waktu berjalannya proses (preempt by time). Penjadwalan tanpa prioritas berasumsi bahwa semua proses memiliki kepentingan yang sama, sehingga tidak ada prioritas tertentu. Semua proses dianggap penting sehingga diberi sejumlah waktu oleh pemroses yang disebut kwanta (quantum) atau time slice dimana proses itu berjalan.
Konsep dasar dari algoritma ini adalah dengan menggunakan time-sharing. Pada dasarnya algoritma ini sama dengan FCFS, hanya saja bersifat preemptive. Setiap proses mendapatkan waktu CPU yang disebut dengan waktu quantum (quantum time) untuk membatasi waktu proses, biasanya 1-100 milidetik. Jika proses masih running sampai akhir quantum, maka CPU akan mempreempt proses itu dan memberikannya ke proses lain. Ketika quantum habis untuk satu proses tertentu, maka proses tersebut akan diletakkan diakhir daftar (list).
Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first come first served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.
Jika suatu proses memiliki CPU burst lebih kecil dibandingkan dengan waktu quantum, maka proses tersebut akan melepaskan CPU jika telah selesai bekerja, sehingga CPU dapat segera digunakan oleh proses selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang lebih besar dibandingkan dengan waktu quantum, maka proses tersebut akan dihentikan sementara jika sudah mencapai waktu quantum, dan selanjutnya mengantri kembali pada posisi ekor dari ready queue, CPU kemudian menjalankan proses berikutnya.
Jika terdapat n proses pada ready queue dan waktu quantum q, maka setiap
proses mendapatkan 1/n dari waktu CPU paling banyak q unit waktu pada sekali
penjadwalan CPU. Tidak ada proses yang menunggu lebih dari (n-1)q unit waktu.
Performansi algoritma round robin dapat dijelaskan sebagai berikut, jika q besar, maka
yang digunakan adalah algoritma FIFO, tetapi jika q kecil maka sering terjadi context
switch.
Ketentuan algoritma round robin adalah sebagai berikut:
1. Jika kwanta dan proses belum selesai maka proses menjadi runnable dan pemroses dialihkan ke proses lain.
2. Jika kwanta belum habis dan proses menunggu suatu kejadian (selesainya operasi I/O), maka proses menjadi blocked dan pemroses dialihkan ke proses lain.
3. Jika kwanta belum habis tapi proses telah selesai, maka proses diakhiri dan pemroses dialihkan ke proses lain.
Algoritma penjadwalan ini dapat diimplementasi sebagai berikut:
1. Mengelola senarai proses read (runnable) sesuai urutan kedatangan.
2. Ambil proses yang berada di ujing depan antrian menjadi running.
3. Bila kwanta belum habis dan proses selesai maka ambil proses di ujung depan antrian proses ready.
4. Jika kwanta habis dan proses belum selesai maka tempatkan proses running ke ekor antrian proses ready dan ambil proses di ujung depatn antrian proses ready.
Masalah yang timbul adalah menentukan besar kwanta, yaitu :
1. Kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround time
rendah.
2. Kwanta terlalu kecil menyebabkan peralihan proses terlalu banyak sehingga
menurunkan efisiensi proses.
Switching dari satu proses ke proses lain membutuhkan kepastian waktu yang
digunakan untuk administrasi, menyimpan, memanggil nilai-nilai register, pemetaan
memori, memperbaiki tabel proses dan senarai dan sebagainya. Mungkin proses
switch ini atau konteks switch membutuhkan waktu 5 msec disamping waktu pemroses yang dibutuhkan untuk menjalankan proses tertentu. Dengan permasalahan tersebut tentunya harus ditetapkan kwanta waktu yang optimal berdasarkan kebutuhan sistem dari hasil percobaan atau data historis. Besar kwanta waktu beragam bergantung beban sistem. Apabila nilai quantum terlalu singkat akan menyebabkan terlalu banyak switch antar proses dan efisiensi CPU akan buruk, sebaliknya bila nilai quantum terlalu lama akan menyebabkan respon CPU akan lambat sehingga proses yang singkat akan menunggu lama.
Sebuah quantum sebesar 100 msec merupakan nilai yang dapat diterima.
Penilaian penjadwalan ini berdasarkan kriteria optimasi :
• Adil, adil bila dipandang dari persamaan pelayanan oleh pemroses.
• Efisiensi, cenderung efisien pada sistem interaktif.
• Waktu tanggap, memuaskan untuk sistem interaktif, tidak memadai untuk sistem waktu nyata.
• Turn around time Cukup baik.
• Throughtput Cukup baik.



Penjadwalan ini :
• Baik untuk sistem interactive-time sharing dimana kebanyakan waktu
dipergunakan menunggu kejadian eksternal. Contoh : text editor, kebanyakan waktu program adalah untuk menunggu keyboard, sehingga dapat dijalankan proses-proses lain.
• Tidak cocok untuk sistem waktu nyata apalagi hard-real-time applications.

Contoh: Misalkan ada 3 proses: P1, P2, dan P3 yang meminta pelayanan CPU dengan quantum-time sebesar 4 milidetik.
Process Burst Time
P1 20
P2 4
P3 8
Penjadwalan proses dengan algoritma round robin dapat dilihat pada gant chart berikut :

Waktu tunggu untuk P1 adalah 4, P2 adalah 8, dan P3 adalah 12 sehingga rata-rata waktu tunggu adalah (4+ 8+ 12)/3 = 8 milidetik.
Algoritma Round-Robin ini di satu sisi memiliki keuntungan, yaitu adanya keseragaman waktu. Namun di sisi lain, algoritma ini akan terlalu sering melakukan switching seperti yang terlihat pada Gambar di bawah ini. Semakin besar quantum-timenya maka switching yang terjadi akan semakin sedikit.

Waktu turnaround juga tergantung ukuran waktu quantum. Seperti pada Gambar 4-5, rata-rata waktu turnaround tidak meningkat bila waktu quantum dinaikkan. Secara umum, rata-rata waktu turnaround dapat ditingkatkan jika banyak proses menyelesaikan CPU burst berikutnya sebagai satu waktu quantum. Sebagai contoh, terdapat tiga proses masing-masing 10 unit waktu dan waktu quantum 1 unit waktu, rata-rata waktu turnaround adalah 29. Jika waktu quantum 10, sebaliknya, rata-rata waktu turnaround turun menjadi 20.