Kilitlenmesiz Veri Yapıları: C++, Java ve .NET Örnekleriyle Eksiksiz Kılavuz

Mutex basittir. Kilitlersiniz, paylaşılan durumu değiştirirsiniz, kilidi açarsınız. Erişim isteyen her iş parçacığı sırasını bekler. Sorun, yüksek çekirdek sayılarında ve yüksek işlem hacminde "sırasını beklemek"tir; bu serileştirme bir sınır haline gelir. Kilidi tutan bir iş parçacığı önceliklendirilebilir ve bu da diğer tüm iş parçacıklarının boşta kalmasına neden olabilir. Öncelik tersine çevrilmesi, düşük öncelikli iş parçacıklarının yüksek öncelikli iş parçacıklarını engellemesine neden olabilir. Saniyede milyonlarca işlemi onlarca çekirdekte işleyen sistemlerde, mutex çekişmesi sadece işleri yavaşlatmakla kalmaz; işlem hacmini de çökertir.

Kilitsiz veri yapıları, karşılıklı dışlamayı atomik işlemlerle değiştirir. Çatışmayı önlemek yerine, ona tolerans gösterir ve ondan kurtulurlar. Karşılaştırma ve değiştirme işleminde başarısız olan bir iş parçacığı, güncellenmiş durumla yeniden dener. Hiçbir iş parçacığı diğerini engellemez. En az bir iş parçacığı her zaman ilerleme kaydeder. Sonuç, yüksek çekişme altında önemli ölçüde daha iyi verim, konvoy etkileri olmadan öngörülebilir gecikme ve tasarım gereği kilitlenme ve öncelik tersine çevrilmesinin ortadan kaldırılmasıdır. Bedeli ise uygulama karmaşıklığıdır: ABA problemi, bellek geri kazanım tehlikeleri, yanlış paylaşım ve ince bellek sıralama gereksinimleri, kilit tabanlı kodda bulunmayan tuzaklardır. Bu makale, bunların hepsini somut kodlarla ele almaktadır.

Kilitlenme gerektirmeyen, bekleme gerektirmeyen ve Mutex yöntemleri: Hangisini kullanmalı?

Bir uygulama yaklaşımı seçmeden önce, asıl soru sistemin aslında hangi ilerleme garantisine ihtiyaç duyduğudur. Üç model, iş parçacıkları rekabet ettiğinde ne vaat ettikleri konusunda farklılık gösterir.

Model	İlerleme Garantisi	Tipik Gecikme	karmaşa	En
Mutex / kilit tabanlı	Engelleme, iş parçacıkları bekliyor	Tartışma altında öngörülemez	Düşük	Düşük çekişmeli paylaşımlı durum, basit doğruluk gereksinimleri
Kilitsiz	Sistem genelinde en az bir iş parçacığı ilerliyor.	Düşük çekişme altında	Yüksek	Yüksek verimli kuyruklar, yığınlar, sayaçlar
Bekleme yok	Her iş parçacığı, sınırlı adımlarla tamamlanır.	Sınırlı en kötü durum	Çok yüksek	Gerçek zamanlı sistemler, güvenlik açısından kritik, katı gecikme süresi SLA'ları
Engelsiz	Tek başına ilerleme, ancak rakipsiz olduğunda mümkündür.	Tartışmasız düşük seviye	Orta	İşlemsel bellek prototipleri, araştırma bağlamları

Kilitlenmesiz yapı, yüksek eşzamanlılık gerektiren üretim sistemleri için pratik bir varsayılan yaklaşımdır. Michael-Scott kuyruğu, Treiber yığını ve çoğu üretim MPMC halka tamponu kilitlenmesizdir. Aşırı çekişme altında tek tek iş parçacıkları kaynak yetersizliğinden dolayı çalışmaz hale gelebilir, ancak sistem bir bütün olarak ilerleme kaydeder.

Bekleme gerektirmeyen algoritmalar, iş parçacığı başına sınırlı ilerlemeyi garanti eder ancak önemli ölçüde daha karmaşık algoritmalar gerektirir. Evrensel yapılar mevcuttur ancak yüksek ek yük getirirler. Bekleme gerektirmeyen algoritmalar, ortalama verimden ziyade kuyruk gecikmesinin daha önemli olduğu zorlu gerçek zamanlı bağlamlar için uygundur.

