Jaki jest najlepszy sposób implementacji słownika bezpiecznego dla wątków?


109

Udało mi się zaimplementować słownik bezpieczny dla wątków w C #, wyprowadzając z IDictionary i definiując prywatny obiekt SyncRoot:

public class SafeDictionary<TKey, TValue>: IDictionary<TKey, TValue>
{
    private readonly object syncRoot = new object();
    private Dictionary<TKey, TValue> d = new Dictionary<TKey, TValue>();

    public object SyncRoot
    {
        get { return syncRoot; }
    } 

    public void Add(TKey key, TValue value)
    {
        lock (syncRoot)
        {
            d.Add(key, value);
        }
    }

    // more IDictionary members...
}

Następnie blokuję ten obiekt SyncRoot wśród moich konsumentów (wiele wątków):

Przykład:

lock (m_MySharedDictionary.SyncRoot)
{
    m_MySharedDictionary.Add(...);
}

Udało mi się to zrobić, ale zaowocowało to brzydkim kodem. Moje pytanie brzmi: czy istnieje lepszy, bardziej elegancki sposób implementacji słownika bezpiecznego dla wątków?


3
Co jest w tym brzydkiego?
Asaf R

1
Myślę, że odnosi się do wszystkich instrukcji blokujących, które ma w swoim kodzie w konsumentach klasy SharedDictionary - blokuje kod wywołujący za każdym razem, gdy uzyskuje dostęp do metody w obiekcie SharedDictionary.
Peter Meyer

Zamiast używać metody Add, spróbuj przypisać wartości ex- m_MySharedDictionary ["key1"] = "item1", jest to bezpieczne wątkowo.
testuser

Odpowiedzi:


43

Jak powiedział Peter, możesz zawrzeć całość bezpieczeństwa wątków wewnątrz klasy. Będziesz musiał uważać na wszelkie zdarzenia, które ujawnisz lub dodasz, upewniając się, że są wywoływane poza jakimikolwiek zamkami.

public class SafeDictionary<TKey, TValue>: IDictionary<TKey, TValue>
{
    private readonly object syncRoot = new object();
    private Dictionary<TKey, TValue> d = new Dictionary<TKey, TValue>();

    public void Add(TKey key, TValue value)
    {
        lock (syncRoot)
        {
            d.Add(key, value);
        }
        OnItemAdded(EventArgs.Empty);
    }

    public event EventHandler ItemAdded;

    protected virtual void OnItemAdded(EventArgs e)
    {
        EventHandler handler = ItemAdded;
        if (handler != null)
            handler(this, e);
    }

    // more IDictionary members...
}

Edycja: dokumentacja MSDN wskazuje, że wyliczanie z natury nie jest bezpieczne dla wątków. Może to być jeden z powodów ujawniania obiektu synchronizacji poza klasą. Innym sposobem podejścia byłoby zapewnienie pewnych metod wykonywania akcji na wszystkich członkach i blokowanie wyliczania członków. Problem polega na tym, że nie wiesz, czy akcja przekazana do tej funkcji wywołuje jakiegoś członka słownika (co spowodowałoby zakleszczenie). Ujawnienie obiektu synchronizacji umożliwia konsumentowi podjęcie tych decyzji i nie ukrywa zakleszczenia wewnątrz klasy.


@fryguybob: Wyliczenie było właściwie jedynym powodem, dla którego ujawniłem obiekt synchronizacji. Zgodnie z konwencją blokowałbym ten obiekt tylko wtedy, gdy wyliczam w kolekcji.
GP.

1
Jeśli twój słownik nie jest zbyt duży, możesz wyliczyć go na kopii i mieć to wbudowane w klasę.
fryguybob

2
Mój słownik nie jest zbyt duży i myślę, że to załatwiło sprawę. To, co zrobiłem, to utworzenie nowej metody publicznej o nazwie CopyForEnum (), która zwraca nowe wystąpienie Dictionary z kopiami prywatnego słownika. Ta metoda została następnie wywołana w celu wyliczenia, a SyncRoot został usunięty. Dzięki!
GP.

12
Nie jest to również klasa z natury bezpieczna dla wątków, ponieważ operacje słownikowe są zwykle szczegółowe. Trochę logiki na wzór if (dict.Contains (cokolwiek)) {dict.Remove (cokolwiek); dict.Add (cokolwiek, newval); } jest z pewnością stanem wyścigu czekającym na wystąpienie.
cokół

207

Klasa .NET 4.0, która obsługuje współbieżność, nosi nazwę ConcurrentDictionary.


4
Proszę oznaczyć to jako odpowiedź, nie potrzebujesz niestandardowego słownika, jeśli własna .Net ma rozwiązanie
Alberto León

