Karakteristik Deadlock

Pada kondisi deadlock, proses tidak akan pernah selesai dieksekusi, sehingga penggunaan resource terkait tidak dapat dialokasikan ke proses lainnya dan mengakibatkan mencegah pekerjaan lainnya untuk mulai berjalan. Sebelum membahas mengenai penanganan masalah deadlock, telebih dahulu kita harus mengetahui karakteristik dari berbagai kondisi penyebab terjadinya deadlock itu sendiri.

Situasi deadlock dapat terjadi jika empat kondisi berikut berlangsung (hold) secara simultan/bersamaan dalam sebuah sistem.

1. Mutual Exclusion – setidaknya terdapat satu resource pada mode operasi normal bersifat non-shareable, yang memiliki arti hanya satu proses dalam satu waktu yang dapat menggunakan resource tersebut. Jika proses lain meminta resource tersebut, maka proses yang meminta harus ditunda (delay) dengan cara menunggu (waitting) hingga resource yang di maksud dilepas (release).
2. Hold dan Wait – sebuah proses harus menahan/menggunakan (hold) setidaknya satu resource dan menunggu (waitting) untuk memperoleh resource selanjutnya yang dibutuhkan dan sedang ditahan/digunakan oleh proses lainnya.
3. No Preemption – resource yang sedang digunakan tidak dapat didahului/disela, yang berati resourse tersebut hanya dapat di lepas (release) oleh proses yang sedang menahannya (hold) sampai selesai mengerjakan tugasnya, kemudian barulah dapat digunakan oleh proses lainnya.
4. Circular Wait – misal himpunan {P0, P1,…, Pn} yang merupakan proses-proses yang sedang menunggu satu sama lain. Misal P0 sedang mengunggu resource yang sedang ditahan (held) oleh P1, sementara P1 sedang menunggu resource lainnya yang ditahan oleh P2, selanjutnya … proses Pn-1 sedang menunggu resource lainnya yang ditahan oleh Pn, dan Pn juga sedang menunggu resource yang ditahan oleh P0.

Keempat kondisi-kondisi penyebab terjadinya deadlock tersebut tidak sepenuhnya independen, seperti kondisi circular-wait yang mengimplikasikan/kosenkuensi dari kondisi hold-and-wait.

Resource Allocation Graph (RAG)

Situasi deadlock dapat dideskripsikan kedalam graf secara tepat menggunakan sistem yang disebut dengan resource-allocation graph (RAG). Pada RAG terdiri dari himpunan disebut dengan simpul/vertices/nodes (V) dan himpunan sisi/arah/edges (E). Himpunan V dibagi kedalam dua jenis node yang berbeda yaitu node P = {P0, P1, P2, …, Pn}, terdiri dari sekumpulan proses pada sistem, dan node R = {R0, R1, R2, …, Rm}, terdiri dari berbagai resource pada sistem.

Pada pembahasan ini terdapat instilah instace of yang berarti perwujudan dari suatu kelas/himpunan menjadi objek. Contoh instance of resource Rj, yang berarti kelas sumber daya Rj dapat diwujudkan berupa objek seperti prosesor, memori, printer dll.

Arah edge dari proses Pi ke resource Rj dilambangkan/dinotasikan dengan Pi → Rj, yang berarti bahwa proses Pi meminta/request sebuah instance of resource Rj, dan sedang menunggu/memasuki status waitting resource tersebut, dan hal ini disebut dengan request edge. Sebaliknya jika arah edge dari resource Rj ke proses Pi dilambangkan dengan Rj → Pi, yang berarti bahwa instance of resource Rj telah dialokasikan ke proses Pi dan hal ini disebut dengan assigment edge.

Secara gambar, setiap proses Pi adalah lingkaran, setiap sumber daya Rj adalah persegi panjang, dan kerena jenis sumber daya mungkin lebih dari satu perwujudan/instance maka direpresentasikan sebagai titik dalam persegi panjang. Sebagai catatan pada gambar dibawah, setiap request edge hanya menunjuk ke persegi panjang Rj, sementara setiap assigment edge harus menunjukkan ke salah satu titik dalam persegi panjang.

Gambar Resource-Allocation Graph Tanpa Deadlock.

Berikut penjelasan mengenai situasi dan kondisi yang terdapat pada gambar RAG diatas.

• a. Himpunan P, R dan E.
  • P = {P1, P2, P3}
  • R = {R1, R2, R3, R4}
  • E = {P1 → R1, P2 → R3, R1 → P2, R2 → P1, R2 → P2, R3 → P3}
• b. Resource instance.
  • Terdapat 1 resource instance dari tipe R1.
  • Terdapat 2 resource instances dari tipe R2.
  • Terdapat 1 resource instance dari tipe R3.
  • Terdapat 3 resource instances dari tipe R4.
• c. Process states/status proses.
  • Proses P1 sedang menahan (holding) satu resource instance dari tipe R2, serta P1 menunggu (waitting) resource instace dari tipe R1.
  • Proses P2 sedang menahan (holding) dua resource instances dari tipe R1 dan R2, serta P2 sedang menunggu (waitting) resource instance dari tipe R3.
  • Proses P3 sedang menahan (holding) satu resource instances dari tipe R4.

Berdasarkan pendefenisian RAG diatas, dapat ditunjukkan bahwa tidak terdapat putaran/siklus (cycles) sehingga sistem ini tidak terjadi deadlock, sebaliknya jika terjadi siklus maka deadlock dapat terjadi.

Gambar Resource-Allocation Graph Dengan Deadlock.

Untuk mengilustrasikan konsep deadlock lebih lanjut, misalkan pada RAG gambar diatas ditambahkan proses P3 melakukan request instance of resource dari tipe R ,sehingga terdapat dua siklus yang mengakibatkan terjadinya deadlock pada sistem ini. Berikut proses state siklusnya.

• • P1 → R1→ P2 → R3 → P3 → R2 → P1
• • P2 → R3 → P3 → R2 → P2

Proses P1, P2, dan P3 mengalami deadlock. Hal ini terjadi karena proses P2 sedang menunggu request instance dari R3 yang sedang ditahan oleh proses P3, dan pada saat yang sama, P3 juga sedang menunggu proses P1 atau P2 untuk melepas resource instance dari tipe R2, serta proses P1 juga sedang menunggu proses P2 untuk melepaskan resource instance dari tipe R1.

Gambar RAG Dengan Cycle Tidak Deadlock.

Meskipun terdapat siklus pada sistem, belum tentu akan terjadi deadlock. Observasi pada gambar RAG dengan Cycle tidak Deadlock, bahwa proses P4 bisa saja melepas resource instance dari tipe R2, sehingga dapat dialokasikan untuk proses P3, serta memutuskan siklus/cycle. Begitu juga halnya request edge P1 → R1, mungkin saja proses P2 melepas resource instance dari tipe R1.

Referensi

1. Operating Systems: Internals and Design Principles (8th Edition), William Stallings, 2014.
2. Operating System Concepts (9th Edition in Chinese) by Abraham Silberschatz et al.
3. The Linux Programming Interface: A Linux and UNIX System Programming Handbook, Michael Kerrisk.