Engelleme içermeyen yaklaşım, üretim ortamında nadiren doğrudan kullanılır. Bazı işlemsel bellek uygulamalarında ortaya çıkar ve algoritma doğruluğunu kanıtlamada bir basamak görevi görür.

Çoğu yüksek eşzamanlılık sistemi için: çekişme düşük ve doğruluk basit olduğunda mutex kullanın, çekişme altında verimliliğin önemli olduğu durumlarda kilitlenmesiz (lock-free) yaklaşım kullanın, yalnızca en kötü durumdaki iş parçacığı başına gecikme süresi zorunlu bir gereklilik olduğunda beklemesiz (wait-free) yaklaşım kullanın.

Kilitlenmesiz Veri Yapısı Nedir?

Bir veri yapısı, üzerinde çalışan tüm iş parçacıkları arasında en az birinin, diğer iş parçacıklarının ne yaptığına veya nasıl zamanlandığına bakılmaksızın, işlemini sonlu sayıda adımda tamamlayacağını garanti ediyorsa, kilitlenmesiz (lock -free) olarak adlandırılır. Bu resmi tanımın kesin bir sonucu vardır: hiçbir kilitlenmesiz algoritma kilitlenmeye yol açamaz. Bir iş parçacığı durdurulursa, askıya alınırsa veya yavaş çalışırsa, diğer iş parçacıkları ilerlemeye devam eder.

Mekanizma atomik işlemlerdir, yani tek bir bölünmez birim olarak yürütülen CPU komutlarıdır. Evrensel temel işlem Karşılaştırma ve Değiştirme (CAS) işlemidir :

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS, donanım düzeyinde atomiktir. x86'da ise şöyledir: CMPXCHG talimat. ARM'de bu, şu şekilde uygulanır: LDXR/STXR (Yükleme-özel/depolama-özel), LL/SC (Yükleme-Bağlantılı/Depolama-Koşullu) varyantıdır. Bir iş parçacığı bir değeri okur, yeni bir değer hesaplar ve yalnızca başka biri arada değiştirmediyse CAS kullanarak onu yükler. CAS başarısız olursa, iş parçacığı yeni değerle tekrar dener.

C++11 ve sonrasında bu, şu şekilde ortaya çıkar: std::atomic:

cpp

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak CAS temel öğesidir. Başarısızlık durumunda güncellenir. expected Geçerli değere otomatik olarak ayarlanır, bu da yeniden deneme döngüsünü alışılmış bir durum haline getirir.

ABA Sorunu: Lock-Free'nin En Tehlikeli Tuzağı

ABA problemi, kilitlenmesiz programlamada en sezgisel olmayan doğruluk tehlikesidir. CAS, yeni bir değer yüklemeden önce bir bellek konumunun hala beklenen değeri içerip içermediğini kontrol eder. Okuma ve CAS arasında bu değerin değiştirilip değiştirilmediğini tespit edemez. Konum hala orijinal değere benziyor, ancak sistemin temel durumu CAS'ın göremediği şekillerde değişmiştir.

Senaryo Adım Adım

Tek bir işaretçi kullanan kilitlenmesiz bir yığını ele alalım. top:

1. A başlığı şöyle diyor: top = Node1Node1'in bir sonraki işaretçisi Node2'dir.
2. A iş parçacığı, pop işlemini tamamlamadan önce kesintiye uğratılıyor.
3. B iş parçacığı Node1'i kaldırır (üstteki Node2 olur), ardından Node2'yi kaldırır (üstteki null olur).
4. B iş parçacığı yeni bir düğüm ekler ve bu düğüm, Node1 ile aynı bellek adresinde tahsis edilir (serbest liste ayırıcılarında yaygındır). Top = Node1 (aynı işaretçi, farklı içerik).
5. A iş parçacığı yeniden başlıyor. CAS'ı görüyor. top == Node1 (beklenen değer), başarılı olur ve ayarlar. top = Node2Ama Node2 çoktan serbest bırakılmıştı. Felaket.

ABA problemi her veri yapısında farklı şekilde kendini gösterir:

