Deadlock pada Sistem Operasi

Pengertian Deadlock

Deadlock adalah keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses. Deadlock bisa digambarkan sebagai berikut :

Kejadian Deadlock selalu tidak lepas dari sumber daya, bahwa hampir seluruhnya merupakan masalah sumber daya yang digunakan bersama-sama. Oleh karena itu, kita juga perlu tahu tentang jenis sumber daya, yaitu: sumber daya dapat digunakan lagi berulang-ulang dan sumber daya yang dapat digunakan dan habis dipakai atau dapat dikatakan sumber daya sekali pakai. Sumber daya ini tidak habis dipakai oleh proses mana pun.Tetapi setelah proses berakhir, sumber daya ini dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian sumber daya ini.

Contohnya prosesor, Channel I/O, disk, semaphore. Contoh peran sumber daya jenis ini pada terjadinya Deadlock ialah misalnya sebuah proses memakai disk A dan B, maka akan terjadi Deadlock jika setiap proses sudah memiliki salah satu disk dan meminta disk yang lain. Masalah ini tidak hanya dirasakan oleh pemrogram tetapi oleh seorang yang merancang sebuah sistem operasi. Cara yang digunakan pada umumnya dengan cara memperhitungkan dahulu sumber daya yang digunakan oleh proses-proses yang akan menggunakan sumber daya tersebut. Contoh lain yang menyebabkan Deadlock dari sumber yang dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses yang memakai memori utama. Ada empat kondisi yang dapat menyebabkan terjadinya deadlock. Keempat kondisi tersebut tidak dapat berdiri sendiri, namun saling mendukung.

1. Mutual exclusion. 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.

2. Hold and wait. Proses yang sedang memakai sumber daya boleh meminta sumber daya lagi maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak dipakai oleh proses lain, hal ini dapat menyebabkan kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.

3. No preemption. Sumber daya yang ada pada sebuah proses tidak boleh diambil begitu saja oleh proses lainnya. Untuk mendapatkan sumber daya tersebut, maka harus dilepaskan terlebih dahulu oleh proses yang memegangnya, selain itu seluruh proses menunggu dan mempersilahkan hanya proses yang memiliki sumber daya yang boleh berjalan.

4. Circular wait. Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.

Strategi mengatasi Deadlock :

Add beberapa cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:

a. Mengabaikan masalah deadlock.

b. Mendeteksi dan memperbaiki

c. Penghindaran yang terus menerus dan pengalokasian yang baik dengan menggunakan protocol untuk memastikan sistem tidak pernah memasuki keadaan deadlock. Yaitu dengan deadlock avoidance sistem untuk mendata informasi tambahan tentang proses mana yang akan meminta dan menggunakan sumber daya.

d. Pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock dengan deadlock prevention sistem untuk memastikan bahwa salah satu kondisi yang penting tidak dapat menunggu.

Mengabaikan Masalah Deadlock

Untuk memastikan sistem tidak memasuki deadlock, sistem dapat menggunakan pencegahan deadlock atau penghindaran deadlock. Penghindaran deadlock membutuhkan informasi tentang sumber daya yang mana yang akan suatu proses meminta dan berapa lama akan digunakan. Dengan informasi tersebut dapat diputuskan apakah suatu proses harus menunggu atau tidak. Hal ini disebabkan oleh keberadaan sumber daya, apakah ia sedang digunakan oleh proses lain atau tidak. Metode ini lebih dikenal dengan Algoritma Ostrich. Dalam algoritma ini dikatakan bahwa untuk menghadapi Deadlock ialah dengan berpura-pura bahwa tidak ada masalah apa pun. Hal ini seakanakan melakukan suatu hal yang fatal, tetapi sistem operasi Unix menanggulangi Deadlock dengan cara ini dengan tidak mendeteksi Deadlock dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak terjadi apa pun. Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga proses yang menjalankan proses melalui operator harus menunggu pada waktu tertentu dan mencoba lagi.

Mendeteksi dan Memperbaiki

