Różne typy bezpiecznych wątków w Javie

135

Wydaje się, że istnieje wiele różnych implementacji i sposobów generowania zestawów bezpiecznych dla wątków w Javie. Oto kilka przykładów

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (zestaw zestaw)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (nowy ConcurrentHashMap ())

5) Inne zestawy generowane w sposób podobny do (4)

Te przykłady pochodzą z implementacji Concurrency Pattern: Concurrent Set w Javie 6

Czy ktoś mógłby po prostu wyjaśnić różnice, zalety i wady tych i innych przykładów? Mam problem ze zrozumieniem i prostym utrzymaniem wszystkiego z Java Std Docs.

Ben
źródło

Odpowiedzi:

206

1) CopyOnWriteArraySetImplementacja jest dość prosta - w zasadzie ma listę elementów w tablicy, a po zmianie listy kopiuje tablicę. Iteracje i inne dostępy, które są uruchomione w tym czasie, są kontynuowane ze starą tablicą, unikając konieczności synchronizacji między czytnikami i piszącymi (chociaż samo pisanie wymaga synchronizacji). Normalnie szybkie operacje na zbiorach (szczególnie contains()) są tutaj dość wolne, ponieważ tablice będą przeszukiwane w czasie liniowym.

Używaj tego tylko dla naprawdę małych zestawów, które będą często czytane (iterowane) i rzadko zmieniane. (Przykładem byłyby zestawy słuchaczy swingów, ale nie są to tak naprawdę zestawy i powinny być używane tylko z EDT).

2) Collections.synchronizedSetpo prostu zawinie zsynchronizowany blok wokół każdej metody z oryginalnego zestawu. Nie powinieneś uzyskiwać bezpośredniego dostępu do oryginalnego zestawu. Oznacza to, że żadne dwie metody z zestawu nie mogą być wykonywane jednocześnie (jedna będzie blokować, dopóki druga nie zakończy się) - jest to bezpieczne wątkowo, ale nie będziesz mieć współbieżności, jeśli wiele wątków naprawdę używa zestawu. Jeśli używasz iteratora, zwykle nadal musisz zsynchronizować zewnętrzną, aby uniknąć ConcurrentModificationExceptions podczas modyfikowania zestawu między wywołaniami iteratora. Wydajność będzie podobna do oryginalnego zestawu (ale z pewnym narzutem synchronizacji i blokowaniem, jeśli jest używany jednocześnie).

Użyj tego, jeśli masz tylko niską współbieżność i chcesz mieć pewność, że wszystkie zmiany są natychmiast widoczne dla innych wątków.

3) ConcurrentSkipListSetjest równoczesną SortedSetimplementacją, z większością podstawowych operacji w O (log n). Pozwala na jednoczesne dodawanie / usuwanie i odczytywanie / iterację, gdzie iteracja może lub nie może informować o zmianach od czasu utworzenia iteratora. Operacje zbiorcze to po prostu wielokrotne pojedyncze wywołania, a nie atomowo - inne wątki mogą obserwować tylko niektóre z nich.

Oczywiście możesz tego użyć tylko wtedy, gdy masz jakiś całkowity porządek na swoich elementach. Wygląda na to, że jest to idealny kandydat do sytuacji z dużą współbieżnością, dla niezbyt dużych zestawów (ze względu na O (log n)).

4) Dla ConcurrentHashMap(i zbioru pochodnego): Tutaj najbardziej podstawowe opcje są (średnio, jeśli masz dobre i szybkie hashCode()) w O (1) (ale mogą się zdegenerować do O (n)), jak dla HashMap / HashSet. Istnieje ograniczona współbieżność zapisu (tabela jest podzielona na partycje, a dostęp do zapisu zostanie zsynchronizowany na wymaganej partycji), podczas gdy dostęp do odczytu jest w pełni współbieżny z nim samym i zapisywanymi wątkami (ale może jeszcze nie widzieć wyników aktualnie wprowadzanych zmian pisemny). Iterator może, ale nie musi, widzieć zmiany od czasu jego utworzenia, a operacje zbiorcze nie są atomowe. Zmiana rozmiaru jest powolna (jak w przypadku HashMap / HashSet), dlatego staraj się tego uniknąć, szacując wymagany rozmiar podczas tworzenia (i wykorzystując o około 1/3 więcej, ponieważ zmienia rozmiar, gdy jest zapełniony w 3/4).