• YığınCAS işlemi başarılı olur ancak güncel olmayan bir sonraki işaretçiyi kurar ve bu da serbest bırakıldıktan sonra kullanım hatasına neden olur.
• KuyrukBaş veya kuyruk işaretçisi değişmemiş gibi görünse de yapısı değişmiştir.
• Bağlantılı listeBir düğüm hala konumunda gibi görünse de kaldırılmış ve yeniden tahsis edilmiştir.

LL/SC, ABA sorununu ortadan kaldırıyor mu?

Evet, LL/SC (Yükleme Bağlantılı/Depolama Koşullu) CAS'tan daha güçlü anlamlar sunar ve doğal olarak ABA'yı önler. LL, yüklenen bellek adresini "bağlantılı" olarak işaretler. Aynı adrese herhangi bir depolama işlemi LL'den sonra gerçekleştiyse, değer orijinal durumuna geri döndürülmüş olsa bile SC başarısız olur. Değişiklik geçmişi, yalnızca mevcut değer değil, donanım düzeyinde de izlenir.

Ancak, gerçek donanım üzerinde LL/SC uygulamalarının pratik sınırlamaları vardır. ARM ve POWER'da, çekişme olmasa bile (bağlam değiştirme, önbellek boşaltma) hatalı LL/SC hataları meydana gelebilir. Kod, gerçek çakışmalar olmasa bile yeniden deneme döngülerini hesaba katmalıdır. x86'da yerel LL/SC yoktur; CAS donanım temel işlemidir. x86 kodu için, ABA yazılımda engellenmelidir.

ABA'yı Düzeltmek: Üç Yaklaşım

1. Sürüm sayaçları (etiketli işaretçiler)

Sürüm sayacını işaretçiyle aynı atomik kelimeye paketleyin. Her başarılı CAS işlemi sayacı artırır. İşaretçi orijinal değerine dönse bile, sayaç farklı kalır:

cpp

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

Bu, pratikte standart yaklaşımdır. 16 bitlik etiket 65,536 işlemden sonra başa döner; bu teorik olarak güvenli olmasa da çoğu sistem için pratikte yeterlidir, bir iş parçacığının aynı konumda tam olarak 65,536 CAS döngüsü boyunca önceliklendirilmesi son derece düşük bir olasılıktır.

2. Tehlike uyarıları

Her iş parçacığı, şu anda eriştiği düğümlere işaret eden küçük bir "risk işaretçisi" kümesi tutar. Herhangi bir düğümü serbest bırakmadan önce, bir iş parçacığı, başka bir iş parçacığının ona erişmediğini doğrulamak için tüm risk işaretçisi kayıtlarını kontrol eder. Bir risk işaretçisinde görünen bir düğüm, o işaretçi temizlenene kadar ertelenir:

cpp

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

Tehlike işaretçileri, bellek geri kazanımı düzeyinde ABA'yı engeller: herhangi bir iş parçacığı ona tehlike işaretçisi tutarken bir düğüm yeniden kullanılamaz. Bu, serbest bırakmadan önce tüm iş parçacığı tehlike işaretçilerinin taranmasını gerektirir ve bu da iş parçacığı sayısıyla orantılı bir ek yük getirir.

3. Dönem bazlı ıslah (EBR)

İş parçacıkları, küresel olarak izlenen "dönemler" halinde çalışır. Emekliye ayrılan düğümler, dönem başına tamponlanır ve yalnızca tüm iş parçacıkları düğümün emekliye ayrıldığı dönemi geçtikten sonra serbest bırakılır. EBR, tehlike işaretçilerinden daha kullanımı kolaydır ve işlem başına daha düşük ek yük getirir; ancak bu, durgun dönemlerde sınırlı ancak tahmin edilemeyen bellek büyümesi pahasına gerçekleşir.

Java'da, AtomicStampedReference Bu yöntem, bir referansı bir tamsayı damgasıyla eşleştirerek ABA sorununu doğrudan ele alır:

Java

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

Kilitlenmesiz Kuyruk Uygulamaları

