Mutual Exclusion & Deadlock

1. BAMBANG HARIANTO

Mutual  Exclusion (Zulaikhah Nur Fatikatur Rohmah)
Mutual exclusion adalah upaya menjamin pengaksesan sumber daya dedicated benar-benar hanya oleh satu proses tunggal.
DI system uniprosessor, status sumber daya dan pemakai dapat tersedia di memori bersama dan solusi terhadap mutual exclusion dapat diimplementasikan menggunakan variable bersama secara mudag. Di system tersebar sumber daya dan pemakai tersebar tidak terdapat memori bersama. Pendekatan berbasis variable bersama tidak dapat diterapkan, harus digunakan pendekatan berbasis message passing.
Pendekatan penjaminan mutual exclusion di system tersebar:
 Algoritma terpusat
 Algoritma tersebar
Syarat penting solusi penjaminan mutual exclusion adalah:
 Bebas dari deadlock
 Bebas dari startvation
 Fairness
 Fault tolerance

Algoritma terpusat
 Satu proses merupakan coordinator
 Waktu proses-proses lain ingin masuk critical region, proses mengirim pesan ke coordinator memberitahu critical region yang ingin dimasukinya dan meminta ijin.
 Jika tidak ada proses lain di critical region, coordinator mengirim balik jawaban pemberi ijin.
 Ketika ijin tiba proses yang meminta segera memasuki critical region.
 Jika ada proses lain di critical region, coordinator menolak ijin.
Penolakan ijin dapat berupa:
 Mendiamkan, proses peminta blocked dan menunggu jawaban
 Mengirim jawaban berupa “penolakan ijin”
 Mengantrikan permintaan
Keunggulan
 Menjamin mutual exclusion, karena hanya mengijinkan satu proses memasuki critical region
 Adil, karena mengijinkan sesuai urutan diterimanya pesan
 Tak ada proses yang menungggu selamanya
 Mudah diimplementasikan
 Dapat digunakan untuk mengelola sumber daya
Kelemahan
 Terdapat satu titik kegagalan
 Jika coordinator gagal, maka gagallah seluruh system
 Coordinator dapat menjadi botlenect
 Waktu tunda pengiriman sinkronisasi besar

Algoritma Tersebar
Klasifikasi algoritma tersebar:
 Nontoken based algorithms
 Token based algorithms
Beberapa pendekatan noneoken based algorithm:
 Lamport’s algorithms
 Ricart agrawala algorithms
 Maekawa algorithms
Algoritma Lamport
Syarat:
 Perlu pengurutan total seluruh kejadian
 Untuk sembarang pasangan kejadian, tidak boleh ambig, harus diketahui keterdahuluan kejadian.
Solusi
 Penerapan algoritma Lamport untuk pengurutan kejadian
 Penggunaan stempel waktu untuk proses
Algoritma:
 Ketika proses ingin memasuki critical region, proses membangun pesan berisi nama critical region yang ingin dimasuki, nomor proses dan waktu saat itu.
 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, komunikasi ini dapat digunakan.
 Ketika proses menerima pesan permintaan dari proses lain, aksi yang diambil bergantung statenya 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 dating dengan pesan dikirim. Nilai terendang menang. Jika pesan dating lebih rendah, penerima mengirim pesan OK. Jika pesan mempunyai stempel waktu lebih rendah penerima mengantrikan permintaan dating dan tak mengirim apapun.
 Stelah mengirim permintaan meminta ijin memasuki critical region, proses menunggu sampai semua proses lain member ijin. Begitu semua ijin dipunyai, proses memasuki critical region.
 Ketika proses keluar critical region proses mengirim pesan OK ke semua proses yang diantrikan dan menghapusnya semua dari antrian.
Keunggulan
 Dijamin tanpa deadlock atau starvation
 Tak ada satu titik kegagalan
