Algoritma dalam Load Balancing

Berikut algoritma dalam load balancing :

a)      Round Robin and Random Algorithms

Pada algoritma Round Robin and Random proses dibagi secara merata antara semua prosesor. Setiap proses baru yang ditugaskan untuk prosesor baru untuk putaran robin. Urutan proses alokasi dipertahankan pada setiap prosesor lokal independen dari alokasi dari prosesor. Dengan algoritma round robin sama beban kerja diharapkan untuk bekerja dengan baik. Round Robin dan skema Acak  bekerja dengan baik dengan jumlah proses lebih besar dari jumlah prosesor .

Keuntungan dari algoritma Round Robin adalah bahwa hal itu tidak memerlukan komunikasi antarproses. Round Robin dan algoritma Acak keduanya bisa mencapai kinerja terbaik di antara semua algoritma load balancing untuk aplikasi tertentu tujuan khusus. Dalam Robin Round umum dan Acak tidak diharapkan untuk  mencapai kinerja yang baik dalam kasus umum.

b)       Algorithm Middle Manager

Dalam algoritma ini , prosesor pusat memilih host untuk proses baru. Prosesor minimal dimuat tergantung pada beban keseluruhan yang dipilih ketika proses dibuat. Load manajer memilih host untuk proses baru sehingga beban prosesor menegaskan ke tingkat yang sama sebanyak mungkin. Dari informasi tangan di manajer sistem pembebanan beban negara pusat membuat load balancing penghakiman. Informasi ini diperbarui oleh prosesor remote, yang mengirim pesan setiap kali beban pada mereka perubahan. Informasi ini dapat bergantung pada menunggu proses induk penyelesaian proses anak-anaknya, akhir eksekusi paralel Manajer load load balancing membuat keputusan berdasarkan informasi beban sistem, sehingga keputusan terbaik ketika proses dibuat. Tingginya tingkat komunikasi antar-proses yang bisa membuat negara bottleneck. Algoritma ini diharapkan untuk melakukan lebih baik daripada aplikasi paralel, terutama bila kegiatan dinamis diciptakan oleh

host yang berbeda.

c)      Threshold Algorithm

Menurut algoritma ini, proses ditugaskan segera setelah penciptaan ke host. Host untuk proses baru dipilih secara lokal tanpa mengirim pesan jarak jauh. Setiap prosesor menyimpan salinan pribadi dari beban sistem. Beban prosesor bisa mencirikan oleh salah satu dari tiga tingkatan: underloaded, medium dan Overloaded. Dua parameter ambang tunder dan Tupper dapat digunakan untuk menggambarkan level.

Pada awalnya, semua prosesor dianggap berada di bawah dimuat. Ketika keadaan beban prosesor melebihi batas tingkat beban, maka mengirimkan pesan tentang negara beban baru untuk semua prosesor terpencil, secara teratur memperbarui mereka untuk keadaan beban aktual dari seluruh sistem. Jika negara lokal tidak kelebihan beban maka proses dialokasikan secara lokal. Jika tidak, remote di bawah prosesor dimuat dipilih, dan jika tidak ada tuan rumah tersebut terjadi, prosesnya juga dialokasikan secara lokal. Algoritma Ambang batas memiliki proses komunikasi yang rendah antar dan sejumlah besar alokasi proses lokal. Kemudian menurunkan alokasi overhead proses remote dan overhead dari pengaksesan memori jauh, yang menyebabkan peningkatan kinerja.

Kelemahan dari algoritma ini adalah bahwa semua proses dialokasikan secara lokal ketika semua prosesor terpencil kelebihan beban. Sebuah beban pada satu prosesor kelebihan beban bisa jauh lebih tinggi dari pada prosesor kelebihan beban lain, menyebabkan gangguan signifikan dalam load balancing, dan meningkatkan waktu eksekusi sebuah aplikasi Dinamis

d)     Central Queue Algorithm

