Apa itu Dispatching Algorithm ?

Kali ini saya kembali membahasa mengenai sistem operasi namun ternyata didalamnya terdapat algoritma yang memanage penjadwalan kerja suatu proses atau sebuah thread pada sistem operasi. Dispatching Algorithm merupakan sebuah algoritma penjadwalan jangka pendek (short-therm scheduller) yang bertugas dalam memanage kerja suatu proses atau thread yang terjadi pada sistem operasi. Dispatching Algorithm adalah algoritma yang berperan penting dalam teknologi processor yang mengatur jalannya suatu proses yang berurutan pada suatu antrian yang dapat mengeksekusi setiap thread pada sistem operasi dengan dua processor, dengan kata lain algoritma ini digunakan dalam sistem cara kerja CPU untuk mengeksekusi suatu proses yang terdiri dari beberapa thread berbeda secara berurutan sesuai urutan antrian. 

Sementara itu beberapa algoritma yang terdapat dalam algoritma penjadwalan CPU sbb :

• Algoritma FIFO (First-in, First-out) : merupakan algoritma yang menjalankan proses-proses yang telah diberi waktu pemroses yang diurutkan berdasarkan waktu kedatangan proses-proses tersebut menuju sistem, setelah masing-masing proses mendapat jatah waktu pemroses barulah proses dijalankan oleh processor hingga selesai. (Algoritma nonpreemptive)
• Algoritma SJF (Shortest Job First) : merupakan algoritma yang mengatur proses berdasarkan prioritas yang tinggi yang telah dijadwalkan sebelumnya secara FIFO atau FCFS (First-come, First-serve), mekanisme SJF ini lebih kepada mendahulukan penjadwalan proses yang selesai terlebih dahulu dalam jangka waktu terpendek sampai selesai setelah itu SJF akan mengeksekusi penjadwalan selanjutnya dengan waktu terpendek lainnya begtitu seterusnya hingga semua proses selesai dijalankan. (Algoritma nonpreemptive)
• Algoritma PS (Priority Schedulling) : merupakan algoritma yang memberi suatu prioritas pada setiap proses dan proses yang mempunyai prioritas tertinggi memiliki waktu pemroses yang akan dijalankan atau dieksekusi terlebih dahulu (running). (Algoritma preemptive)
• Algoritma RR (Round-robin) : merupakan algoritma yang menganggap semua proses penting untuk dieksekusi sehingga pada masing-masing proses diberi sejumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice tempat dimana proses tersebut akan dijalankan. Proses akan berjalan selama satu kwanta yang kemudian penjadwalan akan mengalihkan pada pemroses dan akan mengeksekusi proses berikutnya selama 1 kwanta begitu seterusnya hingga kembali pada proses pertama dan berulang. (Algoritma preemptive)

Penggambara algoritma penjadwalan pada CPU :

Algoritma FIFO

Misal  : Terdapat tiga proses  P₁ ,  P₂ ,  &  P₃ 

Contoh :

Gant chart sesuai antrian konsep FIFO :

 

Maka :  

• Waktu tunggu untuk P₁ adalah 0, P₂  adalah 24 dan P₃ adalah 27 
• Rata-rata waktu tunggu adalah ( P₁ +   P₂ +  P₃  ) / 3 = ( 0 + 24 + 27 ) / 3 = 17 milidetik
• Jika urutan prosesnya   P₂ ,  P₃ , P₁ maka ( P₂ +  P₃ +  P₁  ) / 3 = ( 6 + 0 + 3 ) / 3 = 3 milidetik. Gambar Gant Chartnya : 

 

Algoritma SJF

Misal : Terdapat empat proses P₁ ,  P₂ ,  P₃ , & P₄

Contoh :

Cara 1

 

Cara 2 

 

Pada contoh diatas cara satu dan cara dua mempunyai urutan proses yang berbeda dengan jumlah urutan kwanta yang berbeda pula yaitu : 

• Pada cara 1 :  P₁ =  8 ,  P₂ = 7 ,  P₃ = 6, dan P₄ = 5 dengan urutan proses P₁ ,  P₂ ,  P₃ ,  P₄
• Pada cara 2 : P₁  =  8 ,  P₂ = 7 ,  P₃ = 6, dan P₄ = 5 dengan urutan proses  P₄ ,  P₃ ,  P₂ , P₁

Maka :

• Tabel penyelesaian 

 

Penjelasan :

• Kedua cara menghasilkan turn arround time yang berbeda.
• Cara penghitungan :

P₁ = P₁

P₂ = P₁  + P₂

P₃ = P₁  + P₂ + P₃

P₄ = P₁  + P₂ + P₃ + P₄

Dimana : P₁ =  8 ,  P₂ = 7 ,  P₃ = 6, dan P₄ = 5

Algoritma PS

 

Misal : Terdapat empat proses P₁ ,  P₂ ,  P₃ ,  P₄ , &  P₅

Contoh :

Grant chartnya sesuai dengan algoritma PS :

Karena algoritma PS mendahulukan proses yang akan di running terlebih dahulu dilihat dari jumlah parity maka :

• Waktu tunggu untuk P₁ adalah 6, P₂  adalah 0,  P₃ adalah 16, P₄ adalah 18 dan P₅ adalah 1
• Rata-rata waktu tunggu adalah ( P₁ +   P₂ +  P₃+  P₄ +  P₅  ) / 5 = ( 6 + 0 + 16 + 18 + 1 ) / 5 = 8,2 milidetik

Algoritma RR 

Misal  : Terdapat tiga proses  P₁ ,  P₂ ,  &  P₃ dengan quantum time 4 milidetik

Contoh :

Grant chartnya sesuai dengan algoritma RR :

  

Maka :

• Waktu tunggu untuk P₁ adalah 6, P₂  adalah 4, dan  P₃ adalah 7
• Rata-rata waktu tunggu adalah ( P₁ +   P₂ +  P₃ ) / 3 = ( 6 + 4 + 7 ) / 3 = 5,66 milidetik

Semoga bermanfaat :)