Kelemahan
 Jumlah pesan yang diperlukan per masuk ke critical region adalah 2(n-1), dimana n adalah jumlah proses yang terdapat di system.
 Menjadi terdapat n titik kegagalan, karena diamnya proses (walau secara tak benar) akan diinterpresentasikan sebagai penolakan ijin sehingga memblock semua usaha semua proses yang ingin memasuki critical region.
 Pemakaian primitive komunikasi kelompok atau tiap proses harus mengelola keanggotaan kelompok termasuk proses yang memasuki, meninggalkan dan crash. Metode ini terbaik bekerja pada sekelompok kecil proses yang tak pernah berubah keanggotaan kelompoknya.
 Karena yang memtuskan n proses maka terdapat beban jaringan yang tinggi.
Algoritma Ricart-Agrawala
Algoritma ini merupakan optimasi Lamport, memerlukan 2(n-1) pesan per-eksekusi critical region. Waktu tunda sinkronisasi adalah T.
Roucariol dan Carcalho mengusulkan peningkatan terhadap algoritma Ricart-Agrawala sehingga memerlukan sejumlah 0 sampai 2(N-1) pesan per ekekusi critical region.
Algoritma Maekawa
Algoritma ini berbeda dengan kebanyakan penyelesaian, yaitu:
 Situs tidak perlu memperoleh permintaan ijin dari semua situs, tapi hanya satu subset situs. Berbeda dengan algoritma Lamport, dan Algoritma Ricart-agrawala dimana semua situs berpartisipasi dalam penyelesaian.
 Situs dapat hanya mengirim satu pesan REPLY hanya setelah menerima pesan RELEASE untuk pesan REPLY sebelumnya.
Algoritma ini memerlukan 3 √  per eksekusi critical region. Waktu tunda sinkronisasi adalah 2T. Dapat mengakibatka deadlock.

Token based algorithm
Satu token unik dipakai bersama diantara semua situs. Proses diijinkan untuk memasuki critical section bila memiliki token.
Beberapa pendekatan token-based algorithm:
 Token-ring algorithm
 Suzuki-kasami’s broadcast algorithm
 Singhal’s heuristic algorithm
 Raymond’s tree-based algorithm
Algoritma token ring
Terdapat ring logic secara perangkat lunak
Yang terpenting tiap proses mengetahui urutan proses berikutnya
 Ketika ring diinisialisasi, proses 0 diberi token.
 Token berkeliling ring. Token melewati proses k ke proses k+1 (modulo ukuran ring) dengan pesan point to point
 Ketika proses memperoleh token dari tetangganya, proses memeriksa apakah prose situ sedang berusaha memasuki critical region.
 Jika proses yang mempunyai token tapi tidak ingin masuk critical region, proses segera melewatkan token. Konsekuensinya, jika tak ada proses yang ingin masuk critical region, token hanya berputar dengan kecepatan tinggi mengelilingi ring.
Keunggulan
 Algoritma ini menjamin hanya satu proses masuk critical region, karena hanya satu proses yang dapat mempunyai token
 Starvation tak terjadi karena adanya pengurutan proses
Kelemahan
 Jika token hilang, token harus dibangkitkan lagi. Mendeteksi token hilang adalah sulit karena jumlah waktu antara kedua kemunculan tak dibatasi. Karena tidak adanya token selama satu jam tidak berarti hilang, mungkin suatu proses masih menggunakannya.
 Proses crash yang menimbulkan kesulitan.
Suzuki kasami’s broadcast algorithm
Pada algoritma ini, situs yang ingin memasuki critical region yang tidak mempunyai token membroadcast pesan request untuk token ke semua situs lain. Situs yang memegang token akan mengirim token ke situs yang meminta.
Masalah yang harus diselesaikan;
 Pembedaan antara pesan using dan pesan saat itu
 Penentuan situs yang mempunyai pesan request paling perlu.