27
(Pamiętaj, że druga odpowiedź została napisana na długo przed pojawieniem się .NET 4.0 (wydanego w 2010).)
Jeppe Stig Nielsen

1
Niestety nie jest to rozwiązanie bez blokad, więc jest bezużyteczne w bezpiecznych zestawach SQL Server CLR. Potrzebowałbyś czegoś takiego, jak opisano tutaj: cse.chalmers.se/~tsigas/papers/Lock-Free_Dictionary.pdf lub może ta implementacja: github.com/hackcraft/Ariadne
Triynko

2
Wiem, że naprawdę stary, ale ważne jest, aby pamiętać, że użycie ConcurrentDictionary zamiast Dictionary może spowodować znaczne straty wydajności. Jest to najprawdopodobniej wynikiem kosztownego przełączania kontekstu, więc upewnij się, że potrzebujesz słownika bezpiecznego dla wątków, zanim go użyjesz.
przegrany

60

Próba wewnętrznej synchronizacji prawie na pewno będzie niewystarczająca, ponieważ jej poziom abstrakcji jest zbyt niski. Załóżmy, że operacje Addi są ContainsKeyindywidualnie bezpieczne dla wątków w następujący sposób:

public void Add(TKey key, TValue value)
{
    lock (this.syncRoot)
    {
        this.innerDictionary.Add(key, value);
    }
}

public bool ContainsKey(TKey key)
{
    lock (this.syncRoot)
    {
        return this.innerDictionary.ContainsKey(key);
    }
}

Co się dzieje, gdy wywołujesz ten rzekomo bezpieczny dla wątków fragment kodu z wielu wątków? Czy zawsze będzie działać dobrze?

if (!mySafeDictionary.ContainsKey(someKey))
{
    mySafeDictionary.Add(someKey, someValue);
}

Prostą odpowiedzią jest: nie. W pewnym momencie Addmetoda zgłosi wyjątek wskazujący, że klucz już istnieje w słowniku. Możesz zapytać, jak to może być z bezpiecznym słownikiem? Cóż, tylko dlatego, że każda operacja jest bezpieczna dla wątków, połączenie dwóch operacji nie jest, ponieważ inny wątek mógłby zmodyfikować ją między wywołaniem ContainsKeya Add.

Co oznacza, że ​​aby poprawnie napisać tego typu scenariusz, potrzebujesz blokady poza słownikiem, np

lock (mySafeDictionary)
{
    if (!mySafeDictionary.ContainsKey(someKey))
    {
        mySafeDictionary.Add(someKey, someValue);
    }
}

Ale teraz, widząc, że musisz napisać zewnętrzny kod blokujący, mieszasz synchronizację wewnętrzną i zewnętrzną, co zawsze prowadzi do problemów, takich jak niejasny kod i zakleszczenia. Więc ostatecznie prawdopodobnie lepiej:

  1. Użyj normalnego Dictionary<TKey, TValue>i zsynchronizuj zewnętrznie, zamykając na nim operacje złożone lub

  2. Napisz nową otokę bezpieczną dla wątków z innym interfejsem (tj. Nie IDictionary<T>), która łączy operacje, takie jak AddIfNotContainedmetoda, więc nigdy nie musisz łączyć operacji z niej.

