Lesen/Schreiben von Speicher Multithreaded



  • Hallo zusammen

    ich habe einen Speicherbereich auf den mehrere Threads schreiben oder Lesen können (sollen).
    Dort will ich entsprechend folgender Regeln den Zugriff steuern:

    • Leseoperationen dürfen nicht zeitgleich mit Schreiboperationen stattfinden
    • Leseoperationen dürfen parallel stattfinden
    • mehrere Schreiboperationen dürfen nicht parallel stattfinden

    Das ganz soll NICHT mit CriticalSections umgesetzt werden sondern mit atomics:

    Mein erster Ansatz war dann dieser hier, mit jeweils einem std::atomic<int> als Counter der Schreibzugriffe bzw. Lesezugriffe. Diese werden erhöht bei Zugriff und gesenkt nach Ende des Zugriffs.

    bool DataAccessControl::startWriteAccess()
    {
        // Warten auf Ende einer anderen Schreib-Operation, falls vorhanden
        while( WriteAccessCounter > 0 );
       
       // GENAU HIER KÖNNTE EIN ANDERER THREAD SICH SCHON WIEDER DEN SCHREIBZUGRIFF SICHERN
    
        // Warten auf das Ende aller Leseoperationen, falls vorhanden
        while( ReadAccessCounter > 0 );
    
        // Sind bereit fuer Zugriff
        ++WriteAccessCounter;
        return ReadAccessCounter == 0 && WriteAccessCounter == 1;
    }
    
    bool DataAccessControl::endWriteAccess()
    {
        --WriteAccessCounter;
        return WriteAccessCounter == 0;
    }
    

    Das Problem habe ich mit großen Buchstaben im Quellcode beispielhaft notiert.
    Die Hauptaufgabe ist also nach Ende des Spins, also der Warteschleife auf den Zugriff direkt den eigenen Zugriff abzusichern, ohne das zwischendrin wieder jemand reingrätscht.

    Wie würde man sowas (performant) erledigen?

    Es gibt ja das "atomic_flag" ( https://de.cppreference.com/w/cpp/atomic/atomic_flag/test_and_set ), das quasi das abtesten und das setzen in einem Schwung macht. Für ein "bool" anstatt eines Counters wäre das dann tragbar, aber ich brauche ja, zumindest für die Lesezugriffe einen Counter.



  • Zunächst mal würde ich Zeile 12 eine Instruktion vorziehen, also zwischen Zeile 4 und 9 einfügen, oder übersehe ich auf die Schnelle etwas?



  • Es könnte dann trotzdem noch ein anderer Thread vorher WriteAccessCounter hochzählen. Dann wäre der WAC==2.

    Also Thread A wird nach Zeile 9 unterbrochen und Thread B erst nach dem Inkrement. Wenn Thread A jetzt weitermacht wird wird wieder der Schreibzugriff inkrementiert. Das heißt, da müsste man nochmal den ersten Spinlock wiederholen. Wobei dann natürlich RAC wieder modifiziert werden könnte?!

    Wieso muss das unbedingt ohne Mutex sein?



  • @Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

    Es könnte dann trotzdem noch ein anderer Thread vorher WriteAccessCounter hochzählen. Dann wäre der WAC==2.

    Also Thread A wird nach Zeile 9 unterbrochen und Thread B erst nach dem Inkrement. Wenn Thread A jetzt weitermacht wird wird wieder der Schreibzugriff inkrementiert. Das heißt, da müsste man nochmal den ersten Spinlock wiederholen. Wobei dann natürlich RAC wieder modifiziert werden könnte?!

    Grundsätzlich kann hier zwischen zwei Anweisungen immer ein anderer Thread reingrätschen, deswegen glaube ich inzwischen auch nicht mehr, dass das hier ohne Zauberei nur mit diesen Countern zu bewältigen ist.

    @Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

    Wieso muss das unbedingt ohne Mutex sein?

    Mir ist es relativ egal. Fokus liegt nur in dem Fall zu 100% auf Performance-Maximum. Daher schwebt mir zunächst mal eine Lösung mit std::atomics vor. Mutex wäre natürlich eine Alternative, falls die Mutexes performant genug sind...

    Ich erwarte häufige Zugriffe auf diesen Speicherbereich, daher ist mir die Performance wichtig.



  • Na dann gilt eh beides machen und dann profilen, weil umsonst sind die atomics auch nicht.

    Aber ne Lösung für parallele Lesezugriffe ... da muss ich jetzt auch erstmal nachdenken.



  • Was den Schreibzugriff angeht, bin ich glaube schon etwas weiter:

    bool DataAccessControl::startWriteAccess()
    {
        // Warten auf Ende einer anderen Schreib-Operation, falls vorhanden
        int32_t oldValue = 0;
        while ( !WriteAccessCounter.compare_exchange_weak( oldValue, 1 ) )
        {
            // Wenn wir hier landen ist, oldValue nicht mehr 0. 0 Ist aber unser Erwartungswert, also setzen wir ihn wieder
            oldValue = 0;
        }
    
        // Warten auf das Ende aller Leseoperationen, falls vorhanden
        while( ReadAccessCounter > 0 );
        return true;
    }
    

    Das "compare_exchange_weak" wartet quasi darauf, dass der WAC == 0 wird und setzt dann direkt den wert 1, ohne das dazwischen ein anderer Thread reingrätschen kann.
    Hinterher warte ich ganz normal darauf, dass der RAC auch 0 wird. Ein neuer ReadAccess kann mir da nicht mehr dazu kommen, da die Bedingung für einen ReadAccess ist, dass kein WriteAccess vorliegt, und diesen habe ich mir ja bereits gesichert.

    Bleibt noch der Schreibzugriff.
    Dort muss ich quasi warten bis der WAC == 0 wird UND dann direkt den RAC erhöhen....



  • @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    daher ist mir die Performance wichtig

    Und Spinlocks sind da besser als Mutexes?



  • Der Trick ist ein einziges Atomic zu verwenden indem man ein Bit für "gibt es einen Writer" und die restlichen Bits für den Leser-Zähler verwendet.

    Oder du verwendest einfach SRWLocks: https://docs.microsoft.com/en-us/windows/win32/sync/slim-reader-writer--srw--locks
    Oder du verwendest einfach std::shared_mutex: https://en.cppreference.com/w/cpp/thread/shared_mutex

    Wie würde man sowas (performant) erledigen?

    Auf Windows: SRWLocks
    Ansonsten: erstmal gucken wie schnell std::shared_mutex ist, sollte schnell genug sein
    Ansonsten: selbst schreiben, wie oben angedeutet



  • Ich fand den Artikel seinerzeit interessant:

    https://webkit.org/blog/6161/locking-in-webkit/

    Weiß jetzt aber nicht, ob sie das immer noch verwenden.

    Die SRW Locks können auch relativ teuer sein. Und die shared_mutex Implementierung von VC++ verwendet die auch.

    Das sind aber schon extreme Optimierungen. Wenn sowas wirklich eine größere Rolle spielt, stimmt eher was mit dem restlichen Code nicht.



  • Da hier mehrmals das Word Spinlock gefallen ist hier nur ein Hinweis wieso so was im userspace nicht gut ist:

    https://mjtsai.com/blog/2020/01/06/beware-spinlocks-in-user-space/

    Dadurch kann man nicht vollständig (Data-)Races verhindern.



  • @firefly sagte in Lesen/Schreiben von Speicher Multithreaded:

    Dadurch kann man nicht vollständig (Data-)Races verhindern.

    Magst du erklären? In dem verlinkten Beitrag ist von Data Races nicht die Rede.



  • Kann gut sein das mit dem Data Races falsch verstanden habe oder miss interpretiert habe.



  • @manni66 sagte in Lesen/Schreiben von Speicher Multithreaded:

    @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    daher ist mir die Performance wichtig

    Und Spinlocks sind da besser als Mutexes?

    Letztendlich wird auch beim Mutex oder bei einer CritSect gewartet. Mag sein, dass das dort effizienter geschieht. Keine Ahnung.

    Hier hat scheinbar jemand Performance-Tests mit verschiedenen Lock-Varianten gemacht:
    https://stackoverflow.com/questions/13206414/why-slim-reader-writer-exclusive-lock-outperformance-the-shared-one

    Das Mutex kommt dabei gar nicht gut weg. Allerdings sind die Umstände des Tests nicht bekannt.



  • @hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

    Der Trick ist ein einziges Atomic zu verwenden indem man ein Bit für "gibt es einen Writer" und die restlichen Bits für den Leser-Zähler verwendet.

    Klingt eigentlich gut, nur es bleibt halt immer das Problem, dass man Abprüfen bis gewünschtem Zustand und Setzen des neuen Zustands ( Z.b. Lese-Zähler erhöht um 1 ) in einem Rutsch erledigen muss, ohne dass ein anderer Thread die Möglichkeit hat zwischen die Lese und die Schreib-Instruktion zu kommen.



  • @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    @manni66 sagte in Lesen/Schreiben von Speicher Multithreaded:

    @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    daher ist mir die Performance wichtig

    Und Spinlocks sind da besser als Mutexes?

    Letztendlich wird auch beim Mutex oder bei einer CritSect gewartet. Mag sein, dass das dort effizienter geschieht. Keine Ahnung.

    Ja klar geht das da effizienter. Deswegen direkt zu Anfang meine Frage. Ein Spinlock ist ja quasi die Nutzung der CPU als Heizung, ein wartender Mutex jedoch gibt die Kontrolle an den OS-Scheduler zurück, verbraucht während der Wartezeit also keine CPU Leistung.



  • @Tyrdal sagte in Lesen/Schreiben von Speicher Multithreaded:

    @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    @manni66 sagte in Lesen/Schreiben von Speicher Multithreaded:

    @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    daher ist mir die Performance wichtig

    Und Spinlocks sind da besser als Mutexes?

    Letztendlich wird auch beim Mutex oder bei einer CritSect gewartet. Mag sein, dass das dort effizienter geschieht. Keine Ahnung.

    Ja klar geht das da effizienter. Deswegen direkt zu Anfang meine Frage. Ein Spinlock ist ja quasi die Nutzung der CPU als Heizung, ein wartender Mutex jedoch gibt die Kontrolle an den OS-Scheduler zurück, verbraucht während der Wartezeit also keine CPU Leistung.

    Naja letztendlich muss man wissen, was das Ziel ist. Das Mutex braucht deutlich länger, um die Kontrolle zurückzubekommen als z.b. ein Atomic mit Spinlock. Dafür bezahlt man mit CPU-Usage.

    Ich werde ohnehin verschiedene Varianten testen, auch mit Mutex und dann mal ein paar Messwerte aufnehmen. Da für mich aber die Zugriffszeiten im Vordergrund stehen ist mir eben an der Lock-Free-Variante mit atomics gelegen. Herausforderungen braucht der Mensch 😉

    Das gute am Mutex ist: Wenn es keine Kollision gibt, kann man den Zeitaufwand für Lock und Unlock mit 0 annehmen.



  • @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    @hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

    Der Trick ist ein einziges Atomic zu verwenden indem man ein Bit für "gibt es einen Writer" und die restlichen Bits für den Leser-Zähler verwendet.

    Klingt eigentlich gut, nur es bleibt halt immer das Problem, dass man Abprüfen bis gewünschtem Zustand und Setzen des neuen Zustands ( Z.b. Lese-Zähler erhöht um 1 ) in einem Rutsch erledigen muss, ohne dass ein anderer Thread die Möglichkeit hat zwischen die Lese und die Schreib-Instruktion zu kommen.

    Allergrundlegendste Grundoperation bei Atomics: Compare-And-Swap.



  • @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    Das gute am Mutex ist: Wenn es keine Kollision gibt, kann man den Zeitaufwand für Lock und Unlock mit 0 annehmen.

    Du kannst annehmen was du willst, bloss stimmen tut es deswegen nicht. Gerade wenn es keine Kollisionen gibt sind Spin-Locks ideal. Wobei ideal != "0 Kosten". Und der Unterschied zu einer guten Mutex Implementierung ist nicht gross.



  • @It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

    Hier hat scheinbar jemand Performance-Tests mit verschiedenen Lock-Varianten gemacht:
    https://stackoverflow.com/questions/13206414/why-slim-reader-writer-exclusive-lock-outperformance-the-shared-one

    Das Mutex kommt dabei gar nicht gut weg. Allerdings sind die Umstände des Tests nicht bekannt.

    Das was dort "mutex" genannt wird ist wohl ein Windows Mutex: https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-createmutexw
    Hat mit std::mutex nixe zu tun. Wo findet ihr Kids bloss immer diese total sinnfreien Vergleiche?



  • @hustbaer das Internet bietet halt auch viel Schund an. Deswegen schrieb ich ja auch, dass man die Hintergründe der PerformanceMessung nicht kennt, geschweige denn den Quellcode.

    Das hier ist wohl vermutlich eine Implementation von dem Lock-Free-Ding, was du erwähnt hast, mit einem INT welches ein WriteAccess-Bit enthält.
    https://yizhang82.dev/lock-free-rw-lock


Log in to reply