Deadlock terjadi ketika dua atau lebih thread saling menunggu kunci yang dipegang thread lain, sehingga tidak ada yang bisa maju—program menggantung selamanya. Deadlock adalah bug paling sulit didiagnosis karena tidak ada pesan error: program hanya berhenti merespons. Pada chapter ini kita mereproduksi deadlock klasik dengan dua thread dan dua mutex (masing-masing thread mengunci urutan berbeda), lalu mengatasinya dengan dua solusi konkret: lock ordering (konvensi urutan kunci yang sama di seluruh kode) dan timed lock (memberi batas waktu agar thread bisa melepas kunci yang dipegang dan mencoba lagi).

Empat Kondisi Coffman #

Menurut kondisi Coffman (1971), deadlock terjadi hanya bila keempat kondisi berikut terpenuhi secara bersamaan:

  1. Mutual exclusion: Sumber daya (mutex) tidak bisa dipakai bersama—hanya satu thread pada satu waktu.
  2. Hold and wait: Thread memegang satu kunci sambil menunggu kunci lain.
  3. No preemption: Kunci tidak bisa diambil paksa—harus dilepas sukarela oleh pemegang.
  4. Circular wait: Ada siklus thread A menunggu thread B, thread B menunggu thread A.

Memutus salah satu kondisi sudah cukup mencegah deadlock. Strategi paling umum adalah memutus circular wait lewat lock ordering, atau memutus no preemption dengan timeout.

Visualisasi Konsep #

Diagram berikut memperlihatkan siklus circular wait klasik: Thread 1 memegang mutex A sambil menunggu mutex B, sedangkan Thread 2 memegang mutex B sambil menunggu mutex A—tidak ada yang bisa maju:

Pada diagram di atas, Thread 1 dan Thread 2 sama-sama memegang satu mutex sambil menunggu mutex yang dipegang oleh thread lain. Tanda panah penuh menyatakan kepemilikan (thread memegang kunci), dan tanda panah putus-putus menyatakan penantian (thread memblok menunggu kunci tersedia). Karena tidak ada thread yang bersedia melepas kunci yang sudah dimiliki—hold and wait—dan tidak ada mekanisme untuk mengambil kunci paksa—no preemption—siklus tidak pernah pecah dan program menggantung selamanya. Solusi paling umum adalah lock ordering: menetapkan urutan global (misalnya selalu kunci A dulu sebelum B) sehingga siklus tidak pernah terbentuk. Alternatif lain adalah timed lock (pthread_mutex_timedlock) yang memberi batas waktu—bila waktu habis, thread melepas kunci yang sudah dimiliki dan mencoba lagi.

Reproduksi Deadlock Klasik #

Program berikut membuat dua thread yang masing-masing butuh dua mutex (A dan B). Thread 1 mengunci A dulu, lalu B. Thread 2 mengunci B dulu, lalu A. Karena keduanya jalan paralel dan jeda 50 ms diselipkan di antara dua lock, deadlock hampir pasti terjadi.

c 
/* File: deadlock_klasik.c - deadlock: dua thread, dua mutex, urutan berbeda */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>
#include <time.h>

static pthread_mutex_t mutex_A = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t mutex_B = PTHREAD_MUTEX_INITIALIZER;

static void jeda_ms(int ms) {
    struct timespec ts = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&ts, NULL);
}

/* Thread 1: kunci A dulu, lalu B */
static void *thread1(void *arg) {
    (void) arg;
    printf("[T1] mengunci A...\n");
    pthread_mutex_lock(&mutex_A);

    jeda_ms(50);                       /* beri waktu thread2 mengunci B */

    printf("[T1] mencoba mengunci B...\n");
    pthread_mutex_lock(&mutex_B);       /* <-- DEADLOCK di sini */

    printf("[T1] memegang A dan B\n");
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return NULL;
}

/* Thread 2: kunci B dulu, lalu A (urutan terbalik!) */
static void *thread2(void *arg) {
    (void) arg;
    printf("[T2] mengunci B...\n");
    pthread_mutex_lock(&mutex_B);

    jeda_ms(50);

    printf("[T2] mencoba mengunci A...\n");
    pthread_mutex_lock(&mutex_A);       /* <-- DEADLOCK di sini */

    printf("[T2] memegang B dan A\n");
    pthread_mutex_unlock(&mutex_A);
    pthread_mutex_unlock(&mutex_B);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);

    /* Beri batas 3 detik; bila tidak selesai, deadlock terjadi */
    struct timespec batas = { 3, 0 };
    nanosleep(&batas, NULL);

    printf("[main] 3 detik berlalu, kemungkinan deadlock!\n");
    return 0;
}

Compile dan jalankan dengan timeout untuk memastikan tidak menggantung selamanya:

