Wie implementiert man einen 64-Bit-Atomzähler mit nur 32-Bit-Atomvariablen?

Implementierung eines 64-Bit-Atomzählers mit 32-Bit-Atomvariablen

Frage:

Entwerfen und implementieren Sie einen 64-Bit-Atomzähler mit 32-Bit-Atomvariablen. Der Zähler verfügt über einen einzigen Schreiber (Signalhandler) und mehrere Lesegeräte.

Code:

class counter {
    atomic<uint32_t> lo_{};
    atomic<uint32_t> hi_{};
    atomic<uint32_t> gen_{};

    uint64_t read() const {
        auto acquire = memory_order_acquire;
        uint32_t lo, hi, gen1, gen2;
        do {
            gen1 = gen_.load(acquire);
            lo = lo_.load(acquire);
            hi = hi_.load(acquire);
            gen2 = gen_.load(acquire);
        } while (gen1 != gen2 || (gen1 & 1));
        return (uint64_t(hi) << 32) | lo;
    }

    void increment() {
        auto release = memory_order_release;
        gen_.fetch_add(1, release);
        uint32_t newlo = 1 + lo_.fetch_add(1, release);
        if (newlo == 0) {
            hi_.fetch_add(1, release);
        }
        gen_.fetch_add(1, release);
    }
};

Antwort:

Der bereitgestellte Code ist eine korrekte Implementierung eines 64-Bit-Atomzählers unter Verwendung von 32-Bit-Atomvariablen. Es verwendet eine als SeqLock bekannte Technik, die eine Generationszählung verwendet, um die Konsistenz der oberen und unteren Hälften des Zählers aufrechtzuerhalten.

Der Lesevorgang verwendet eine Schleife, um während der Verarbeitung den korrekten Zustand des Zählers zu ermitteln mögliche Wettrennen zwischen Lesern und Autoren. Der Schreibvorgang erhöht sowohl den oberen als auch den niedrigen Teil des Zählers atomar und verwendet dabei die Speicherreihenfolge, um das korrekte Verhalten sicherzustellen.

Verbesserte Implementierung:

Während der bereitgestellte Code korrekt ist , es kann für eine bessere Leistung und Effizienz verbessert werden:

• Anstatt atomare RMW-Operationen für die Zählernutzlast zu verwenden, verwenden sie kann durch einfache Lade- und Speichervorgänge ersetzt werden, um unnötigen Overhead zu vermeiden.
• Der Sequenzzähler kann auch mit einfachen Lade- und Speichervorgängen beibehalten werden, da er nur monoton ansteigend und nicht atomar aktualisiert werden muss.

Alternatives Design:

Ein alternatives Design, das atomare RMW-Operationen vollständig überflüssig macht, ist die Verwendung einer Union eines volatilen uint64_t und eines std::atomic Variable. Der flüchtige Teil kann zum Lesen und Schreiben des Werts verwendet werden, während die atomare Variable zum Aktualisieren des Sequenzzählers verwendet werden kann. Dieser Ansatz bietet die notwendigen Garantien für korrektes Verhalten und optimiert gleichzeitig die Leistung.

Das obige ist der detaillierte Inhalt vonWie implementiert man einen 64-Bit-Atomzähler mit nur 32-Bit-Atomvariablen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!