Kuyruklar, en sık ihtiyaç duyulan kilitlenmesiz yapıdır. Klasik kilitlenmesiz kuyruk, iki işaretçi (baş ve kuyruk) ve bir bekçi düğümü kullanarak eş zamanlı ekleme ve çıkarma işlemlerine olanak sağlayan Michael-Scott kuyruğudur.

SPSC Kuyruğu: Minimum Senkronizasyonla Maksimum Performans

Tek üreticili tek tüketicili bir kuyruk, tüm yazma-yazma ve okuma-okuma çekişmelerini ortadan kaldırır. Bir iş parçacığı kuyruğun sonuna yazar; bir iş parçacığı başından okur. Üretici ve tüketici arasında yalnızca baş işaretçisi paylaşılır:

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

MKS alignas(64) Baş ve kuyruk kısımlarının konumu kritik öneme sahiptir. Bu olmadan, her ikisi de aynı önbellek satırına sığar. Kuyruğa yapılan her yazma işlemi, baş kısmını okuyan çekirdek tarafından görülebilen bir önbellek satırı geçersizleştirmesini tetikler ve bunun tersi de geçerlidir; bu da bağımsız olması gereken işlemleri seri hale getiren yanlış bir paylaşıma yol açar.

MPMC Kuyruğu: Çok Üreticili Çok Tüketici

Tamamen eş zamanlı bir MPMC kuyruğu önemli ölçüde daha karmaşıktır. Üretim uygulamalarında, kilit kullanmadan üreticileri ve tüketicileri koordine etmek için her yuva başına bir sıra numarası kullanılır:

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET Eşzamanlı Kuyruk: İç İşleyişi Nasıl

.NET'in ConcurrentQueue<T> .NET 5 ve üzeri sürümlerde segmentli dizi yapısı kullanılır. Her segment, baş ve son indeksleri ile yönetilen sabit boyutlu bir dizidir. Interlocked (Temel donanımdaki CAS'a karşılık gelen) işlemler. Segmentler, geçici bir bağlantı aracılığıyla birbirine bağlanır. _nextSegment İşaretçi. Enqueue, mevcut kuyruk segmentine ekleme yapar ve dolduğunda segment zincirini büyütür. Dequeue, baş segmentten okur ve baş dizinini atomik olarak ilerletir.

En önemli tasarım kararı, küresel bir kilitlenmeyi önlemektir. Üreticiler yalnızca mevcut segmentin kuyruk endeksi üzerinden rekabet eder. Tüketiciler yalnızca baş endeksi üzerinden rekabet eder. Hiçbir üretici hiçbir zaman bir tüketiciyle rekabet etmez. Bu da ConcurrentQueue<T> Üretici-tüketici boru hatları için son derece verimli:

csharp

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

Kilitlenmesiz Kodda Önbellek Tutarlılığı ve Yanlış Paylaşım

Kilitlenmesiz uygulamalarda önbellek tutarlılığı, görünmez performans değişkenidir. Bir çekirdek bir bellek konumuna yazdığında, o konumu içeren 64 baytlık önbellek satırının tamamı diğer tüm çekirdeklerin önbelleklerinde geçersiz hale gelir. Okuma işlemine başlamadan önce güncellenmiş satırı almaları gerekir. Sık atomik güncellemeler içeren kilitlenmesiz kodda, bu önbellek satırı geçersizleştirme işlemi baskın maliyet haline gelebilir.

Yanlış paylaşım, iki iş parçacığının aynı önbellek satırını paylaşan farklı değişkenleri değiştirmesi durumunda ortaya çıkar. İş parçacıklarının hiçbiri aynı veriye erişmiyor olsa da, önbellek tutarlılık protokolü tüm önbellek satırını çekişmeli olarak ele alır:

cpp

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

MESI protokolü (Değiştirilmiş, Özel, Paylaşılan, Geçersiz), x86 işlemcilerinin önbellek satırı sahipliğini nasıl koordine ettiğini açıklar. Bir çekirdek, diğer çekirdeklerle paylaştığı bir konuma (Paylaşılan durum) yazmak istediğinde, bir yazma isteği yayınlamalı, tüm paylaşanlardan onay beklemeli ve Değiştirilmiş duruma geçmelidir. Bu tutarlılık protokolüne gidiş-dönüş, çok soketli bir sistemde 50-300+ döngü sürer. Yanlış paylaşım, bağımsız iş parçacığı yerel işlemlerini önbellek tutarlılığı trafiğine dönüştürerek, çekirdek sayısıyla doğrusal olarak artması gereken performansı düşürür.

