Mutual Exclusion

Contoh Implementasi Mutual Exclusion dan Metodenya

——————————————————————

Pengertian Mutual Exclusion

Mutual Exclusion adalah suatu cara yang menjamin sebuah proses yang menggunakan variabel atau berkas yang sama (digunakan juga oleh proses lain), maka proses lain akan dikeluarkan dari pekerjaan yang sama. Lebih tepatnya lagi Mutual exclusion adalah persoalan untuk menjamin hanya ada satu proses yang mengakses sumber daya pada suatu interval waktu tertentu. Salah satu contoh Mutual exclusion terjadi pada  printer daemon.

Daemon untuk printer adalah proses penjadwalan dan pengendalian untuk mencetak berkas-berkas di printer sehingga menjadikan seolah-olah printer dapat digunakan secara  simultan oleh proses-proses. Daemon untuk printer mempunyai tempat penyimpanan di harddisk ( disebut spooler) untuk menyimpan berkas-berkas yang akan dicetak . Direktori spooler itu terbagi ddalam sejumlah slot. Slot berisi satu berkas yang akan dicetak . Terdapat variabel in yang menunjuk slot bebas di ruang harddisk yang dipakai untuk menyimpan berkas yang hendak dicetak.

 

  • Skenario yang membuat  situasi kacau

Misal A dan B ingin mencetak berkas , variabel in bernilai 9

  • Skenario

    Proses A membaca variabel in bernilai 9 . Belum sempat A mengerjakan proses , penjadwal menjadwalkan proses B berjalan . Prose B yang juga ingin mencetak segera membaca variabel in , variabel in masih bernilai 9. Proses B dapat menyelesaikan prosesnya . Proses B menyimpan berkas B di slot 9. Proses a dijadwalkan kembali dan segera menyimpan berkas A di slot 9. Berkas B tertimpa berkas A , B tidak akan pernah mendapat cetakan.

    Pada contoh , terdapat kondisi yaitu 2 proses atau lebih sedang membaca atau menulis data bersama ( yaitu variabel in) dengan hasil akhir bergantung jalanya proses-proses . hasil akhir tidak bisa diprediksi , kondisi yang tidak dapat diprediksi hasilnya bergantung pada jalanya proses-proses yang bersaing disebut kondisi pacu ( race condition) Kondisi pacu harus dihilangkan agar hasil dapat diprediksi dan tidak bergantung jalanya proses-proses itu.

    Pokok penyelesaian  permasalahan adalah sisitem harus mencegah lebih dari satu proses membaca atau menulis data bersama disaat yang bersamaan karena bagian program yang sedang mengakses memori atau sumber daya yang dipakai bersama dapat menimbulkan kondisi pacu/critical section/region.

    Kesuksesan proses-proses konkuren memerlukan pendefinisian critical section dan memaksakan mutual exclusion diantaraproses-proses konkuren yang sedang berjalan . Penyelesaian mutual exclusion merupakan landasan pemrosesan konkuren.

Metode-Metode Penjaminan mutual exclusion

  • Metode Variabel lock sederhanaMetode ini sederhana , meniru mekanisme penguncian pintu bahwa kunci pintu diganti variabel lock . Variabel lock bernilai 0 berarti pintu tidak terkunci , bernilai 1 berarti pintu terkunci. Metode ini gagal karena analoinya tidak sepenuhnya sama.Mekanisme yang diiusulkan

    Ketika prosesss hendak masuk mutual exclusion , proses lebih dulu memeriksa variabel lock dengan ketentuan sebagai berikut :

      • Jika variabel lock bernilai 0,proses menge-set variabel lock menjadi 1 dan segera masuk mutual exclusion
      • Jika variabel lock bernilai 1, proses menunggu sampai nilai variabel lock menjadi 0 ( situasi ini berarti sedang terdapat proses lain di mutual exclusion )Skenario yang membuat situasi kacau

    Metode ini tidak menjamin proses memasuki critical section yang telah dimasui proses lain . Saat proses A telah membaca variabel lock dan sebelum men-set variabel lock dan sebelum menset variabel lock menjadi 1 , penjadwal dapat menjadwalkan proses B. Proses B pun membaca variabel lock yang masih bernilai 0 dan masuk critical section . Penjadwal kemudian menggilir A lagi , karena telah membaca variabel lock bernilai 0 maka proses A pun segera masuk critical section yang sedang dimasuki B . Secara bersamaan A dan B masuk critical section yang sama . Kriteria 1 terlanggar , metode ini sama sekali tidak bisa digunakan.

  • Metode Dengan Busy Waiting
    • Metode penyelesaian Dekker

     Implementasi mutual exclusion secara perangkat lunak yang sukses pertama kali diberikan Dekker, matematikawan Belanda.

    Perhatikan program penyelesaian Dekker berikut ini

    Algoritma Dekker untuk menyelesaikan mutual-exclusion adalah rumit. Algoritma Dekker mempunyai properti-properti berikut:

    • Tidak memerlukan instruksi-instruksi perangkat keras khusus.
    • Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain memasuki critical section itu.
    • Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan.

    Program sulit diikuti dan pembuktian kebenarannya memerlukan kecerdikan. Peterson member penyelesaian sederhana dan elegan terhadap persoalan mutual exclusion.

    • Metode Penyelesaian Peterson

    Penyelesaian Peterson adalah sebagai berikut:

    Mekanisme kerja Peterson adalah sebagai berikut:

    Sebelum masuk critical_section, proses memanggil enter_critical_section. Sebelum memanggil enter_critical_section, proses memeriksa sampai kondisi aman untuk enter_critical_section. Terjadi busy Waiting. Setelah selesai di critical section, proses menandai pekerjaan telah selesai dan mengizinkan proses lain masuk.

    Skenario

    Keadaan awal adalah tidak ada proses di critical_section. Proses o akan masuk critical section. Proses menandai elemen array-nya dan menge-set turn ke o. Proses memeriksa kondisi untuk masuk critical region. Karena proses 1 tidak berkepentingan (elemen interested tidak di tandai) maka prosedur enter_critical_section segera dilaksanakan.

    Jika kemudian, proses 1 akan masuk critical section. Proses akan menunggu sampai interested[0] menjadi FALSE. Kondisi ini hanya terjadi ketika proses 0 menge-set elemen itu yaitu ketika keluar dari critical section. Metode ini terjadi busy waiting, yaitu proses harus menghabiskan jatahnya untuk memeriksa kondisi.

    Skenario proses o dan 1 memanggil enter_critical_section hamper simultan

    Keduanya menyimpan normor proses di turn, yang terakhir dipertimbangkan, yang terdahulu hilang karena ditimpa. Misalnya, proses 1 menyimpan lebih akhir maka turn bernilai 1. Ketika kedua proses mengeksekusi pernyataan while, proses o mengeksekusi o kali dan memasuki critical_section. Proses 1 loop dan tidak memasuki critical_section.

    Dengan algoritma Peterson, proses-proses dapat masuk critical section dengan aman tanpa terganggu proses lain. Penyelesaian Peterson dapat di generalisasi untuk banyak proses konkuren secara mudah, tidak Cuma untuk dua proses.

 

 

 

Sumber : http://jerseybiru.wordpress.com/2013/04/25/mutual-exclusion-dan-deadlock/

Comments are closed.