Koordinasi Terdistribusi

Sistem terdistribusi adalah suatu kesatuan dari elemen-elemen yang saling berinteraksi secara sistematis dan teratur untuk mendistribusikan data, informasi, obyek dan layanan dari dan kepada pengguna yang terkait didalamnya dengan melakukan pengiriman pesan (message passing).  Agar tidak terjadi konflik saat mendistribusikan data, maka diperlukan sinkronisasi dan koordinasi antar komputer.  Dalam sistem terdistribusi berbasis koordinasi, fokusnya adalah pada bagaimana koordinasi antara proses berlangsung. Jika ada lebih dari satu proses yang siap running, maka Sistem Operasi akan menentukan salah satu proses untuk running lebih dulu.

Aktivitas Koordinasi Terdistribusi :

1.       Pengurutan Event

          • Memori & clock tdk tunggal

          • Tdk mungkin menyatakan urutan dua kejadian

• Hanya dpt ditentukan partial ordering (pengurutan sebagian) relasi Happened-Before (Hukum sebab-akibat : suatu pesan dapat diterima setelah pesan tersebut dikirim. Jika A dan B adalah event pada proses yg sama, dan A dieksekusi sebelum B, maka A → B)

2.       Mutual Exclusion

Pendekatan Tersentralisasi (Centralized)

• Salah satu proses dipilih sebagai koordinator utk mengatur entri ke CS

• Menggunakan pesan request-reply-release untuk masuk ke CS

• (+): menjamin mutex, dpt menjamin fairness (no starvation)

• (--): jika koordinator gagal → perlu dipilih kembali

Pendekatan Terdistribusi Penuh (Fully Distributed)

• Untuk masuk ke CS, proses mengirimkan pesan request (Pi, TS) ke

semua proses

• Pengiriman reply oleh Pi ke Pk :

– Jika Pi sedang berada di CS, reply ke Pk ditunda

– Jika Pi tidak akan masuk ke CS, reply langsung dikirim ke Pk

– Jika Pi akan masuk ke CS dan TS(Pi) < TS(Pk) maka reply ke Pk ditunda

• (+): menjamin mutex, bebas deadlock dan starvation

• (--): jumlah pesan minimum 2(n-1), proses harus tahu identitas semua proses lain, tidak  berfungsi jika ada proses yg gagal, mengganggu proses lain yg tidak akan masuk ke CS

Pendekatan Token Passing

• Menggunakan satu token yg beredar diantara proses

• Hanya proses yg memiliki token saat itu yg dapat masuk ke CS

• Syarat: adanya lingkaran lojik yg menghubungkan semua proses

• (+): menjamin mutex, bebas starvation

• (--): jika token gagal → perlu digenerate kembali, jika proses gagal → perlu dibentuk ring lojik baru

3.       Atomisitas

• Tiap situs memiliki koordinator transaksi yg berfungsi menjamin

atomisitas eksekusi transaksi, dengan cara:

– memulai eksekusi transaksi

– memecah menjadi beberapa sub-transaksi dan mendistribusikannya pada

situs-situs yg cocok utk dieksekusi

– mengkoordinasikan terminasi transaksi (commit, atau abort)

• Tiap situs menyimpan log untuk tujuan recovery

Protokol Two-Phase Commit (2PC)

• Semua situs yg mengeksekusi transaksi T harus memiliki hasil akhir

yg sama (commit atau abort)

• JikaT adalah transaksi yg diinisiasi pada situs Si dengan koordinator Ci

, maka setelah transaksi selesai Ci memulai protokol 2PC:

– Fase1: Ci mengirimkan pesan ke semua situs yg mengeksekusi T untuk

mengetahui transaksi commit atau abort

– Fase2: Ci menentukan hasil akhir transaksi setelah menerima respon dari

semua situs; transaksi commit jika semua situs memberi respon commit

Penanganan Kegagalan pada 2PC

• Kegagalan pada salah satu situs yg berpartisipasi

– Masalah: situs yg selesai melakukan recovery harus memeriksa

log utk menentukan status transaksi

– Jika commit, situs melakukan redo(T)

– Jika abort, situs melakukan undo(T)

• Kegagalan pada koordinator

– Masalah: situs yg berpartisipasi harus menentukan nasib T

– Jika salah satu situs berisi record atau ,

maka coordinator akan mengikuti hasilnya

– Jika ada situs yg belum berisi maka koordinator tdk

dpt memutuskan

• Kegagalan pada jaringan

– Masalah: pesan yg dikirimkan tidak sampai

– Jika beberapa link terputus dapat dilakukan partisi jaringan

4.       Concurrency Control