Yanlış paylaşımı tespit etme: kullan perf stat -e cache-misses,L1-dcache-load-misses Linux'ta veya Windows'ta Visual Studio'nun CPU performans profili aracında. Önbelleğe sığan çok iş parçacıklı bir programda yüksek oranda L1 önbellek isabeti olmaması, yanlış paylaşımın güçlü bir göstergesidir.

Bellek Sıralaması: Neden memory_order_relaxed Her zaman yeterli değildir

C + + std::atomic Bu işlemler, C++11 bellek modelinden gelen bellek sıralamasının tüm yelpazesini ortaya koymaktadır. Yanlış sıralama seçimi, ABA probleminden sonra kilitlenmesiz kodda en sık karşılaşılan ikinci hatadır.

cpp

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

Sık yapılan bir hata: kullanmak relaxed Bir serbest bırakma bayrağı için. Ayarlayan bir iş parçacığı. ready = true 'da relaxed Sıralama, önceki yazma işlemlerinin de aynı şekilde gerçekleşeceğini garanti etmez. data diğer okuma iş parçacıkları tarafından görülebilir. readyEdinme/bırakma çifti, yazar ve okuyucuyu birbirine bağlayan "önce gerçekleşme" ilişkisini oluşturur.

Treiber Yığını: C++'da Kilitlenmesiz Yığın

Treiber yığını, en basit, önemsiz olmayan kilitlenmesiz veri yapısıdır. Tek bir eleman üzerinde CAS döngüsü kullanır. top işaretçi:

cpp

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

