Lock-free bağlı liste CAS tabanlı implementasyonlar, mutex kullanmadan thread-safe veri yapısı oluşturmanın en eğitici örneklerinden biridir. Ancak bu yapıyı doğru kurmak, Compare-And-Swap'in nüanslarını ve ABA problemini derinlemesine anlamayı gerektirir. Temel CAS döngüsü şu şekilde işler: okuma → hesaplama → koşullu yazma. Atomik işlem başarısız olursa döngü tekrar başlar. Tek bağlı listede düğüm ekleme şöyle görünür: ```c void push(Node* new_node) { Node* old_head; do { old_head = head.load(std::memory_order_relaxed); new_node->next = old_head; } while (!head.compare_exchange_weak( old_head, new_node, std::memory_order_release, std::memory_order_relaxed)); } ``` Bu push implementasyonu doğrudur çünkü CAS'ın başarısız olduğu durumda yeni head değeri `old_head`'e yüklenir ve döngü tekrar çalışır. ABA problemi pop operasyonunda ortaya çıkar. Senaryo: T1 head = A, A->next = B durumunu okur; T2 A'yı çıkarır, B'yi çıkarır, A'yı tekrar ekler. T1, A'nın hâlâ head olduğunu görür, CAS başarılı olur; ancak A->next artık B'yi göstermez, geçersiz bir işaretçi veya farklı bir düğüm olabilir. ABA çözüm yöntemleri: **1. Tagged Pointer (Stamp/Version):** Pointer'a ekstra bit ekleyerek her güncellemeyle sayaç artırılır. 64-bit sistemlerde üst bitler bu amaçla kullanılabilir: ```c std::atomic<uint64_t> head; // lower 48 bit: pointer, upper 16 bit: tag ``` `compare_exchange` hem pointer hem tag'i birlikte kontrol eder; böylece A = B = A senaryosu, tag farklılığı nedeniyle yakalanır. **2. Hazard Pointer:** Her thread, aktif olarak eriştiği düğüm adreslerini bir hazard pointer listesine kaydeder. Bellek geri dönüşümü bu listeye bakarak gerçekleşir; listede olan bir adres serbest bırakılmaz. Lock-free bağlı liste CAS implementasyonlarında en güvenilir ABA önleme yöntemidir. **3. Epoch-Based Reclamation (EBR):** Thread'ler epoch sayacına katılır; tüm thread'ler yeni epoch'a geçmeden eski epoch'un belleği serbest bırakılmaz. crossbeam (Rust) kütüphanesi bu yöntemi kullanır. **Memory Ordering:** Lock-free algoritmalar memory ordering kararlarıyla da şekillenir. `relaxed` ordering CAS döngüsünde okuma için yeterli olabilir; ancak yazma tarafının `release`, okuma tarafının `acquire` kullanması zorunludur. Aksi halde derleyici ve CPU yeniden sıralama optimizasyonları değerleri tutarsız gösterebilir. Pratik değerlendirme: Lock-free bağlı liste CAS implementasyonu, mutex'li alternatiflere kıyasla yüksek çekişme senaryolarında throughput avantajı sağlar. Düşük çekişmede ise CAS retry overhead'i nedeniyle geride kalabilir. Benchmark yapmadan karar vermek yanıltıcıdır.