Ch 7 : Deadlock

Deadlock Problem

Deadlock Problem terjadi karena sekumpulan proses-proses yang di-blok dimana setiap proses membawa sebuah resource dan menunggu untuk mendapatkan resource yang dibawa proses lain.

Misalnya dalam sistem terdapat 2 buah disk drive dan terdapat 2 proses. Masing-masing proses membawa 1 disk drive dan masing-masing membutuhkan disk drive yang dibawa oleh proses lain sehingga terjadi keadaan saling menunggu resource dan proses akan di-blok.

Deadlock Problem juga bisa dimisalkan pada Bridge Crossing Example.

System Model

Dalam sebuah sistem terdapat beberapa resource yang digunakan oleh proses-proses untuk menyelesaikan task. Resource tersebut terdiri dari CPU cycles, memory space, I/O devices yang disebut resource type R₁, R₂, ..., R_n . Setiap resource mempunyai beberapa anggota W_i. Setiap prses menggunakan resource sesuai urutan :

·         Request
·         Use
·         Release

Deadlock Characteristic

Deadlock dapat terjadi bila 4 kondisi ini terpenehi :

·         Mutual Exclusion : Hanya satu proses pada satu waktu yang dapat menggunakan sebuah resource
·         Hold and Wait : Sebuah proses yang membawa sedikitnya satu resource menunggu untuk mendapatkan tambahan resource yang dibawa oleh proses lain.
·         No Preemption : Sebuah resource dapat dilepas secara voluntir oleh proses yang memegangnya bilamana proses tersebut telah menyelesaikan task.
·         Circular Wait :   Terdapat sekumpulan proses yang saling menunggu resource yang dibawa oleh proses-proses dalam kumpulan itu.

Deadlock dapat digambarkan lebih presisi menggunakan resource allocation graph.

Notasi yang digunakan pada resource allocation graph :

Contoh resource allocation graph yang terjadi deadlock :

Contoh resource allocation graph yang tidak terjadi deadlock :

Bisa dilihat bahwa P₄ tidak membutuhkan resource lain sehingga dia dapat melepaskan R₂ yang dipegangnya secara voluntir dan dapat digunakan oleh P₃ sehinggat tidak terjadi keadaan saling membutuhkan.

Methods for Handling Deadlocks

Ada 3 metode untuk menangani deadlock.

•          Menggunakan Protocol untuk memastikan tidak terjadi deadlock pada sistem.
•          Mengijinkan sistem memasuki deadlock dan kemudian di-recover.
•          Mengabaikan masalah dan berpura-pura seakan deadlock tidak pernah terjadi pada sistem. Metode ini yang paling banyak diterapkan oleh sistem operasi, termasuk UNIX.

Deadlock Prevention

Untuk melakukan pencegahan deadlock, bisa dilakukan dengan mencegah salah satu kondisi yang menyebabkan terjadinya deadlock.

