mutual eksklusi pada sistem terdistribusi
TRANSCRIPT
copyrig
ht G
ilangK 2009
MUTUAL EKSKLUSI PADA SISTEM
TERDISTRIBUSIOleh :
Gilang Kurniaji
copyrig
ht G
ilangK 2009
MUTUAL EKSKLUSI
� Mutual eksklusi => Kondisi dimana hanya
mengizinkan satu buah proses yang memasuki
daerah kritisnya pada satu waktu.
� Pendekatan mutual eksklusi dapat dilakukan
dengan pendekatan algoritma, pendekatan
copyrig
ht G
ilangK 2009
dengan pendekatan algoritma, pendekatan
hardware dan dukungan sistem operasi.
� Pendekatan algoritma dapat dilakukan melalui
algoritma dekker dan algoritma peterson.
� Pendekatan hardware => interupt disabling,
instruksi mesin khusu dan instruksi exchange.
� Dukungan sistem operasi => semaphore,
messaging.
copyrig
ht G
ilangK 2009
MUTUAL EKSKLUSI TERDISTRIBUSI (MET)
� Asumsi :
� Setiap proses terdiri dari n proses, setiap proses
berada pada prosesor yan berbeda.
� Setiap proses memiliki daerah kritis yang
.membutuhkan kebijakan mutual eksklusi.
copyrig
ht G
ilangK 2009
� Kebutuhan Dasar : Jika ada satu proses
mengakses daerah kritisnya maka tidak ada
proses lain yang mengakses daerah kritis.
� Pendekatan algoritma bertujuan untuk
mengatur kebijakan mutual eksklusi.
� Mutual eksklusi menggunakan pendekatan
messaging antar proses sebagai cara utama.
copyrig
ht G
ilangK 2009
MET : KEBUTUHAN UTAMA
� Harus dipastikan tidak ada proses yang
mengakses daerah kritis secara simultan.
� Proses yang tidak memerlukan daerah kritis
harus tetap berjalan tanpa ada interferensi.
� No deadlock and Starvation.
copyrig
ht G
ilangK 2009
� No deadlock and Starvation.
� Ketika tidak ada proses di daerah kritis maka
proses yang akan masuk dapat melakukan tanpa
permisi dan gangguan.
� Proses masuk ke daerah kritis dengan waktu
yang dibatasi. Tidak ada proses yang
memonopoli daerah kritis.
copyrig
ht G
ilangK 2009
MODELOFMET
copyright GilangK 2009copyright GilangK 2009
PENDEKATAN ALGORITMA
TERSENTRALISASI
Coordina
tor
Process
Process
A
I’ll
enter
OK ‘A’
copyrig
ht G
ilangK 2009
ProcessProcess
B
Process
C
Shared
item
(critical
Section)
copyrig
ht G
ilangK 2009
ALGORITMA
PENDEKATAN TERSENTRALISASI (LANJUTAN)
� Ada satu node sebagai koordinator pengaksesan
critical section.
� Proses yang akan memasuki daerah kritis
mengirimkan pesan permintaan ke koordinator.
� Koordinator menentukan prose mana yang bisa
copyrig
ht G
ilangK 2009
� Koordinator menentukan prose mana yang bisa
mengakses daerah kritis dengan mengirimkan
balasan. Bila proses mendapatkan balasan dari
koordinator maka dapat masuk ke daerah kritis.
� Setelah proses memasuki daerah kritis maka
mengirimkan pesan release kepada koordinator,
agar daerah kritis dapat diakses oleh proses lain.
copyrig
ht G
ilangK 2009
SIFAT
PENDEKATAN TERSENTRALISASI (LANJUTAN)
� Kelebihan :
� Menjamin mutual eksklusi
� Tidak ada starvation
� Pemesanan permintaan akses
� Hanya butuh tiga pesan
copyrig
ht G
ilangK 2009
� Hanya butuh tiga pesan
� Kelemahan :
� Bila node koordinator rusak maka sistem akan crash.
� Node akan menjadi antrean, maka perlu skema
khusus bagi koordinator proses
copyrig
ht G
ilangK 2009
PENDEKATAN ALGORITMA TERDISTRIBUSI
Ciri :
� Semua proses memiliki informasi yang sama secararata-rata.
� Masing-masing node hanya memiliki gambaranparsial dan harus menentukan kebijakan dariinformasi tersebut.
copyrig
ht G
ilangK 2009
informasi tersebut.
� Seluruh node akan menjadi sama tanggung jawabnyauntuk keputusan akhir.
� Seluruh node bergantung kepada upaya rata-rata dalam pengaruh dari sebuah keputusan akhir.
� Kesalahan dari sebuah node secara umum tidakmengakibatkan seluruh sistem hancur.
� Terdapat clock umum untuk seluruh sistem denganmeregulasikan waktu even.
copyrig
ht G
ilangK 2009
SKEMA ALGORITMA TERDISTRIBUSI
Proses
AProses
Daerah
kritis
I not
use
Ok up
2 u
copyrig
ht G
ilangK 2009
AProses
C
Proses
B
I’m
inn
copyrig
ht G
ilangK 2009
MASALAH YANG TIMBUL
� Clock secara umum akan mengakibatkan adanya
deadlock, ketika ada dua proses yang
mengirimkan secara bersamaan.
� Untuk itu diperkenalkan pendekatan penanda
waktu (time stamping) untuk menyempurnakan
copyrig
ht G
ilangK 2009
waktu (time stamping) untuk menyempurnakan
algoritma terdistribusi.
� Sinkronisasi dari penanda waktu harus dipatuhi
oleh semua proses. Jika tidak akan deadlock.
copyrig
ht G
ilangK 2009
TIME STAMPING
� Timestappingmengurutkan event yang terdiri dari transmisi event. Contohnya bila ada dua buah proses A dan B, bila proses A lebihdahulu daripada proses B maka nilai timestap dari A lebih rendahdari B.
� Masing-masing event memiliki clock lokal. Clock lokal digunakansebagai penghitung sederhana yang meningkat diantara dua ataulebih event yang dieksekusi selama proses berlangsung.
� Sebuah proses meningkatkan nilai clock lokal setiap kali menerimapesan yang memiliki timestamp lebih dari nilai local clock saat ini.
copyrig
ht G
ilangK 2009
� Sebuah proses meningkatkan nilai clock lokal setiap kali menerimapesan yang memiliki timestamp lebih dari nilai local clock saat ini. Ketika proses menerima pesan, maka akan proses akan men-setcounter satu kali lebih tinggi dari nilai maksimal dari nilai clock sekarang dan waktu penanda kedatangan pesan.
� Ketika ada dua proses yang mengirimkan pesan secara bersamaandan konkuren. Prioritas ditentukan berdasarkan proses identitasuntuk menghindari deadlock. Contohnya pesan dikirim oleh P1 danP2 pada saat local clock 5. Maka yang didahulukan adalah pesanmilik P1.
� Pesan yang dikirim akan diterima oleh semua proses yang ada dalamsatu jaringan.
copyrig
ht G
ilangK 2009
PENDEKATAN ALGORITMA TERDISTRIBUSI
PENUH (FULLY DISTRIBUTED)
� Ketika proses (P1) akan mengakses ke sumber kritis, maka akan menggeneralisasi timestamp danmengirimkan pesan permintaan ke semua proses.
� Ketika proses yang lain menerima permintaan pesandari proses P1 maka akan dibalas secepatnya ataumungkin akan menolak melakukan balasan kembali.
copyrig
ht G
ilangK 2009
mungkin akan menolak melakukan balasan kembali. Hal ini tergantung ada tidaknya pesan permintaanyang telah dibalas sebelumnya.
� Ketika proses P1 telah mendapatkan balasan darisemua proses maka ia akan dapat masuk ke daerahkritisnya.
� Saat sudah keluar dari daerah kritisnya maka prosesP1 akan mengirimkan pesan pelepasan keseluruhproses.
copyrig
ht G
ilangK 2009
LANJUTAN
Pembalasan oleh proses didasarkan pada :
� Jika Proses berada dalam daerah kritis maka akanmenunda pengiriman pesan balasan ke proses yang meminta.
� Jika proses tidak menunggu untuk memasukkanbagian kritis (tidak mengeluarkan sebuah
copyrig
ht G
ilangK 2009
bagian kritis (tidak mengeluarkan sebuahpermintaan tetap) akan mentransmisikan balasan.
� Jika proses menunggu untuk memasukkan daerahkritis namun belum dilakukan maka ia akanmemeriksa timestamp yang ada pada dirinya. Jika Ts lebih besar dari waktu pada saat dia mengirimkanpesan permintaan maka pembalasan pesan akanditunda, jika tidak maka balasan akan dikirimsegera.
copyrig
ht G
ilangK 2009
SIFAT ALGORITMA TERDISTRIBUSI
SEMPURNA
� Kelebihan
� Free Deadlock
� Free Starvation
� Ensure Mutual Exclusion
� Kelemahan
� Karena setiap proses harus mengetahui keadaan dan
copyrig
ht G
ilangK 2009
� Karena setiap proses harus mengetahui keadaan danidentitas dari proses yang lain. Maka kegiatanpenambahan dan penghapusan proses menjadi kompleks.
� Bila satu proses rusak, maka seluruh sistem akan kolaps. Hal ini dapat diatasi dengan memonitoring secara holistic dan terus menerus terhadap semua proses.
� Proses yang tidak harus memasuki wilayah kritisnyaharus menghentikan sementara kegiatannya untukmemberikan kesempatan proses lain memasukki daerahkritis. Hal ini berpengaruh pada performa dari sistem
copyrig
ht G
ilangK 2009
SKEMASISTEMTERDISTRIBUSISEMPURNA
copyright GilangK 2009copyright GilangK 2009
PENDEKATAN TOKEN PASING
� Menggunakan logika cincin untuk
mendistribusikan token ke proses selanjutnya.
� Satu token hanya dipegang oleh satu proses. Dan
proses yang berhak masuk ke daerah kritis
adalah proses pembawa token.
copyrig
ht G
ilangK 2009
adalah proses pembawa token.
� Ketika telah selesai memasuki daerah kritis,
proses mengirim token ke proses selanjutnya.
� Saat proses akan membutuhkan daerah kritis
dan tidak membawa token. Maka akan
mengirimkan pesan ke seluruh proses dan
menunggu untuk gilirannya.
copyrig
ht G
ilangK 2009
SKEMA TOKEN PASSING
A
C
B
h
Sorry I
reguest
first dude
copyrig
ht G
ilangK 2009
f
E
D
C
gi’mfinish
I’ll pass
it
I need
copyrig
ht G
ilangK 2009
SIFAT TOKEN PASSING
� Kelebihan
� Tidak ada starvation
� Terpenuhinya mutual eksklusi.
� Pada saat kondisi terburuk sekalipun, tidak adaproses yang terhenti hanya untuk menunggu proseslain memasuki daerah kritisnya.
copyrig
ht G
ilangK 2009
lain memasuki daerah kritisnya.
� Kelemahan
� Kemungkinan hilangnya token diantara proses. Sulitmelakukan pencarian dan regenerasi token.
� Jika proses crash, maka sulit dideteksi. Dan ketikaada proses yang mati tidak dapat dideteksi olehproses sebelahnya karena sistem ini terlalu mudahdalam melakukan recover.
copyrig
ht G
ilangK 2009
KESIM
PULAN
copyright GilangK 2009
�None is Robust to System Crash
copyright GilangK 2009
DAFTAR RUJUKAN
� Stalling, William.2005. Sistem Operasi :Internal
dan Prinsip Prinsip Perancangan Jilid 1 edisi
keempat.Jakarta : PT Indeks Kelompok
Gramedia.
� Stalling, William.2005. Sistem Operasi :Internal
copyrig
ht G
ilangK 2009
� Stalling, William.2005. Sistem Operasi :Internal
dan Prinsip Prinsip Perancangan Jilid 2 edisi
keempat.Jakarta : PT Indeks Kelompok
Gramedia.
� Fornacario, William.2003. Operating System
Mutual Exclusion in Distributed System.pdf,
(Online), diakses pada 5 Desember 2009
copyrig
ht G
ilangK 2009