Algoritma Penjadwalan Round Robin dengan Contoh

Apa itu Penjadwalan Round-Robin?

Nama algoritma ini berasal dari prinsip round-robin, dimana setiap orang mendapat bagian yang sama secara bergiliran. Ini adalah algoritma penjadwalan tertua dan paling sederhana, yang banyak digunakan untuk multitasking.

Dalam penjadwalan Round-robin, setiap tugas siap dijalankan secara bergiliran hanya dalam antrian siklik untuk jangka waktu terbatas. Algoritme ini juga menawarkan eksekusi proses yang bebas kelaparan.

Karakteristik Penjadwalan Round-Robin

Berikut adalah karakteristik penting dari Penjadwalan Round-Robin:

  • Round robin adalah algoritma pre-emptive
  • CPU dialihkan ke proses berikutnya setelah interval waktu tetap, yang disebut kuantum waktu/irisan waktu.
  • Proses yang didahului ditambahkan ke akhir antrian.
  • Round robin adalah model hybrid yang digerakkan oleh jam
  • Irisan waktu harus minimum, yang ditetapkan untuk tugas tertentu yang perlu diproses. Namun, ini mungkin berbeda dari satu OS ke OS lainnya.
  • Ini adalah algoritma waktu nyata yang merespons peristiwa dalam batas waktu tertentu.
  • Round robin adalah salah satu algoritma tertua, teradil, dan termudah.
  • Metode penjadwalan yang banyak digunakan di OS tradisional.

Contoh Penjadwalan Round-robin

Pertimbangkan tiga proses berikut ini

antrian proses Waktu meledak
P1 4
P2 3
P3 5

Penjadwalan round-robin

Langkah 1) Eksekusi dimulai dengan proses P1 yang memiliki waktu burst 4. Di sini setiap proses dijalankan selama 2 detik. P2 dan P3 masih dalam antrian tunggu.

Penjadwalan round-robin

Langkah 2) Pada waktu =2, P1 ditambahkan ke akhir Antrian dan P2 mulai dijalankan

Penjadwalan round-robin


Langkah 3) Pada time=4 , P2 didahului dan ditambahkan di akhir antrian. P3 mulai dijalankan.

Penjadwalan round-robin

Langkah 4) Pada time=6 , P3 didahului dan ditambahkan di akhir antrian. P1 mulai dijalankan.

Penjadwalan round-robin

Langkah 5) Pada time=8 , P1 memiliki waktu burst 4. Eksekusi telah selesai. P2 memulai eksekusi

Penjadwalan round-robin

Langkah 6) P2 memiliki waktu burst 3. P2 telah dieksekusi selama 9 interval. Pada waktu=2, P3 menyelesaikan eksekusi. Kemudian, PXNUMX memulai eksekusi hingga selesai.

Penjadwalan round-robin

Langkah 7) Mari kita hitung waktu tunggu rata-rata untuk contoh di atas.

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

Keuntungan Penjadwalan Round-robin

Berikut kelebihan/kelebihan metode penjadwalan Round-robin:

  • Pesawat ini tidak menghadapi masalah kelaparan atau efek konvoi.
  • Semua pekerjaan mendapatkan alokasi CPU yang adil.
  • Ini menangani semua proses tanpa prioritas apa pun
  • Jika Anda mengetahui jumlah total proses dalam antrian yang dijalankan, Anda juga dapat mengasumsikan waktu respons kasus terburuk untuk proses yang sama.
  • Metode penjadwalan ini tidak bergantung pada waktu burst. Itu sebabnya ini mudah diimplementasikan pada sistem.
  • Ketika suatu proses dieksekusi pada jangka waktu tertentu, proses tersebut akan didahului, dan proses lain akan dijalankan pada jangka waktu tertentu.
  • Mengizinkan OS menggunakan metode peralihan Konteks untuk menyimpan status proses yang telah dilakukan sebelumnya.
  • Ini memberikan kinerja terbaik dalam hal waktu respons rata-rata.

Kekurangan Penjadwalan Round-robin

Berikut ini kekurangan/kekurangan menggunakan penjadwalan Round-robin:

  • Jika waktu pemotongan OS rendah, output prosesor akan berkurang.
  • Metode ini menghabiskan lebih banyak waktu pada peralihan konteks
  • Kinerjanya sangat bergantung pada kuantum waktu.
  • Prioritas tidak dapat ditetapkan untuk proses tersebut.
  • Penjadwalan round-robin tidak memberikan prioritas khusus pada tugas-tugas yang lebih penting.
  • Mengurangi pemahaman
  • Kuantum waktu yang lebih rendah menghasilkan overhead peralihan konteks yang lebih tinggi dalam sistem.
  • Menemukan kuantum waktu yang tepat adalah tugas yang cukup sulit dalam sistem ini.

Latensi Kasus Terburuk

Istilah ini digunakan untuk waktu maksimum yang dibutuhkan untuk pelaksanaan semua tugas.

  • dt = Menunjukkan waktu deteksi ketika suatu tugas dimasukkan ke dalam daftar
  • st = Menunjukkan waktu peralihan dari satu tugas ke tugas lainnya
  • et = Menunjukkan waktu pelaksanaan tugas

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

Kesimpulan

  • Nama algoritma ini berasal dari prinsip round-robin, dimana setiap orang mendapat bagian yang sama secara bergiliran.
  • Round robin adalah salah satu algoritma tertua, paling adil, dan termudah serta metode penjadwalan yang banyak digunakan secara tradisional OS.
  • Round robin adalah algoritma pre-emptive
  • Keuntungan terbesar dari metode penjadwalan round-robin adalah jika Anda mengetahui jumlah total proses dalam antrian yang dijalankan, maka Anda juga dapat mengasumsikan waktu respons kasus terburuk untuk proses yang sama.
  • Metode ini menghabiskan lebih banyak waktu pada peralihan konteks
  • Latensi kasus terburuk adalah istilah yang digunakan untuk waktu maksimum yang dibutuhkan untuk pelaksanaan semua tugas.