Apa iku lock-free programming lan CAS? Terangna masalah ABA lan kapan nganggoné.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming ngoordinasi thread tanpa mutex, nganggo loop atomik compare-and-swap (CAS) supaya sethithiké siji thread tansah maju senadyan liyané mandheg.** Ora ana thread sing bisa diblokir déning liyané sing nyekel lock.

## CAS

**Compare-and-swap** kanthi atomik nyetèl sawijining lokasi menyang nilai anyar mung yèn isih nyekel nilai lawas sing dikarepaké; yèn ora, dhèwèké gagal lan sampeyan coba manèh. Iku primitif ing mburiné stack, queue, lan 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 mung ngecek nilaine isih sing dikarepaké — dudu yèn ora tau owah. Yèn dhèwèké lunga A → B → A antara maca lan CAS sampeyan, CAS-é kasil nanging donyané wis owah ing ngisoré (contoné node sing wis diculaké lan dienggo manèh).

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

**Solusi**: pasangna pointer karo counter versi (`AtomicStampedReference`, tagged pointer) supaya A-kanthi-tag-1 ≠ A-kanthi-tag-2, utawa nganggo hazard pointer / epoch reclamation kanggo keamanan memori.

## Kapan nganggoné

- **Nganggo** kanggo kahanan dinuduhaké sing panas lan alus (counter, single-producer queue) ing endi rebutan lock ngdominasi, utawa ing endi thread ora kena tau diblokir (real-time, signal handler).
- **Ngindhari** minangka standar: angèl dibenerake, gampang ngenalaké bug ABA lan urutan-memori, lan asring ora luwih cepet tinimbang mutex sing apik nalika rebutan sethithik.

## Kenapa iki penting

Struktur lock-free mènèhi jaminan maju lan ngindhari deadlock lan priority inversion, nanging standar kebeneran-é dhuwur. Ngerti CAS, ABA, lan masalah reclamation nuduhaké sampeyan bisa nalar ing level model-memori — lan, sing wigati, ngerti kapan *ora* njupuk iku.

CAS

Masalah ABA

Kapan nganggoné

Kenapa iki penting

Pitakon sing gegandhengan