Algorithmus für eine einfache nicht-locking-on-lesen gleichzeitige Karte?

Question

Ich versuche, eine Karte zu schreiben, die threadsicher ist, aber niemals beim Lesen blockiert oder blockiert. Ich versuche, eine schreibgeschützte Map zu verwenden, die beim Schreiben kopiert wird. Die Idee ist get() ist sperren-frei, und put() kopiert die aktuelle schreibgeschützte unterliegende Karte zu einem neuen, tut das Put und tauscht die aktuelle zugrunde liegende Karte für ein neues aus. (Ja, put() ist ineffizient, da sie kopiert die gesamte Karte, aber ich interessiere mich nicht für meinen Anwendungsfall)

Meinen ersten Stich an dieser std verwendet :: Atom < * StringMap> für den Read-Only Karte ABER es ist ein großer Fehler mit diesem, wahrscheinlich aufgrund meiner Java-Hintergrund. get() erhält atomar einen Zeiger auf die zugrunde liegende Karte, die die aktuelle sein kann oder nicht, wenn es es lädt (was in Ordnung ist). Aber put() löscht die zugrunde liegende Karte, nachdem sie es für die neue austauscht. Wenn get() ruft die alte Karte gerade als es gelöscht wird, wird dies offensichtlich zum Absturz bringen.

Ein Freund von mir vorgeschlagen shared_ptr, aber er ist nicht sicher, ob die shared_ptr-Operationen schließen unter den Abdeckungen. Die Doktoren sagen, dass es thread-safe ist, obwohl. Edit: Wie Nosid darauf hinweist, ist es nicht threadsicher und ich brauche die spezielle atomare Operation von std :: atomic.

Also meine Fragen sind: 1. Ist dieser Algorithmus realisierbar? 2. Führen shared_ptr-Operationen Sperren aus, besonders beim Zugriff?

#include <unordered_map> 
#include <atomic> 
#include <pthread.h> 
#include <memory> 

typedef std::unordered_map<std::string, std::string> StringMap; 

class NonBlockingReadMap { 
private: 
    pthread_mutex_t fMutex;  
    std::shared_ptr<StringMap> fspReadMapReference; 


public: 

    NonBlockingReadMap() { 
     fspReadMapReference = std::make_shared<StringMap>(); 
    } 

    ~NonBlockingReadMap() { 
     //so, nothing here? 
    } 

    std::string get(std::string &key) { 
     //does this access trigger any locking? 
     return fspReadMapReference->at(key); 
    } 

    void put(std::string &key, std::string &value) { 
     pthread_mutex_lock(&fMutex); 
     std::shared_ptr<StringMap> spMapCopy = std::make_shared<StringMap>(*fspReadMapReference); 
     std::pair<std::string, std::string> kvPair(key, value); 
     spMapCopy->insert(kvPair); 
     fspReadMapReference.swap(spMapCopy); 
     pthread_mutex_unlock(&fMutex); 
    } 

    void clear() { 
     pthread_mutex_lock(&fMutex); 
     std::shared_ptr<StringMap> spMapCopy = std::make_shared<StringMap>(*fspReadMapReference); 
     fspReadMapReference.swap(spMapCopy); 
     spMapCopy->clear(); 
     pthread_mutex_unlock(&fMutex); 
    } 

}; 

Answer 1

Ihr Code enthält ein Daten Rennen auf den std::shared_ptr und das Verhalten von Programmen mit Daten Rennen ist in C++ nicht definiert.

Das Problem ist: Die Klasse std::shared_ptr ist nicht Thread-sicher. Es gibt jedoch spezielle atomare Operationen für std::shared_ptr, die verwendet werden können, um das Problem zu lösen.

Sie weitere Informationen über diese atomare Operationen auf der folgenden Webseite finden:

• http://en.cppreference.com/w/cpp/memory/shared_ptr/atomic

Answer 2

Reader sollte zwei Operationen ausführen: Get und Put. get ruft immer den neuen Zeiger ab und erhöht die Anzahl der Atome. Put gibt den Zeiger frei und dekrementiert. Löschen Sie die Karte, wenn der Zähler auf Null geht. Der Autor erstellt eine neue Karte und macht sich daran. Dann legt er die alte Karte an, um sie zum Löschen zu markieren.