Użyj tego, gdy masz duże zestawy, dobrą (i szybką) funkcję skrótu i ​​możesz oszacować rozmiar zestawu i wymaganą współbieżność przed utworzeniem mapy.

5) Czy istnieją inne współbieżne implementacje map, których można by tutaj użyć?

Paŭlo Ebermann
źródło
1
Tylko korekta wzroku w 1), proces kopiowania danych do nowej macierzy musi zostać zablokowany przez synchronizację. Dlatego CopyOnWriteArraySet nie pozwala całkowicie uniknąć konieczności synchronizacji.
CaptainHastings,
Na ConcurrentHashMap oparciu o zestaw „staraj się więc tego uniknąć, szacując wymagany rozmiar podczas tworzenia”. Rozmiar, który podasz mapie, powinien być o ponad 33% większy niż szacunek (lub znana wartość), ponieważ rozmiar zestawu zmienia się przy 75% obciążeniu. UżywamexpectedSize + 4 / 3 + 1
Daren
@Daren, myślę, że pierwszy +ma być *?
Paŭlo Ebermann
@ PaŭloEbermann Oczywiście ... tak powinno byćexpectedSize * 4 / 3 + 1
Daren
1
W przypadku ConcurrentMap(lub HashMap) w Javie 8, jeśli liczba wpisów mapowanych do tego samego zasobnika osiągnie wartość progową (uważam, że jest to 16), lista zostanie zmieniona na drzewo wyszukiwania binarnego (drzewo czerwono-czarne do dokładnego określenia) iw takim przypadku wyszukaj czas byłby O(lg n)i nie O(n).
akhil_mittal
20

Możliwe jest połączenie contains()wydajności HashSetz właściwościami związanymi ze współbieżnością, CopyOnWriteArraySetużywając AtomicReference<Set>i zastępując cały zestaw przy każdej modyfikacji.

Szkic wdrożeniowy:

public abstract class CopyOnWriteSet<E> implements Set<E> {

    private final AtomicReference<Set<E>> ref;

    protected CopyOnWriteSet( Collection<? extends E> c ) {
        ref = new AtomicReference<Set<E>>( new HashSet<E>( c ) );
    }

    @Override
    public boolean contains( Object o ) {
        return ref.get().contains( o );
    }

