Mutual Exclusion

Bab 6 . Mutual Exclusion

6.1 Pentingnya Mutual Exclusion

Mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya pad satu interval  waktu tertentu . pentingnya mutual exclusion dapat dilihat pada ilustrasi berikut :

-          Ilustrasi ilustrasi eksekusi daemon printer

-          Ilustrasi aplikasi abungan

6.1.1 Ilustrasi Printer Daemon

Daemon printer adalah proses pendjadwalan dan pengendalian percetakan pada berkas-berkas di printer sehingga seolah-olah printer dapat digunakan secara simultan oleh proses-proses . Daemon printer mempunyai ruang disk (directory spooler)untuk mrnyimpan berkas-berkas yang dicetak . Direktori spooler membagi menjadi sejumlah slot. Slot diisi berkas yang dicetak .

6.1.2 Ilustrasi  Aplikasi Tabungan

Seluruh system yang melibatkan banyak proses mengakses satu sumber daya bersama selalu menimbulkan masalah mutual exclusion .

6.1.3 Kriteria Penyelesaian Mutual Exclusion

Fasilitas atau kemampuan dukungan mutual exclusion harus memenuhi kriteria berikut :

1.      Mutual exclusion harus dijamin

Hanya satu proses pada satu saat yang diijinkan masuk critical selection . Proses-proses ini lain dilarang masuk critical selection yang sama pada saat proses masuk .

2.      Prose yang berada di non critical selection , dilarang mem-blocked proses0proses lain , yang ingin masuk .

3.      Harus dijamin proses yang ingn masuk , tidak menunggu lama .

4.      Tidak harus menunggu waktu tunda .

5.      Tidak ada asumsi mengenai kecepatan asumtif .

Kriteria diatas merupakan kriteria pokok ynag mesti dipenuhi . Yang melanggar sama sekali tidak bias digunakan .

6.2 Metode-Metode Penjaminan Mutual Exclusion

Contoh metode yang digunakan :

1.      Metode naïf

Metode variable lock sederhana

2.      Metode untuk situasi tertentu

Bergantian secara kuat

3.      Metode menggunakan bussy waiting

Metode penyelesaian dekker

Metode penyelesaian Peterson

4.      Metode penyelesaian level tinggi

Metode semaphore

6.2.1 Metode Naif

Disebut naïf karena tidak menyelesaikan mutual exclusion .

6.2.1.1 Metode Variabel Lock Sederhana

Meniru mekanisme penguncian pintu dengan kunci pintu diganti variable lock . variable lock bernilai 0 berarti pintu tidak terkunci , bernilai 1 pintu terkunci . jika gagal apabila analogi tidak sepenuhnya sama .

6.2.2 Metode Untuk Situasi Tertentu

6.2.2.1 Metode Bergantian Secara Kuat

Dapat mengalir terus masuk critical selection secara bergantian terus .

-          Variabel turn (giliran)

Mencatat (nomor) proses yang masuk critical selection . variable variable turn diinisialisai 0

-          Busy Waiting

Kondisi memeriksa varabel terus-menerus , menunggu sampai sau nilai muncul .

6.3 Metode Dengan Busy Waiting

6.3.1 Metode Secara Perangkat Lunak

6.3.1.1 Metode Penyelesaian Dekker

Algoritma dekker menyelesaika mutual exclusion dengan kompleks . Algoritma Dekker mempunyai property-properti berikut :

-          Tidak memerlukan instruksi-instruksi khusus .

-          Proses yang beroprasi di luar critical selection tidak dapat mencegah proses lain masuk .

-          Proses yang ingin masuk critical selection dapat segera masuk apabila dimingkinkan .

6.3.2 Metode Dengan Dukungan  Perangkat Keras

6.3.2.1 Metode Pematian Interupsi

Proses ini mematiakn intrupsi ke pemroses dan segera memasuki critical selection . proses kembali megaktifkan interupsi segera setelah meninggalkan critical selection .

-          Proses tidak dapat beralih ke proses lain . karena interupsi clock dimatikan sehingga pendjadwalan tidak tidak dieksekusi .

-          Proses dapat memakai memori bersama tanpa takut intervensi proses lain .

Kelemahan Utama

-          Bila proses mematikan interupsi mengalami gangguan maka proses tak akan menghidupkan interupsi kembali .   

-          Jika terdapat dua proses atau lebih , mematiakan interupsi hanya berpengaruh pada pemroses yang meneksekusi instruksi itu .

6.3.2.2 Metode Dengan Instruksi  Test And Set Lock

Pemroses bertindak independent . intrupsi di satu pemroses tidak mempengaruhi pemroses-pemroses lain . Perancangan perangkat menyediakan instruksi-instruksi atomic yang dapat didintupsi , instruksi dilaksanakan sampai selesai . Instruksi-instruksi yang dirancang untuk menyelesaikan mutual exclusion antara lain :

-          Tsl (test and set lock).

-          Tas and ts (test and set).

-          Cs (compare and set).

-          Exchange (xchg)

