Zmienne lotne i bariera pamięci w java

Question

Mam strukturę danych, która składa się z połączonych węzłów. Możesz myśleć o niej jak o prostej liście powiązań. Każdy węzeł listy składa się z pewnej wartości i następnego pola wskazującego drugi węzeł lub wartość null, jeśli jest to ostatni węzeł. Pierwszy węzeł działa jako root, nie ma żadnej wartości, która wskazuje tylko na następny węzeł. Wszystkie pozostałe węzły są praktycznie niezmienne, a mianowicie, gdy nie zostaną stworzone ani ich wartość, ani ich następna zmiana pola podczas życia, chyba że struktura zostanie usunięta, co odnosi się do konkretnej sytuacji.

Jeden (tylko jeden) wątek dodaje nowe węzły z przodu listy. Osiąga się to przez skonstruowanie nowego obiektu, ustawienie jego pól i ustawienie następnego pola na obiekt wskazany przez root, a następnie ustawienie następnego pola głównego korzenia do tego nowego węzła.

Pozostałe węzły przeglądają strukturę, wykonując tylko odczyty. Mają odniesienie do węzła głównego, następnie przechodzą przez inne węzły, dopóki nie znajdą tego, czego szukają lub nie dojdą do końca listy.

Moje pytanie brzmi: czy wystarczy, aby kolejna zmienna była niestabilna? Z mojego rozumienia modelu pamięci Java, jeśli wątek główny (ten, który dodaje nowe węzły), wykona lotny zapis podczas dodawania nowego węzła, wtedy wszystko zostanie zsynchronizowane dokładnie i nie wystąpią niespójności.

Czy można założyć, że na podstawie architektury x86 odczyt zmiennych lotnych nie spowoduje pogorszenia wydajności? Ponieważ inne wątki często przeglądają strukturę czytając kolejne pole, ważne jest, aby można to było zrobić bez żadnych barier pamięci itp.

Mam również jeszcze jeden problem. Wątki, które będą przeglądać strukturę, będą również zawierać kilka dodatkowych węzłów. Węzły te będą całkowicie wątkowo-lokalne, a więc będą używane tylko przez wątek, który je utworzył i nie będą w ogóle udostępniane. Dla tych dodatkowych węzłów niepotrzebne jest, aby następne pole było niestabilne. Ponadto ustawienie zmiennego następnego pola spowoduje barierę pamięci, która spowoduje niepożądaną utratę wydajności. Zastanawiam się, czy istnieje sposób, aby tego uniknąć. Idealnie byłoby idealnie, gdyby następne pole działało czasami jako zmienne pole, a czasem jako normalne pole;) lub gdybym miał pełną kontrolę i mógł samodzielnie tworzyć bariery pamięci, kiedy tylko potrzebuję.

Edit:

Ja też zastanawiałem byłoby możliwe jakoś zsynchronizować wszystkie te pisze na innej zmiennej lotnych? Na przykład inne zupełnie niezwiązane ze sobą zmienne statyczne? Skoro lotne zapisy przepłukują wszystkie oczekujące zapisy, czy następne pole nie byłoby niestabilne i zamiast tego inna zmienna lotna byłaby napisana po tym, jak wątek aktualizujący wykona całą pracę?

Nie wydaje mi się to zbyt bezpieczne, ponieważ nie ma żadnych zdarzeń przed relacją i poprzednie zapisy mogą zostać ponownie uporządkowane. Można przypisać następne przypisania pól za pomocą przypisań pól wartości prowadzących do powtarzających się wątków obserwujących niespójny stan obiektu.

Ale może uda się stworzyć taki system, który byłby bezpieczny?Jak o tym:

aktualizacja wątku najpierw konstruuje nowy obiekt, inicjalizuje jego pola wartości, ustawia następne pole do węzła wskazanego przez węzeł główny, wykonuje lotny zapis na pewnej zmiennej statycznej, ustawia następne pole węzła głównego do nowo utworzonego węzła

Answer 1

1.

W oparciu o to, co mówisz tutaj

budowy nowego obiektu, ustawienie jego pola i ustawienie następne pole do obiektu wskazanym przez root, następnie ustawienie root następne pole do tego nowego węzła.

Następnie tak, ustawienie następnego pola na lotny będzie poprawnie synchronizowane. Ważne jest, aby zrozumieć, dlaczego. Masz trzy zestawy zapisów przed ręką, jeden do obiektu węzła, jeden do pól i jeden do węzłów obok (choć nie do końca jasne, dlaczego to robisz, może tęsknię za czymś zrozumiałem).

Tak, to jest 2 + (liczba N pola) zapisuje. W tym momencie nie ma żadnego związku pomiędzy zdarzeniami i jeśli węzeł jest zapisany normalnie, nie ma żadnej gwarancji. Jak tylko napiszesz na zmiennym polu, wszystkie poprzednie zapisy będą teraz widoczne.

2.

Lotny odczytuje/zapisuje na x86 (lub jakikolwiek cache-spójne) system operacyjny ma następujące atrybuty:

volatile-read: very close to a normal read 
volatile-write: about 1/3 the time of a synchronization write 
     (whether within intrinsic locking or j.u.c.Lock locking) 

3.

wygląda będziesz musiał stworzyć VolatileNode i Node. Było propozycję Java 7 wyjść z Fences API, które można określić, jaki styl odczytu/zapisu chcesz wykonać ze statycznym klasie użytkowej, ale nie wygląda jak jego zwolnieniu

EDIT:

Thkala popełnił wielki punkt czuję warto w tym

choć należy podkreślić, że wstępnie JSR133 JVM (Java < czyli 5,0) nie mają taką samą semantykę

To, co napisałem, nie dotyczy aplikacji uruchamianych w Javie 1.4 lub mniejszej.

Answer 2

Making pole volatilenext wiązałyby się bariera pamięci na wszystkich instancji klasy węzła, a nie tylko węzła głównego. Spodziewam się, że będzie droższe niż po prostu przy użyciu synchronized w węźle głównym. Ponadto JVM może być w stanie zoptymalizować wywołania metod o wiele lepiej. Zobacz także this i this.

Powiedziawszy, prawdopodobnie powinieneś wypróbować zarówno benchmark/profile, aby zobaczyć co się stanie.

Answer 3

Twój węzeł główny faktycznie nie musi być węzłem. Potrzebujesz tylko odniesienia do pierwszego "prawdziwego" węzła.

public class LinkedList { 
    private volatile Node firstNode; 
    ... 
    addNode(Node node) { 
    node.next = firstNode; 
    firstNode = node; 
    } 
} 

Więc nie trzeba, aby pole next lotny we wszystkich węzłach; węzły nie są w ogóle synchronizowane. Można użyć tej klasy dla niezsynchronizowanych połączonych list, jeśli nie masz nic przeciwko kosztowi zmiennego dostępu do pierwszego węzła. Możesz też po prostu przepisać klasę na nieulotną wersję firstNode dla niezsynchronizowanej wersji.