    @Override
    public boolean add( E e ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( current.contains( e ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.add( e );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

    @Override
    public boolean remove( Object o ) {
        while ( true ) {
            Set<E> current = ref.get();
            if ( !current.contains( o ) ) {
                return false;
            }
            Set<E> modified = new HashSet<E>( current );
            modified.remove( o );
            if ( ref.compareAndSet( current, modified ) ) {
                return true;
            }
        }
    }

}
Oleg Estekhin
źródło
W rzeczywistości AtomicReferenceoznacza wartość zmienną. Oznacza to, że żaden wątek nie odczytuje nieaktualnych danych i zapewnia happens-beforegwarancję, że kompilator nie może zmienić kolejności kodu. Ale jeśli AtomicReferenceużywane są tylko metody get / set of , to faktycznie oznaczamy naszą zmienną jako zmienną w fantazyjny sposób.
akhil_mittal
Ta odpowiedź nie może być wystarczająco pozytywna, ponieważ (1) jeśli czegoś nie przegapiłem, będzie działać dla wszystkich typów kolekcji (2) żadna z innych klas nie zapewnia sposobu na atomową aktualizację całej kolekcji naraz ... Jest to bardzo przydatne .
Gili
Próbowałem zawłaszczyć to dosłownie, ale okazało się, że zostało to oznaczone abstract, najwyraźniej aby uniknąć konieczności pisania kilku metod. Zacząłem je dodawać, ale napotkałem blokadę za pomocą iterator(). Nie wiem, jak utrzymać iterator nad tą rzeczą bez niszczenia modelu. Wydaje się, że zawsze muszę przechodzić przez refi za każdym razem mogę uzyskać inny zestaw bazowy, co wymaga uzyskania nowego iteratora na zestawie bazowym, co jest dla mnie bezużyteczne, ponieważ zacznie się od pozycji zero. Jakieś spostrzeżenia?
nclark
Okay, myślę, że gwarancja jest taka, że ​​każdy klient otrzymuje stałą migawkę w czasie, więc iterator podstawowej kolekcji działałby dobrze, jeśli to wszystko, czego potrzebujesz. Moim przypadkiem użycia jest zezwolenie konkurującym wątkom na „zajęcie” w nim poszczególnych zasobów i nie zadziała, jeśli mają różne wersje zestawu. Po drugie jednak ... myślę, że mój wątek musi tylko uzyskać nowy iterator i spróbować ponownie, jeśli CopyOnWriteSet.remove (selected_item) zwróci false ... Co musiałby zrobić niezależnie :)
nclark
11

Jeśli Javadocs nie pomoże, prawdopodobnie powinieneś po prostu znaleźć książkę lub artykuł, aby przeczytać o strukturach danych. W skrócie:

  • CopyOnWriteArraySet tworzy nową kopię podstawowej tablicy za każdym razem, gdy modyfikujesz kolekcję, więc zapisy są powolne, a iteratory są szybkie i spójne.
  • Collections.synchronizedSet () używa starych zsynchronizowanych wywołań metod, aby ustawić ochronę wątków. Byłaby to wersja o niskiej wydajności.
  • ConcurrentSkipListSet oferuje wydajne zapisy z niespójnymi operacjami wsadowymi (addAll, removeAll itp.) I Iteratorami.
  • Collections.newSetFromMap (new ConcurrentHashMap ()) ma semantykę ConcurrentHashMap, która moim zdaniem niekoniecznie jest zoptymalizowana pod kątem odczytu lub zapisu, ale podobnie jak ConcurrentSkipListSet ma niespójne operacje wsadowe.
Ryan Stewart
źródło
1
developer.com/java/article.php/10922_3829891_2/ ... <nawet lepsze niż książka)
ycomp
1

Jednoczesny zestaw słabych odniesień

Kolejnym zwrotem akcji jest bezpieczny dla wątków zestaw słabych odniesień .

Taki zestaw jest przydatny do śledzenia subskrybentów w scenariuszu pub-sub . Kiedy subskrybent znajduje się poza zasięgiem w innych miejscach i dlatego zmierza w kierunku zostania kandydatem do zbierania śmieci, nie trzeba mu przeszkadzać z wdzięcznym anulowaniem subskrypcji. Słabe odwołanie umożliwia subskrybentowi dokończenie jego przejścia do bycia kandydatem do czyszczenia pamięci. Kiedy śmieci zostaną ostatecznie zebrane, wpis w zestawie jest usuwany.

Chociaż żaden taki zestaw nie jest dostarczany bezpośrednio z dołączonymi klasami, możesz go utworzyć za pomocą kilku wywołań.

Najpierw zaczynamy od tworzenia Setsłabych referencji, wykorzystując WeakHashMapklasę. Jest to pokazane w dokumentacji klasy dla Collections.newSetFromMap.

Set< YourClassGoesHere > weakHashSet = 
    Collections
    .newSetFromMap(
        new WeakHashMap< YourClassGoesHere , Boolean >()
    )
;

Wartość mapy, Booleannie ma znaczenia tutaj jako Key mapy sprawia, że naszeSet .

W scenariuszu takim jak pub-sub potrzebujemy bezpieczeństwa wątków, jeśli subskrybenci i wydawcy działają w oddzielnych wątkach (całkiem prawdopodobne).

Idź o krok dalej, pakując jako zsynchronizowany zestaw, aby uczynić ten zestaw bezpiecznym dla wątków. Przekaż wezwanie do Collections.synchronizedSet.

this.subscribers =
        Collections.synchronizedSet(
                Collections.newSetFromMap(
                        new WeakHashMap <>()  // Parameterized types `< YourClassGoesHere , Boolean >` are inferred, no need to specify.
                )
        );

Teraz możemy dodawać i usuwać subskrybentów z naszego wynikowego Set. A wszyscy „znikający” subskrybenci zostaną ostatecznie automatycznie usunięci po wykonaniu operacji czyszczenia pamięci. To, kiedy nastąpi to wykonanie, zależy od implementacji modułu odśmiecania pamięci maszyny JVM i aktualnej sytuacji w środowisku wykonawczym. Aby WeakHashMapzapoznać się z dyskusją i przykładem, kiedy i jak baza usuwa wygasłe wpisy, zobacz pytanie: * Czy WeakHashMap stale rośnie, czy też czyści klucze śmieci? * .

Basil Bourque
źródło