MUTUAL EXCLUSION
Mutual exclusion merupakan kondisi dimana terdapat sekumpulan proses yang hanya salah satu proses yang mengakses sumber daya tertentu atau melakukan fungsi tertentu pada saat tertentu. Keberadaan mutual exclusion ini berfungsi untuk mencegah penggunaan secara bersamaan resource tertentu (contohnya variabel global) oleh potongan kode program yang disebut critical section.
Mutual exclusion ini dapat ditimbulkan akibat adanya interaksi antara proses-proses yang berjalan. Dengan adanya interaksi proses yang memungkinkan adanya kompetisi antar proses, konsep bagi-pakai maupun cooperative antar proses maka kemungkinan terjadinya critical section akan terjadi.
Untuk mengatasi hal tersebut maka dibuatlah sebuah sistem manajemen proses mutual exclusion. Mutual exclusion pertama kali diungkapkan oleh Edsger Djikstra pada tahun 1965. Sejak saat itu banyak solusi yang ditawarkan untuk mengatasi adanya mutual exclusion.
A. Konsep Mutual Exclusion
Untuk menjelaskan bagaimana konsep mutual exclusion. Maka akan diambil sebuah contoh kejadian. Anggap sebuah perintah didalam code merubah sebagian dari data selama beberapa penjalanan program, ketika thread lain yang mungkin dipicu oleh event yang tidak diperkirakan mulai dieksekusi. Jika pada saat yang bersamaan thread kedua ini membaca dari potongan data yang sama, sedangkan data tersebut dalam proses yang sedang akan ditulisi, maka kondisi ini adalah kondisi yang tidak konsisten dan tidak dapat diperkirakan. Jika thread kedua mencoba meng-overwrite data tersebut, akan mengakibatkan keadaan yang tidak dapat ditangani (unresolveable state). Shared data diatas yang sedang diakses oleh critical sections bagaimanapun juga harus dilindungi, jadi proses lain yang membaca dari atau menulis ke dalam potongan data harus dikeluarkan dari pengeksekusian.
Jadi konsep utama dari mutual exclusion adalah bagaimana melakukan manipulasi dan membuat kebijakan tentang bagaimana tata cara pengaksesan critical section oleh proses satu dengan yang lain yang mengakses secara simultan. Mutual exclusion baik yang terjadi pada proses uniprocessing, multiprocessing maupun sistem yang cooperative, solusi yang harus dilakukan bagaimana pengontrolan akses ke sumberdaya.
Persyaratan mutual exclusion adalah sebagai berikut,
1. Mutual exclusion harus dilaksanakan: diantara sejumlah proses yang memiliki bagian kritis bagi sumber daya yang sama atau objek bagi pakai, pada suatu saat tertentu hanya sebuah proses yang diizinkan memasuki daerah kritisnya.
2. Suatu proses yang berhenti di dalam bagian kritisnya tidak boleh menganggu proses lainnya.
3. Suatu proses yang memerlukan akses ke bagian kritis tidak boleh di-delay-kan dalam waktu yang tidak tertentu.
4. Apabila di dalam bagian kritis tidak ada proses,proses yang ingin masuk ke dalam bagian kritisnya harus diizinkan masuk tanpa delay.
5. Tidak ada asumsi dibuat tentang kecepatan proses relative atau jumlah prosesor.
6. Suatu proses berada pada di dalam bagian kritisnya dalam waktu tertentu saja.
Terdapat beberapa cara untuk memenuhi persyaratan mutual exclusion , yakni dengan pendekatan software, pendekatan mesin (instruksi-instruksi mesin special purpose) dan feature-feature dukungan sistem operasi.
B. Mutual Exclusion secara Software
Pendekatan yang dilakukan secara software ini mengamsumsikan mutual exclusion elementer pada tingkat akses memori. Dengan kata lain, akses simultan ke lokasi yang sama dalam memori diserialkan oleh beberapa memori arbiter,walaupun urutan pemberian akses tidak ditentukan terlebih dahulu. Dan tidak diasumsikan adanya dukungan pada tingkat hardware, sistem operasi atau bahasa pemrograman.
1. Algoritma Dekker
Algoritma ini dirancang oleh ahli matematika Belanda bernama Dekker. Algoritma ini menjabarkan mutual exclusion bagi dua proses. Solusi yang dikembangkan oleh algoritma ini dilakukan secara bertahap. Kelebihan dari algoritma ini adalah mampu menjelaskan bug-bug yang paling sering dijumpai di dalam pembuatan program-program konkuren.
Didalam algoritma ini terdapat beberapa usaha yang dilakukan untuk melakukan mutual exclusion pada dua proses.
1.1. Usaha Pertama
Mekanisme yang paling umum digunakan adalah Constrain. Yakni hanya mengizinkan satu akses ke lokasi memori pada suatu saat tertentu. Cara yang dilakukan adalah dengan membuat satu variabel bebas (int turn = 0). Sebuah proses (P0 atau P1), yang menginginkan untuk mengeksekusi bagian kritisnya harus memeriksa isi dari turn. Jika nilai turn sama dengan jumlah dari proses, maka proses dapat melanjutkan ke bagian kritis. Jika tidak maka proses tersebut menunggu untuk dapat mengeksekusi waktu krisisnya, atau yang dinamakan busywaiting. Busywaiting adalah proses menunggu untuk mengeksekusi namun terus melakukan pemeriksaan terhadap nilai dari turn.
Usaha pertama ini telah mampu memenuhi persayaratan mutual exclusion, namun memiliki dua kekurangan mendasar. Pertama, proses-proses harus diawasi dengan ketat dalam bergantian penggunaan bagian-bagian kritisnya. Jadi kecepatan ekseskusi ditentukan oleh kecepatan proses yang lebih lambat yang dimiliki oleh kedua proses. Apabila P0 mengkases bagian kritisnya 1 kali dalam satu jam, sedangkan P1 mengakses 1000 kali dalam satu jam. Maka P0 akan dipaksa menerima kelajuan dari P1. Masalah yang lebih serius terjadi apabila ada saru proses yang mengalami kegagalan, proses yang lain akan terblokir semua.
Jadi usaha tersebut walaupun sudah dikatakan mampu melakukan teknik penstrukturan yang berguna, namun belum mampu mendukung pengolahan konkuren. Usaha pertama ini biasanya dikenal dengan nama coroutine.
1.2. Usaha Kedua
Usaha kedua ini dilakukan untuk memenuhi syarat agar proses dapat memeriksa keadaan proses yang lain. Jadi ketika sebuah proses musnah, proses yang lain masih bisa mengeksekusi ke bagian kritisnya.
Untuk itu dibuat variabel global bagi pakai Flag[0] dan Flag[1]. Flag[0] berhubungan dengan P0 dan Flag[1] berhubungan dengan P1. Ilustrasinya, ketika proses P1 akan memasukki bagian kritis maka ia memeriksa Flag [0] miliki P0. Jika Flag[0] bernilai false maka P1 akan mengeksusi bagian kritisnya dan mengeset Flag[1] menjadi bernilai true. Setelah selesai mengeksekusi, maka Flag[1] diset kembali menjadi nilai false.
Dengan pendekatan seperti ini maka apabila sebuah proses mengalami kegagalan di luar bagian kritis, proses lain tidak akan terblokir. Proses akan dapat masuk kebagian kritisnya sesering mungkin yang ia mau karena status flag selalu bernilai false, namun ketika proses gagal ketika berada di bagian kritisnya maka proses akan terblokkir selamanya.
Namun proses ini memiliki tingkat sulisi yang lebih buruk dari usaha pertama. Hal ini dikarenakan usaha kedua tidak mampu menjamin adanya mutual exclusion. Dengan sistem pendekatan seperti di atas maka akan terjadi kemungkinan kedua proses berada pada bagian kritisnya secara bersamaan. Dan ini akan menjadi deadlock.
1.3. Usaha Ketiga
Usaha ketiga ini dilakukan untuk menyempurnakan kelemahan yang dimiliki oleh usaha kedua. Dalam usaha kedua bila proses rusak pada bagian diluar kritisnya maka proses lain masih dapat mengakses bagian kritisnya. Namun ketika proses terhenti di bagian kritisnya, maka proses akan terblokir selamanya.
Ilustrasi yang dilakukan menggunakan sudut pandang P0. Ketika P0 akan mengeksekusi bagian kritisnya maka akan mengeset flag [0] bernilai true agar proses P1 tidak dapat mengakses bagian kritisnya ketika P0 sedang memasukki bagian kritisnya. Hal ini telah mampu memenuhi syarat mutual exclusion.
Namun dengan mengeset nilai flagnya menjadi true sebelum mengeksekusi bagian kritisnya, maka hal ini akan menimbulkan masalah baru. Yakni ketika kedua proses pada saat yang bersamaan mengeset flag masing-masing menjadi true sebelum mengerjakan bagian kritisnya, maka kedua proses mengira proses lain sedang berada di bagian kritis. Kejadian ini merupakan deadlock.
1.4. Usaha Keempat
Usaha keempat ini menjamin adanya mutual exclusion. Usaha keempat ini mengatur sedemikian rupa supaya setiap proses tidak masuk ke bagian kritis. Kondisi ini dikenal dengan nama livestock.
Skenario ini tidak dapat diterima karena, hanya dapat dijelaskan dan tidak dapat dipertahankan untuk suatu waktu yang lama.
1.5. Solusi yang Benar
Pendekatan dengan flag array masih belum cukup untuk mengatasi masalah “mutual courtesy”. Untuk itu perlu membuat urutan aktivitas kedua proses, hal ini dapat diatasi dengan menggunakan variabel turn pada pendekatan pertama. Variabel turn ini akan mengindikasikan proses mana yang mempunyai hak memasuki daerah kritisnya.
Solusi ini dapat dijelaskan sebagai berikut. Ketika P0 ingin memasukki daerah kritisnya, P0 menyetel flagnya ke true. Kemudian P0 memeriksa flag P1. Apabila flagnya false, P0 dapat dengan segera memasukki bagian kritisnya, jika tidak, P0 memeriksa dengan turn. Jika ditemukan bahwa turn = 0, kemudian mengetahui bahwa akan kembali untuk memaksakan dan secara periodic memeriksa P1 flag. P1 akan dalam beberapa titik memeriksa bahwa akan kembali ke pemeriksaan kembali dan men-set flag false, membolehkan P0 untuk dilanjutkan. Setelah P0 telah digunakan dalam bagian kritis, akan men-set flag ke false untuk membebaskan bagian kritis dan men-set turn ke 1 untuk mentransfer hak untuk memaksakan ke P1.
2. Algoritma Peterson
Algoritma dekker menyelesaikan masalah mutual exclusion namun menggunakan program yang agak rumit dan sulit dipahami serta kebenarannya sangat sulit dibuktikan. Peterson telah memberikan solusi yang singkat dan baik sekali. Sesuai dengan solusi yang ditawarkan, flag variabel array global digunakan untuk mengindikasikan bahwa posisi setiap proses dalam kaitannya dengan mutual exclusion, dan variabel turn digunakan untuk memecah konflik yang simultan.
Untuk lebih jelasnya seperti berikut, Apabila P0 menyetel flag[0] ke true , P1 tidak bisa masuk ke bagian kritis. Apabila P1 telah masuk ke bagian kritis, flag[1] menjadi true dan P0 tidak dapat masuk kebagian kritis. Sebaliknya mutual blocking dicegah dicegah dengan memanfaatkan variabel turn.
Untuk lebih jelasnya dapat dilihat pada kemungkinan yang akan terjadi sebagai berikut:
1. P1 tidak berminat memasukki bagian kritisnya. Hal ini tidak mungkin terjadi karena P1 mengimplikasikan flag[1] = false.
2. P1 sedang menunggu bagian kritisnya. Tidak dapat terjadi karena jika turn = 1 maka P1 dapat memasukki bagian kritisnya.
3. P1 Sedang menggunakan bagian kritisnya dan memonopoli. Hal ini tidak terjadi karena karena P1 memiliki kewajiban member kesempatan kepada P0 dengan cara men-set turn menjadi 0.
Algoritma ini mampu menjelaskan mutual exclusion secara lebih mudah. Dan algoritma ini mampu dengan mudah untuk degenerate untuk sistem n-proses.
C. Mutual Exclusion secara Hardware
1. Interrupt Disabling
Dalam sebuah mesin uniprocessor, proses konkuren tidak dapat ditumpang-tindihkan; proses tersebut hanya dapat digilirkan saja. Di samping itu, suatu proses akan terus-menerus berjalan sampai memanggil layanan sistem operasi atau sampai diinterupsi. Karena itu, untuk menjamin mutual exclusion, maka penting untuk mencegah proses untuk tidak diinterupsi. Kemampuan ini dapat diberikan dalam bentuk primitive yang ditentukan oleh kernel sistem untuk mengizinkan (enable) dan tidak mengizinkan (disable) interrupt.
Karena bagian kritis tidak dapat diinterupsi, mutual exclusion akan dijamin. Namun, harga pendekatan ini cukup mahal. Efisiensi eksekusi akan berkurang dalam jumlah yang cukup berarti karena prosesor memiliki kemampuan terbatas untuk menggilirkan program. Masalah kedua adalah di mana pendekatan ini tidak akan berhasil apabila digunakan pada arsitektur multiprocessor. Apabila sistem komputer memiliki prosesor yang jumlahnya lebih dari satu, (umumnya) pada suatu saat tertentu lebih dari satu proses akan melakukan eksekusi. Dalam hal seperti ini, interrupt yang tidak diizinkan tidak akan menjamin mutual exclusion.
2. Instruksi Mesin Khusus
Dalam suatu konfigurasi multiprocessor, beberapa prosesor berbagi-pakai akses ke sebuah memori utama umum. Pada konfigurasi seperti itu, tidak ada hubungan master/slave, melainkan prosesor tersebut berlaku sebagai hubungan mitra (peer) yang independen. Tidak terdapat mekanisme interupsi di antara prosesor yang mana dapat dijadikan dasar mutual exclusion. Seperti telah dinyatakan sebelumnya, pada tingkatan hardware, akses ke lokasi memori tidak mencakup akses lainnya ke lokasi yang sama itu. Dengan menjadikannya sebagai dasar, para perancang telah mengajukan beberapa instruksi mesin yang melaksanakan aksinya secara atomik, seperti pembacaan dan penulisan atau pembacaan dan pengujian, sebuah lokasi memori yang memiliki satu siklus pembacaan instruksi. Karena dilakukan dalam bentuk instruksi tunggal, aksi-aksi itu tidak akan terganggu oleh instruksi lainnya.
3. Sifat-sifat Pendekatan Mesin
Penggunaan instruksi mesin khusus untuk melaksanakan mutual exclusion memiliki beberapa kelebihan:
a. Dapat diterapkan pada sembarang jumlah proses baik pada sistem proses tunggal maupun sistem prosesor jamak yang berbagi-pakai memori utama.
b. Cukup sederhana sehingga mudah untuk diverifikasi.
c. Dapat digunakan untuk mendukung beberapa bagian kritis; setiap bagian kritis dapat ditetapkan oleh variabel miliknya sendiri.
Namun, terdapat juga beberapa kekurangan:
a. Adanya busy-waiting sehingga, pada saat suatu proses sedang menunggu akses ke bagian kritisnya, proses tersebut menghabiskan waktu prosesor.
b. Mungkin terjadi starvation. Pada saat sebuah proses meninggalkan bagian kritisnya dan lebih dari sebuah proses berada dalam keadaan menunggu, pemilihan proses yang menunggunya bersifat sembarang. Dengan demikian, sebagian proses akan selalu ditolak ntuk mendapatkan akses.
Dapat terjadi deadlock. Perhatikan skenario berikut pada sistem prosesor tunggal. Proses P1 mengeksekusi instruksi khusus (misalnya, tetset, exchange) dan memasuki bagian kritisnya. Kemudian P1 diinterupsi agar menyerahkan prosesor ke P2, yang memiliki prioritas yang lebih tinggi. Sekarang apabila P2 berusaha untuk menggunakan sumber daya yang sama dengan P1, P2 akan ditolak aksesnya karena adanya mekanisme mutual exclusion. Jadi P2 akan menuju dalam loop busy-waiting. Namun, P1 tidak akan pernah dikirimkan (diproses) karena memiliki prioritas yang lebih rendah dibandingkan dengan proses yang sudah siap (ready) lainnya, yaitu P2.Download Doc Version : KONKURENSI dan MUTUAL EXCLUSION