1.      Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi system mana yang terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka diadakan proses untuk memperbaiki dan menjadikan sistem berjalan kembali. Jika sebuah sistem tidak memastikan deadlock akan terjadi, dan juga tidak didukung dengan pendeteksian deadlock serta pencegahannya, maka kita akan sampai pada kondisi deadlock yang dapat berpengaruh terhadap performance sistem karena sumber daya tidak dapat digunakan oleh proses sehingga proses-proses yang lain juga terganggu. Akhirnya sistem akan berhenti dan harus direstart.

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.

Ada beberapa jalan untuk kembali dari Deadlock, yaitu:

1.      Lewat Preemption

Dengan cara untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya pada proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh pemilik dari sumber daya tersebut tergantung dari sifat sumber daya itu sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak mungkin. Cara ini dapat dilakukan dengan memilih korban yang akan dikorbankan atau diambil sumber dayanya untuk sementara, tentu saja harus dengan perhitungan yang cukup agar waktu yang dikorbankan seminimal mungkin. Setelah kita melakukan preemption dilakukan pengkondisian proses tersebut dalam kondisi aman. Setelah itu proses dilakukan lagi dalam kondisi aman tersebut.

2.      Lewat Melacak Kembali

Setelah melakukan beberapa langkah preemption, maka proses utama yang diambil sumber dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu dibutuhkan langkah untuk kembali pada keadaan aman dimana proses masih berjalan dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan sangat sulit menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara mematikan program tersebut lalu memulai kembali proses. Meski pun sebenarnya lebih efektif jika hanya mundur beberapa langkah saja sampai deadlock tidak terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke disk, sehingga saat terjadi deadlock dapat mulai dari tempat terakhir penandaannya berada.

3.      Lewat mematikan proses yang menyebabkan Deadlock

Cara yang paling umum ialah mematikan semua proses yang mengalami deadlock. Cara ini paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun, untuk beberapa sistem, kita juga dapat mematikan beberapa proses saja dalam siklus deadlock untuk menghindari deadlock dan mempersilahkan proses lainnya kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber dayanya, dengan cara ini maka masalah pemilihan korban menjadi lebih selektif, sebab telah diperhitungkan beberapa kemungkinan jika si proses harus melepaskan sumber dayanya.

Kriteria pemilihan korban ialah:

• Yang paling jarang memakai prosesor

• Yang paling sedikit hasil programnya

• Yang paling banyak memakai sumber daya sampai saat ini

• Yang alokasi sumber daya totalnya tersedkit

• Yang memiliki prioritas terkecil

4.      Menghindari Deadlock

