Algorytm dla prostej równoległej mapy bez blokowania w trakcie czytania?

Question

Próbuję zapisać mapę, która jest wątkowo bezpieczna, ale nigdy nie blokuje ani nie blokuje odczytu. Moją próbą jest użycie mapy tylko do odczytu, która zostanie skopiowana podczas pisania. Pomysł to get() jest blokowany, a put() kopiuje bieżącą mapę tylko do odczytu do nowej, umieszcza ją i zamienia bieżącą mapę bazową na nową. (Tak, put() jest nieefektywne, ponieważ kopie całej mapy, ale nie dbam o mój przypadek użycia)

Moje pierwsze ukłucie w ten używany std :: atomowy < * StringMap> na tylko do odczytu map ALE Istnieje ogromny błąd w tym, prawdopodobnie ze względu na moje tło Java. get() atomicznie dostaje wskaźnik do mapy bazowej, która może być lub nie jest aktualna, gdy ją wczytuje (co jest ok). Ale put() usuwa mapę bazową po zamianie jej na nową. Jeśli get() wywołuje starą mapę w momencie jej usunięcia, spowoduje to oczywiście awarię.

Mój przyjaciel zasugerował shared_ptr, ale nie jest pewien, czy operacje shared_ptr wykonują jakąkolwiek blokadę pod kołdrą. Doktorzy twierdzą, że jest bezpieczny dla wątków. Edytuj: Nosid wskazuje, że nie jest bezpieczny dla wątków i potrzebuję specjalnej operacji atomowej ze std :: atomic.

Moje pytania brzmią: 1. Czy ten algorytm jest wykonalny? 2. Czy operacje shared_ptr powodują blokowanie, szczególnie w przypadku dostępu?

#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

Kod zawiera wyścig danych na std::shared_ptr i zachowanie programów z wyścigach danych jest niezdefiniowana w C++. Problem dotyczy: Klasa std::shared_ptr nie jest wątkowa. Istnieją jednak specjalne operacje atomowe dla std::shared_ptr, które można wykorzystać do rozwiązania problemu.

można znaleźć więcej informacji na temat tych operacji atomowych na następującej stronie internetowej:

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

Answer 2

Czytelnik powinien wykonać dwie operacje: pobrać i umieścić. get zawsze pobiera nowy wskaźnik i zwiększa liczbę atomową. Put zwalnia wskaźnik i dekrementy. Usuń mapę, gdy liczba zejdzie do zera. Pisarz tworzy nową mapę i robi to. Następnie umieszcza się na starej mapie, aby oznaczyć ją do usunięcia.