Deadlocks



Gambaran Mengenai Deadlock

  • Pada sistem multiprogramming, beberapa proses mungkin saja harus berkompetisi untuk menggunakan sumber daya yang jumlahnya terbatas. Jika sebuah proses me-request sumber daya dan sumber daya tersebut tidak tersedia pada saat itu (sedang dipegang oleh proses lain), maka proses tersebut akan memasuki status wait (proses diblok). Status proses yang sedang menunggu tersebut bisa saja tidak akan pernah berubah karena sumber daya yang di-request proses tersebut sedang dipegang oleh proses lain yang juga sedang menunggu. Situasi demikian dinamakan sebagai deadlock.
  • Berdasarkan uraian pada poin di atas, dapat disimpulkan bahwa deadlock terjadi saat dua atau lebih proses menunggu suatu kejadian selama tak terhingga karena kejadian tersebut hanya bisa disebabkan oleh sebuah proses yang sedang menunggu.
  • Dengan kata lain, deadlock terjadi saat himpunan proses yang masing-masing memegang sumber daya sedang diblok dan menunggu untuk mendapatkan sumber daya yang sedang dipegang oleh proses lain dalam himpunan proses tersebut.
  • Ilustrasi deadlock dapat digambarkan dengan masalah jembatan penyeberangan.
    (lihat simulasi masalah jembatan penyeberangan)


[Top]


Model Sistem

  • Sebuah sistem terdiri dari sumber daya dengan jumlah terbatas yang didistribusikan kepada sejumlah proses yang berkompetisi untuk mendapatkan sumber daya.
  • Sumber daya terbagi menjadi beberapa tipe dan tiap tipe sumber daya dapat terdiri dari sejumlah instance yang identik. Contoh tipe sumber daya adalah space memory, siklus CPU, dan I/O devices (misalnya : printer dan tape drives). Jika sebuah sistem memiliki 2 printer maka sumber daya bertipe printer mempunyai 2 instance.
  • Status proses terhadap sumber daya yang perlu digunakannya adalah sebagai urutan berikut :
    1. Request :
      Jika request proses terhadap suatu sumber daya belum dipenuhi (misalnya : sumber daya yang di-request sedang digunakan oleh proses lain), maka proses yang me-request harus menunggu sampai sumber daya yang diperlukannya tersedia).
    2. Use :
      Proses dapat menggunakan sumber daya (misalnya : jika sumber daya-nya adalah printer, maka proses dapat melakukan pencetakan dengan printer).
    3. Release:
      Proses melepaskan sumber daya.
  • Status deadlock pada sebuah sistem dapat terjadi baik dengan melibatkan tipe sumber daya yang sama, maupun dengan melibatkan tipe sumber daya yang berbeda.
    (lihat simulasi deadlock dengan melibatkan tipe sumber daya yang sama)
    (lihat simulasi deadlock dengan melibatkan tipe sumber daya yang berbeda)


Karateristik Deadlock

  • Saat terjadi deadlock, proses-proses tidak pernah selesai diekseskusi.
  • Syarat perlu terjadinya deadlock yaitu :
    • Mutual exclusion :
      Hanya satu proses pada suatu waktu yang dapat menggunakan sebuah sumber daya.
    • Hold and wait :
      Suatu proses yang sedang memegang satu atau lebih sumber daya sedang menunggu sumber daya tambahan yang sedang dipegang oleh proses lain.
    • No preemption
      Sumber daya hanya dapat lepas dari proses yang sedang memegangnya jika proses itu sendiri yang melepas sumber daya tersebut secara sukarela setelah proses itu menyelesaikan task-nya.
    • Circular Wait
      Terdapat sebuah himpunan proses yang sedang menunggu yaitu : (P0, P1, ..., Pn), dimana P0 menunggu sumber daya yang sedang dipegang oleh P1, P1 menunggu sumber yang sedang dipegang oleh P2, ... , Pn-1 menunggu sumber daya yang sedang dipegang oleh Pn, dan Pn menunggu sumber daya yang sedang dipegang oleh P0.
  • Deadlock dapat dideskripsikan dengan menggunakan graph berarah bernama resource-allocation graph.
    (lihat simulasi pengenalan resource-allocation graph)
  • Jika resource-allocation graph tidak mengandung cycle, maka deadlock tidak akan terjadi.
    (lihat simulasi resource-allocation graph yang tidak mengandung cycle)
  • Jika resource allocation graph mengandung cycle :


[Top]


Metode Untuk Menangani Deadlocks

  • Menggunakan protokol yang menjamin sistem tidak akan pernah memasuki status deadlock
  • Membolehkan sistem memasuki status deadlock, lalu dilakukan recover.
  • Menganggap bahwa deadlocks tidak pernah terjadi dalam sistem (metode ini digunakan oleh sebagian besar sistem operasi termasuk UNIX).


[Top]


Pencegahan Deadlock

Dengan memastikan bahwa setidaknya satu dari syarat perlu deadlock tidak terpenuhi, maka terjadinya deadlock dapat dicegah.Oleh karena itu, untuk mencegah deadlock diupayakan agar salah satu dari mutual exclusion, hold and wait, no preemption atau circular wait tidak terpenuhi.


[Top]


Menghindari Deadlock

  • Menghindari deadlock berarti menghindari jangan sampai sistem berada pada status tidak aman.
  • Sistem dikatakan berada pada status aman bila sistem dapat mengalokasikan sumber daya ke masing-masing proses dengan urutan tertentu dan masih bisa menghindari deadlock
  • Jika sistem berada pada status aman maka deadlock tidak akan terjadi.
  • Jika sistem berada pada status tidak aman maka deadlock mungkin terjadi.
  • Beberapa algoritma untuk menghindari deadlock :


[Top]


Pendeteksian Deadlock


Jika deadlock dapat terjadi pada sebuah sistem maka sistem tersebut harus menyediakan allgoritma untuk mendeteksi apakah deadlock telah terjadi dan algoritma untuk memulihkan sistem dari deadlock.


[Top]


Pemulihan Dari Deadlock

  • Terminasi proses
  • Sumber daya preemption


[Top]