bash 
gcc -std=c11 -Wall -Wextra -pthread -o deadlock_klasik deadlock_klasik.c
timeout 5 ./deadlock_klasik
echo "exit code: $?"

Output yang Dihasilkan:

text 
[T2] mengunci B...
[T1] mengunci A...
[T2] mencoba mengunci A...
[T1] mencoba mengunci B...
[main] 3 detik berlalu, kemungkinan deadlock!

Mari kita telaah baris-baris kode di atas:

  1. Baris 6-7 (mutex_A, mutex_B): Dua mutex global—masing-masing melindungi satu resource. Thread butuh keduanya untuk menyelesaikan tugas.
  2. Baris 17 (jeda_ms(50)): Tidur 50 ms setelah lock pertama. Tanpa jeda ini, deadlock bisa jarang terjadi karena satu thread mungkin selesai sebelum yang lain mulai. Jeda memaksa kedua thread memegang satu kunci masing-masing secara bersamaan.
  3. Baris 20 (pthread_mutex_lock(&mutex_B) di thread1): Thread 1 sudah memegang A, sekarang minta B. Tapi B sedang dipegang thread 2—thread 1 memblokir.
  4. Baris 36 (pthread_mutex_lock(&mutex_A) di thread2): Simetri: thread 2 sudah memegang B, sekarang minta A. Tapi A sedang dipegang thread 1—thread 2 memblokir.
  5. Hasilnya: Thread 1 menunggu B, thread 2 menunggu A. Tidak ada yang bisa maju—circular wait terbentuk. Program berhenti di sini selamanya bila main tidak membatasi dengan timer 3 detik.
  6. return 0 di akhir main: Bahwa main selesai tidak menyelamatkan thread yang masih memblokir di pthread_mutex_lock. Saat main exit, seluruh proses di-terminate oleh kernel—termasuk thread yang menggantung. Inilah mengapa kita melihat “[main] 3 detik berlalu” tetapi tidak pernah melihat “[T1] memegang A dan B”.

Solusi 1: Lock Ordering #

Cara paling sederhana memutus circular wait adalah konvensi urutan kunci: semua thread mengunci mutex dalam urutan yang sama. Bila semua thread mengunci A dulu baru B, tidak mungkin thread 1 memegang A tanpa B sementara thread 2 memegang B tanpa A.

c 
/* File: deadlock_ordering.c - solusi: lock ordering (selalu A dulu, baru B) */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>
#include <time.h>

static pthread_mutex_t mutex_A = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t mutex_B = PTHREAD_MUTEX_INITIALIZER;

static void jeda_ms(int ms) {
    struct timespec ts = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&ts, NULL);
}

/* Thread 1: kunci A, lalu B */
static void *thread1(void *arg) {
    (void) arg;
    printf("[T1] mengunci A...\n");
    pthread_mutex_lock(&mutex_A);

    jeda_ms(50);

    printf("[T1] mengunci B...\n");
    pthread_mutex_lock(&mutex_B);

    printf("[T1] memegang A dan B\n");
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return NULL;
}

/* Thread 2: kunci A dulu, lalu B (urutan sama dengan thread1) */
static void *thread2(void *arg) {
    (void) arg;
    printf("[T2] mengunci A...\n");
    pthread_mutex_lock(&mutex_A);

    jeda_ms(50);

    printf("[T2] mengunci B...\n");
    pthread_mutex_lock(&mutex_B);

    printf("[T2] memegang A dan B\n");
    pthread_mutex_unlock(&mutex_B);
    pthread_mutex_unlock(&mutex_A);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("Selesai tanpa deadlock.\n");
    return 0;
}

Compile dan jalankan:

bash 
gcc -std=c11 -Wall -Wextra -pthread -o deadlock_ordering deadlock_ordering.c
timeout 5 ./deadlock_ordering
echo "exit code: $?"

Output yang Dihasilkan (urutan bisa berbeda antar eksekusi):

text 
[T1] mengunci A...
[T2] mengunci A...
[T1] mengunci B...
[T1] memegang A dan B
[T2] mengunci B...
[T2] memegang A dan B
Selesai tanpa deadlock.

Perhatikan: salah satu thread (misalnya T1) berhasil mengunci A lebih dulu. Thread 2 mencoba mengunci A tetapi memblokir karena A masih dipegang T1. T1 melanjutkan mengunci B, melakukan tugasnya, lalu melepaskan B dan A. Saat A dilepas, T2 baru bisa mengunci A dan melanjutkan. Tidak ada momen di mana dua thread sama-sama memegang satu kunci dan menunggu kunci lain—circular wait tidak pernah terbentuk.

Solusi 2: Timed Lock #

Bila urutan kunci sulit dipertahankan (misalnya kode lama, atau thread bekerja pada resource yang berbeda-beda), solusi alternatif adalah memberi batas waktu pada pthread_mutex_lock dengan pthread_mutex_timedlock. Bila timeout tercapai, thread melepas kunci yang sudah dipegang dan mencoba lagi—memutus no preemption.