Hakkında yorum delete node Kritik nokta şudur: Basit silme işlemi, daha önce açıklanan ABA tehlikesidir. Üretim ortamındaki bir Treiber yığınında, düğüm geri kazanımı tehlike işaretçileri, dönem tabanlı geri kazanım veya çöp toplama gerektirir (Java/C# bunu otomatik olarak halleder).

Java Kilitlenmesiz Veri Yapıları

Java'nın standart kütüphanesi, üretim kalitesinde kilitlenmesiz uygulamalar sunmaktadır. java.util.concurrent:

Sınıf	Structure	Ilerleme	notlar
AtomicReference<T>	Tek değer	Kilitsiz	CAS nesne referansı üzerinde
AtomicStampedReference<T>	Değer + pul	Kilitsiz	Sürüm sayacı yoluyla ABA önleme
ConcurrentLinkedQueue<T>	Michael-Scott kuyruğu	Kilitsiz	FIFO, sınırsız
ConcurrentLinkedDeque<T>	Kilitsiz kuyruk	Kilitsiz	Her iki uç
LongAdder	sayaç	Kilitsiz	Çizgili, yüksek verimli sayım

LongAdder Özellikle belirtilmesi gereken bir nokta var. Tüm iş parçacıkları arasında rekabet eden tek bir atomik sayaç yerine, her birine iş parçacıklarının bir alt kümesinin eriştiği şeritli bir sayaç dizisi tutulur. Rekabet, tek bir konumda yoğunlaşmak yerine şeritler arasında yayılır. Toplam, tembel bir şekilde toplanır. sum()Çok sayıda iş parçacığında yüksek frekanslı artırma işlemleri için, LongAdder önemli ölçüde üstün performans sergiliyor AtomicLong.incrementAndGet():

Java

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

Ne kadar SMART TS XL Kilitlenmesiz Sistem Geliştirmeyi Destekler

Kilitlenmesiz kod, doğru yazılması en zor kod türlerinden biridir. Hatalar deterministik değildir, yalnızca belirli ara katmanlama durumlarında ortaya çıkar ve genellikle yalnızca büyük ölçekli üretimde görülür. Statik analiz, bir yarış koşulunun ortaya çıkmasını beklemek yerine, kodun yapısal özelliklerini yürütmeden önce inceleyerek bu sorunu ele alır.

SMART TS XL Eşzamanlı kodun tüm yürütme yollarını analiz eder ve atomik işlemlerin korudukları bellek konumlarıyla nasıl ilişkili olduğunu izler. Kilitlenmesiz kodu eski bileşenlerle veya çok dilli mimarilerle birleştiren sistemler için, tek dilli araçların sağlayamayacağı sınır ötesi görünürlük sunar: kilitlenmesiz bir C++ bileşeni tarafından erişilen paylaşımlı bir bellek bölgesinin, ondan okuyan Java servisiyle nasıl ilişkili olduğu veya eşzamanlı bir kuyruğun COBOL tabanlı bir işleme hattına nasıl beslendiği gibi.

Statik kod analizi özelliği, eşzamanlılık tehlikeleriyle ilişkili kalıpları belirler: karşılık gelen edinme semantiği olmayan atomik yüklemeler, başarısızlık durumunda beklenen değeri güncellemeyen CAS döngüleri, farklı iş parçacıkları tarafından erişilen alanların hizalama dolgusu olmadan birlikte konumlandırıldığı paylaşılan veri yapıları. Etki analizi özelliği, paylaşılan eşzamanlı bir veri yapısına hangi alt bileşenlerin bağlı olduğunu izler, böylece yapının arayüzünde veya geri kazanım stratejisinde yapılacak değişiklikler, değişiklik yapılmadan önce doğru şekilde kapsamlandırılabilir.

Kilitlenmesiz bileşenlerin eski tip toplu işleme, mesaj kuyruklama ara yazılımları ve modern hizmet katmanlarıyla birlikte var olması gereken kurumsal sistemler için, SMART TS XL'S bağımlılık eşlemesi Bu, eşzamanlı veri yollarının, tüm sistem yığını boyunca farklı dillerde yazılmış bileşenleri nasıl birbirine bağladığına dair mimari bir bakış açısı sunar.

Kilitsiz Sistem Ne Zaman Yanlış Seçim Olabilir?

Kilitsiz yapılar her zaman mutex'ten daha iyi değildir. Kilitsiz yapıların tercih edilme durumu, iş yükünün gerçek çekişme profiline bağlıdır. Düşük iş parçacığı sayılarında veya düşük çekişmede, iyi uygulanmış bir mutex daha hızlıdır çünkü atomik yeniden deneme döngülerinin ve çekirdekler arası önbellek satırı geçersizleştirmesinin ek yükünü ortadan kaldırır.

Mutex'i şu durumlarda kullanın:

• İplik sayısı düşük (4-8'in altında) veya çekişme seyrek.
• Kritik bölüm uzun ve karmaşık (kilitsiz döngüler, bölüme göre daha pahalı hale geliyor).
• Doğruluk, verimlilikten daha önemlidir ve kilit mekanizmasıyla algoritma daha basittir.
• Platform, verimli futex tabanlı kilitleme sistemine sahiptir (Linux). pthread_mutex(Windows SRWLOCK)

Kilitleme özelliğini şu durumlarda kullanın:

• İplik sayısı yüksek ve çekişme sürüyor.
• İşlemler kısa sürer (CAS döngüsü ek yükü, işleme göre küçüktür).
• Engelleme kabul edilemez (gerçek zamanlı iş parçacıkları, kesme işleyicileri, sinyal işleyicileri)
• Kilitlerin kilit sırası bağımlılıkları getireceği diğer kilitsiz yapılarla birleştirme

Bekleme gerektirmeyen özelliği şu durumlarda kullanın:

• Her iş parçacığı, diğer iş parçacıklarından bağımsız olarak, sınırlı bir süre içinde tamamlanmalıdır.
• Kaynak yetersizliğinin kabul edilemez olduğu, gerçek zamanlı veya güvenlik açısından kritik gereksinimler.
• Algoritma, her iş parçacığı için sınırlı adımlı tamamlamayı destekleyecek şekilde yapılandırılabilir.

Kilitlenmesiz programlama disiplini, onu her yerde seçmek değil, tam olarak özellikleri (engellenmeyen ilerleme, kilitlenmenin ortadan kaldırılması, önceliklendirmeye tolerans) sistemin gerçek gereksinimleriyle eşleştiği yerlerde seçmektir.