Algoritma ini sederhanya, hanya memerlukan 0 sampai N pesan per eksekusi critical region. Waktu tunda sinkronisasi adalah 0 atau T. tidak diperlukan pesan dan waktu tunda sinkronisasi jika situs tekah memegang token pada saat akan mengeksekusi critical region.
SInghal’s heuristic algorithm
Pada algoritma ini masing-masing situs mengelola informasi mengenai state dari situs lain dan menggunakannya untuk memilih sekumpulan situs yang paling berpeluang memiliki token. Situs meminta token hanya ke situs-situs ini, emreduksi jumlah pesan ytang diperlukan untuk mengeksekusi ritical region. Algoritma disebut heuristic karena melakukan pemilihan secara heuristic dalam pengiriman pesan.
Raymond’s tree based algorithm
Pada algoritma ini situs secara logic disusun dalam satu pohon berarah sehingga busur pohon berarah ke situs yang mempunyai token. Setiap simpul yang mempunyai variable local holder di situs-situs itu, setiap situs mempunyai jalur berarah yang menuju ke situs yang memgang token. Situs akar, variable holder menunjuk dirinya sendiri.
Penyelesaian berbasis token umumnya merupakan algoritma yang efisien dalam pengiriman pesan disbanding non-token.

Penanganan deadlock
Deadlock di system tersebar serupa deadlock di system pemroses 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. Simpul menyatakan transaksi item data, busur ,menyatakan item data. Terjadi deadlock jika dan hanya terdapat siklus di waith for graph
Deteksi deadlock secara terpusat
 Algoritma deteksi terpusat sepenuhnya
Merupakan solusi sederhana, yaitu satu server berperan sebagai detector deadlock global. Server-server lain mengirim kopian wait for graph local ke detector global. Detector global menyusun wait for graph global dari informasi-informasi wait for graph local. Detector global memeriksa wait for graph global. Bila ditemukan siklus detector global membuat keputusan penyelesaian deadlock dan menginstruksikan server lain untuk membatalkan transaksi untuk penyelesaian deadlock.
Kelemahan: bergantung pada satu server sehingga dapat menjadi bottlenect, rentan kegagalan, kurang fault tolerance dan tidak dapat di skala menjadi sitem besar. Lalu lintas informasi sangat tinggi membebani jaringan.
Deteksi deadlock secara tersebar
Pada algoritma ini semua situs secara bersama bekerja mendeteksi siklus di graph state yang tersebar pada beberapa situs system. Algoritma deteksi deadlock tersebar dapat dimulai kapanpun saat satu proses dipaksa menunggu, dapat dimulai oleh situs local dari proses atau situs dimana proses harus menunggu.
Deteksi deadlock hirarki
Pada algoritma ini, situs secara logic disusun secara hirarki dan satu situs bertanggung jawab untuk mendeteksi deadlock yang melibatkan situs-situs anaknya. Algoritma ini memanfaatkan keunggulan pola-pola pengaksesan yang terlokalisasi ke kelompok-kelompok situs untuk optimasi kinerja.

Penyelesaian deadlock
Membatalkan sedikitnya satu proses yang terlibat deadlock dan memberikan sumber daya sumber dayanya ke proses-proses lain yang terlibat deadlock
Informasi yang diperlukan
Proses yang terlibat di deadlock dan sumber daya yang digenggam proses-proses.
Penyebab penyelesaian di system tersebar lebih rumit:
 Proses yang mendeteksi deadlock tidak mengetahui semua proses yang terlibat deadlock
 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 bertanggung jawab menyelesaikan deadlock.
2. SUMBER LAIN
MUTUAL EXCLUSION (Kinanthi Wahyuadi)
A.    Definisi
Mutual Exclusion adalah Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada suatu waktu. Tiga kondisi untuk menentukan mutual Exclusion  diantaranya : Tidak ada dua proses yang pada saat bersamaan berada di critical region. Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain Tidak ada proses yang tidak bisa masuk ke critical region
http://lecturer.d3ti.mipa.uns.ac.id/arum/files/2010/09/deadlockk.pdf  [08.30]
Kriteria penyelesaian Mutual Exclusion :
    Mutual Exclusion harus dijamin.
    Hanya satu proses pada satu saat yang diizinkan masuk Critical Section/Region.
    Proses yang berada di noncritical section, dilarang memblok proses-proses yang ingin masuk critical section.
    Harus dijamin proses yang ingin masuk critical section tidak menunggu lama hingga waktu tak terhingga, agar tidak terjadi deadlock atau starvation.
    Ketika ada proses di critical section maka proses yang ingin masuk critical section harus diijinkan segera masuk tanpa waktu tunda.
    Tidak ada asumsi mengenai kecepatan relative proses atau jumlah proses yang ada.

