Mutual Eksklusi Pada Sistem Terdistribusi
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Mutual Eksklusi Pada Sistem Terdistribusi as PDF for free.
More details
- Words: 1,221
- Pages: 21
Oleh : Gilang Kurniaji
copyright GilangK 2009
MUTUAL EKSKLUSI PADA SISTEM TERDISTRIBUSI
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 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.
copyright GilangK 2009
MUTUAL EKSKLUSI TERDISTRIBUSI (MET)
Asumsi :
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.
copyright GilangK 2009
Setiap proses terdiri dari n proses, setiap proses berada pada prosesor yan berbeda. Setiap proses memiliki daerah kritis yang .membutuhkan kebijakan mutual eksklusi.
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. 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.
copyright GilangK 2009
MODEL OF MET
copyright GilangK 2009
PENDEKATAN ALGORITMA TERSENTRALISASI OK ‘A’
I’ll enter
Coordina tor Process Process B Shared item (critical Section)
Process C
copyright GilangK 2009
Process A
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 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.
copyright GilangK 2009
SIFAT PENDEKATAN TERSENTRALISASI (LANJUTAN)
Kelebihan :
Kelemahan : Bila node koordinator rusak maka sistem akan crash. Node akan menjadi antrean, maka perlu skema khusus bagi koordinator proses
copyright GilangK 2009
Menjamin mutual eksklusi Tidak ada starvation Pemesanan permintaan akses Hanya butuh tiga pesan
PENDEKATAN ALGORITMA TERDISTRIBUSI
copyright GilangK 2009
Ciri : Semua proses memiliki informasi yang sama secara rata-rata. Masing-masing node hanya memiliki gambaran parsial dan harus menentukan kebijakan dari informasi tersebut. Seluruh node akan menjadi sama tanggung jawabnya untuk keputusan akhir. Seluruh node bergantung kepada upaya rata-rata dalam pengaruh dari sebuah keputusan akhir. Kesalahan dari sebuah node secara umum tidak mengakibatkan seluruh sistem hancur. Terdapat clock umum untuk seluruh sistem dengan meregulasikan waktu even.
SKEMA ALGORITMA TERDISTRIBUSI
Proses A
I not use Daerah kritis
Proses C
I’m inn Proses B
copyright GilangK 2009
Ok up 2u
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 algoritma terdistribusi. Sinkronisasi dari penanda waktu harus dipatuhi oleh semua proses. Jika tidak akan deadlock.
copyright GilangK 2009
TIME STAMPING
copyright GilangK 2009
Timestapping mengurutkan event yang terdiri dari transmisi event. Contohnya bila ada dua buah proses A dan B, bila proses A lebih dahulu daripada proses B maka nilai timestap dari A lebih rendah dari B. Masing-masing event memiliki clock lokal. Clock lokal digunakan sebagai penghitung sederhana yang meningkat diantara dua atau lebih event yang dieksekusi selama proses berlangsung. Sebuah proses meningkatkan nilai clock lokal setiap kali menerima pesan yang memiliki timestamp lebih dari nilai local clock saat ini. Ketika proses menerima pesan, maka akan proses akan men-set counter satu kali lebih tinggi dari nilai maksimal dari nilai clock sekarang dan waktu penanda kedatangan pesan. Ketika ada dua proses yang mengirimkan pesan secara bersamaan dan konkuren. Prioritas ditentukan berdasarkan proses identitas untuk menghindari deadlock. Contohnya pesan dikirim oleh P1 dan P2 pada saat local clock 5. Maka yang didahulukan adalah pesan milik P1. Pesan yang dikirim akan diterima oleh semua proses yang ada dalam satu jaringan.
PENDEKATAN ALGORITMA TERDISTRIBUSI PENUH (FULLY DISTRIBUTED)
copyright GilangK 2009
Ketika proses (P1) akan mengakses ke sumber kritis, maka akan menggeneralisasi timestamp dan mengirimkan pesan permintaan ke semua proses. Ketika proses yang lain menerima permintaan pesan dari proses P1 maka akan dibalas secepatnya atau mungkin akan menolak melakukan balasan kembali. Hal ini tergantung ada tidaknya pesan permintaan yang telah dibalas sebelumnya. Ketika proses P1 telah mendapatkan balasan dari semua proses maka ia akan dapat masuk ke daerah kritisnya. Saat sudah keluar dari daerah kritisnya maka proses P1 akan mengirimkan pesan pelepasan keseluruh proses.
LANJUTAN
copyright GilangK 2009
Pembalasan oleh proses didasarkan pada : Jika Proses berada dalam daerah kritis maka akan menunda pengiriman pesan balasan ke proses yang meminta. Jika proses tidak menunggu untuk memasukkan bagian kritis (tidak mengeluarkan sebuah permintaan tetap) akan mentransmisikan balasan. Jika proses menunggu untuk memasukkan daerah kritis namun belum dilakukan maka ia akan memeriksa timestamp yang ada pada dirinya. Jika Ts lebih besar dari waktu pada saat dia mengirimkan pesan permintaan maka pembalasan pesan akan ditunda, jika tidak maka balasan akan dikirim segera.
SIFAT ALGORITMA TERDISTRIBUSI SEMPURNA
Kelebihan Free Deadlock Free Starvation Ensure Mutual Exclusion
Kelemahan Karena setiap proses harus mengetahui keadaan dan identitas dari proses yang lain. Maka kegiatan penambahan 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 kritisnya harus menghentikan sementara kegiatannya untuk memberikan kesempatan proses lain memasukki daerah kritis. Hal ini berpengaruh pada performa dari sistem
copyright GilangK 2009
SKEMA SISTEM TERDISTRIBUSI SEMPURNA
copyright 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. 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.
copyright GilangK 2009
SKEMA TOKEN PASSING Sorry I reguest first dude copyright GilangK 2009
A
B
h C
I need
g
i’m finish
D f E I’ll pass it
SIFAT TOKEN PASSING
Kelebihan Tidak ada starvation Terpenuhinya mutual eksklusi. Pada saat kondisi terburuk sekalipun, tidak ada proses yang terhenti hanya untuk menunggu proses lain memasuki daerah kritisnya.
Kelemahan Kemungkinan hilangnya token diantara proses. Sulit melakukan pencarian dan regenerasi token. Jika proses crash, maka sulit dideteksi. Dan ketika ada proses yang mati tidak dapat dideteksi oleh proses sebelahnya karena sistem ini terlalu mudah dalam melakukan recover.
copyright GilangK 2009
None is Robust to System Crash
KESIMPULAN
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 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
copyright GilangK 2009
copyright GilangK 2009
MUTUAL EKSKLUSI PADA SISTEM TERDISTRIBUSI
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 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.
copyright GilangK 2009
MUTUAL EKSKLUSI TERDISTRIBUSI (MET)
Asumsi :
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.
copyright GilangK 2009
Setiap proses terdiri dari n proses, setiap proses berada pada prosesor yan berbeda. Setiap proses memiliki daerah kritis yang .membutuhkan kebijakan mutual eksklusi.
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. 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.
copyright GilangK 2009
MODEL OF MET
copyright GilangK 2009
PENDEKATAN ALGORITMA TERSENTRALISASI OK ‘A’
I’ll enter
Coordina tor Process Process B Shared item (critical Section)
Process C
copyright GilangK 2009
Process A
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 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.
copyright GilangK 2009
SIFAT PENDEKATAN TERSENTRALISASI (LANJUTAN)
Kelebihan :
Kelemahan : Bila node koordinator rusak maka sistem akan crash. Node akan menjadi antrean, maka perlu skema khusus bagi koordinator proses
copyright GilangK 2009
Menjamin mutual eksklusi Tidak ada starvation Pemesanan permintaan akses Hanya butuh tiga pesan
PENDEKATAN ALGORITMA TERDISTRIBUSI
copyright GilangK 2009
Ciri : Semua proses memiliki informasi yang sama secara rata-rata. Masing-masing node hanya memiliki gambaran parsial dan harus menentukan kebijakan dari informasi tersebut. Seluruh node akan menjadi sama tanggung jawabnya untuk keputusan akhir. Seluruh node bergantung kepada upaya rata-rata dalam pengaruh dari sebuah keputusan akhir. Kesalahan dari sebuah node secara umum tidak mengakibatkan seluruh sistem hancur. Terdapat clock umum untuk seluruh sistem dengan meregulasikan waktu even.
SKEMA ALGORITMA TERDISTRIBUSI
Proses A
I not use Daerah kritis
Proses C
I’m inn Proses B
copyright GilangK 2009
Ok up 2u
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 algoritma terdistribusi. Sinkronisasi dari penanda waktu harus dipatuhi oleh semua proses. Jika tidak akan deadlock.
copyright GilangK 2009
TIME STAMPING
copyright GilangK 2009
Timestapping mengurutkan event yang terdiri dari transmisi event. Contohnya bila ada dua buah proses A dan B, bila proses A lebih dahulu daripada proses B maka nilai timestap dari A lebih rendah dari B. Masing-masing event memiliki clock lokal. Clock lokal digunakan sebagai penghitung sederhana yang meningkat diantara dua atau lebih event yang dieksekusi selama proses berlangsung. Sebuah proses meningkatkan nilai clock lokal setiap kali menerima pesan yang memiliki timestamp lebih dari nilai local clock saat ini. Ketika proses menerima pesan, maka akan proses akan men-set counter satu kali lebih tinggi dari nilai maksimal dari nilai clock sekarang dan waktu penanda kedatangan pesan. Ketika ada dua proses yang mengirimkan pesan secara bersamaan dan konkuren. Prioritas ditentukan berdasarkan proses identitas untuk menghindari deadlock. Contohnya pesan dikirim oleh P1 dan P2 pada saat local clock 5. Maka yang didahulukan adalah pesan milik P1. Pesan yang dikirim akan diterima oleh semua proses yang ada dalam satu jaringan.
PENDEKATAN ALGORITMA TERDISTRIBUSI PENUH (FULLY DISTRIBUTED)
copyright GilangK 2009
Ketika proses (P1) akan mengakses ke sumber kritis, maka akan menggeneralisasi timestamp dan mengirimkan pesan permintaan ke semua proses. Ketika proses yang lain menerima permintaan pesan dari proses P1 maka akan dibalas secepatnya atau mungkin akan menolak melakukan balasan kembali. Hal ini tergantung ada tidaknya pesan permintaan yang telah dibalas sebelumnya. Ketika proses P1 telah mendapatkan balasan dari semua proses maka ia akan dapat masuk ke daerah kritisnya. Saat sudah keluar dari daerah kritisnya maka proses P1 akan mengirimkan pesan pelepasan keseluruh proses.
LANJUTAN
copyright GilangK 2009
Pembalasan oleh proses didasarkan pada : Jika Proses berada dalam daerah kritis maka akan menunda pengiriman pesan balasan ke proses yang meminta. Jika proses tidak menunggu untuk memasukkan bagian kritis (tidak mengeluarkan sebuah permintaan tetap) akan mentransmisikan balasan. Jika proses menunggu untuk memasukkan daerah kritis namun belum dilakukan maka ia akan memeriksa timestamp yang ada pada dirinya. Jika Ts lebih besar dari waktu pada saat dia mengirimkan pesan permintaan maka pembalasan pesan akan ditunda, jika tidak maka balasan akan dikirim segera.
SIFAT ALGORITMA TERDISTRIBUSI SEMPURNA
Kelebihan Free Deadlock Free Starvation Ensure Mutual Exclusion
Kelemahan Karena setiap proses harus mengetahui keadaan dan identitas dari proses yang lain. Maka kegiatan penambahan 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 kritisnya harus menghentikan sementara kegiatannya untuk memberikan kesempatan proses lain memasukki daerah kritis. Hal ini berpengaruh pada performa dari sistem
copyright GilangK 2009
SKEMA SISTEM TERDISTRIBUSI SEMPURNA
copyright 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. 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.
copyright GilangK 2009
SKEMA TOKEN PASSING Sorry I reguest first dude copyright GilangK 2009
A
B
h C
I need
g
i’m finish
D f E I’ll pass it
SIFAT TOKEN PASSING
Kelebihan Tidak ada starvation Terpenuhinya mutual eksklusi. Pada saat kondisi terburuk sekalipun, tidak ada proses yang terhenti hanya untuk menunggu proses lain memasuki daerah kritisnya.
Kelemahan Kemungkinan hilangnya token diantara proses. Sulit melakukan pencarian dan regenerasi token. Jika proses crash, maka sulit dideteksi. Dan ketika ada proses yang mati tidak dapat dideteksi oleh proses sebelahnya karena sistem ini terlalu mudah dalam melakukan recover.
copyright GilangK 2009
None is Robust to System Crash
KESIMPULAN
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 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
copyright GilangK 2009
Related Documents
Mutual Eksklusi Pada Sistem Terdistribusi
July 2020 6
Jenis Sistem Operasi Terdistribusi
May 2020 23
1_pengenalan Sistem Terdistribusi
May 2020 8
Sekilas Sistem Terdistribusi
June 2020 5
Sistem File Terdistribusi
June 2020 15
Sistem Terdistribusi - Tcp Ip
June 2020 13More Documents from "Djoko Triw"
Mutual Eksklusi Pada Sistem Terdistribusi
July 2020 6
Kata Pengantar.docx
April 2020 8
Lembar Pengesahan.docx
April 2020 8
1-s2.0-s0268401216301694-main
August 2019 14
Laporan Kp.docx
April 2020 8