Deadlock

Prinsip dari deadlock

Deadlock ialah suatu kondisi permanen dimana proses tidak berjalan lagi ataupun tidak ada komunikasi lagi antar proses. Deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses lain yang sedang menunggu sumber daya yang dipegang oleh proses tersebut. Atau dengan kata lain setiap proses dalam set menunggu untuk sumber yang hanya bisa dikerjakan oleh proses lain dalam set yang sedang menunggu. Contoh yang paling mudah ialah gambar berikut ini

Pada gambar diatas, tidak ada yang dapat maju karena keduanya memperebutkan jalan yang sama ( yang dilingkari ), demikian juga deadlock saat semua proses memperebutkan sumber yang sama. Contoh lain yang dapat merepresentasikan deadlock ialah jembatan gantung sebagai berikut :

sehingga orang yang ada di sebelah kiri jembatan tidak dapat melaju sebab terjadi deadlock di tengah jembatan ( bagian yang dilingkari ).Contoh lain ialah di persimpangan jalan jalan berikut ini:

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 bisa dikatakan bahwa setiap mobil tidak bisa meanjutkan perjalanan lagi atau dengan kata lain terjadi deadlock. Contoh lain pada proses yang secara umum terdiri dari tiga tahap, yaitu untuk meminta, memakai, dan melepaskan sumber daya yang di mintanya. Contoh kode-nya :

public class Proses {
    public synchronized void getA() {
        //proses untuk mendapat sumber daya a 
    }
    
    public synchronized void getB(){
        //proses untuk mendapat sumber daya b
    }
    
    public void releaseA(){
        //proses untuk melepaskan sumber daya a
    }
    
    public void releaseB(){
        //proses untuk melepaskan sumber daya b
    }
}

public class Coba {
    public static void main(String [] args) {
        Proses P = new Proses();
        Proses Q = new Proses();
        P.getA();
        Q.getB();
        P.getB();
        Q.getA();
    }
}
    

tanpa adanya perintah untuk mereleased artinya saat P mendapatkan A dan Q mendapatkan B, tetapi tidak dilepaskan, maka saat P minta B dan Q minta A, maka keduanya akan saling menunggu hingga salah satu melepaskan sumber dayanya, sedangkan kebutuhan P ada pada Q dan Q ada pada P, sehingga terjadi deadlock. Secara umum kejadian ini dapat mudah terjadi dalam pemrograman multi-thread. Sebab ada kemungkinan lebih besar untuk menggunakan sumber daya bersama.

Sumber Daya

Kejadian deadlock selalu tidak lepas dari sumber daya, seperti kita lihat dari contoh contoh diatas, 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 bisa digunakan lagi berulang-ulang dan sumber daya yang bisa digunakan dan habis dipakai atau bisa dikatakan sumber daya sekali pakai.

Sumber Daya yang Bisa Dipakai Berulang-Ulang

Sumber daya ini tidak habis dipakai oleh proses manapun.Tetapi setelah proses berakhir, sumber daya ini dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian sumber daya ini. Contohnya prosesor, kanal I/O, disk, semaphores. 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 deadlock dari sumber yang dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses yang memakai memori utama. Contohnya dapat dilihat dari kode berikut ini:

//dari kelas proses kita tambahkan method yaitu meminta
public void meminta( int banyakA ) {
    //meminta dari sumber daya a
    if ( banyakA < banyak )
         banyak = banyak - banyakA;
    else
        wait();
}

//mengubah kode pada mainnya sebagai berikut
public static void main ( String [] args ) {
    Proses P = new Proses();
    Proses Q = new Proses();
    P.meminta(80);
    Q.meminta(70);
    P.meminta(60);
    Q.meminta(80);
}

private int banyak = 200;
private int banyakA;
      

Setelah proses P dan Q telah melakukan fungsi meminta untuk pertama kali, maka sumber daya yang tersedia dalam banyak ialah 50 ( 200-70- 80). Maka saat P menjalankan fungsi meminta lagi sebanyak 60, maka P tidak akan menemukan sumber daya dari banyak sebanyak 60, maka P akan menunggu hingga sumber daya yang diminta dipenuhi. Demikian juga dengan Q, akan menunggu hingga permintaannya dipenuhi, akhirnya terjadi deadlock. Cara mengatasinya dengan menggunakan memori maya.

Kondisi untuk Terjadinya deadlock

Menurut Coffman( 1971 ) ada empat kondisi yang bisa mengakibatkan terjadinya deadlock, yaitu :

  1. Mutual Eksklusif: 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. Memegang dan menunggu: 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 bisa menyebabkan kelaparan sumber daya sebab bisa saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama

  3. Tidak ada 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: adanya kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya

Penanganan deadlock

Banyak cara untuk menanggulangi deadlock:

  1. Mengabaikan masalah deadlock.

  2. Mendeteksi dan memperbaiki

  3. 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 men- data informasi tambahan tentang proses mana yang akan meminta dan menggunakan sumber daya.

  4. Pencegahan yang secara struktur bertentangan dengan 4 kondisi terjadinya deadlock dengan deadlock prevention sistem untuk memasti- kan bahwa salah satu kondisi yang penting tidak dapat menunggu.

Mendeteksi dan Memperbaiki

Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi sistem mana yang terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka diadakan proses untuk memperbaiki dan menjadikan sistem berjalan kembali. Ada beberapa jalan untuk kembali dari deadlock:

Menghindari deadlock

