Kunci Mati (DeadLock)

Thread bisa diblok dan objek bisa memanggil metode synchronized ke suatu objek sehingga objek lain tidak bisa mengakses objek tersebut hingga kuncinya dilepas. Karenanya mungkin saja satu thread tersangkut menunggu suatu thread, akan tetapi thread yang ditunggu ini juga sedang menunggu thread lain, dan seterusnya. Jika rangkaian kunci kembali ke thread pertama, maka semua thread akan diam menunggu satu sama lain dan tidak akan pernah jalan. Kasus ini dinamakan kunci mati (deadlock).
Jika program yang kita buat tiba-tiba mengalamai deadlock, kita akan segera tahu dan memperbaikinya. Akan tetapi permasalahan utamanya adalah deadlock sulit untuk dideteksi. Sering kali program yang kita buat tampak baik-baik saja, akan tetapi mungkin menyimpan bahaya laten deadlock, yang suatu saat nanti terjadi ketika program sudah dirilis (bahkan sering kali deadlock ini juga tidak bisa direproduksi sehingga menyulitkan debugging). Mencegah deadlock dengan membuat desain program yang lebih hati-hati sangat penting ketika kita membuat program banyak thread.
Mari kita lihat contoh klasik dari deadlock yang ditemukan oleh Dijkstra, yaitu "ilmuwan yang sedang makan". Misalnya ada 5 orang ilmuwan (kita bisa mengganti berapa saja). Ilmuwan-ilmuwan ini menghabiskan sebagian waktu untuk berfikir dan sebagian lagi untuk makan. Ketika mereka berfikir, mereka tidak membutuhkan apa-apa, akan tetapi ketika mereka makan, mereka duduk di meja dengan jumlah alat makan yang terbatas. Mereka membutuhkan dua garpu untuk mengambil spaghetti dari mangkok di tengah meja.
Kesulitannya adalah karena ilmuwan tidak punya uang, mereka tidak mampu untuk membeli banyak garpu. Hanya ada 5 garpu yang tersedia. Garpu-garpu ini diletakkan di meja tersebar di dekat masing-masing ilmuwan ini. Ketika ilmuwan ingin makan, dia harus mengambil garpu di sebelah kiri dan kanannya. Jika ilmuwan di sebelahnya sedang menggunakan garpu tersebut, maka ia harus menunggu hingga garpunya selesai digunakan.
Persoalan ini menjadi menarik karena menjelaskan bahwa program yang sepertinya berjalan dengan benar akan tetapi mudah terkena deadlock. Kita bisa mengganti beberapa konstanta sehingga deadlock bisa lebih cepat terjadi, atau bisa dicegah sama sekali. Parameter-parameter yang bisa diganti adalah konstanta bertipe final static int di awal deklarasi kelas IlmuwanMakan. Jika kita menggunakan banyak ilmuwan dan waktu berfikir yang lama, deadlock akan lebih jarang terjadi.

package com.lyracc.ilmuwanmakan;
 
import java.util.*;
 
class Garpu {
    private static int hitung = 0;
    private int nomor = hitung++;
 
    public String toString() {
        return "garpu " + nomor;
    }
} // akhir kelas Garpu
 
class Ilmuwan extends Thread {
    private static Random acak = new Random();
    private static int hitung = 0;
    private int nomor = hitung++;
    private Garpu garpuKiri;
    private Garpu garpuKanan;
    static int waktuFikirMaks = IlmuwanMakan.WAKTU_FIKIR_MAKS;
 
    public Ilmuwan(Garpu kiri, Garpu kanan) {
        garpuKiri = kiri;
        garpuKanan = kanan;
        start();
    }
 