•          Mencegah Mutual Exclusion : Resource pada sistem harus tidak dapat digunakan bersama-sama (nonsharable resource).
•          Mencegah Hold and Wait : Harus ada jaminan bahwa tiap proses meminta resource, resource tersebut tidak sedang dibawa oleh proses lain.
•          Mencegah No Preemption : Jika suatu proses meminta resource yang tidak dapat langsung dipenuhi, maka proses tersebut harus melepaskan semua resource yang dibawanya. Resource pada proses yang sedang waiting akan ditunda dan ditambahkan ke daftar resource. Proses hanya akan di-restart jika ia dapat memperoleh resource lama dan resource barunya.
•          Mencegah Circular Wait : Sistem mempunyai daftar permintaan resource dari semua proses dan diurut secara numerik.

     Deadlock Avoidance

      Untuk menghindari terjadinya dealock, bisa dilakukan dengan mengetahui informasi tambahan tentang bagaimana resource digunakan. Model yang paling sederhana dan berguna membutuhkan informasi tentang jumlah maksimum resource dari tiap tipe yang mungkin dibutuhkan. Deadlock-avoidance algorithm secara dinamis akan memeriksa status alokasi resource untuk memastikan tidak terjadinya kondisi circular-wait. Status alokasi resource ditentukan oleh jumlah resource yang tersedia, yang telah dialokasikan dan permintaan maksimum dari proses-proses.

      Untuk menghindari deadlock, kita perlu juga mengetahui tentang safe state dan unsafe state. Sistem dikatakan safe state jika sistem tersebut dapat mengalokasikan resource secara berurutan untuk setiap proses sehingga tidak terjadi deadlock. Misalkan sistem mempunyai 9 resource dan proses P_i dan P_j, proses P_i membutuhkan 5 resource untuk menyelesaikan task dan baru memegang 4 resource, P_j membutuhkan 8 resource dan baru memegang 3 resource, sehingga hanya tersisa 2 resource yang masih bebas. Sistem harus menentukan urutan proses dalam penggunaan resource tersebut, karena resource yang bebas tidak mampu memenuhi kebutuhan P_j, maka P_j harus menunggu hingga P_i menyelesaikan task-nya, sehingga Pj bisa menggunakan resource yang ada di P_i dan sistem menjadi safe state. Sebaliknya, bila sistem tidak dapat mengalokasikan resource, maka sistem akan menjadi usnsafe state dan memungkinkan terjadinya deadlock.

      Ada 2 macam algoritma yang bisa digunakan untuk menghindari deadlock, yaitu resource-allocation graph algorithm (untuk menghindari deadlock pada sistem yang hanya mempunyai satu instance saja pada tiap resource)  dan banker’s algorithm (untuk menghindari deadlock pada sistem yang mempunyai banyak instance untuk tiap resource).

      Dalam resource-allocation graph algorithm, terdapat istilah claim edge dan request edge. Claim edge menandakan bahwa suatu proses mungkin akan meminta suatu resource (digambarkan dengan tanda panah putus-putus) dan request edge menandakan bahwa proses tersebut melakukan permintaan terhadap suatu resource (digambarkan dengan tanda panah langsung). Claim edge akan berubah menjadi request edge bila proses meminta resource. Request edge akan kembali menjadi claim edge saat proses selesai menggunakan resource.

      Contoh bisa dilihat pada gambar di bawah ini.

      Pada gambar bisa dilihat bahwa P₁ dan P₂ mungkin akan membutuhkan R₂ untuk menyelesaikan task. Bila sistem mengalokasikan R₂ pada P₂ maka akan memungkinkan terjadinya cycle yang menyebabkan deadlock. Sehingga sistem tidak boleh mengalokasikan R₂ pada P₂,  bila sistem memaksa mengalokasikan maka akan terjadi keadaan unsafe state seperti pada gambar di bawah ini.

  

      Dalam algoritma Banker, terdapat 4 struktur data yang dibutuhkan, yaitu :

      (n=jumlah proses & m= jumlah resource)

•          Available : Vektor panjang m. Jika Available[j]=k, terdapat k instance tipe resource R_j yang tersedia.
•          Max : Matriks m x n. Jika Max[i,j]=k, maka proses P_i hanya bisa meminta maksimal sebanyak k instance tipe resource R_j.
•          Allocation : Matriks n x m. Jika Allocation[i,j]=k, maka proses P_i sedang dialokasikan sebanyak k instance tipe resource R_j.
•          Need : Matriks n x m. Jika Need[i,j]=k, maka P_i membutuhkan sebanyak k instance tipe resource R_j untuk menyelesaikan task.

      Need [i,j] = Max[i,j] – Allocation [i,j]

      Ada 2 algoritma dalam Algoritma Banker, yaitu Safety Algorithm dan Resource-Request Algorithm.

     Safety Algorithm digunakan untuk menentukan apakah sistem dalam keadaan safe atau unsafe. Algoritma : 

       1.      Anggap Work dan Finish adalah vektor dengan panjang m dan n.

           Inialisasikan:

Work = Available

Finish [i] = false for i = 0, 1, …, n- 1

      2.      Cari i yang memenuhi kondisi berikut:

(a)    Finish [i] = false