B.    Metode-metode Penjamin Mutual Exclusion
1.    Metode Naif
Sebenarnya metode ini tidak menyelesaikan mutual exclusion, karena masih terdapat scenario proses yang membuat situasi kacau. Metode ini sering disebut metode variable lock sederhana.
Ketika proses hendak masuk critical section, proses lebih dulu memeriksa variable lock dengan ketentuan :
    Jika variable lock bernilai 0, proses mengeset variable lock menjadi 1 dan segera masuk critical section.
    Jika variable lock bernilai 1, proses menunggu sampai nilai variabel lock menjadi 0.

2.    Metode untuk situasi tertentu
Metode ini sering disebut metode bergantian secara ketat yang mengasumsikan proses-proses yang hendak masuk critical section secara bergantian terus menerus. Proses memeriksa terus menerus sehingga kondisi siap untuk diproses. Kondisi ini tidak dapat ditentukan lamanya waktu sehingga menyia-nyiakan waktu pemroses. Suatu saat kondisi akan crash ketika ada proses yang harus segera masuk sementara ada proses lain yang masih berjalan.

3.    Metode Busy Waiting
a.    Metode Penyelesaian Dekker
Algoritma Dekker mempunyai property-property berikut :
    Tidak memerlukan instruksi-instruksi perangkat keras khusus.
    Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain memasuki critical section.
    Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan.
b.    Metode Penyelesaian Peterson
Sebelum masuk critical section, proses memanggil enter_critical_section, namun sebelumnya proses memeriksa sampai kondisi aman. Terjadi busy waiting, setelah selesai proses menandai pekerjaan dan mengijinkan proses lain masuk.
Keadaan awal tidak ada proses di critical section. Proses 0 akan masuk critical section. Proses menandai elemen arraynya dan mengeset turn ke 0. Proses memeriksa kondisi, dan prosedur enter_critical_section dilaksanakan. Jika kemudian, proses 1 akan masuk, proses akan menunggu sampai interest(0) menjadi FALSE. Kondisi ini hanya terjadi jika proses 0 mengeset elemen itu dan keluar dari critical section.
c.    Metode Pematian Interupsi
Proses mematikan interupsi ke pemroses dan segera masuk ke critical section. Proses kembali mengaktifkan interupsi segera setelah meninggalkan critical section. Metode ini mengakibatkan :
    Pemroses tidak dapat beralih ke proses lain karena interupsi clock dimatikan sehingga penjadual pun tidak dieksekusi. Karena penjadual tidak beroperasi maka tidak terjadi alih proses.
    Proses dapat memakai memori bersama tanpa takut terinvensi proses lain karena memang tidak ada proses lain yang dieksekusi saat itu.
Kelemahan utama :
    Bila proses yang mematikan interupsi mengalami gangguan maka proses tidak akan pernah menghidupkan interupsi kembali. Kejadian ini mengakibatkan kematian seluruh system.
    Jika terdapat dua pemroses atau lebih, mematikan interupsi hanya berpengaruh pada pemroses yang sedang mengeksekusi intruksi itu. Proses lain masih dapat memasuki critical section.

d.    Metode Test and Set Lock (TSL)
Metode ini membaca isi memori ke register dan kemudian menyimpan nilai bukan 0  ke alamat memori. Pemroses yang mengeksekusi instruksi tsl mengunci bus memori, mencegah pemroses lain mengkases memori.

e.    Metode Exchange (XCHG)
Metode ini menggunakan instruksi exchange (xchg). Instruksi xchg menukarkan dua isi memori.
f.    Metode Instruksi Mesin
Keunggulan :
    Sederhana dan mudah diverifikasi
    Dapat diterapkan ke sembarang jumlah proses
    Dapat digunakan untuk mendukung banyak critical region