Pada sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja. Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak( dalam arti tidak terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:

  1. Jangan memulai proses apapun jika proses tersebut akan membawa kita pada kondisi deadlock, sehingga tidak mungkin terjadi deadlock karena ketika akan menuju deadlock sudah dicegah

  2. Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan membawa kita pada suatu keadaan deadlock

Jadi diadakan dua kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan ditambah dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar jangan sampai terjadi deadlock. Pada deadlock avoidance sistem dilakukan dengan cara memastikan bahwa program memiliki maksimum permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan selalu dalam kondisi aman. Baik mengadakan permintaan awal ataupun saat meminta permintaan sumber daya tambahan, sistem harus selalu berada dalam kondisi aman.

Algoritma Bankir

Menurut Dijstra (1965) algoritma penjadwalan dapat menghindari deadlock dan algoritma penjadwalan itu lebih dikenal dengan sebutan algoritma bankir. Algoritma ini dapat digambarkan sebagai seorang bankir dikota kecil yang berurusan dengan kelompok orang yang meminta pinjaman. Jadi kepada siapa dia bisa memberikan pinjamannya.Dan setiap pelanggan memberikan batas pinjaman maksimum kepada setiap peminjam dana.

Tentu saja si bankir tahu bahwa si peminjam tidak akan meminjam dana maksimum yang mereka butuhkan dalam waktu yang singkat melainkan bertahap. Jadi dana yang ia punya lebih sedikit dari batas maksimum yang dipinjamkan. Lalu ia memprioritaskan yang meminta dana lebih banyak, sedangkan yang lain disuruh menunggu hingga peminta dana yang lebih besar itu mengembalikan pinjaman berikut bunganya, baru setelah itu ia meminjamkan pada peminjam yang menunggu.

Jadi algoritma bankir ini mempertimbangkan apakah permintaan mereka itu sesuai dengan jumlah dana yang ia miliki, sekaligus memperkirakan jumlah dana yang mungkin diminta lagi. Jangan sampai ia sampai pada kondisi dimana dananya habis dantidak bisa meminjamkan uang lagi. Jika demikian maka akan terjadi kondisi deadlock. Agar kondisi aman, maka asumsi setiap pinjaman harus dikembalikan waktu yang tepat.

Secara umum algoritma bankir dapat dibagi menjadi 4 struktur data :

  1. Tersedia : jumlah sumber daya/dana yang tersedia

  2. Maksimum : jumlah sumber daya maksimum yang diminta oleh setiap proses

  3. Alokasi : jumlah sumber daya yang dibutuhkan oleh setiap proses

  4. Kebutuhan : sumber daya yang sedang dibutuhkan oleh setiap proses

Pencegahan deadlock

Jika pada awal bab ini kita membahas tentang ke-empat hal yang menyebabkan terjadinya deadlock. Maka pada bagian ini, kita akan membahas cara menanggulangi keempat penyebab deadlock itu, sehingga dengan kata lain kita mengadakan pencegahan terhadap deadlock.

Penanggulangannya ialah sebagai berikut :

  1. Masalah Mutual Eksklusif Kondisi ini tidak dapat dilarang, jika aksesnya perlu bersifat spesial untuk satu proses, maka hal ini harus di dukung oleh kemampuan sistem operasi. Jadi diusahakan agar tidak mempergunakan kondisi spesial tersebut sehingga sebisa mungkin deadlock bisa dihindari.

  2. Masalah Kondisi Menunggu dan Memegang Penanggulangan deadlock dari kondisi ini lebih baik dan menjanjikan, asalkan kita bisa menahan proses yang memegang sumber daya untuk tidak menunggu sumber daya laun, kita bisa mencegah deadlock. Caranya ialah dengan meminta semua sumber daya yang ia butuhkan sebelum proses berjalan. Tetapi masalahnya sebagian proses tidak mengetahui keperluannya sebelum ia berjalan. Jadi untuk mengatasi hal ini, kita dapat menggunakan algoritma bankir. Yang mengatur hal ini bisa sistem operasi ataupun sebuah protokol. Hasil yang bisa terjadi ialah sumber daya lebih di-spesifikasi dan kelaparan sumber daya, atau proses yang membutuhkan sumber daya yang banyak harus menunggu sekian lama untuk mendapat sumber daya yang dibutuhkan.

  3. Masalah tidak ada Preemption Hal ketiga ialah jangan sampai ada preemption pada sumber daya yang telah dialokasikan. Untuk memastikan hal ini, kita bisa menggunakan protokol. Jadi jika sebuah proses meminta sumber daya yang tidak dapat dipenuhi saat itu juga, maka proses mengalami preempted. Atau dengan kata lain ada sumber daya dilepaskan dan diberikan ke proses yang menunggu, dan proses itu akan menunggu sampai kebutuhan sumber dayanya dipenuhi.

    Atau kita harus mencek sumber daya yang dimaui oleh proses di cek dahulu apakah tersedia. Jika ya maka kita langsung alokasikan, sedangkan jika tidak tersedia maka kita melihat apakah ada proses lain yang menunggu sumber daya juga. Jika ya, maka kita ambil sumber daya dari proses yang menunggu tersebut dan memberikan pada proses yang meminta tersebut. Jika tidak tersedia juga, maka proses itu harus menunggu. Dalam menunggu, beberapa dari sumber dayanya bisa saja di preempted, tetapi jika ada proses yang memintanya. Cara ini efektif untuk proses yang menyimpan dalam memory atau register.

  4. Masalah Circular Wait Masalah ini dapat ditangani oleh sebuah protokol yang menjaga agar sebuah proses tidak membuat lingkaran siklus yang bisa mengakibatkan deadlock