DEADLOCK PADA SISTEM OPERASI

Deadlock dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem operasi adalah kebuntuan proses. Jadi Deadlock ialah suatu kondisi dimana proses tidak berjalan lagi atau tidak ada komunikasi lagi antar proses. Deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses lain, proses lain itu pun sedang menunggu sumber daya yang dipegang olehnya. Dengan kata lain setiap proses dalam set menunggu untuk sumber yang hanya dapat dikerjakan oleh proses lain dalam set sedang menunggu.

Contoh sederhananya ialah pada gambar berikut ini.

Terjadinya deadlock pada jembatan penyebrangan

Contoh yang lain terjadi pada persimpangan jalan:

Deadlock terjadi pada persimpangan jalan

Dalam kasus ini setiap mobil bergerak sesuai nomor yang ditentukan, tetapi tanpa pengaturan yang benar, maka setiap mobil akan bertemu pada satu titik yang permanen (yang dilingkari) atau dapat dikatakan bahwa setiap mobil tidak dapat melanjutkan perjalanan lagi atau dengan kata lain terjadi Deadlock.

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 2 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.

Diagram Graf
Sebuah sistem komputer terdiri dari berbagai macam sumber-daya (resources), seperti:
• Fisik (Perangkat, Memori)
• Logika (Lock, Database record)
• Sistem Operasi (PCB Slots)
• Aplikasi (Berkas)

Diantara sumber-daya tersebut ada yang preemptable dan ada juga yang tidak. Sumber-daya ini akan digunakan oleh proses-proses yang membutuhkannya. Mekanisme hubungan dari proses-proses dan sumber-daya yang dibutuhkan/digunakan dapat di diwakilkan dengan graf.
Graf adalah suatu struktur diskrit yang terdiri dari vertex dan sisi, dimana sisi menghubungkan vertexvertex yang ada. Berdasarkan tingkat kompleksitasnya, graf dibagi menjadi dua bagian, yaitu simple graf dan multigraf. Simpel graf tidak mengandung sisi paralel (lebih dari satu sisi yang menghubungkan dua vertex yang sama). Berdasarkan arahnya graf dapat dibagi menjadi dua bagian yaitu graf berarah dan graf tidak berarah. Graf berarah memperhatikan arah sisi yang menghubungkan dua vertex, sedangkan graf tidak berarah tidak memperhatikan arah sisi yang menghubungkan dua vertex.

Dalam hal ini akan dibahas mengenai implementasi graf dalam sistem operasi. Salah satunya dalah graf alokasi sumber daya. Graf alokasi sumber daya merupakan graf sederhana dan graf berarah. Graf alokasi sumber daya adalah bentuk visualisasi dalam mendeteksi maupun menyelesaikan masalah deadlock. Graf alokasi sumber daya mempunyai komponen- komponen layaknya graf biasa. Hanya saja dalam graf alokasi sumber daya ini, vertex dibagi menjadi dua jenis yaitu:

1. Proses P= {P0, P1, P2, P3,..., Pi,..., Pm}. Terdiri dari semua proses yang ada di sistem. Untuk proses, vertexnya digambarkan sebagai lingkaran dengan nama prosesnya.
2. Sumber daya R= {R0, R1, R2, R3,..., Rj,..., Rn}. Terdiri dari semua sumber daya yang ada di
   sistem. Untuk sumber daya, vertexnya digambarkan sebagai segi empat dengan instansi yang
   dapat dialokasikan serta nama sumber dayanya.

Sisi, E={Pi®Rj,…, Rj®Pi} terdiri dari dua jenis, yaitu:
a. Sisi permintaan: Pi®Rj Sisi permintaan menggambarkan adanya suatu proses Pi yang meminta sumber daya Rj.
b. Sisi alokasi: Rj®Pi. Sisi alokasi menggambarkan adanya suatu sumber daya Rj yang mengalokasikan salah satu instansi-nya pada proses P

Misalkan suatu graph pengalokasian sumber daya dengan ketentuan sebagai berikut:
Himpunan P,R dan E:
     • P={P1, P2, P3}
     • R={R1, R2, R3, R4}
     • E={P1®R1, P2®R3, R1®P3, R2®P2, R2®P1, R3®P3}
Instansi sumber daya:
     • R1 memiliki satu instansi
     • R2 memiliki dua instansi
     • R3 memiliki satu instansi
     • R4 memiliki tiga instansi
Status Proses:
     • Proses P1 mengendalikan sebuah instansi R2 dan menunggu sebuah instansi dari R1.
     • Proses P2 mengendalikan sebuah instansi dari R1 dan R2, dan menunggu sebuah instansi R3
     • Proses P3 mengendalikan sebuah instansi dari R3.

Grafik pengalokasian sumber daya

Pada gambar graph di atas tidak terdapat adanya cycle, sehingga  proses tidak mengalami terjadinya deadlock. Sekarang perhatikan graph berikut yang terdapat cycle dan memungkinkan terjadinya deadlock.

Terdapat dua cycle (circuit) pada graph di atas yaitu:
P1-R1-P2-R3-P3-R2-P1 dan P2-R3-P3-R2-P2

Proses P1, P2 dan P3 terjadi deadlock. Proses P2 menunggu R3, dimana sedang dikendalikan oleh P3. Proses P3 di sisi lain sedang menunggu proses P1 dan P2 melepas sumber daya R2. Kemudian P1 menunggu proses P2 melepas sumber daya R1. Sekarang perhatikan graph berikut yang terdapat cycle P1-R1-P3-R2-P1.

Walaupun terdapat cycle namun pada proses-proses tersebut tidak terjadi deadlock. Proses P4 akan melepas instansi sumber daya R2 yang akan dialokasikan untuk proses P3. Solusi Penanggulangan Deadlock.







Add beberapa cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:

• Mengabaikan masalah deadlock.
• Mendeteksi dan memperbaiki
• 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.
  
• 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.
  
  
  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.
  
  
  
  Sumber : http://imam_muiz.staff.gunadarma.ac.id