Apa itu deadlock?

Deadlock terjadi ketika dua atau lebih thread saling menunggu resource yang dipegang oleh thread lain, sehingga tidak ada satu pun yang bisa lanjut — semuanya terjebak menunggu selamanya. Ini salah satu bug paling menyebalkan dalam pemrograman konkuren karena sering tidak muncul konsisten (tergantung timing), dan program terlihat hang tanpa error apapun.

Empat syarat yang harus terpenuhi bersamaan supaya deadlock terjadi: mutual exclusion (resource cuma bisa dipegang satu thread), hold and wait (thread pegang satu resource sambil menunggu resource lain), no preemption (resource tidak bisa direbut paksa), dan circular wait — ada rantai melingkar, Thread A menunggu resource milik Thread B, Thread B menunggu resource milik Thread A.

Ilustrasi

Thread1: LOCK mutex_a → LOCK mutex_b (terblokir, mutex_b dipegang Thread2)
Thread2: LOCK mutex_b → LOCK mutex_a (terblokir, mutex_a dipegang Thread1)
 
Thread1 menunggu mutex_b, Thread2 menunggu mutex_a → deadlock

Kenapa penting

Kasus paling umum: dua mutex yang di-lock dengan urutan berbeda oleh dua thread berbeda. Ini sangat mudah terjadi tanpa sengaja di codebase yang punya banyak lock, apalagi kalau lock-nya tersebar di beberapa fungsi atau modul yang dipanggil dari urutan berbeda-beda.

Reproduksi

Struktur proyek

.
└── deadlock_demo.c

Step 1: kode yang sengaja deadlock

Thread1 lock A lalu B, Thread2 lock B lalu A.

// JANGAN dipakai di production, ini contoh bug
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
 
pthread_mutex_t mutex_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_b = PTHREAD_MUTEX_INITIALIZER;
 
void *thread1_func(void *arg)
{
    pthread_mutex_lock(&mutex_a);
    printf("Thread1 lock A\n");
    sleep(1); // kasih kesempatan thread2 lock B
 
    pthread_mutex_lock(&mutex_b);
    printf("Thread1 lock B\n");
 
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
    return NULL;
}
 
void *thread2_func(void *arg)
{
    pthread_mutex_lock(&mutex_b);
    printf("Thread2 lock B\n");
    sleep(1);
 
    pthread_mutex_lock(&mutex_a); // deadlock di sini
    printf("Thread2 lock 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_func, NULL);
    pthread_create(&t2, NULL, thread2_func, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("Selesai (kalau sampai sini, tidak deadlock)\n");
    return 0;
}

Kalau kamu compile dan jalankan ini, program akan hang setelah mencetak “Thread1 lock A” dan “Thread2 lock B” — tidak pernah mencetak “Selesai”.

Step 2: solusi — lock ordering konsisten

Pastikan semua thread mengunci lock dengan urutan yang sama.

void *thread2_func_fixed(void *arg)
{
    pthread_mutex_lock(&mutex_a); // urutan disamakan dengan thread1
    printf("Thread2 lock A\n");
    sleep(1);
 
    pthread_mutex_lock(&mutex_b);
    printf("Thread2 lock B\n");
 
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
    return NULL;
}

Dengan urutan yang disamakan, circular wait tidak mungkin terjadi.

Step 3: alternatif — trylock dengan backoff

Kalau urutan lock memang tidak bisa disamakan, gunakan pthread_mutex_trylock yang tidak memblokir.

void *thread2_func_trylock(void *arg)
{
    while (1) {
        pthread_mutex_lock(&mutex_b);
        if (pthread_mutex_trylock(&mutex_a) == 0) {
            printf("Thread2 lock B lalu A\n");
            pthread_mutex_unlock(&mutex_a);
            pthread_mutex_unlock(&mutex_b);
            break;
        }
        pthread_mutex_unlock(&mutex_b); // gagal dapat A, lepas B, hindari hold-and-wait
        usleep(1000); // backoff sebelum retry
    }
    return NULL;
}

Penjelasan

pthread_mutex_trylock mencoba lock tanpa memblokir — langsung return, bukan menunggu. Return 0 kalau berhasil, non-zero (biasanya EBUSY) kalau gagal. Ini memungkinkan thread untuk mundur dan coba lagi nanti, alih-alih terjebak menunggu selamanya.

Backoff (usleep(1000)) itu jeda singkat sebelum retry, supaya thread tidak langsung mencoba lagi dalam loop ketat — kalau tidak, dua thread bisa saling gagal trylock terus-menerus tanpa progress, yang disebut livelock1.

Sebelum vs sesudah fix

Time Thread1 (asli) Thread2 (asli) Status
t0 LOCK A LOCK B OK
t1 (nunggu B) (nunggu A) deadlock
Time Thread1 (fixed) Thread2 (fixed) Status
t0 LOCK A (nunggu A) OK
t1 LOCK B (nunggu A) OK
t2 UNLOCK B, A LOCK A OK
t3 LOCK B OK
t4 UNLOCK B, A selesai

Kompilasi

gcc -o deadlock_demo deadlock_demo.c -lpthread
./deadlock_demo

Untuk mendeteksi deadlock secara otomatis saat development:

valgrind --tool=helgrind ./deadlock_demo

atau compile dengan ThreadSanitizer:

gcc -fsanitize=thread -o deadlock_demo deadlock_demo.c -lpthread

Best practices

Dokumentasikan urutan lock secara eksplisit kalau ada lebih dari 2 lock yang sering dipakai bersamaan, dan pastikan urutannya konsisten di seluruh codebase. Trylock + backoff bisa jadi alternatif kalau urutan lock memang tidak bisa disamakan, tapi ingat ini menambah kompleksitas dan berisiko livelock kalau backoff-nya tidak wajar. Minimalkan jumlah lock yang dipegang sekaligus, dan pakai pthread_mutex_timedlock kalau butuh timeout.

Deadlock tidak selalu muncul saat testing — jangan anggap kode aman hanya karena lolos test manual beberapa kali. Pakai tools seperti Helgrind atau ThreadSanitizer secara rutin.

Kesimpulan

Deadlock terjadi ketika empat syaratnya terpenuhi bersamaan, dan cara paling praktis mencegahnya adalah memutus salah satu syarat itu — paling umum lewat lock ordering yang konsisten. Kalau kamu punya lebih dari satu lock, urutan pengambilannya harus konsisten di seluruh codebase.

Footnotes

  1. Selain deadlock, ada juga livelock (thread terus aktif tapi tidak ada progress) dan starvation (satu thread tidak pernah dapat giliran karena kalah bersaing terus dengan thread lain) — dua masalah terkait yang sering disebut bersamaan dengan deadlock. ↩