Τι είναι ο lock-free programming και το CAS; Εξήγησε το πρόβλημα ABA και πότε να το χρησιμοποιείς.

Question

IT Interview Practice · Accepted Answer

**Ο lock-free programming συντονίζει threads χωρίς mutexes, χρησιμοποιώντας atomic compare-and-swap (CAS) loops ώστε τουλάχιστον ένα thread να προχωρά πάντα ακόμη κι αν τα άλλα κολλήσουν.** Κανένα thread δεν μπορεί να μπλοκαριστεί από ένα άλλο που κρατά ένα lock.

## CAS

Το **Compare-and-swap** θέτει ατομικά μια θέση σε μια νέα τιμή μόνο αν αυτή εξακολουθεί να κρατά την αναμενόμενη παλιά τιμή· αλλιώς αποτυγχάνει και κάνεις retry. Είναι το primitive πίσω από τα lock-free stacks, queues και 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
```

## Το πρόβλημα ABA

Το CAS ελέγχει μόνο ότι η τιμή είναι ακόμη η αναμενόμενη — όχι ότι δεν άλλαξε ποτέ. Αν πήγε A → B → A ανάμεσα στο read σου και στο CAS, το CAS πετυχαίνει αλλά ο κόσμος μετακινήθηκε από κάτω σου (π.χ. ένα node που ελευθερώθηκε και ξαναχρησιμοποιήθηκε).

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

**Λύση**: συνδύασε τον pointer με έναν version counter (`AtomicStampedReference`, tagged pointers) ώστε A-with-tag-1 ≠ A-with-tag-2, ή χρησιμοποίησε hazard pointers / epoch reclamation για memory safety.

## Πότε να το χρησιμοποιείς

- **Χρησιμοποίησέ το** για hot, λεπτόκοκκη κοινόχρηστη κατάσταση (counters, single-producer queues) όπου κυριαρχεί το lock contention, ή όπου ένα thread δεν πρέπει ποτέ να μπλοκάρει (real-time, signal handlers).
- **Απόφυγέ το** ως προεπιλογή: είναι δύσκολο να το κάνεις σωστά, εύκολο να εισαγάγεις ABA και memory-ordering bugs, και συχνά όχι γρηγορότερο από ένα καλό mutex υπό χαμηλό contention.

## Γιατί έχει σημασία

Οι lock-free δομές δίνουν εγγυήσεις προόδου και αποφεύγουν το deadlock και το priority inversion, αλλά ο πήχης της ορθότητας είναι υψηλός. Το να ξέρεις το CAS, το ABA και το πρόβλημα του reclamation σηματοδοτεί ότι μπορείς να συλλογιστείς σε επίπεδο memory-model — και, κυρίως, να ξέρεις πότε *να μην* καταφύγεις σε αυτό.

CAS

Το πρόβλημα ABA

Πότε να το χρησιμοποιείς

Γιατί έχει σημασία

Σχετικές ερωτήσεις