Çfarë është lock-free programming dhe CAS? Shpjego problemin ABA dhe kur ta përdorësh.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming i koordinon thread-et pa mutexes, duke përdorur loop-e atomike compare-and-swap (CAS) që të paktën një thread gjithmonë bën progres edhe nëse të tjerët ngecin.** Asnjë thread s'mund të bllokohet nga një tjetër që mban një lock.

## CAS

**Compare-and-swap** e vendos atomikisht një vendndodhje në një vlerë të re vetëm nëse ende mban vlerën e vjetër të pritur; përndryshe dështon dhe ti ribën. Është primitivi pas stack-eve, queue-ve dhe counter-ave lock-free.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomik, i pandashëm
  else: return false
```

```java
// Increment lock-free via loop retry CAS
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // ribëj nëse dikush tjetër fitoi
```

## Problemi ABA

CAS kontrollon vetëm që vlera është ende ajo e pritura — jo që ajo s'ndryshoi kurrë. Nëse shkoi A → B → A mes read-it tënd dhe CAS, CAS-i ka sukses por bota lëvizi poshtë teje (p.sh. një node i liruar dhe i riperdorur).

```text
Thread 1: read A ............... CAS(A→X) ka sukses ✗ (por lista ndryshoi!)
Thread 2:      pop A, push B, push A përsëri
```

**Rregullim**: çifto pointer-in me një version counter (`AtomicStampedReference`, tagged pointers) që A-me-tag-1 ≠ A-me-tag-2, ose përdor hazard pointers / epoch reclamation për siguri memorie.

## Kur ta përdorësh

- **Përdore** për gjendje të ndarë të nxehtë dhe të imët (counters, single-producer queues) ku lock contention dominon, ose ku një thread s'duhet të bllokohet kurrë (real-time, signal handlers).
- **Shmange** si parazgjedhje: është e vështirë për ta bërë saktë, e lehtë për të futur bug-e ABA dhe memory-ordering, dhe shpesh jo më e shpejtë se një mutex i mirë nën contention të ulët.

## Pse ka rëndësi

Strukturat lock-free japin garanci progresi dhe shmangin deadlock dhe priority inversion, por shiriti i korrektësisë është i lartë. Të njohësh CAS, ABA dhe problemin e reclamation sinjalizon që mund të arsyetosh në nivelin e memory-model — dhe, thelbësisht, të dish kur *të mos* kapesh pas tij.

CAS

Problemi ABA

Kur ta përdorësh

Pse ka rëndësi

Pyetje të ngjashme