Kelemahan :
    Merupakan metode dengan busy waiting, sangat tidak efisien.
    Adanya busy waiting memungkinkan terjadi deadlock dan starvation.
 
4.    Metode Penyelesaian Level Tinggi (Metode Semapore)
Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Proses berhenti sampai proses memperoleh penanda tertentu. Variabel khusus untuk penandaan ini disebut semaphore. Semaphore mempunyai dua property :
a.    Semaphore dapat diinisialisasi dengan nilai bukan negative.
b.    Ada dua operasi terhadap semaphore yaitu Operasi Up dan Operasi Down.

Operasi Down
Operasi ini menurunkan nilai semaphore. Jika nilai semaphore menjadi bukan positif maka proses yang mengeksekusinya diblok. Operasi Down adalah atomic (atomic action), tidak dapat diinterupsi sebelum selesai. Menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblok sebagai instruksi tunggal. Tidak ada proses lain yang dapat diakses sampai proses selesai.

Operasi Up
Operasi ini menaikkan nilai semaphore. Jika satu proses atau lebih telah diblok pada suatu semaphore tidak dapat menyelesaikan operasi down maka salah satu dipilih oleh system dan dibolehkan menyelesaikan operasi downnya. Operasi Up menaikan nilai semaphore, memindahkan dari antrian dan menempatkan satu proses ke senarai ready tidak dapat diinterupsi.

Sebelum masuk critical section, proses melakukan down. Bila berhasil maka proses masuk critical section. Bila tidak berhasil maka proses diblok pada semaphore. Proses yang diblok dapat melanjutkan jika proses yang berada di critical section keluar dan melakukan operasi up dan menjadikan proses yang diblok menjadi ready dan berlanjut hingga operasi downnya berhasil.

C.    Implementasi Semaphore
1.    Pematian Interupsi
Sistem operasi mematikan interupsi selagi memeriksa semaphore, memperbarui, dan menjadikan proses diblok. Karena semua aksi hanya memerlukan beberapa instruksi, pematian interupsi tidak merugikan.
2.    Instruksi tsl
Pada banyak pemroses, tiap semaphore dilindungi variable lock dan instruksi tsl agar menjamin hanya satu pemroses yang saat itu memanipulasi semaphore
http://godaizone.blogspot.com/2010/12/mutual-exclusion.html [08.35]

3. SUMBER LAIN
MUTUAL EXCLUSION & DEADLOCK (Muhammad Ridwan)
A. Mutual Exclusion adalah Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada suatu waktu (kondisi-kondisi untuk solusi). Tiga kondisi untuk menentukan mutual Exclusion diantaranya :
1.Tidak ada dua proses yang pada saat bersamaan berada di critical region.
2.Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain
3.Tidak ada proses yang tidak bisa masuk ke critical region
Merupakan kondisi dimana terdapat sumber daya yang tidak dapat dipakai  bersama pada waktu yang bersamaan (misalnya : printer, disk drive).  Kondisi demikian disebut sumber daya kritis, dan bagian program yang  menggunakan sumber daya kritis disebut critical region / section.  Hanya satu program pada satu saat yang diijinkan masuk ke critical region. Pemogram tidak dapat bergantung pada sistem operasi untuk memahami dan  memaksakan batasan ini, karena maksud program tidak dapat diketahu oleh  sistem operasi.
Hanya saja, sistem operasi menyediakan layanan (system call) yang bertujuan  untuk mencegah proses lain masuk ke critical section yang sedang digunakan proses tertentu.

Sumber: http://ariszona.wordpress.com/2010/04/19/sistem-operasithread-mutual-exclusion-race-condition/
B. 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 protokol
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
Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi sistem
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:
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.
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.
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
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.

Sumber
* http://nugan88.wordpress.com/2011/10/03/deadlock-pada-sistem-operasi

4.PENATAAN TUGAS,PEMBUATAN BLOG DAN PENGIRIMAN EMAIL
TUGAS MUTUAL EXCLUSION & DEADLOCK (Wengky Irawan)