c 
/* File: deadlock_timed.c - solusi: timed lock untuk deteksi deadlock */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <pthread.h>
#include <time.h>
#include <errno.h>

static pthread_mutex_t mutex_A = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t mutex_B = PTHREAD_MUTEX_INITIALIZER;

static void jeda_ms(int ms) {
    struct timespec ts = { ms / 1000, (ms % 1000) * 1000000L };
    nanosleep(&ts, NULL);
}

/* Hitung abstime dari sekarang + ms */
static struct timespec abstime_dari_sekarang(int ms) {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    ts.tv_sec  += ms / 1000;
    ts.tv_nsec += (ms % 1000) * 1000000L;
    if (ts.tv_nsec >= 1000000000L) {
        ts.tv_sec  += 1;
        ts.tv_nsec -= 1000000000L;
    }
    return ts;
}

static void *thread1(void *arg) {
    (void) arg;
    pthread_mutex_lock(&mutex_A);
    printf("[T1] pegang A, mencoba B (timeout 500 ms)...\n");
    jeda_ms(50);

    struct timespec dl = abstime_dari_sekarang(500);
    int rc = pthread_mutex_timedlock(&mutex_B, &dl);
    if (rc == 0) {
        printf("[T1] dapat B, sukses\n");
        pthread_mutex_unlock(&mutex_B);
    } else if (rc == ETIMEDOUT) {
        printf("[T1] TIMEOUT mencoba B - kemungkinan deadlock, lepas A\n");
    } else {
        printf("[T1] error: %d\n", rc);
    }
    pthread_mutex_unlock(&mutex_A);
    return NULL;
}

static void *thread2(void *arg) {
    (void) arg;
    pthread_mutex_lock(&mutex_B);
    printf("[T2] pegang B, mencoba A (timeout 500 ms)...\n");
    jeda_ms(50);

    struct timespec dl = abstime_dari_sekarang(500);
    int rc = pthread_mutex_timedlock(&mutex_A, &dl);
    if (rc == 0) {
        printf("[T2] dapat A, sukses\n");
        pthread_mutex_unlock(&mutex_A);
    } else if (rc == ETIMEDOUT) {
        printf("[T2] TIMEOUT mencoba A - kemungkinan deadlock, lepas B\n");
    } else {
        printf("[T2] error: %d\n", rc);
    }
    pthread_mutex_unlock(&mutex_B);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("Selesai.\n");
    return 0;
}

Compile dan jalankan:

bash 
gcc -std=c11 -Wall -Wextra -pthread -o deadlock_timed deadlock_timed.c
timeout 5 ./deadlock_timed
echo "exit code: $?"

Output yang Dihasilkan:

text 
[T1] pegang A, mencoba B (timeout 500 ms)...
[T2] pegang B, mencoba A (timeout 500 ms)...
[T1] TIMEOUT mencoba B - kemungkinan deadlock, lepas A
[T2] TIMEOUT mencoba A - kemungkinan deadlock, lepas B
Selesai.

Mari kita telaah baris-baris kode di atas:

  1. Baris 18-28 (abstime_dari_sekarang): pthread_mutex_timedlock menerima absolute time (waktu dinding), bukan durasi relatif. Fungsi ini menghitung abstime dengan menambah milidetik ke CLOCK_REALTIME. Karena absolute, bila thread dipanggil ulang nanti, harus hitung ulang.
  2. Baris 32 (pthread_mutex_timedlock(&mutex_B, &dl)): Mencoba kunci B paling lama hingga dl. Bila dapat dalam batas waktu, return 0. Bila tidak, return ETIMEDOUT.
  3. Baris 38 (pthread_mutex_unlock(&mutex_A)): Setelah timeout, thread melepaskan A. Inilah yang memutus no preemption—sekarang thread lain bisa mengunci A bila perlu.
  4. Hasil: Kedua thread mengalami timeout dan melepaskan kunci. Program selesai dengan rapi (tidak menggantung), dan kita tahu ada potensi deadlock karena melihat pesan “TIMEOUT”. Di produksi, kita bisa log ini untuk diagnosis.

Strategi Lain: Hierarki dan Try-Lock Loop #

Untuk kasus kompleks, dua pola tambahan sering dipakai:

  • Lock hierarchy: Beri nomor pada setiap mutex. Aturan: hanya boleh mengunci mutex dengan nomor lebih besar dari yang sedang dipegang. Bila semua thread ikuti aturan ini, circular wait mustahil terjadi.
  • Try-lock loop: Pakai pthread_mutex_trylock. Bila gagal, lepaskan semua kunci yang sudah dipegang dan ulangi dari awal. Pola ini lebih mahal tetapi fleksibel—cocok bila jumlah kunci bervariasi.