Apa itu lock-free programming dan CAS? Jelaskan masalah ABA dan kapan menggunakannya.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming mengoordinasikan thread tanpa mutex, menggunakan loop atomic compare-and-swap (CAS) sehingga setidaknya satu thread selalu membuat kemajuan bahkan jika yang lain macet.** Tidak ada thread yang dapat terblokir oleh thread lain yang memegang sebuah lock.

## CAS

**Compare-and-swap** secara atomik menetapkan sebuah lokasi ke nilai baru hanya jika ia masih memegang nilai lama yang diharapkan; jika tidak ia gagal dan Anda coba lagi. Ini adalah primitive di balik stack, queue, dan counter lock-free.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, indivisible
  else: return false
```

```java
// Lock-free increment via CAS retry loop
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // retry if someone else won
```

## Masalah ABA

CAS hanya memeriksa bahwa nilainya masih yang diharapkan — bukan bahwa ia tidak pernah berubah. Jika ia berpindah A → B → A antara pembacaan Anda dan CAS, CAS berhasil tetapi dunia telah bergerak di bawah Anda (misalnya sebuah node yang dibebaskan-dan-dipakai-ulang).

```text
Thread 1: read A ............... CAS(A→X) succeeds ✗ (but list changed!)
Thread 2:      pop A, push B, push A again
```

**Perbaikan**: pasangkan pointer dengan sebuah version counter (`AtomicStampedReference`, tagged pointer) sehingga A-dengan-tag-1 ≠ A-dengan-tag-2, atau gunakan hazard pointer / epoch reclamation untuk keamanan memory.

## Kapan menggunakannya

- **Gunakan** untuk shared state yang panas dan berbutir halus (counter, single-producer queue) di mana lock contention mendominasi, atau di mana sebuah thread tidak boleh pernah memblokir (real-time, signal handler).
- **Hindari** sebagai default: sulit untuk dibuat benar, mudah memperkenalkan bug ABA dan memory-ordering, dan sering kali tidak lebih cepat daripada mutex yang baik di bawah contention rendah.

## Mengapa ini penting

Struktur lock-free memberikan jaminan kemajuan dan menghindari deadlock serta priority inversion, tetapi standar correctness-nya tinggi. Mengetahui CAS, ABA, dan masalah reclamation menandakan Anda dapat bernalar pada level memory-model — dan, yang krusial, tahu kapan *tidak* meraihnya.

CAS

Masalah ABA

Kapan menggunakannya

Mengapa ini penting

Pertanyaan terkait