6.3.2.3 Metode Dengan Instruksi Excange (XCHG)

Instruksi Excange

Intel menyediakan instruksi ini . instruksi ini saling menukarkan antara dua sisi memori .

6.2.3.4 Karakteristik Pendekatan Dengan Instruksi Mesin

Penggunaan karakter ini memiliki kelebihan dan kekurangan .

Kelebihan :

-          Sederhana dan mudah diverifikasi

-          Dapat diterapkan ke sembarang jumlah proses , baik tunggla maupun bersama .

-          Dapat digunakan untuk mendukung banyk critical selection .

Kekurangan :

-          Sangat tidak efisien .

-          Memungkinkan terjadinya dead lock dan startvation .

6.3.3 Dampak Adanya Busy Waiting

Tidak dapat diterapkan pada saat system dengn pendjadwalan berprioritas . Aturan pendjadwalan berprioritas selalu mendjadwalkan proses-proses berprioritas lebih tinggi di antrian proses ready .

6.4 Metode Dengan Semaphore

Karenat terdapat kelemahan-kelemahan yang tak dapat diterima dari metode-metode busy waiting , maka perlu dicari metoe-metode lain .

6.4.1 Deskripsi Semaphore

Semaphore adalah Dua proses atau lebih dapat bekerjasama dengan menggunakan penanda-penanda sederhana . proses dipaksa berhenti sampaI proses memperoleh penanda tertentu . Sembarang kebutuhan koordiansi kompleks dapat dipenuhi dengan struktur penanda yang sesuai kebutuhannya .

6.4.2 Mutual Exclusion dengan Semamphore

Adanya semaphore mempermudah persoalalan mutual exclusion .

6.4.3 Implementasi Semaphore

Beragam skema dapat diterapkan untuk implementasi Up dan Down . Esensi  masalah implementasi adalah menjamin mutual exclusion variable semaphore , yaitu hanya mengijinkan satu proses pada saat yang boleh memanipulasi semaphore , salah stu dari Up dan Down .

Bab 7 . Deadlock   

Proses disebut dead lock jika proses menunggu suatu kejadian tertentu yang tak akan pernah terjadi . sekumpulan proses berkondisi dead lock bila setiap proses yang ada di kumpulan itu menunggu kejadian yang hanya dilakukan proses lain yang juga berada di kumpulan itu .

Deadlock terjadi ketika proses mengakses secara eksklusif sumber daya . Semua deadlock yang terjadi melibatkan persaingan memperoleh sumber daya ekslusif oleh dua proses atau lebih .

7.1 Model Deadlock

- Meminta (request).

- Memakai (user).

- Melepaskan (release).

7.1.1 Syarat-syarat Perlu Bagi Terjadinya Deadlock

1. Mutual Exclusion

2. Kondisi genggam dan tunggu

3. Kondisi non-preemtion

4. Kondisi menunggu secara sirkuler

Mutual Exclusion

Tiap sumber daya saat itu diberikan tepat pada satu proses.

Kondisi Genggam dan Tunggu

            Proses yang menggenggam sumber daya , menunggu sumber daya baru.

Kondisi Non-Preemption

Sumber daya yang diberikan sebelumnya diberikan tidak dpat diambill paksa dari proses itu . harus secara eksplisi dilepaskan dari proses yang menggenggamnya .

Kondisi Menunggu Secara Sirkuler

            Harus terdapat rantai sirkuler dari dua proses atau lebih .

7.2 Metode-Metode Mengatasi Deadlock

1. Deadlock Prevention

2. Deadlock Avoidance

3. Deadlock Detection

7.3 Pencegahan Deadlock

- Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus .

- Harus melepas sumber daya apabila proses telah memegang sumber daya tertentu .

7.4 Penghidaran Deadlock  (Deadlock Avoidence)

Memberikan akses kepada sumber daya yang menjamin tidak terjadi deadlock. Dengan strategi ini, selalu dihidarkan pengalokasian sumber daya yang  dapat beresiko deadlock.

7.5 Deteksi dan Pemulihan Deadlock (Deadlock Detection & Recovery)

Membiarkan deadlock terjadi, jika kemudian terjadi lakukan upaya peneyelesaian. Terdiri dari dua langkah pokok :

-          Deteksi adanya deadlock

Pemulihan Deadlock

-          Jika diketahui terjadi deadlock, maka deadlock harus diputuskan dengan menghilangkan salah satu atau lebih sarat perlu terjadinya deadlock.

Hal-hal yang merumitkan pemulihan deadlock :

-          Belum dapat memutuskan apakah deadlock benar terjadi

-          Tidak dimilki mekanisme suspend proses yang memadai.

-          Diperlukan kemampuan operator yang memadai untuk suspend secara efektif

Hal-hal yang terjadi dalam mendeteksi adanya deadlock adalah:

-          Permintaan sumber daya dikabulkan selama memungkinkan.

-          Sistem operasi memeriksa adakah kondisi circular wait secara periodik.

-          Pemeriksaan adanya deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah proses.

-          Memeriksa dengan algoritma tertentu.