რა არის lock-free programming და CAS? ახსენით ABA პრობლემა და როდის გამოვიყენოთ ის.

Question

IT Interview Practice · Accepted Answer

**Lock-free programming კოორდინაციას უწევს thread-ებს mutex-ების გარეშე, ატომური compare-and-swap (CAS) loop-ების გამოყენებით, ისე რომ ყოველთვის სულ მცირე ერთი thread მიიწევს წინ, თუნდაც სხვები გაჩერდნენ.** ვერცერთ thread-ს ვერ დაბლოკავს lock-ის მჭერი სხვა.

## CAS

**Compare-and-swap** ატომურად აყენებს ლოკაციას ახალ მნიშვნელობაზე მხოლოდ იმ შემთხვევაში, თუ ის ჯერ კიდევ იჭერს მოსალოდნელ ძველ მნიშვნელობას; წინააღმდეგ შემთხვევაში ის ვარდება და თქვენ ხელახლა ცდით. ეს არის primitive lock-free stack-ების, queue-ებისა და მთვლელების უკან.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # ატომური, განუყოფელი
  else: return false
```

```java
// Lock-free increment CAS retry loop-ით
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // ხელახლა სცადეთ, თუ სხვამ მოიგო
```

## ABA პრობლემა

CAS მხოლოდ ამოწმებს, რომ მნიშვნელობა ჯერ კიდევ მოსალოდნელია — არა რომ ის არასდროს შეცვლილა. თუ ის შეიცვალა A → B → A თქვენს read-სა და CAS-ს შორის, CAS წარმატდება, მაგრამ სამყარო ქვემოთ მოძრაობდა (მაგ. გათავისუფლებული და ხელახლა გამოყენებული node).

```text
Thread 1: read A ............... CAS(A→X) succeeds ✗ (მაგრამ list შეიცვალა!)
Thread 2:      pop A, push B, push A again
```

**გამოსწორება**: დააწყვილეთ pointer version მთვლელთან (`AtomicStampedReference`, tagged pointer-ები), რომ A-with-tag-1 ≠ A-with-tag-2, ან გამოიყენეთ hazard pointer-ები / epoch reclamation მეხსიერების უსაფრთხოებისთვის.

## როდის გამოვიყენოთ

- **გამოიყენეთ** ცხელი, წვრილმარცვლოვანი გაზიარებული მდგომარეობისთვის (მთვლელები, single-producer queue-ები), სადაც lock კონკურენცია დომინირებს, ან სადაც thread არასდროს არ უნდა დაიბლოკოს (real-time, signal handler-ები).
- **აირიდეთ** როგორც ნაგულისხმევი: მისი სწორად გაკეთება რთულია, ABA და memory-ordering bug-ების შემოტანა ადვილია და ხშირად არ არის უფრო სწრაფი, ვიდრე კარგი mutex დაბალი კონკურენციის ქვეშ.

## რატომ არის ეს მნიშვნელოვანი

Lock-free სტრუქტურები იძლევიან progress გარანტიებს და აცილებენ deadlock-სა და priority inversion-ს, მაგრამ კორექტულობის ზოლი მაღალია. CAS-ის, ABA-სა და reclamation პრობლემის ცოდნა მიანიშნებს, რომ შეგიძლიათ იმსჯელოთ memory-model დონეზე — და, რაც მთავარია, იცოდეთ, *როდის არ* მიმართოთ მას.

CAS

ABA პრობლემა

როდის გამოვიყენოთ

რატომ არის ეს მნიშვნელოვანი

დაკავშირებული კითხვები