Sistem Operasi Terdistribusi Sub Topik: Koordinasi Terdistribusi

Pengurutan Event
• Pengurutan event sangat diperlukan, untuk alokasi resources

• Pada DS tidak ada memori dan clock milik bersama pengurutan event

bersifat relatif terhadap waktu (relasi happened before)

Relasi Happened Before

• Aturan:

– Jika A dan B adalah event pada proses yg sama, dan A dieksekusi sebelum

B, maka A ke B

– Jika A adalah event pengiriman pesan oleh satu proses dan B adalah event

penerimaan pesan oleh proses lain, maka A ke B

– Jika A ke B dan B ke C, maka A ke C

– Relasi ke bersifat irreleflexive partial ordering

– Jika A ke B, mungkin A dan B saling mempengaruhi

– Jika event A dan B tidak terkait dgn relasi , maka ke A dan B konkuren (saling

tidak mempengaruhi)

Implementasi

• Idealnya, diperlukan satu clock milik bersama atau

kumpulan clock yg disinkronisasikan

• Global ordering menggunakan timestamp:

– untuk tiap pasang A dan B, jika A ke B maka timestamp A <

timestamp B

• Clock Lojik, dapat diimplementasikan sbg counter yg

diinkremen setiap eksekusi event berurutan pada satu

proses

– Tiap proses Pi memiliki clock lojik LCi

– Pada proses Pi , jika A terjadi sebelum B maka LCi (A) < LCi (B)

– Antar proses, jika proses Pi menerima pesan (event B) dgn

timestamp t sedangkan LCi (B) < t, maka Pi harus memajukan

clocknya sehingga LCi (B) = t + 1

Artikel terkait :

• Mutual Exclusion

• Atomisitas

• Concurrency Control