X'inhu l-lock-free programming u s-CAS? Spjega l-problema ABA u meta tużah.

Question

IT Interview Practice · Accepted Answer

**Il-lock-free programming jikkoordina t-threads mingħajr mutexes, billi juża loops atomiċi ta' compare-and-swap (CAS) biex mill-inqas thread wieħed dejjem jagħmel progress anke jekk l-oħrajn jieqfu.** L-ebda thread ma jista' jiġi mblukkat minn ieħor li jżomm lock.

## CAS

**Compare-and-swap** jissettja b'mod atomiku post għal valur ġdid biss jekk għadu jżomm il-valur qadim mistenni; inkella jfalli u terġa' tipprova. Huwa l-primittiva wara l-lock-free stacks, queues, u counters.

```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
```

## Il-problema ABA

CAS jiċċekkja biss li l-valur għadu dak mistenni — mhux li qatt ma nbidel. Jekk mar A → B → A bejn il-read u s-CAS tiegħek, is-CAS jirnexxi imma d-dinja ċċaqilqet taħtek (eż. node li ġie lliberat u użat mill-ġdid).

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

**Soluzzjoni**: għaqqad il-pointer ma' version counter (`AtomicStampedReference`, tagged pointers) biex A-with-tag-1 ≠ A-with-tag-2, jew uża hazard pointers / epoch reclamation għas-sigurtà tal-memorja.

## Meta tużah

- **Uża** għal shared state jaħraq u fine-grained (counters, single-producer queues) fejn il-lock contention tiddomina, jew fejn thread qatt m'għandu jimblokka (real-time, signal handlers).
- **Evita** bħala default: huwa diffiċli biex tagħmlu sew, faċli li ddaħħal ABA u bugs ta' memory-ordering, u ħafna drabi mhux aktar mgħaġġel minn mutex tajjeb taħt contention baxxa.

## Għaliex huwa importanti

L-istrutturi lock-free jagħtu garanziji ta' progress u jevitaw deadlock u priority inversion, imma l-livell tal-correctness huwa għoli. Li tkun taf is-CAS, l-ABA, u l-problema tar-reclamation jindika li tista' tirraġuna fil-livell tal-memory-model — u, l-aktar importanti, tkun taf meta *ma* għandekx tużah.

CAS

Il-problema ABA

Meta tużah

Għaliex huwa importanti

Mistoqsijiet relatati