Apakah itu pengaturcaraan lock-free dan CAS? Terangkan masalah ABA dan bila untuk menggunakannya.

Question

IT Interview Practice · Accepted Answer

**Pengaturcaraan lock-free menyelaraskan thread tanpa mutex, menggunakan gelung compare-and-swap (CAS) atomik supaya sekurang-kurangnya satu thread sentiasa membuat kemajuan walaupun yang lain terhenti.** Tiada thread boleh disekat oleh yang lain yang memegang lock.

## CAS

**Compare-and-swap** secara atomik menetapkan satu lokasi kepada nilai baharu hanya jika ia masih memegang nilai lama yang dijangka; jika tidak ia gagal dan anda mencuba semula. Ia ialah primitif di sebalik stack, queue, dan pembilang 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 menyemak nilai itu masih yang dijangka — bukan bahawa ia tidak pernah berubah. Jika ia pergi A → B → A antara bacaan anda dan CAS, CAS berjaya tetapi dunia telah bergerak di bawah anda (cth. nod yang telah dibebaskan-dan-diguna-semula).

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

**Pembaikan**: pasangkan pointer dengan pembilang versi (`AtomicStampedReference`, tagged pointer) supaya A-dengan-tag-1 ≠ A-dengan-tag-2, atau gunakan hazard pointer / epoch reclamation untuk keselamatan memori.

## Bila untuk menggunakannya

- **Gunakan** untuk keadaan dikongsi yang panas dan berbutir-halus (pembilang, queue pengeluar-tunggal) di mana perebutan lock mendominasi, atau di mana sebuah thread tidak boleh sekali-kali disekat (masa nyata, pengendali isyarat).
- **Elakkan** sebagai lalai: ia sukar untuk dibetulkan, mudah untuk memperkenalkan pepijat ABA dan susunan-memori, dan selalunya tidak lebih pantas daripada mutex yang baik di bawah perebutan rendah.

## Mengapa ia penting

Struktur lock-free memberikan jaminan kemajuan dan mengelakkan deadlock serta pembalikan keutamaan (priority inversion), tetapi bar ketepatannya tinggi. Mengetahui CAS, ABA, dan masalah reclamation menandakan anda boleh menaakul pada aras model-memori — dan, yang penting, mengetahui bila untuk *tidak* mencapainya.

CAS

Masalah ABA

Bila untuk menggunakannya

Mengapa ia penting

Soalan berkaitan