Opowieść o dwóch iteratorach: konkurencyjne strategie modyfikacji w Javie

Autorem notatki jest Grzegorz Mirek, programista z Krakowa. Zaczął rozwijać się w Javie około 6 lat temu jeszcze na studiach i od tego czasu niestrudzenie doskonali swoje umiejętności w tym obszarze. Szczególnie interesuje się wydajnością i optymalizacją JVM, o czym głównie pisze na swoim blogu . Do najpopularniejszych pytań podczas rozmów kwalifikacyjnych w języku Java należą: Jaka jest różnica między iteratorami odpornymi na awarie i bezpiecznymi? Najbardziej uproszczona odpowiedź na to pytanie brzmi: Iterator odporny na awarie zgłasza wyjątek ConcurrentModificationException, jeśli kolekcja ulegnie zmianie podczas iteracji, ale iterator odporny na awarie nie. Chociaż brzmi to dość sensownie, nie jest jasne, co osoba przeprowadzająca rozmowę ma na myśli, mówiąc „bezpieczna w razie awarii”? Specyfikacje języka Java nie definiują tego terminu w odniesieniu do iteratorów. Istnieją jednak cztery konkurencyjne strategie modyfikacji.

Modyfikacja konkurencyjna

Najpierw zdefiniujmy, czym jest modyfikacja konkurencyjna (lub równoległa). Załóżmy, że mamy kolekcję i gdy iterator jest aktywny, zachodzą pewne zmiany, które nie pochodzą od tego iteratora. W tym przypadku otrzymujemy konkurencyjną modyfikację. Podam prosty przykład: załóżmy, że mamy kilka wątków. Pierwszy wątek wykonuje iterację, a drugi wątek wstawia lub usuwa elementy z tej samej kolekcji. Możemy jednak uzyskać wyjątek ConcurrentModificationException podczas działania w środowisku jednowątkowym:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Szybkość awarii

Powyższy fragment kodu jest przykładem iteratora odpornego na awarie . Jak widać, podczas próby pobrania drugiego elementu z iteratora został zgłoszony wyjątek ConcurrentModificationException . Skąd iterator wie, że kolekcja została zmodyfikowana od czasu jej utworzenia? Na przykład kolekcja może mieć znacznik daty/godziny, powiedzmy lastModified . Tworząc iterator, należy skopiować to pole i zapisać je w obiekcie iteratora. Następnie za każdym razem, gdy wywołasz metodę next() , po prostu porównasz wartość lastModified z kolekcji z kopią z iteratora. Bardzo podobne podejście stosuje się np. przy implementacji klasy ArrayList . Posiada zmienną instancji modCount , która przechowuje liczbę modyfikacji listy:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

Należy zauważyć, że iteratory odporne na awarie działają w oparciu o najlepsze w swojej klasie, co oznacza, że ​​nie ma gwarancji, że w przypadku równoczesnej modyfikacji zostanie zgłoszony wyjątek ConcurrentModificationException . Nie należy więc na nich polegać - raczej należy ich używać do wykrywania błędów. Większość kolekcji niewspółbieżnych zapewnia niezawodne iteratory.

Słaba spójność

Większość współbieżnych kolekcji w pakiecie java.util.concurrent (takich jak ConcurrentHashMap i większość Queue ) udostępnia słabo spójne iteratory. Znaczenie tego terminu jest bardzo dobrze wyjaśnione w dokumentacji :

• Można je przetwarzać równolegle z innymi operacjami
• Nigdy nie zgłaszają wyjątku ConcurrentModificationException
• Gwarantuje się, że przejdą przez istniejące elementy w momencie utworzenia iteratora dokładnie raz i mogą (ale nie muszą) odzwierciedlać późniejsze modyfikacje.

Migawka

Dzięki tej strategii iterator jest powiązany ze stanem kolekcji w momencie jej utworzenia – jest to migawka kolekcji. Wszelkie zmiany wprowadzone w oryginalnej kolekcji powodują utworzenie nowej wersji podstawowej struktury danych. To pozostawia naszą migawkę niezmienioną, więc nie odzwierciedla zmian w kolekcji, które nastąpiły po utworzeniu iteratora. Jest to stara, dobra technika kopiowania przy zapisie (COW) . Całkowicie rozwiązuje problem współbieżnych modyfikacji, więc przy tym podejściu nie jest generowany wyjątek ConcurrentModificationException . Ponadto iteratory nie obsługują operacji zmieniających elementy. Kolekcje typu „kopiuj przy zapisie” są zwykle zbyt drogie w użyciu, ale warto z nich korzystać, jeśli zmiany zachodzą znacznie rzadziej niż przechodzenia przez iteratory. Przykładami są klasy CopyOnWriteArrayList i CopyOnWriteArraySet .

Nieokreślone zachowanie

Możesz napotkać niezdefiniowane zachowanie w starszych typach kolekcji, takich jak Vector i Hashtable . Obydwa posiadają standardowe , niezawodne iteratory, ale w dodatku pozwalają na zastosowanie implementacji interfejsu Enumeration i nie wiedzą, jak się zachować w przypadku jednoczesnej modyfikacji. Możesz napotkać, że niektóre elementy się powtarzają lub ich brakuje, a nawet dziwne wyjątki. Lepiej się z nimi nie bawić!