Mutual Exclusion
Mutual Exclusion adalah suatu cara yang menjamin jika ada sebuah proses yang menggunakan variabel atau berkas yang sama (digunakan juga oleh proses lain), maka proses lain akan dikeluarkan dari pekerjaan yang sama. Jadi, Mutual Exclusive terjadi ketika hanya ada satu proses yang boleh memakai sumber daya, dan proses lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut.
Bagian program yang sedang mengakses memori atau sumberdaya yang dipakai bersama disebut critical section / region. Kesuksesan proses-proses kongkuren memerlukan pendefinisian critical section dan memaksakan mutual exclusion diantara proses-proses kongkuren yang sedang berjalan. Pemaksaan mutual exclusion merupakan landasan pemrosesan kongkuren, namun pemaksaan mutual exclusion dapat menimbulkan 2 masalah yaitu :
- Deadlock
Adalah banyak proses yang saling menunggu hasil dari proses yang lain untuk dapat melanjutkan atau menyelesaikan tugasnya.
- Startvation
Adalah suatu proses akan menunggu suatu kejadian atau hasil suatu proses lain supaya dapat menyelesaikan tugasnya, tetapi kejadian yang ditunggu tidak pernah terjadi karena selalu diambil lebih dulu oleh proses yang lain.
Tgl akses 22 April 2013
Syarat penting solusi penjaminan mutual-exclusion adalah:
ü Bebas dari deadlock
ü Bebas dari starvation
ü Fairness
ü Fault-tolerance
Pendekatan penjaminan mutual-exclusion di sistem tersebar:
v Algoritma terpusat
v Algoritma tersebar
Algoritma Terpusat
Ø Satu proses merupakan koordinator.
Ø Waktu proses-proses lain ingin masuk critical region, proses mengirim pesan ke koordinator memberitahu critical region yang ingin dimasukinya dan meminta ijin.
Ø Jika tidak ada proses lain di critical region, koordinator mengirim balik jawaban pemberian ijin.
Ø Ketika ijin tiba, proses yang meminta segera memasuki critical region.
Ø Jika ada proses lain di critical region, koordinator menolak ijin.
Penolakan ijin dapat berupa:
Ø Mendiamkan, proses peminta blocked dan menunggu jawaban.
Ø Mengirim jawaban berupa “penolakan ijin”
Ø Mengantrikan permintaan
Keunggulan :
1. Menjamin mutual-exclusion
Karena hanya mengijinkan satu proses memasuki critical region.
2. Adil
Karena mengijinkan sesuai urutan diterimanya pesan.
3. Tak ada proses yang menunggu selamanya.
4. Mudah diimplementasikan.
5. Dapat digunakan untuk mengelola sumber daya.
Kelemahan :
1. Terdapat satu titik kegagalan
2. Jika koordinator gagal, maka gagallah seluruh sistem.
3. Koordinator dapat menjadi botlenect
4. Waktu tunda pengiriman sinkronisasi besar
Algoritma Tersebar
Klasifikasi algoritma tersebar:
o Nontoken-based algorithms
o Token based algorithms
Nontoken-Based Algorithms
Beberapa pendekatan nontoken-based algorithm:
1. Lamport’s algorithm
2. Ricart-agrawala algorithm
3. Maekawa algorithm
1. Lamport’s algorithm
Syarat :
o Perlu pengurutan total seluruh kejadian
o Untuk sembarang pasangan kejadian, tidak boleh ambigu, harus diketahui keterdahuluan kejadian.
Solusi :
o Penerapan algoritma Lamport untuk pengurutan kejadian
o Penggunaaan stempel waktu untuk proses
Algoritma :
o Ketika proses ingin memasuki critical region, proses pembangun pesan berisi nama critical region yang ingin dimasuki, nomor proses dan waktu saaat itu.
o Proses mengirim pesan ke semua proses lain, secara konseptual termasuk ke dirinya. Pengiriman pesan diasumsikan handal,yaitu setiap pesan di-ack. Jika komunikasi kelompok handal tersedia, maka komunikasi ini dapat digunakan.
o Ketika proses menerima pesan permintaan dari proses lain, aksi yang diambil bergantung state-nya berkaitan dengan critical region yang diminta. Terdapat tiga kasus yaitu :
1. Jika penerima tidak berada di critical region dan tidak ingin memasuki, penerima mengirim balik pesan OK ke pengirim.
2. Jika penerima telah berada di critical region proses tidak menjawab. Proses mengantrikan permintaan itu.
3. Jika penerima ingin memasuki critical region tapi belum melakukannya, penerima membandingkan stempel waktu pesan datang dengan pesan dikirim. Nilai terendah menang. Jika pesan datang lebih rendah, penerima mengirim pesan OK. Jika pesan mempunyai stempel waktu lebih rendah, penerima mengantrikan permintaan datang dan tak mengirim apapun.
o Setelah mengirim permintaan meminta ijin memasuki critical region, proses menunggu sampai semua proses lain memberi ijin. Begitu semua ijin dipunyai, proses memasuki critical region.
o Ketika proses keluar critical region, proses mengirim pesan OK semua proses yang diantrikan dan menghapus semuanya dari antrian.
Keunggulan :
o Dijamin tanpa deadlock atau starvation
o Tak ada satu titik kegagalan
Kelemahan :
o Jumlah pesan yang diperlukan per masuk ke critical region adalah 2(n-1),dimana n adalah jumlah proses yang terdapat di sistem.
o Menjadi terdapat n kegagalan, karena diamnya proses (meski secara tak benar) akan diinterpretasikan sebagai penolakan ijin, sehingga akan mem-block semua usaha semua proses untuk memasuki critical region.
o Pemakaian primitif komunikasi kelompok atau tiap proses harus mengelola keanggotaan kelompok termasuk proses yang memasuki, meninggalkan dan crash. Metode ini terbaik bekerja dalam sekelompok kecil proses yang tak pernah berubah keanggotaan kelompoknya.
o Karena yang memutuskan n proses maka terdapat beban jaringan yang tinggi.
2. Ricart-agrawala algorithm
Algoritma ini merupakan optimasi Lamport, memerlukan 2(N-1) pesan per eksekusi critical region waktu tunda sinkronisasi adalah T.
3.Algoritma Maekawa
Algoritma ini berbeda dengan kebanyakan penyelesaian, yaitu :
o Situs tidak perlu meminta ijin dari semua situs, tapi hanya satu subset situs. Berbeda dengan algoritma Lamport, dan algoritma Ricart-Agrawala dimana semua situs berpartisipasi dalam penyelesaian.
o Situs hanya dapat mengirim satu pesan REPLAY pada satu waktu. Situs hanya dapat mengirim pesan REPLAY setelah menerima pesan RELEASE untu REPLAY sebelumnya.
Algoritma ini memerlukan 3√N per eksekusi critical region. Waktu tunda sinkronisasi adalah 2T dapat mengakibatkan Deadlock.
Token-Based Algorithm
Satu token unik dipakai bersama diantara semua situs. Proses diijinkan memasuki critical section bila memiliki token.
Beberapa pendekatan Token-Based Algorithm :
o Token-ring algorithm
o Suzuki-Kasami’s broadcast algorithm
o Singhal’s heuristic algorithm
o Raymond’s tree-based algorithm
Algoritma Token Ring
Terdapat ring logik secara perangkat lunak.
Yang terpenting tiap proses mengetahui urutan proses berikutnya.
o Ketika ring diinisialisasi,proses O diberi token.
o Token berkeliling ring. Token melewati proses k ke proses k+1 dengan pesan point-to-point.
o Ketika proses memperoleh token dari tetangganya, proses memeriksa apakah proses tersebut sedang berusaha memasuki critical region.
§ Jika ingin memasuki, proses memasuki critical region, mengerjakan semua yang diperlukan dan meninggalkan critical region.
§ Setelah keluar, proses melewatkan token ke ring. Proses tidak diijinkan memasuki critical region yang kedua kali dengan token yang sama.
o Jika proses yang memiliki token tapi tidak ingin memasuki critical region, proses segera melewatkan token.
Keunggulan:
o Algoritma ini menjamin hanya ada satu proses yang memasuki critical region, karena hanya satu proses yang mempunyai token.
o Starvation tidak terjadi karena adanya pengurutan proses.
Kelemahan:
o Jika token hilang, token harus dibangkitkan lagi.
o Proses yang crash akan menimbulakan kesulitan.
Suzuki-Kasami’s Broadcast Algorithm
Pada algoritma ini, situs yang ingin memasuki critical regionyang tak mempunyai token membroadcast pesan REQUEST untuk token ke semua situs lain.
o Jika menerima pesan REQUEST saat mengeksekusi critical region, proses mengirim token setelah proses keluar dari critical region.
o Proses bisa memasuki critical region berulangkali sampai sistem mengirimkan token kepada situs yang meminta.
Masalah yang harus diselesaikan :
o Pembedaan antara pesan usang dan pesan saat itu.
o Penentuan situs yang mempunyai REQUEST paling perlu.
Singhal’s Heuristic Algorithm
Pada algoritma ini, masing masing situs mengelola informasi mengenai state dari situs situs lain dan menggunakannya untuk memilih sekumpulan situs yang paling berpeluang memiliki token. Situs meminta token hanya ke situs situs ini.
Algoritma ini berpotensi mengakibatkan Deadlock atau startvation. Diperlukan rancangan sehingga situs dapat memilih satu subset yang sedikitnya satu situs dijamin memegang token sebentar kemudian.
Raymond’s tree-based algorithm
Pada algoritma ini, situs- situs secara logik disusun dalam satu pohon berarah sehingga busur-busur berarah ke situs yang mempunya token. Setiap simpul yang mempunyai variabel lokal holder menunjuk ke simpul tetangga dekat pada jalur berarah ke simpul akar. Jika diikuti variabel holder di situs-situs itu, setiap situs mempunyai jalur berarah yang menuju ke situs yang memegang token.
DEADLOCK
Deadlock di sistem tersebar serupa deadlock di sistem pemproses tunggal, hanya lebih rumit. Deadlock lebih sulit dihindari, dicegah, dideteksi dan dipulihkan saat diketahui terdapat deadlock karena informasi tersebar di banyak mesin.
Deteksi Deadlock
Kebanyakan deteksi deadlock adalah dengan menemukan siklus di wait-for graph. Disana simpul menyatakan transaksi dan item data, busur menyatakan item data yang digenggam satu transaksi atau proses sedang menunggu item data. Terjadi Deadlock hanya terjadi/ terdapat di wait-for graph.
Deteksi deadlock tersebar memerlukan penemuan siklus di wait-for graph global yang tersebar di beberapa server yang terlibat pelayanan.
Deteksi deadlock pada sistem tersebar:
Ø Deteksi deadlock secara terpusat
Ø Deteksi deadlock secara tersebar
1.Deteksi Deadlock Secara Terpusat
Algoritma Deteksi Terpusat Sepenuhnya
Merupakan solusi sederhana, yaitu satu server berperan sebagai detektor deadlock global. Server-server lainnya mengirim kopain wait-for graph lokal ke detektor global. Detektor global menyusun wait-for graph global dari informasi-informasi wait-for graph lokal. Detektor global memeriksa wait-for graph global. Bila ditemukan siklus, detektor global membuat keputusan penyelesaian deadlock dan mengintruksikan server-server lain untuk membatalkan transaksi untuk penyelesaian deadlock.
Kelemahan
Bergantung pada satu server sehingga dapat menjadi bottlenect, rentan kegagalan, kurang fault-tolerence dan tidak dapat diskala menjadi sistem besar. Lalu lintas informasi sangat tinggi membebani jaringan.
2.Deteksi Deadlock Secara Tersebar
Pada algoritma deteksi deadlock tersebar, semua situs secara bersama bekerja mendeteksi siklus di graph state yang tersebar pada beberapa situs di sistem. Algoritma deteksi deadlock tersebar dapat dimulai kapanpunsaat satu proses dipaksa menunggu, dapat dimulai oleh situs lokal dari proses atau situs dimana proses harus menunggu.
Tardapat beragam algoritma deteksi deadlock secara tersebar, antara lain:
o Algoritma path-pushing
o Algoritma edge-chasing
o Algoritma diffusion computation
o Algoritma global state detection
Algoritma Path-pushing
Informasi kebergantungan wait-for dipropagasikan dalam bentuk path-path. Algoritma yang termasuk kelas ini adalah algoritma Obermarck yang diimplementasikan pada sistem berbasis R* IBM.
Algoritma obermarck dapat mendeteksi Phantom Deadlock yang sesungguhnya bukan deadlock.
Algoritma Edge-chasing
Pesan pesan kusus disebut probe berkililing sepanjang busur busur dari WFG untuk mendeteksi keberadaan siklus. Ketika proses blocked menerima probe, proses mempropagasi probe sepanjang busur busur di WFG. Proses menyatakan deadlock ketika proses menerima probe yang dimulainya.
Algoritma Diffusion Computation
Menggunakan algoritma echo untuk mendeteksi deadlock. Untuk mendeteksi deadlock, proses mengirim pesan pesan query sepanjang busur busur keluar di WFG. Query query ini secara berurutan dipropagasikan sepanjang busur busur WFG. Query query akan diabaikan oleh proses yang sedang berjalan dan digemakan oleh proses proses blocked dengan cara :
Ketika proses blocked menerima query pertama sebagai deteksi deadlock, proses tidak mengirim pesan jawaban sampai proses telah menerima pesan jawaban untuk setiap query yang dikirimkannya.
Untuk query query berikutnya sebagai deteksi deadlock saat itu, proses segera mengirim pesan jawaban. Proses yang memulai deteksi deadlock mendeteksi terjadinyan deadloc ketika menerima jawaban dari semua query yang dikirimkannya.
Algoritma Global State Detection
Algoritma ini berbasis state global yang mempunyai properti berikut :
o Snapshot konsisten dari sistem tersebar dapat diperoleh tanpa membekukan komputasi.
o Snapshot konsisten dapat tidek menyatakan state sistem pada satu waktu, tapi jika properti stabil terdapat di sistem sebelum pengumpulan snapshot dimulai, maka properti ini akan tetap ada di snapshot.
Deteksi deadlock dengan cara ini adalah dengan mengambil satu snapshot dari sistem dan memeriksa keberadaan kondisi deadlock.
Algoritma Deteksi Deadlock Hirarki
Pada algoritma ini, situs situs disusun secara hirarki dan satu situs bertanggungjawab untuk mendeteksi deadlock yang melibatkan situs situs anaknya. Algoritma ini memanfaatkan kenggulan pola pola pengaksenan yang teralokasi ke kelompok kelompok situs untuk optimasi kinerja.
Penyelesaian Deadlock
Cara
Membatalkan sedikitnya satu proses yang terlibat deadlockdan memberikan sumber dayanya ke proses lain yang terlibat deadlock.
Informasi yang Diperlukan
Proses proses yang terlibat deadlock dan sumber daya yang digenggam proses.
Penyebab penyelesaian di sistem tersebar lebih rumit:
o Proses yang mendeteksi deadlock tidak mengetahui semua proses yang terlibat deadlock.
o Dua proses atau lebih dapat secara independen mendeteksi deadlock yang sama. Jika setiap proses yang mendeteksi deadlock itu menyelesaikan deadlock, maka penyelesaian deadlock akan tidak efisien. Kita memerlukan pengolahan post-detection untuk memilih proses yang bertanggungjawab menyelesaikan deadlock.
Pemilihan Koordinator
Banyak algoritma tersebar memerlukan satu proses bertindak sebagai koordinator, inisiator, pengurut, atau lainnya, melakukan peran kusus. Umumnya, tidak peduli proses yang mengambil tanggungjawab ini, terpenting terdapat satu proses yang melakukan tugas ini. Diperlukan pemilihan koordinator.
Asumsi
o Semua proses dianggap tepat sama tanpa berkarakteristik berbeda.
o Tiap proses bernomor unik, misalnya alamat jaringan.
Asumsi
Satu proses per mesin.
o Tiap proses mengetahui nomor proses dari setiap proses lain.
o Yang tidak diketahui: proses mana yang saat itu yang aktif dan tidak aktif.
Pemilihan Proses Bernomor Tertinggi
Algoritma pemilihan berusaha menemukan proses bernomor proses tertinggi dan diberi tugas sebagai koordinator.
Tujuannya untuk memutuskan koordinator baru.
Algoritma Bully ( Oleh Garcia-Molina (1982))
Asumsi
Tiap kelompok mengetahui identitas identitas dan alamat alamat dari anggota lain.
Terdapat tiga tipe pesan :
1. Pesan Pemilihan (Pesan untuk pemberitahuan dimulainya pemilihan)
2. Pesan Jawaban (pesan sebagai tanggapan dari pesan pemilihan)
3. Pesan Koordinator (pesan sebagai pemberitahuan identitas koordinator baru)
Mekanisme
Saat proses X memperingatkan koordinator tidak lagi menanggapi permintaan, proses X menginisiasi pemilihan. Proses X melakukan tindakan berikut :
1. X mengirim pesan election ke setiap proses lebih tinggi.
2. Jika tidak ada yang menanggapi, X memenangkan pemilihan dan menjadi koordinator yang baru. Kemudian proses X mengirim pesan coordinator untuk memberi tahu proses lain mengenai koordinator yang baru.
3. Jika terdapat proses bernomor lebih tinggi, proses mengirim pesan answer.
o Proses X menunggu sampai proses lebih tinggi mengirim pesan coordinator sebagai tanda pengambilan peran koordinator.
o Bila proses X tidak menerima pesan coordinator berarti proses yang lebih tinggi telah mengalami kegagalan. Proses X kembali mengulangi siklus pemilihan koordinator yang baru.
Proses yang menerima pesan coordinator akan merekam identifier koordinator. Saat pesan yang sebelumnya mengalami kegagalan dapat berjalan kembali, proses itu akan segera memulai fase pemilihan. Jika identifier proses merupakan yang tertinggi, proses akan menjadi koordinator baru, meskipun proses koordinator lama masih berfungsi.
Algoritma Ring
Asumsi
Proses proses terurut secara fisik atau logik, tiap proses mengetahui penerusnya.
Saat satu proses memperingatkan bahwa koordinator tidak berfungsi, proses mengirim pesan election berisi nomor prosesnya dan mengirim ke penerusnya. Jika penerusnya berhenti, pengirim melompati penerusnya itu dan mengirim ke anggota berikutnya di ring atau proses setelahnya, sampai satu proses yang berjalan ditemukan. Pada tiap langkah, pengiriman menambahkan nomor prosesnya ke senarai di proses.
Proses akan kembali ke proses yang memulai. Proses mengenalikejadian ini saat menerima pesan berisi nomor prosesnya. Pada saat itu, tipe pesan proses diubah menjadi coordinator dan berputar sekali lagi, menginformasikan ke proses lain mengenai proses yang bertindak sebagai koordinator dan anggota anggota ring yang baru.
Sumber : Buku Bambang Harianto
Postingan