(b)   Need_i £ Work

             Jika tidak ada i yang memenuhi langsung ke langkah 4

       3.      Work = Work + Allocation_i
       Finish[i] = true
       Kembali ke langkah  2.

       4.      If Finish [i] == true untuk semua i, maka sistem dalam keadaan safe state.

      Resource-Request Algorithm. Request_i adalah vektor permintaan untuk proses P_i.  Jika Request_i [j] = k maka proses P_i menginginkan k instances dari resource type R_j.

      Algoritmanya :

      1.      Jika Request_i £ Need_i  ke langkah 2.  Selain itu, terjadi kondisi error, proses melebihi jumlah claim maksimum.

      2.      Jika Request_i £ Available, ke langkah 3. Selain itu P_i  harus menunggu karena resource tidak tersedia.

      3.      Alokasikan resource ke  P_i dengan modifikasi state sebagai berikut:

·   Available = Available  – Request;

·   Allocation_i = Allocation_i + Request_i;

·   Need_i = Need_i – Request_i;

•          Jika kondisi safe Þ Resources dialkokasikan ke Pi.
•          Jika kondis  unsafe Þ Pi harus menunggu dan alokasi resource yang lama dikembalikan.

     Deadlock Detection

      Untuk mendeteksi adanya deadlock, sistem harus menyedikan algoritma untuk menguji keadaan sistem apakah deadlock telah terjadi dan algoritma untuk memperbaiki deadlock.

      Untuk deadlock dengan single instance pada tiap resource type, kita dapat mendeteksi adanya deadlock dengan menggunakan bentuk resource allocation graph yang disebut wait-for graph. Pada wait-for graph, notasi PiàRxàPj diganti menjadi PiàPj. Jadi yang terlihat hanya proses menunggu proses lain.

      

      Contoh :

       Resource allocation graph

       Wait-for graph

      Untuk deadlock dengan Several Instances pada tiap resource type, kita bisa mendeteksi dengan menggunakan algoritma yang mirip dengan algoritma Banker.

      Struktur data yang dibutuhkan :

·         Available : Vektor panjang m menandakan jumlah resource yang tersedia untuk tiap resource type.

·         Allocation : Matriks n x m yang mendefinisikan jumlah resource untuk setiap resource type yang sedang dialokasikan pada tiap proses.

·         Request : Matriks n x m yang mendefinisikan permintaan tiap proses. Jika Request[i,j]=k, maka proses P_i meminta k instance dari resource type R_j.

       Algoritma :

          1.      Anggap Work dan Finish adalah vektor panjang m dan n

                 Inisialisasikan:

(a)    Work = Available

(b)   For i = 1,2, …, n, if Allocationi != 0, then
 Finish[i] = false;otherwise, Finish[i] = true

           2.      Cari indeks i yang memenuhi kondisi berikut :

(a)    Finish[i] == false

(b)   Request_i £ Work

Jika tidak ada i yang memenuhi, maka masuk ke langkah ke 4.

            3.      Work = Work + Allocation_i
            Finish[i] = true
            Kembali ke langkah 2

             4.      If Finish[i] == false, for some i, 1 £ i £  n, maka sistem dalam keadaan deadlock. Moreover, if                   Finish[i] == false, maka P_i deadlock.

      Algoritma ini memerlukan operasi O(m x n²) untuk mendeteksi apakah sistem dalam keadaan deadlock atau tidak.

      Seberapa sering perlunya dilakukan deteksi deadlock, tergantung seberapa sering deadlock terjadi dan berapa proses yang dibutuhkan untuk roll back.

     Recovery from Deadlock

      Ada 2 macam cara untuk memperbaiki deadlock yaitu process termination dan resource preemption.

     Metode yang digunakan dalam process termination ialah :

•          Menghentikan (abort) semua proses yang deadlock.
•          Menghentikan satu demi satu proses tiap waktu hingga siklus deadlock hilang.

      Metode yang digunakan dalam resource preemption ialah dengan resource pada satu proses harus diambil dan diberikan ke proses lain hingga siklus deadlock hilang. Hal yang harus diperhatikan dalam resource preemption ialah :

•          Pilih korban (proses) yang bernilai kecil.
•          Lakukan roll back (me-restart proses, kembali ke safe state).
•          Jangan sampai terjadi starvation.
• 
  

      Agar sebuah sistem dapat menangani deadlock secara maksimal, maka sistem tersebut harus mempunyai algoritma untuk mencegah, menghindari, mendeteksi dan memperbaiki deadlock.

S   Sumber : Operating System Concepts with Java 8th Edition - Silberschatz

•