Deadlock dan Starvation

Prinsip-Prinsip Deadlock

1. Definisi Deadlock

    Pemblokiran permanen sejumlah proses yang berkompetesi dalam mendapatkan sumber daya sistem                  atau yang berkomunikasi satu dengan lainnya.
    Semua Deadlock mencakup konflik kebutuhan akan sumber daya oleh dua proses atau lebih. Contoh yang umumnya adalah Deadlock lalu lintas . Gambar 1.1 menunjukan situasi empat mobil tiba dipersimpangan empat arah dalam waktu yang hampir bersamaan. keempat kuadran persimpangan itu merupakan sumber daya yang memerlukan kontrol, pada suatu saat, apabila keempat mobil itu ingin melintasi persimpangan, persyaratan sumber dayanya adalah sebagai berikut:

• Mobil yang bergerak ke utara membutuhkan kuadran 1 dan kuadran 2.
• Mobil yang bergerak ke barat membutuhkan kuadran 2 dan kuadran 3.
• Mobil yang bergerak ke selatan membutuhkan kuadran 3 dan kuadran 4.
• Mobil yang bergerak ke timur membutuhkan kuadran 4 dan kuadran 1.

Aturan jalan raya yang normal adalah bahwa mobil yang berada dipersimpangan empat arah harus memberikan jalan kepada mobil yang berada disebelah kanannya. Aturan ini akan berfungsi apabila terdapat hanya dua atau tiga mobil di persimpangan itu, Misalnya, apabila hanya mobil yang menuju utara dan yang menuju barat tiba dipersimpangan, mobil yang menuju utara akan menunggu, sedangkan mobil yang menuju barat melanjutkan perjalanannya. Namun apabila empat buah mobil tiba dipersimpangan pada saat yang hampir bersamaan, keempat mobil itu akan terjadi Deadlock.

• Penjelasan Deadlock (Gambar 1.1)

•  Contoh Deadlock (Gambar 1.2)

Apabila keempat mobil itu mengabaikan aturan  dan melanjutkan perjalanan dengan melintasi persimpangannya, keempat mobil itu akan mengambil satu sumber daya (satu kuadran) namun tidak dapat melanjutkan perjalannya karena sumber daya yang keduanya diperlukan telah diambil oleh mobil lainnya.   


       
2. Penyebab Deadlock  / Syarat Terjadi Deadlock

•     Mutual Exclusion : Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada    suatu waktu.

•     Hold and Wait : Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber daya dapat meminta    sumber daya yang lain.

•     Non-pre-emptive : Kondisi dimana suatu sumber daya yang sedang berada pada suatu proses tidak dapat diambil secara paksa dari proses tersebut,sampai proses itu melepaskannya.

•     Circular Wait : Kondisi yang menyatakan bahwa adanya rantai saling meminta sumber daya yang dimiliki oleh suatu proses oleh proses lainnya.

3. Menghindari Deadlock
    Sistem perlu memiliki informasi awal mengenai kebutuhan sumber daya

•  Tiap proses menyatakan kebutuhan maksimum tiap jenis sumber yg dibutuhkan
•  Algoritma deadlock-avoidance secara dinamis memeriksa state alokasi sumber daya untuk   menjamin tdk terjadinya kondisi circular-wait
• State alokasi sumber daya didefinisikan oleh banyaknya sumber daya yg tersedia dan yg dialokasikan, dan permintaan sumber daya maksimum oleh proses

Jika proses meminta sumber daya yg tersedia, sistem harus memutuskan apakah alokasi sumber daya ini   akan menghasilkan safe state
Sistem berada pada safe state jika terdapat urutan event yg tidak menyebabkan deadlock jika semua proses meminta sumber daya maksimum sekaligus

•   Logikanya:
     – Jika sistem berada pd safe state 􀃆 no deadlock
     – Jika sistem berada pd unsafe state 􀃆 kemungkinan deadlock
     – Pencegahan: sistem tidak masuk ke unsafe state

4. Mengatasi Deadlock
   Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku

• Mutual Exclusion : membuat file spool untuk resource yang digunakan bersama-sama
• Hold and Wait : memaksa sebuah proses untuk melepaskan resource yang dimilikinya ketika meminta resource baru
• Circular Waiting : memberikan penamaan resource berdasarkan urutan atau level
• No Preemption : membolehkan adanya preemption
• Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker
• Resource manager menolak proses yang meminta resource yang berpotensi deadlock
• Jika ada permintaan resource yang maksimum digunakan, maka proses tersebut akan dipaksa untuk melepaskan resource yang sudah dimiliknya
• Perlu adanya informasi tambahan
• Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery, Algoritma Ostrich
• Tindakan recovery yang dilakukan adalah : melakukan preemption, membuat checkpoint untuk rollback lalu membunuh proses yang prioritasnya kecil

5. Mencegah Deadlock
    Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan
    Jika proses telah sedang memegang resource tertentu, untuk permintaan berikutnya proses harus melepas dulu resource yg dipegangnya.
    Beri pengurutan linear terhadap resource pada semua proses