Penjadwalan Round Robin

Penjadwalan Round Robin (RR)

Round robin adalah sebuah susunan yang memilih semua elemen pada grup seperti beberapa perintah rasional, biasanya dari atas sampai ke bawah sebuah daftar/susunan dan kembali lagi keatas dan begitu seterusnya. Dapat diandaikan bahwa round robin seperti mengambil giliran (“taking turns”).

Dalam cara kerja komputer, satu metode memiliki beberapa proses program yang berbeda dalam mengambil giliran, dengan menggunakan sumber daya komputer ke batas proses setiap jangka waktu pendek tertentu, kemudian membatalkan/menghentikan proses yang sedang berjalan kepada proses yang mendapat giliran berikutnya. Biasa diartikan sebagai  proses Penjadwalan Round Robin.

Dapat dianalogikan seperti turnamen olahraga, dimana round robin menyusun/mengatur semua tim atau para pemain mengambil/memainkan giliran mereka bermain. Yang akan menghasilkan pemenang dari turnamen yang telah diselenggarakan.

Pengertian lain Round Robin Merupakan :

· Penjadwalan yang paling tua, sederhana, adil,banyak digunakan algoritmanya  dan mudah diimplementasikan/diterapkan.

· Penjadwalan ini bukan dipreempt(diinterupsi) oleh proses lain tetapi oleh penjadwal  berdasarkan lama waktu berjalannya proses (preempt by time).

· Penjadwalan tanpa prioritas (pengutamaan).

·Dapat dikatakan 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. Jika proses masih running sampai akhir quantum, maka CPU akan mempreempt proses itu dan memberikannya ke proses lain. Penjadwal membutuhkannya dengan memelihara daftar proses dari runnable. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 quantum dan akan banyak peralihan proses sehingga banyak waktu terbuang.  Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma first come first served (siapa yang datang pertama, dialah yang dilayani). Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

Ketika quantum habis untuk satu proses tertentu, maka proses tersebut akan diletakkan diakhir daftar (list), seperti nampak dalam gambar berikut ini :

					Proses Saat Ini

+---+     +---+     +---+     +---+     +---+                              +---+   +---+    +---+    +---+    +---+

 :  B  :--:   F    :--:   D   :--:   G   :--:   A  :                              :  B  :--:  F   :--:   D  :--:   G   :--:  A :

+---+     +---+     +---+     +---+     +---+                              +---+   +---+    +---+    +---+    +---+

Gambar 4.1(a) : Daftar proses runnable. 

     4.1(b) : Daftar proses runnable sesudah      proses b habis quantum-nya.

Algoritma yang digunakan :

1. Jika kwanta habis 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 tetapi proses telah selesai, maka proses diakhiri dan pemroses dialihkan ke proses lain.

Diimplementasikan dengan :

1. Mengelola senarai proses ready (runnable) sesuai urutan kedatangan.

2. Ambil proses yang berada di ujung 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 depan antrian proses ready.

Masalah yang timbul adalah menentukan besar kwanta, yaitu :

· Kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround time rendah.

· 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 :

a. 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.

b. Tidak cocok untuk sistem waktu nyata apalagi hard-real-time applications.

Jadi kesimpulan yang dapat ditambahkan dari round robin adalah:

• Tiap proses memperoleh alokasi waktu CPU dlm kuantum waktu, biasanya 10-100 ms
• Setelah kuantum waktu lewat, proses dipreempted dan dimasukkan ke belakang antrian ready
• Jika ada n proses pada antrian ready dan kuantum waktu=q, maka:

§  Pada gilirannya tiap proses memperoleh 1/n waktu CPU selama q

§  Tidak ada proses yg menunuggu lebih dari (n-1)q unit waktu

• Performansi:

§ q besar   FIFO

§ q kecil   overhead untuk context switch sangat besar

Contoh :

Proses	Durasi	Urutan	Kedatangan
P1	3	1	0
P2	4	2	0
P3	3	3	0

Asumsi : kuantum waktu =  1 unit ; P1, P2, dan P3 tidak pernah diblokir

P1

P2

P3

P1

P2

P3

P1

P2

P3

P2

•  Waktu tunggu:   

P1=0+2+2=4,   

P2=1+2+2+1=6   

P3=2+2+2=6

• Waktu tunggu rata-rata:  (4+6+6)/3=5.33