(Sam mam tendencję do # 1)


10
Warto zauważyć, że .NET 4.0 będzie zawierał całą gamę bezpiecznych wątkowo kontenerów, takich jak kolekcje i słowniki, które mają inny interfejs niż standardowa kolekcja (tj. Robią za Ciebie opcję 2 powyżej).
Greg Beech

1
Warto również zauważyć, że ziarnistość oferowana przez nawet prymitywne blokowanie będzie często wystarczająca dla podejścia z jednym piszącym wielu czytelników, jeśli zaprojektuje się odpowiedni moduł wyliczający, który poinformuje podstawową klasę, kiedy zostanie usunięta (metody, które chciałyby napisać słownik podczas istnieje niewykorzystany moduł wyliczający, który powinien zastąpić słownik kopią).
supercat

6

Nie powinieneś publikować swojego prywatnego obiektu blokady za pośrednictwem właściwości. Obiekt blokady powinien istnieć prywatnie wyłącznie w celu pełnienia funkcji punktu spotkania.

Jeśli wydajność okaże się słaba przy użyciu standardowego zamka, kolekcja zamków Power Threading firmy Wintellect może być bardzo przydatna.


5

Istnieje kilka problemów związanych z metodą implementacji, którą opisujesz.

  1. Nigdy nie powinieneś ujawniać swojego obiektu synchronizacji. Spowoduje to otwarcie się na konsumenta, który chwyci przedmiot i zamknie go, a następnie wzniesiesz toast.
  2. Implementujesz bezpieczny interfejs bez wątków z klasą bezpieczną dla wątków. IMHO to będzie cię kosztować w dół drogi

Osobiście odkryłem, że najlepszym sposobem implementacji klasy bezpiecznej dla wątków jest niezmienność. To naprawdę zmniejsza liczbę problemów, które możesz napotkać z bezpieczeństwem wątków. Sprawdź Eric Lippert na bloga po więcej szczegółów.


3

Nie musisz blokować właściwości SyncRoot w obiektach konsumenckich. Blokada, którą masz w metodach słownika, jest wystarczająca.

Do opracowania: kończy się to, że słownik jest zablokowany na dłuższy okres czasu, niż jest to konieczne.

Oto co dzieje się w Twoim przypadku:

Powiedz, że wątek A uzyskuje blokadę w SyncRoot przed wywołaniem m_mySharedDictionary.Add. Wątek B następnie próbuje uzyskać blokadę, ale jest blokowany. W rzeczywistości wszystkie inne wątki są blokowane. Wątek A może wywoływać metodę Add. W instrukcji lock w metodzie Add wątek A może ponownie uzyskać blokadę, ponieważ już jest jej właścicielem. Po wyjściu z kontekstu blokady w ramach metody, a następnie poza metodą, wątek A zwolnił wszystkie blokady, umożliwiając kontynuację innych wątków.

Możesz po prostu zezwolić dowolnemu konsumentowi na wywołanie metody Add, ponieważ instrukcja lock w metodzie Add klasy SharedDictionary będzie miała ten sam efekt. W tym momencie masz nadmiarowe blokowanie. Zablokowałbyś tylko SyncRoot poza jedną z metod słownika, gdybyś musiał wykonać dwie operacje na obiekcie słownika, który wymagał zagwarantowania, że ​​wystąpią po kolei.


1
Nieprawda ... jeśli wykonasz dwie operacje po drugiej, które są wewnętrznie bezpieczne dla wątków, nie oznacza to, że cały blok kodu jest bezpieczny dla wątków. Na przykład: if (! MyDict.ContainsKey (someKey)) {myDict.Add (someKey, someValue); } nie byłoby bezpieczne dla wątków, nawet jeśli ContainsKey i Add są bezpieczne dla wątków
Tim

Twój punkt widzenia jest słuszny, ale jest wyrwany z kontekstu mojej odpowiedzi i pytania. Jeśli spojrzysz na pytanie, nie mówi ono o wywołaniu ContainsKey ani mojej odpowiedzi. Moja odpowiedź odnosi się do uzyskania blokady SyncRoot, która jest pokazana w przykładzie w pierwotnym pytaniu. W kontekście instrukcji lock co najmniej jedna operacja bezpieczna wątkowo byłaby rzeczywiście wykonywana bezpiecznie.
Peter Meyer,

Wydaje mi się, że jeśli wszystko, co kiedykolwiek robi, to dodawanie do słownika, ale ponieważ ma „// więcej członków IDictionary…”, zakładam, że w pewnym momencie będzie chciał odczytać dane ze słownika. W takim przypadku musi istnieć jakiś dostępny z zewnątrz mechanizm blokujący. Nie ma znaczenia, czy jest to SyncRoot w samym słowniku, czy inny obiekt używany wyłącznie do blokowania, ale bez takiego schematu ogólny kod nie będzie bezpieczny dla wątków.
Tim

Zewnętrzny mechanizm blokujący jest taki, jak pokazuje jego przykład w pytaniu: lock (m_MySharedDictionary.SyncRoot) {m_MySharedDictionary.Add (...); } - byłoby całkowicie bezpieczne wykonanie następujących czynności: lock (m_MySharedDictionary.SyncRoot) {if (! m_MySharedDictionary.Contains (...)) {m_MySharedDictionary.Add (...); }} Innymi słowy, zewnętrzny mechanizm blokujący to instrukcja lock działająca na właściwości publicznej SyncRoot.
Peter Meyer,

0

Pomyśl, dlaczego nie odtworzyć słownika? Jeśli czytanie to wiele zapisów, blokowanie zsynchronizuje wszystkie żądania.

przykład

    private static readonly object Lock = new object();
    private static Dictionary<string, string> _dict = new Dictionary<string, string>();

    private string Fetch(string key)
    {
        lock (Lock)
        {
            string returnValue;
            if (_dict.TryGetValue(key, out returnValue))
                return returnValue;

            returnValue = "find the new value";
            _dict = new Dictionary<string, string>(_dict) { { key, returnValue } };

            return returnValue;
        }
    }

    public string GetValue(key)
    {
        string returnValue;

        return _dict.TryGetValue(key, out returnValue)? returnValue : Fetch(key);
    }

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.