Bellek Modeli

Önceki ders ortak veriyi kilitle korumayı ve kilidin bedelinin kaç kez alındığıyla belirlendiğini gösterdi: dört iş parçacığı için kırk bin kilit alma, yerel toplamla dörde inebildi. Kilit her şeyi birden yapar: veriyi tek bir iş parçacığına tutturur ve yazılanların sonraki alana görünmesini sağlar. Bu ders o ikisini ayırıyor. std::atomic bir değişkene yapılan tek bir işlemi bölünmez kılar; ayrıca bu işlemin çevresindeki yazıların başkasına ne zaman görünür olacağını bellek sıralaması belirler. Kursun ölçtüğü soru yine aynı: düzenek bedeli nereye taşıyor? Cevabın sınıfı beklemedir ve ölçü burada da gerçek beklemeyi değil, bir veri yayınının kaç eşgüdüm noktası istediğini sayar. Sayı kanıt aracıdır; ders sınıf adıyla cevaplanır.

Bölünmezlik ile Sıralama Aynı Şey Değildir

std::atomic<int> üzerindeki bir okuma ya da yazma, yarım görülemez: başka bir iş parçacığı ya eski değeri ya yeni değeri görür, arası yoktur. fetch_add gibi okuma-değiştirme-yazma işlemleri bu bölünmezliği üç adımın tamamına yayar: değeri okuma, artırma ve geri yazma tek işlemdir, araya başka bir artış giremez. Bu yüzden kilitsiz bir sayaç artırmak, değişken std::atomic olduğunda veri yarışı sayılmaz.

Ama bölünmezlik, diğer değişkenlere ne olduğunu söylemez. Her atomik işlem bir bellek sıralaması alır ve dört sıralama bu derste önemlidir. std::memory_order_seq_cst varsayılandır: bütün seq_cst işlemleri bütün iş parçacıkları için tek bir ortak sırayla görünür. memory_order_release bir yazıya, memory_order_acquire bir okumaya verilir ve ikisi birlikte çalışır. memory_order_relaxed ise yalnızca bölünmezlik verir, başka hiçbir şey sıralamaz.

Release ve acquire arasındaki ilişki, önce-olur bağıntısı olarak ifade edilir. Bir iş parçacığı bir atomik değişkene release ile yazarsa ve başka bir iş parçacığı o yazılan değeri acquire ile okursa, release’ten önceki bütün yazılar acquire’dan sonraki bütün okumalara görünür olur. Düz, atomik olmayan değişkenler de buna dahildir; yayın bayrağı atomik, yayınlanan veri düz olabilir.

Bir Yayın: Bin Düz Değer, Bir Release Yazısı

Üretici bin düz değeri bir diziye yazar, sonra yalnızca bir atomik bayrağa release ile yazar. Tüketici bayrağı acquire ile okuyup birini görünce bin değerin hepsini görür. Eşgüdüm noktası, üreticide yapılan release yazılarının sayısıdır; düzenek bir yazı için bir nokta ister. Sayacı elle yazmıyoruz: her release yazısından hemen sonra üretici tarafı kendi düz sayacını bir artırır ve sayaç yalnızca join() sonrasında okunur.

// yayin.hpp — iki yayin bicimi: tek bayrak ve her eleman atomik
#pragma once
#include <atomic>
#include <thread>

constexpr int ELEMAN = 1000;

struct TekBayrak {
    int veri[ELEMAN];
    std::atomic<int> hazir{0};
    long esgudum = 0;
    long toplam = 0;
};

inline void uret_tek(TekBayrak& y) {
    for (int i = 0; i < ELEMAN; ++i) y.veri[i] = i;
    y.hazir.store(1, std::memory_order_release);
    ++y.esgudum;
}