Central Queue Algorithm  bekerja pada prinsip distribusi dinamis. Ini pusat kegiatan baru dan permintaan yang tidak terpenuhi sebagai antrian FIFO pada host utama. Setiap aktivitas baru tiba di queue manager dimasukkan ke dalam antrian. Kemudian, setiap kali permintaan untuk kegiatan diterima oleh manajer antrian, ia bisa menghilangkan kegiatan pertama dari antrian dan mengirimkannya ke pemohon. Jika tidak ada kegiatan siap dalam antrian, permintaan buffer, sampai aktivitas baru tersedia. Jika aktivitas baru tiba di queue manager sementara ada terjawab permintaan dalam antrian, permintaan pertama yang akan dihapus dari antrian dan kegiatan baru yang ditugaskan untuk itu.

Ketika beban prosesor berada di bawah ambang batas, manajer beban lokal mengirim permintaan untuk aktivitas baru kepada manajer beban pusat. Manajer beban pusat menjawab permintaan segera jika suatu aktivitas siap ditemukan dalam antrian proses-permintaan, atau antrian permintaan sampai aktivitas baru tiba.

e)      Local Queue Algorithm

Fitur utama dari algoritma ini adalah dukungan proses migrasi dinamis. Ide dasar dari algoritma antrian lokal alokasi statis dari semua proses baru dengan proses migrasi yang diprakarsai oleh tuan rumah pada saat beban yang berada di bawah ambang batas, adalah parameter yang ditetapkan pengguna dari algoritma.

Parameter yang mendefinisikan jumlah minimal proses siap manajer beban upaya untuk memberikan pada setiap prosesor. Awalnya, proses-proses baru yang dibuat pada host utama dialokasikan pada semua host di bawah dimuat. Jumlah kegiatan paralel yang diciptakan oleh paralel pertama membangun pada host utama biasanya cukup untuk alokasi pada semua host remote. Sejak saat itu, semua proses dibuat pada host utama dan semua host lainnya dialokasikan secara lokal.

Ketika tuan rumah yang mendapat di bawah dimuat, manajer beban lokal berusaha untuk mendapatkan beberapa proses dari host remote. Ini secara acak mengirimkan permintaan dengan jumlah proses siap lokal untuk manajer beban terpencil. Ketika seorang manajer beban menerima permintaan seperti itu, hal itu membandingkan nomor lokal proses siap dengan jumlah yang diterima. Jika yang pertama lebih besar dari yang terakhir, maka beberapa proses yang berjalan dipindahkan ke pemohon dan konfirmasi afirmatif dengan jumlah proses yang ditransfer dikembalikan.

Parameter algoritma load balancing

Kinerja algoritma load balancing berbagai diukur dengan parameter berikut :

a)      Overload Rejection

Jika Load Balancing tidak tindakan overload mungkin diperlukan tambahan penolakan. Ketika situasi overload berakhir maka langkah-langkah overload pertama penolakan dihentikan. Setelah periode penjaga singkat Load Balancing juga ditutup.

b)      Fault Toleran

Parameter ini memberikan bahwa algoritma dapat mentolerir kesalahan berliku-liku atau tidak. Hal ini memungkinkan algoritma untuk terus beroperasi dengan benar dalam hal kegagalan beberapa. Jika kinerja menurun algoritma, menurunkan sebanding dengan keseriusan kegagalan, bahkan kegagalan kecil dapat menyebabkan kegagalan total load balancing.

c)      Forecasting Accuracy

Peramalan adalah derajat kesesuaian hasil dihitung ke nilai sebenarnya yang akan dihasilkan setelah eksekusi. Algoritma statis memberikan tingkat akurasi yang lebih dari algoritma yang dinamis seperti dalam asumsi yang paling bekas dibuat selama waktu kompilasi dan di kemudian ini dilakukan selama eksekusi.

d)     Stabilitas

Stabilitas bisa dicirikan dalam hal penundaan dalam transfer informasi antara prosesor dan keuntungan dalam algoritma load balancing dengan mendapatkan performa yang lebih cepat dengan jumlah waktu tertentu.

e)      Sentralisasi atau Desentralisasi

Skema terpusat menyimpan informasi global di node yang ditunjuk. Semua nodepengirim atau penerima mengakses node yang ditunjuk untuk menghitung jumlah beban-transfer dan juga untuk memeriksa bahwa tugas harus dikirim atau diterima dari. Dalamload balancing didistribusikan, setiap node menjalankan keseimbangan secara terpisah.Node menganggur dapat memperoleh beban selama runtime dari antrian global bersama proses.