• Manajer transaksi berfungsi mengelola eksekusi transaksi yg

mengakses data

– Menyimpan log untuk tujuan recovery

– Berpartisipasi dalam skema kontrol-konkurensi untuk mengkoordinasi

eksekusi transaksi

Protokol Locking

• Skema nonreplikasi

– Tiap situs memiliki satu manajer lock lokal untuk mengelola permintaan

lock/unlock data yg disimpan pada situs tsb

– (+): sederhana

– (--): penanganan deadlock lebih rumit karena tdk ditangani oleh satu

Situs

• Pendekatan Koordinator Tunggal

– Ada manajer lock tunggal yg berada pada salah satu situs utk menangani

permintaan lock/unlock data

– Read dpt dilakukan pada situs mana saja yg menyimpan data

– Write dilakukan pada semua replikasi

• Protokol Mayoritas

– Tiap situs memiliki lock manajer yg mengelola data dan

duplikat data yg disimpan pd situs tsb

– Untuk melakukan lock thd data Q yg direplikasi pd

beberapa situs, transaksi mengirim request lock ke >

½ situs yg menyimpan Q

– Lock manajer menentukan lock yg dapat diberikan

– Transaksi thd data tdk dimulai sebelum kunci dari

mayoritas replika diperoleh

– (+): penanganan terdesentralisasi

– (--): penanganan deadlock perlu modifikasi, rumit

5.       Penanganan Deadlock

        ♦  Deadlock Prevention

·       Pencegahan: Faktor-faktor penyebab deadlock yang harus dicegah untuk terjadi

·       4 faktor yang harus dipenuhi untuk terjadi deadlock:

·       Mutual Exclusion: pemakaian resources.

·       Hold and Wait: cara menggunakan resources.

·       No preemption resource: otoritas/hak.

·       Circular wait: kondisi saling menunggu.

·       Jika salah satu bisa dicegah maka deadlock pasti tidak terjadi

♦  Deadlock Detection

·      Mencegah dan menghidari dari deadlock sulit  dilakukan:

·      Kurang efisien dan utilitas sistim

·      Sulit diterapkan: tidak praktis, boros resources

·      Mengizinkan sistim untuk masuk ke “state deadlock”

·      Gunakan algoritma deteksi (jika terjadi deadlock)

·      Deteksi:melihat apakah penjadwalan pemakaian resource yang tersisa masih memungkinkan berada dalam safe state (variasi “safe state”).

·      Skema recovery untuk mengembalikan ke “safe state”

6.       Algoritma Pemilihan

·      Algoritma Bully

Adalah (Gracia-Moliana 1982) algoritma yang mengijinkan proses mengalami crash pada saat terjadi pemilihan (election), meskipun pengiriman pesan antar proses adalah reliable.

Ada tiga tipe pada algoritma

ini, yaitu:

1. election message : digunakan untuk pemberitahuan akan adanya pemilihan

2. answer message : merupakan jawaban dari election message

3. coordinator message : digunakan untuk memberitahukan identitas dari proses pemilihan

Sebuah proses dimulai dengan pemilihan ketika telah diperintahkan, melewati timeout, saat coordinator gagal. Ketika sebuah proses menerima pesan coordinator proses tersebut akan menset variabelnya menjadi elected. Jika sebuah proses menerima proses election proses tersebut akan mengirim jawaban dan akan memulai proses terpilih tersebut, kecuali telah mulai sebelumnya.

·      Algoritma Ring

Tujuan dari algoritma ini adalah untuk memilih sebuah proses tunggal yang disebut koordinator, yang merupakan proses dengan identifier terbesar. Awalnya, setiap proses ditandai sebagai non-peserta dalam pemilihan. Setiap proses bisa mulai pemilihan. Hal hasil dengan menandai dirinya sebagai salah satu peserta, menempatkan para identifier dalam pemilihan pesan dan mengirimkannya kepada tetangga searah jarum jam. Ketika sebuah proses menerima pesan pemilihan, itu membandingkan pengenal dalam pesan dengan sendiri. Jika identifier yang tiba lebih besar, maka meneruskan pesan 10 tetangganya. Jika identifier yang tiba lebih kecil dan penerima bukan merupakan peserta maka pengganti pengenal sendiri dalam pesan dan ke depan itu, tetapi tidak meneruskan pesan jika sudah menjadi peserta. Pada pemilihan penerusan pesan dalam beberapa kasus, proses menandai dirinya sebagai peserta.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~

NB : Correct Me If I'm Wrong

~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Sumber :

Sumber 1

Sumber 2

Sumber 3

Sumber 4

~~~~~~~~~~~~~~~~~~~~~~~~~~~~