    // Ilmuwan berfikir, gunakan sleep untuk mensimulasi
    public void berfikir() {
        System.out.println(this + " berfikir");
        try {
            sleep(acak.nextInt(waktuFikirMaks));
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
 
    // Ilmuwan makan
    public void makan() {
        // cek apakah garpu kirinya tersedia
        synchronized (garpuKiri) {
            System.out.println(this + " punya " + this.garpuKiri
                    + ". Menunggu  " + this.garpuKanan);
 
            // kemudian cek apakah garpu kanannya tersedia
            synchronized (garpuKanan) {
                System.out.println(this + " makan");
            }
        }
    }
 
    public String toString() {
        return "Ilmuwan " + nomor;
    }
 
    // Metode ketika thread dijalankan
    // masing-masing ilmuwan akan berfikir kemudian makan
    // begitu seterusnya
    public void run() {
        while (true) {
            berfikir();
            makan();
        }
    }
} // akhir kelas ilmuwan
 
// Kelas timeout untuk menghentikan proses setelah
// waktu yang ditentukan
class Timeout extends Timer {
    public Timeout(int jeda, final String pesan) {
        super(true); // Daemon thread
        schedule(new TimerTask() {
            public void run() {
                System.out.println(pesan);
                System.exit(0);
            }
        }, jeda);
    }
} // akhir kelas Timeout
 
// Kelas utama
public class IlmuwanMakan {
    final static int JUMLAH_ILMUWAN = 3;   // bisa diganti
    final static int WAKTU_FIKIR_MAKS = 10; // mili detik, bisa diganti
    final static boolean DEADLOCK = true;  // ubah ini menjadi false untuk mencegah deadlock
    final static int WAKTU_TIMEOUT = 10000; // mili detik atau buat 0 jika tidak ingin timeout
 
    public static void main(String[] args) {
        // Buat array ilmuwan sejumlah JUMLAH_ILMUWAN
        Ilmuwan[] ilmuwan = new Ilmuwan[JUMLAH_ILMUWAN];
 
        // Mula-mula buat 2 garpu
        Garpu kiri = new Garpu();
        Garpu kanan = new Garpu();
 
        // Garpu pertama hanya sebagai penanda
        // yaitu garpu di kiri ilmuwan pertama
        Garpu pertama = kiri;
 
        int i = 0;
 
        // buat masing-masing ilmuwan
        // yang pertama memiliki garpu kiri dan kanan
        // ilmuwan kedua duduk di sebelah kanan ilmuwan pertama
        // sehingga garpu kirinya adalah garpu kanan ilmuwan pertama
        // buat garpu baru untuk garpu kanannya
        // demikian seterusnya hingga JUMLAH_ILMUWAN minus 1
        while (i < ilmuwan.length - 1) {
            ilmuwan[i++] = new Ilmuwan(kiri, kanan);
            kiri = kanan;
            kanan = new Garpu();
        }
 
        // Sekarang buat ilmuwan terakhir
        // Jika kita ingin membuat deadlock (makan menghadap meja) :
        // - garpu kirinya adalah garpu kanan ilmuwan sebelumnya
        // - garpu kanannya adalah garpu kiri ilmuwan pertama 
        //
        // Jika tidak (makan berbalik arah)
        // - garpu kirinya adalah garpu kiri ilmuwan pertama
        // - garpu kanannya adalah garpu kanan ilmuwan sebelumnya
        if (DEADLOCK)
            ilmuwan[i] = new Ilmuwan(kiri, pertama);
        else
            ilmuwan[i] = new Ilmuwan(pertama, kiri);
 
        // Keluar dari program setelah jeda waktu selesai
        if (WAKTU_TIMEOUT > 0)
            new Timeout(WAKTU_TIMEOUT, "Waktu habis..");
    }
}

Kelas Garpu dan Ilmuwan menggunakan penghitung otomatis untuk memberi nomor identifikasi tersendiri untuk setiap objek Garpu dan Ilmuwan yang diciptakan. Setiap Ilmuwan diberi referensi ke garpu kiri dan garpu kanan. Garpu-garpu ini akan diambil oleh ilmuwan ketika hendak makan.
Variabel statik waktuFikirMaks adalah waktu maksimum yang digunakan oleh ilmuwan untuk berfikir. Jika nilainya tidak nol, maka nilai variabel ini akan digunakan sebagai argumen perintah sleep() dalam kelas Ilmuwan. Mungkin kita beranggapan dengan mengubah waktu berfikir setiap ilmuwan, mereka tidak akan makan secara bersamaan sehingga kemungkinan terjadinya deadlock menjadi lebih kecil. Padahal sebenarnya tidak demikian.
Di dalam metode makan(), seorang ilmuwan akan mengambil garpu dengan melakukan sinkronisasi pada garpu tersebut. Jika garpu sedang digunakan oleh ilmuwan lain, maka ilmuwan tersebut akan menunggu hingga garpu selesai digunakan. Mula-mula garpu kiri dahulu yang dicoba untuk diambil, baru kemudian garpu kanan. Setelah digunakan, garpu kanan akan dilepas terlebih dahulu baru kemudian garpu kiri.
Dalam metode run() serorang ilmuwan makan dan berfikir terus menerus.
Ada empat konstanta yang bisa kita ubah-ubah di dalam kelas IlmuwanMakan. JUMLAH_ILMUWAN dan WAKTU_FIKIR_MAKS adalah banyaknya ilmuwan yang ada dan waktu fikir ilmuwan seperti dijelaskan sebelumnya. Variabel ketiga DEADLOCK berupa boolean yang bisa berisi true atau false. Jika bernilai true maka program cepat atua lambat pasti akan mengalami deadlock. Untuk menghindari deadlock, kita bisa menggantinya dengan false. Variabel keempat, yaitu WAKTU_TIMEOUT digunakan untuk menghentikan semua proses pada waktu tertentu. Pada proses yang sulit atau tidak mungkin deadlock (jika variabel DEADLOCK false, atau jumlah ilmuwan banyak, atau waktu fikir ilmuwan sangat panjang), maka proses akan berhenti pada waktu time out, seringkali sebelum deadlock terjadi.
Setelah array objek Ilmuwan dibuat, dua objek Garpu akan dibuat. Objek pertama, juga disimpan dalam variabel pertama akan digunakan kemudian. Setiap objek ilmuwan akan diberi garpu kiri dan kanannya, kecuali objek ilmuwan terakhir. Setiap kali, garpu kiri dipindah ke garpu kanan. Bayangkan meja ilmuwan dibuat dalam urutan melingkar berlawanan arah jarum jam. Garpu kiri ilmuwan baru adalah garpu kanan ilmuwan sebelumnya. Sedangkan garpu kanan ilmuwan baru adalah objek garpu baru.
Pada versi di mana DEADLOCK bernilai true, garpu kiri ilmuwan terakhir adalah garpu kanan ilmuwan sebelumnya, akan tetapi garpu kanannya adalah garpu pertama, karena semua ilmuwan duduk pada posisi melingkar. Dengan pengaturan seperti ini, mungkin saja pada suatu waktu semua ilmuwan akan makan dan saling menunggu garpu di sebelahnya, dan ilmuwan sebelahnya menunggu garpu sebelahnya lagi. Dan karena posisi duduknya melingkar, semua saling menunggu satu sama lain.
Coba ganti variabelnya dengan beberapa nilai dan amati seberapa cepat deadlock terjadi. Deadlock ditandai dengan semua ilmuwan saling menunggu satu sama lain hingga waktu time out berakhir. (Seperti pada gambar berikut).

Untuk memecahkan masalah ini, kita harus mengerti bahwa deadlock bisa terjadi jika keempat kondisi berikut ini terjadi pada saat yang sama :

1. Saling melarang (mutual exclusion): Paling sedikit salah satu sumber daya yang digunakan objek tidak boleh digunakan bersama. Dalam hal ini, satu garpu bisa digunakan oleh dua orang ilmuwan
2. Paling sedikit salah satu proses sedang memegang suatu sumber daya, dan di saat yang sama menunggu sumber daya lain yang dipegang oleh proses lain. Dalam hal ini, agar deadlock terjadi, seorang ilmuwan pasti sedang memegang satu garpu dan menunggu garpu lain yang dipegang oleh ilmuwan lain.
3. Suatu sumber daya tidak bisa diambil secara paksa. Proses hanya bisa melepas sumber daya dalam kondisi normal. Ilmuwan-ilmuwan kita adalah orang yang beradab, sehingga tidak bisa merebut garpu yang sedang dipegang oleh ilmuwan lain.
4. Lingkaran menunggu sedang terjadi, di mana proses pertama sedang menunggu satu sumber daya yang dipegang oleh proses kedua, yang juga sedang menunggu sumber daya yang dipegang oleh proses ketiga, dan seterusnya hingga proses terakhir menunggu sumber daya yang dipegang oleh proses pertama, sehingga semua proses saling menunggu satu sama lain. Pada contoh ini, lingkaran menunggu terjadi karena semua ilmuwan mengambil garpu kiri terlebih dahulu baru kemudian garpu kanan. Kita bisa memecahkan deadlock dengan membalik garpu kiri dan garpu kanan pada ilmuwan terakhir, sehingga ilmuwan terakhir akan mengambil garpu kanan terlebih dahulu, baru kemudian garpu kiri.

Karena semua kondisi di atas harus terjadi secara bersama-sama agar deadlock bisa terjadi, maka untuk mencegah terjadinya deadlock, kita harus memecah salah satu kondisi saja. Pada program ini, cara termudah adalah dengan memecah kondisi keempat. Akan tetapi ini bukan satu-satunya pemecahan, kita bisa memecahkannya dengan teknik yang lebih canggih. Untuk ini saya mereferensikan Anda pada buku-buku teknik threading tingkat lanjut untuk lebih detailnya.
Kesimpulannya, Java tidak menyediakan bantuan secara alami untuk mencegah deadlock: Anda harus menghindarinya sendiri dengan membuat program multi threading dengan lebih hati-hati.

Sumber : http://java.lyracc.com/belajar/java-untuk-pemula/kunci-mati-deadlock