inline void tuket_tek(TekBayrak& y) {
    while (y.hazir.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    long t = 0;
    for (int i = 0; i < ELEMAN; ++i) t += y.veri[i];
    y.toplam = t;
}

struct HerEleman {
    std::atomic<int> dizi[ELEMAN];
    long esgudum = 0;
    long toplam = 0;
    HerEleman() {
        for (auto& e : dizi) e.store(-1, std::memory_order_relaxed);
    }
};

inline void uret_hepsi(HerEleman& y) {
    for (int i = 0; i < ELEMAN; ++i) {
        y.dizi[i].store(i, std::memory_order_release);
        ++y.esgudum;
    }
}

inline void tuket_hepsi(HerEleman& y) {
    long t = 0;
    for (int i = 0; i < ELEMAN; ++i) {
        int v;
        while ((v = y.dizi[i].load(std::memory_order_acquire)) == -1) std::this_thread::yield();
        t += v;
    }
    y.toplam = t;
}

TekBayrak dizisi düz bir int dizisidir; hazir bayrağı atomiktir. Üretici bayraktan önce yazar, tüketici bayrağı görmeden dizinin hiçbir elemanına dokunmaz. HerEleman ikinci biçimdir ve Sınırlayıcı Ölçüm bölümünde okunacak. Dizinin sıfırlanması, iş parçacıkları açılmadan önce yapılır: std::thread kurulumu, yapıcının çağrılmasına kadar yapılan her şeyi yeni iş parçacığına görünür kılar.

Relaxed Neyi Vermez

relaxed sıralama, bölünmezlik haricinde hiçbir şey vermez. Bu, relaxed bir fetch_add sayacının yine de doğru toplam vermesi demektir: dört iş parçacığı onar bin kez fetch_add(1, std::memory_order_relaxed) çağırırsa sonuç kırk bin olur, çünkü bölünmezlik her artışı korur. Ama aynı relaxed işlem bir yayın bayrağı olarak kullanılırsa üreticinin düz yazıları tüketiciye görünmeyebilir; bayrak 1 görünmüş ama bin değer eski halinde kalmış olabilir. Bu bir veri yarışıdır ve davranışı tanımsızdır, bu yüzden koşturmuyoruz. Çözüm yayın bayrağında release ve acquire kullanmaktır.

seq_cst ile release/acquire Farkı

Yukarıdaki yayını sıralama belirtmeden yazsaydık, her işlem seq_cst olurdu. Sonuç aynıdır: bayrağı acquire ile okuyan taraf yazılanları görür. Fark, seq_cst’in bir şey daha eklemesidir: bütün seq_cst işlemleri için tek bir toplam sıra vardır ve her iş parçacığı bu sıraya uyar. Release/acquire yalnızca bir yazı ile onu okuyan arasındaki ilişkiyi kurar; iki ilgisiz bayrağın hangisinin önce yazıldığı konusunda iki gözlemcinin anlaşmasını gerektirmez. İki bağımsız yazıcı ve iki okuyucu düşünün: okuyuculardan biri x’in y’den önce yazıldığını, öbürü tersini görebilir. Release/acquire bunu yasaklamaz; iki yazı ve iki okumanın hepsi seq_cst ise bu sonuç yasaktır. Bu durumu koşturmuyoruz, çünkü hangi sonucun görüleceği çizelgeye ve donanıma bağlıdır; ders yalnızca garantinin kapsamını ayırır.

Bu ek garanti bir bedelle gelir: ortak toplam sırayı sağlamak bazı donanımlarda ek engeller gerektirir. Sizin saydığınız eşgüdüm noktası ise değişmez, yine bir yazıdır. Bu yüzden seq_cst‘i bilerek seçmek yerine, yayının yalnızca bir yazı ile bir okumaya dayandığını görüyorsanız release/acquire’a inmek bir seçimdir. Emin değilseniz varsayılan olan seq_cst doğrudur; bu bir hız iddiası değil, doğruluk tercihidir.

// siralama.hpp — ayni yayin, varsayilan seq_cst siralamayla
#pragma once
#include <atomic>
#include <thread>

#include "yayin.hpp"

struct VarsayilanYayin {
    int veri[ELEMAN];
    std::atomic<int> hazir{0};
    long esgudum = 0;
    long toplam = 0;
};

inline void uret_varsayilan(VarsayilanYayin& y) {
    for (int i = 0; i < ELEMAN; ++i) y.veri[i] = i;
    y.hazir.store(1);
    ++y.esgudum;
}

inline void tuket_varsayilan(VarsayilanYayin& y) {
    while (y.hazir.load() == 0) std::this_thread::yield();
    long t = 0;
    for (int i = 0; i < ELEMAN; ++i) t += y.veri[i];
    y.toplam = t;
}

Okuma-Değiştirme-Yazma ve compare_exchange

fetch_add değeri her zaman artırır. Bazen yazının koşullu olması gerekir: “değer hâlâ okuduğum değerse yaz”. compare_exchange_strong(beklenen, istenen) bunu tek bölünmez işlemle yapar. Atomik değer beklenen’e eşitse istenen yazılır ve true döner; eşit değilse hiçbir şey yazılmaz, false döner ve beklenen atomiğin o anki değeriyle güncellenir. Dört iş parçacığı aynı bayrağı 0’dan 1’e çevirmeye çalışırsa tek biri kazanır; diğerleri başarısızlığı görür. Kazananı seçmek için kilit gerekmez.

İşlemin weak biçimi, değer eşit olduğu halde de başarısız olabilir; bu yüzden hep bir döngü içinde kullanılır. Karşılığında bazı donanımlarda daha ucuzdur. Tipik kalıp, değeri okumak, bir aday hesaplamak ve compare_exchange_weak ile yazmayı denemektir; başarısızlıkta beklenen zaten yeni değerle yenilendiği için döngü yeniden okumaz. Aşağıdaki örnek, dört iş parçacığının gördüğü en büyük değeri kilitsiz bulur: aday mevcut değerden büyükse yazmayı dener, değilse döngüden hemen çıkar.

// rmw.hpp — compare_exchange ile tek kazanan ve en buyuk deger
#pragma once
#include <atomic>
#include <thread>
#include <vector>

inline int tek_kazanan(int is_sayisi) {
    std::atomic<int> bayrak{0};
    std::atomic<int> kazanan{0};
    std::vector<std::thread> isler;
    for (int t = 0; t < is_sayisi; ++t) {
        isler.emplace_back([&] {
            int beklenen = 0;
            if (bayrak.compare_exchange_strong(beklenen, 1)) kazanan.fetch_add(1);
        });
    }
    for (auto& is : isler) is.join();
    return kazanan.load();
}

inline int en_buyuk(int is_sayisi, int adet) {
    std::atomic<int> enbuyuk{0};
    std::vector<std::thread> isler;
    for (int t = 0; t < is_sayisi; ++t) {
        isler.emplace_back([&, t] {
            for (int k = 0; k < adet; ++k) {
                int aday = k * is_sayisi + t;
                int mevcut = enbuyuk.load(std::memory_order_relaxed);
                while (aday > mevcut && !enbuyuk.compare_exchange_weak(mevcut, aday)) {
                }
            }
        });
    }
    for (auto& is : isler) is.join();
    return enbuyuk.load();
}

Döngünün kaç kez döndüğü çizelgeye bağlıdır, bu yüzden basılmaz. Sonuç ise çizelgeden bağımsızdır: en büyük aday her koşulda yazılır.

Önce-Olur Zincirini Adım Adım Okumak

Önce-olur bağıntısı geçişlidir. Üç iş parçacığı olsun: A bir düz değeri yazıp bayrak1’e release ile yazar; B bayrak1‘i acquire ile görür, kendi düz değerini yazar ve bayrak2‘ye release ile yazar; C bayrak2‘yi acquire ile görür. C’nin gördüğü, A’nın hiç dokunmadığı bir bayrak üzerinden gelir; yine de A’nın yazısını da görür. Zinciri şöyle okuruz.

1. A’nın düz yazısı, A’nın bayrak1 release yazısından önce olur (aynı iş parçacığında sıra).
2. bayrak1 release yazısı, B’nin onu gören acquire okumasından önce olur (release/acquire çifti).
3. B’nin acquire okuması, B’nin düz yazısından ve bayrak2 release yazısından önce olur (aynı iş parçacığında sıra).
4. bayrak2 release yazısı, C’nin acquire okumasından önce olur (ikinci çift).
5. Geçişlilik: A’nın yazısı C’nin okumasından önce olur, B’ninki de.

Zincirdeki her halka ya aynı iş parçacığındaki sıradır ya da bir release/acquire çiftidir. Bir halka koparsa, örneğin B bayrağı relaxed okursa, 2. adım kurulmaz ve C’nin A’nın yazısını görmesinin hiçbir garantisi kalmaz.

// zincir.hpp — uc is parcaciginda onceolur zinciri
#pragma once
#include <atomic>
#include <thread>

struct Zincir {
    int a = 0;
    int b = 0;
    std::atomic<int> bayrak1{0};
    std::atomic<int> bayrak2{0};
    int gorulen_a = 0;
    int gorulen_b = 0;
};

inline void zincir_a(Zincir& z) {
    z.a = 10;
    z.bayrak1.store(1, std::memory_order_release);
}

inline void zincir_b(Zincir& z) {
    while (z.bayrak1.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    z.b = z.a + 5;
    z.bayrak2.store(1, std::memory_order_release);
}

inline void zincir_c(Zincir& z) {
    while (z.bayrak2.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    z.gorulen_a = z.a;
    z.gorulen_b = z.b;
}

Ölçüm: Kaç Eşgüdüm Noktası

// yayin_olcumu.cpp — iki yayin bicimi ve relaxed bir sayac
#include <atomic>
#include <functional>
#include <iostream>
#include <thread>
#include <vector>

#include "rmw.hpp"
#include "siralama.hpp"
#include "yayin.hpp"
#include "zincir.hpp"

int main() {
    TekBayrak tek;
    {
        std::thread uretici(uret_tek, std::ref(tek));
        std::thread tuketici(tuket_tek, std::ref(tek));
        uretici.join();
        tuketici.join();
    }
    std::cout << "release/acquire yayini bekleme esgudum=" << tek.esgudum
              << " toplam=" << tek.toplam << "\n";

    HerEleman her;
    {
        std::thread uretici(uret_hepsi, std::ref(her));
        std::thread tuketici(tuket_hepsi, std::ref(her));
        uretici.join();
        tuketici.join();
    }
    std::cout << "her eleman atomik bekleme esgudum=" << her.esgudum
              << " toplam=" << her.toplam << "\n";

    std::atomic<long> sayac{0};
    std::vector<std::thread> isler;
    for (int i = 0; i < 4; ++i) {
        isler.emplace_back([&sayac] {
            for (int k = 0; k < 10000; ++k) sayac.fetch_add(1, std::memory_order_relaxed);
        });
    }
    for (auto& is : isler) is.join();
    std::cout << "relaxed sayac bekleme deger=" << sayac.load() << "\n";

    VarsayilanYayin varsayilan;
    {
        std::thread uretici(uret_varsayilan, std::ref(varsayilan));
        std::thread tuketici(tuket_varsayilan, std::ref(varsayilan));
        uretici.join();
        tuketici.join();
    }
    std::cout << "seq_cst yayini bekleme esgudum=" << varsayilan.esgudum
              << " toplam=" << varsayilan.toplam << "\n";

    std::cout << "compare exchange bekleme kazanan=" << tek_kazanan(4) << "\n";
    std::cout << "cas dongusu bekleme enbuyuk=" << en_buyuk(4, 1000) << "\n";

    Zincir zincir;
    {
        std::thread c(zincir_c, std::ref(zincir));
        std::thread b(zincir_b, std::ref(zincir));
        std::thread a(zincir_a, std::ref(zincir));
        a.join();
        b.join();
        c.join();
    }
    std::cout << "onceolur zinciri bekleme a=" << zincir.gorulen_a
              << " b=" << zincir.gorulen_b << "\n";
    return 0;
}

release/acquire yayini bekleme esgudum=1 toplam=499500
her eleman atomik bekleme esgudum=1000 toplam=499500
relaxed sayac bekleme deger=40000
seq_cst yayini bekleme esgudum=1 toplam=499500
compare exchange bekleme kazanan=1
cas dongusu bekleme enbuyuk=3999
onceolur zinciri bekleme a=10 b=15

EB7. İlk satır, bin düz değerin tek bir release yazısıyla yayınlandığını gösterir: esgudum=1. Tüketici acquire okumasıyla bayrağı görünce bin elemanın tamamını okudu ve toplam 499500 çıktı; bu, sıfırdan dokuz yüz doksan dokuza kadar sayıların toplamıdır. Tüketicinin bayrağı görmeden önce kaç kez döndüğü basılmaz, çünkü bu sayı çizelgeye bağlıdır; ölçülen şey döngü sayısı değil, yazılan release sayısıdır.

EB8. Üçüncü satır, relaxed fetch_add sayacının yine 40000 verdiğini gösterir. Sıralama gevşek olduğu halde sonuç doğrudur; çünkü bölünmezlik sıralama değildir ve her artış başka bir artışın içine girmez. Relaxed sayaç, yalnızca son değerin okunduğu ve başka veriyi yayınlamadığı durumda doğru kullanımdır.

EB9. Dördüncü satır, aynı yayının varsayılan seq_cst sıralamayla da bir yazı ve bir okumadan oluştuğunu gösterir: esgudum=1, toplam=499500. Eşgüdüm noktası sayısı sıralamayı değiştirmekle değişmedi; seq_cst farkı bu satırdan okunmaz, çünkü fark yalnızca birbirinden bağımsız iki yayının gözlemciler tarafından sıralanışında ortaya çıkar.

EB10. compare_exchange_strong ile dört iş parçacığı aynı bayrağı 0’dan 1’e çevirmeye çalıştı ve kazanan=1 çıktı. Dördünün de aynı anda başarılı olması mümkün olsaydı sayı birden büyük çıkardı; bölünmez karşılaştırma ve yazma bunu önledi. Hangi iş parçacığının kazandığı basılmadı, çünkü çizelgeye bağlıdır.

EB11. enbuyuk=3999 değeri, dört iş parçacığının ürettiği adayların en büyüğüdür: son adım k=999 ve son iş parçacığı t=3 için 999 * 4 + 3. Başka bir iş parçacığı araya girip değeri değiştirdiğinde compare_exchange_weak başarısız oldu ve mevcut’u güncelledi; döngü adayı yeni değerle yeniden karşılaştırdı. Hiçbir büyük değer, küçük bir değerin ardından yazılıp kaybolmadı.

EB12. Son satırda C iş parçacığı hem a=10 hem b=15 değerini gördü. C’nin hiç okumadığı bayrak1 üzerinden gelen a, zincirin geçişliliği sayesinde görünür oldu. İş parçacıkları sıra dışı başlatılsa bile (C ilk açıldı) sonuç değişmedi, çünkü C bayrağı görene kadar döngüde kaldı.

Sınırlayıcı Ölçüm

Bu dersin ölçtüğü düzenek, bellek sıralamasının eşgüdüm noktası sayısını belirlemesidir. İkinci satır, aynı bin değeri bu kez her elemanı ayrı bir atomik yaparak yayınlıyor. Her yazı release, her okuma acquire; doğruluk bozulmadı, toplam=499500. Ama esgudum=1000: bin kat fazla eşgüdüm noktası.

Bu fark verinin kendisinden değil, yayının ne kadar ince bölündüğünden gelir. Bir bayrak bin değeri korurken, bin atomik her değeri tek tek korur. Önce-olur bağıntısı tek bir release-acquire çifti için ucuzdur ve çiftin önündeki bütün yazıları kapsar; bunun için yayınlanacak veriyi önce toplamak, sonra tek bir noktadan açmak gerekir. Sınır şudur: tüketici verinin yarısını beklemeden kullanmak zorundaysa, tek bayrak yetmez ve parçalı yayın kaçınılmaz olur. Bedeli düşürmek için sıralamayı gevşetmek yetmez; yayının kaç noktaya bölündüğünü azaltmak gerekir.

Özet

• Bu dersin ölçtüğü düzenek bedeli bekleme sınıfına taşır: bellek sıralaması, bir veri yayınının kaç eşgüdüm noktası istediğini belirler; ölçü gerçek bekleme değil, bu noktaların sayısıdır.
• std::atomic bölünmezlik verir; fetch_add gibi okuma-değiştirme-yazma işlemleri üç adımı tek işleme çevirir. Bölünmezlik, sıralama değildir.
• Release yazısı ile acquire okuması önce-olur bağıntısını kurar: acquire, release’in yazdığı değeri okuduğunda release’ten önceki bütün yazılar acquire’dan sonraki bütün okumalara görünür olur.
• seq_cst varsayılandır ve bütün seq_cst işlemlerini tek bir ortak sırada görünür kılar; relaxed yalnızca bölünmezlik verir, bir yayın bayrağı olarak kullanılması veri yarışıdır.
• release/acquire yayini bin değeri bir noktada, her eleman atomik düzeneği bin noktada yayınladı; ikisi de aynı toplamı verdi.

Sonraki Adım

Eşgüdüm noktalarını azaltmak, işin yarısıdır; kalan yarısı verinin bellekte nasıl dizildiğidir. Bir sonraki ders önbellek satırını ve yerelliği açıyor: bir veri düzeni kaç geçişi atlatıyor sorusuyla yapı dizisi ile dizi yapısını karşılaştıracağız.