Pada sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja. Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak (tidak terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:

1. Jangan memulai proses apa pun jika proses tersebut akan membawanya pada kondisi deadlock, sehingga tidak mungkin terjadi deadlock karena pada saat akan menuju deadlock, proses sudah dicegah.

2. Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan membawa kita pada suatu keadaan deadlock. Jadi diadakan dua kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan

ditambah dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar jangan sampai terjadi deadlock. Pada sistem deadlock avoidance (penghindaran) dilakukan dengan cara memastikan bahwa program memiliki maksimum permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan selalu dalam kondisi aman. Baik mengadakan permintaan awal atau pun saat meminta permintaan sumber daya tambahan, sistem harus selalu berada dalam kondisi aman

Mutual exclusion

Dalam ilmu komputer, saling pengecualian mengacu pada kebutuhan untuk menjamin bahwa tidak ada dua proses atau benang (selanjutnya disebut hanya sebagai proses) berada di bagian kritis mereka pada waktu yang sama. Di sini, bagian kritis mengacu pada periode waktu ketika proses mengakses sumber daya bersama, seperti memori bersama. Masalah mutual exclusion pertama kali diidentifikasi dan dipecahkan oleh Edsger W. Dijkstra dalam seminal 1965 makalahnya berjudul: Solusi dari masalah dalam kontrol pemrograman konkuren.

Contoh sederhana mengapa saling pengecualian penting dalam praktek dapat divisualisasikan menggunakan linked list tunggal. Dalam sebuah linked list penghapusan node dilakukan dengan mengubah "berikutnya" pointer dari node sebelumnya untuk menunjuk ke simpul berikutnya (misalnya, jika node i sedang dihapus maka "berikutnya" pointer node i-1 akan diubah untuk menunjuk ke node i +1). Dalam eksekusi mana seperti linked list sedang dibagi antara beberapa proses, dua proses mungkin mencoba untuk menghapus dua node yang berbeda secara bersamaan mengakibatkan masalah berikut: biarkan node i dan i +1 menjadi node yang akan dihapus, lebih jauh lagi, janganlah dari mereka menjadi kepala atau ekor, pointer berikutnya simpul i-1 akan berubah untuk menunjuk ke node i +1 dan pointer berikutnya node i akan berubah untuk menunjuk ke node i +2. Meskipun kedua operasi penghapusan lengkap berhasil, node i +1 tetap ada dalam daftar sejak i-1 dibuat untuk menunjuk ke i +1 skipping node i (yang dibuat untuk menunjuk ke i +2). Hal ini dapat dilihat pada Gambar 1. Masalah ini dapat dihindari dengan menggunakan pengecualian bersama untuk memastikan bahwa update simultan ke bagian yang sama dari daftar tidak dapat terjadi. Isi Menegakkan mutual exclusion

Ada baik perangkat lunak dan solusi perangkat keras untuk menegakkan saling pengecualian. Beberapa solusi yang berbeda dibahas di bawah ini.

Solusi perangkat keras

Pada sistem prosesor tunggal, solusi yang paling sederhana untuk mencapai saling pengecualian adalah untuk menonaktifkan interupsi selama proses 'bagian kritis. Ini akan mencegah rutinitas layanan interupsi dari berjalan (efektif mencegah proses dari yang mendahului). Meskipun ini adalah solusi efektif, hal itu menyebabkan banyak masalah. Jika suatu bagian kritis adalah panjang, maka jam sistem akan melayang setiap kali bagian kritis dieksekusi karena interupsi timer tidak lagi dilayani, sehingga pelacakan waktu mustahil selama bagian kritis. Juga, jika suatu proses menghentikan selama bagian kritis, kontrol tidak akan pernah kembali ke proses lain, secara efektif menghentikan seluruh sistem. Sebuah metode yang lebih elegan untuk mencapai saling pengecualian adalah sibuk-tunggu.

Sibuk-tunggu adalah efektif untuk kedua uniprocessor dan sistem multiprosesor. Penggunaan memori bersama dan tes-dan-set instruksi atom memberikan pengecualian bersama. Sebuah proses dapat menguji-dan-set pada sebuah lokasi di memori bersama, dan karena operasi adalah atom, hanya satu proses dapat mengatur bendera pada suatu waktu. Setiap proses yang tidak berhasil dalam menetapkan bendera dapat pergi untuk melakukan tugas-tugas lain dan coba lagi nanti, lepaskan prosesor ke proses lain dan coba lagi nanti, atau terus loop sementara memeriksa bendera sampai berhasil memperolehnya. Preemption masih mungkin, jadi metode ini memungkinkan sistem untuk terus berfungsi - bahkan jika suatu proses menghentikan sambil memegang kunci.

Beberapa operasi atom lainnya dapat digunakan untuk memberikan mutual exclusion struktur data, yang paling terkenal adalah Bandingkan-Dan-Swap (CAS). CAS dapat digunakan untuk mencapai saling pengecualian menunggu gratis untuk setiap struktur data bersama dengan membuat daftar link di mana setiap node merupakan operasi yang diinginkan yang akan dilakukan. CAS kemudian digunakan untuk mengubah pointer dalam daftar terkait selama penyisipan simpul baru. Hanya satu proses dapat berhasil dalam CAS nya, semua proses lain mencoba untuk menambahkan node pada saat yang sama harus mencoba lagi. Setiap proses kemudian dapat menyimpan salinan lokal dari struktur data, dan setelah melintasi linked list, dapat melakukan setiap operasi dari daftar pada copy lokal.

Solusi Software.

Selain solusi perangkat keras yang didukung, beberapa solusi perangkat lunak yang ada yang menggunakan sibuk menunggu untuk mencapai saling pengecualian. Contoh ini meliputi:

    Algoritma Dekker

    Algoritma Peterson

    Lamport bakery algoritma.

    Algoritma Szymanski

    Algoritma roti hitam-putih Taubenfeld itu.

Algoritma ini tidak bekerja jika eksekusi out-of-order yang digunakan pada platform yang mengeksekusi mereka. Programmer harus menentukan memesan ketat pada operasi memori dalam thread.

Hal ini sering lebih baik untuk menggunakan fasilitas sinkronisasi yang disediakan oleh multithreading perpustakaan sistem operasi, yang akan mengambil keuntungan dari solusi perangkat keras jika memungkinkan, tetapi akan menggunakan solusi perangkat lunak jika tidak ada solusi perangkat keras yang ada. Misalnya, ketika perpustakaan kunci sistem operasi yang digunakan dan benang mencoba untuk memperoleh kunci sudah diperoleh, sistem operasi dapat menangguhkan benang menggunakan saklar konteks dan swap keluar dengan benang lain yang siap untuk dijalankan, atau bisa menempatkan prosesor ke dalam keadaan daya rendah jika tidak ada thread lain yang dapat dijalankan. Oleh karena itu, metode saling pengecualian yang paling modern berusaha untuk mengurangi latensi dan sibuk-menunggu dengan menggunakan antrian dan konteks switch. Namun, jika waktu yang dihabiskan menangguhkan benang dan kemudian mengembalikan itu dapat terbukti selalu lebih dari waktu yang harus menunggu untuk sebuah thread untuk menjadi siap untuk menjalankan setelah diblokir dalam situasi tertentu, maka spinlocks adalah denda solusi (untuk situasi yang hanya).

Mutual exclusion canggih

Solusi yang dijelaskan di atas dapat digunakan untuk membangun sinkronisasi primitif di bawah ini:

    Kunci

    Mutexes reentrant

    Semaphore

    Monitor

    Message passing

    Ruang tupel

Banyak bentuk mutual exclusion memiliki efek samping. Misalnya, Semaphore klasik mengizinkan deadlock, di mana satu proses mendapatkan semaphore, proses lain mendapat semaphore kedua, dan kemudian keduanya menunggu selamanya untuk semaphore lainnya akan dirilis. Lain efek samping umum termasuk kelaparan, di mana proses pernah mendapat sumber daya yang cukup untuk menjalankan sampai selesai, inversi prioritas, di mana thread prioritas yang lebih tinggi menunggu thread prioritas rendah, dan "latency tinggi", di mana respon terhadap interupsi adalah tidak cepat.

Banyak penelitian yang bertujuan untuk menghilangkan efek di atas, sering dengan tujuan menjamin kemajuan non-blocking. Tidak ada skema yang sempurna dikenal. Memblokir sistem panggilan digunakan untuk tidur seluruh proses. Sampai panggilan tersebut menjadi benang aman, tidak ada mekanisme yang tepat untuk tidur satu thread dalam proses .

Kunci eksklusif Reksa pada objek memori (dalam konteks ini berbagi proses / benang memori) yang diperlukan seperti pada objek database (kunci file). Tentu saja, objek database dapat memiliki non-eksklusif (baca) kunci dan karenanya David Hostettler Wain diusulkan nonexs - kunci memori non-eksklusif pada tahun 2006. Ini masih belum diterapkan secara luas.

Sumber:

http://en.wikipedia.org/wiki/Mutual_exclusion 24/4/2013 Anymous

http://nugan88.wordpress.com/2011/10/03/deadlock-pada-sistem-operasi/  October 3, 2011 Wahyu Aji Nugroho

http://rizkyindrawan.wordpress.com/2010/12/02/deadlock-pada-sistem-operasi/ 02/12/2010 Rizky Indrawan

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.