Przygotowanie do SMP na Androida

Android 3.0 i nowsze wersje platformy są zoptymalizowane pod kątem obsługi architektur wieloprocesorowych. W tym dokumencie opisujemy problemy, które mogą wystąpić podczas pisania wielowątkowego kodu w symetrycznych systemach wieloprocesorowych w językach C i C++ oraz w języku programowania Java (ze względu na zwięzłość). Ma służyć jako punkt wyjścia dla deweloperów aplikacji na Androida, a nie jako pełny temat dyskusji.

Wprowadzenie

SMP to skrót od „Symetric Multi-Processor”. Opisuje on konstrukcję, w której co najmniej 2 identyczne rdzenie procesora współdzielą dostęp do pamięci głównej. Aż kilka lat temu wszystkie urządzenia z Androidem były UPRAWNIONE (Uni-Processor).

Większość urządzeń z Androidem (a nawet wszystkie) miała po kilka procesorów, ale w przeszłości tylko jeden z nich służył do uruchamiania aplikacji, a inne zarządzały różnymi częściami sprzętu (np. radiami). Procesory mogą mieć różne architektury, a uruchomione na nich programy nie mogą używać pamięci głównej do komunikacji ze sobą.

Większość sprzedawanych obecnie urządzeń z Androidem opiera się na projektach SMP, co utrudnia pracę programistom. Warunki rasowe w programie wielowątkowym nie mogą powodować widocznych problemów w jednostkach jednoprocesorowych, ale mogą występować regularnie, gdy co najmniej 2 wątki są uruchomione jednocześnie na różnych rdzeniach. Co więcej, kod może być bardziej lub mniej podatny na awarie, jeśli jest uruchomiony w różnych architekturach procesora lub nawet w różnych implementacjach tej samej architektury. Kod, który został dokładnie przetestowany na architekturze x86, może mieć awarię na architekturze ARM. Kod może zacząć działać nieprawidłowo po ponownym skompilowaniu go z użyciem nowszego kompilatora.

W dalszej części tego dokumentu znajdziesz wyjaśnienie, dlaczego tak jest, oraz informacje o tym, co zrobić, by Twój kod działał prawidłowo.

Modele spójności pamięci: dlaczego SMP różnią się od siebie

To krótkie, zwięzłe omówienie złożonego tematu. Niektóre obszary będą niekompletne, ale żadne z nich nie mogą wprowadzać w błąd ani wprowadzać w błąd. Jak dowiesz się w następnej sekcji, te szczegóły zwykle nie mają znaczenia.

W sekcji Więcej informacji na końcu dokumentu znajdziesz wskazówki do bardziej szczegółowego omówienia tematu.

Modele spójności pamięci (często po prostu „modele pamięci”) opisują gwarancje, jakie zapewnia język programowania lub architektura sprzętowa na dostęp do pamięci. Jeśli na przykład wpiszesz wartość adresowaną na adres A, a potem wartość dla adresu B, model może zagwarantować, że każdy rdzeń procesora będzie widzieć zapisy w tej kolejności.

Większość programistów jest przyzwyczajona do spójności sekwencyjnej, która jest opisana w ten sposób (Adve i Gharachorloo):

• Wygląda na to, że wszystkie operacje pamięci są wykonywane pojedynczo
• Wszystkie operacje w jednym wątku są wykonywane w kolejności określonej przez program tego procesora.

Załóżmy, że mamy bardzo prosty kompilator lub interpreter, który nie wprowadza niespodzianek – tłumaczy przypisania w kodzie źródłowym w taki sposób, aby ładować i zapisywać instrukcje w odpowiedniej kolejności – po jednej instrukcji na dostęp. Dla uproszczenia założymy, że każdy wątek jest uruchamiany we własnym procesorze.

Jeśli spojrzysz na fragment kodu i zobaczysz, że wykonuje on odczyty i zapisy z pamięci, w spójnej architekturze procesora wiadomo, że kod będzie odczytywał i zapisywał te odczyty i zapisy w oczekiwanej kolejności. Możliwe, że procesor w rzeczywistości zmienia kolejność instrukcji i opóźnia odczyty i zapisy, ale nie ma sposobu, aby kod działający na urządzeniu stwierdził, że zajmuje się nim coś innego niż wykonywanie instrukcji w prosty sposób. (Zignorujemy wejścia/wyjścia sterownika urządzenia mapowanego na pamięć).

Aby to wyjaśnić, warto rozważyć niewielkie fragmenty kodu, powszechnie nazywane testami lakmusowymi.

Oto prosty przykład, w którym kod jest uruchomiony w 2 wątkach:

Wątek 1	Wątek 2
A = 3 B = 5	reg0 = B reg1 = A

W tym i wszystkich przyszłych przykładach lakmus lokalizacje pamięci są reprezentowane przez wielkie litery (A, B, C), a rejestry procesora zaczynają się od „reg”. Cała pamięć jest początkowo równa zero. Instrukcje są wykonywane od góry do dołu. Wątek 1 przechowuje wartość 3 w lokalizacji A, a potem wartość 5 w lokalizacji B. Wątek 2 wczytuje wartość z lokalizacji B do funkcji reg0, a następnie wczytuje wartość z lokalizacji A do reguły 1. (pamiętaj, że piszemy w jednej kolejności, a czytamy w innej).

Przyjmuje się, że wątek 1 i wątek 2 są uruchamiane w różnych rdzeniach procesora. Zawsze należy przy tym zakładać takie założenia, jeśli chodzi o kod wielowątkowy.

Spójność sekwencyjna gwarantuje, że po zakończeniu wykonywania obu wątków rejestry pojawią się w jednym z tych stanów:

Zarejestruj się	Stany
reg0=5, reg1=3	możliwe (wątek 1 został uruchomiony jako pierwszy)
reg0=0, reg1=0	możliwe (wątek 2 został uruchomiony jako pierwszy)
reg0=0, reg1=3	możliwe (jednoczesne wykonywanie)
reg0=5, reg1=0	nigdy

Aby dojść do sytuacji, w której mamy do czynienia z wartością B=5, zanim sklep zostanie przypisany do A, odczyty lub zapisy musiałyby się odbywać w niewłaściwej kolejności. Na maszynie o spójności sekwencyjnej byłoby to niemożliwe.

Procesory jednostkowe, w tym x86 i ARM, są zwykle spójne sekwencyjnie. Wątki są wykonywane w przeplatany sposób, ponieważ jądro systemu operacyjnego przełącza się między nimi. Większość systemów SMP, w tym x86 i ARM, nie jest spójna sekwencyjnie. Na przykład sprzęt często buforuje zapisane w trakcie pamięci urządzenia, aby nie docierały od razu do pamięci i nie były widoczne dla innych rdzeni.

Szczegóły te mogą się znacznie różnić. Na przykład x86, choć nie spójnie sekwencyjnie, nadal gwarantuje, że reg0 = 5, a reg1 = 0, pozostanie niemożliwy. Sklepy są buforowane, ale ich kolejność jest zachowana. ARM natomiast nie. Kolejność buforowanych magazynów nie jest obsługiwana i magazyny mogą nie docierać do wszystkich innych rdzeni w tym samym czasie. Różnice te są ważne dla programistów montażowych. Jednak, jak widać poniżej, programiści C, C++ i Java mogą i powinni programować w sposób, który ukrywa takie różnice architektoniczne.

Do tej pory nierealistycznie przyjmowaliśmy, że tylko sprzęt zmienia kolejność instrukcji. W rzeczywistości kompilator również porządkuje instrukcje, aby zwiększyć wydajność. W naszym przykładzie kompilator może uznać, że jakiś późniejszy kod w wątku 2 wymagał wartości reg1, zanim potrzebował reg0, więc najpierw załadował reg1. Możliwe też, że jakiś wcześniejszy kod już załadował A. kompilator może użyć tej wartości zamiast ponownie ładować A. W obu przypadkach trzeba zmienić kolejność wczytywania reg0 i reg1.

Zmiana kolejności dostępu do różnych lokalizacji pamięci, zarówno w sprzęcie, jak i w kompilatorze, jest dozwolona, ponieważ nie wpływa na wykonanie pojedynczego wątku i może znacznie zwiększyć wydajność. Jak zobaczymy, z pewną ostrożnością możemy też zapobiec wpływaniu na wyniki programów wielowątkowych.

Ponieważ kompilatory też mogą zmieniać kolejność dostępu do pamięci, ten problem nie jest niczym nowym dla SMP. Nawet w przypadku jednoprocesora kompilator może w naszym przykładzie uporządkować ładunki na reg0 i reg1, a wątek 1 można zaplanować między instrukcją uporządkowaną ponownie. Jeśli jednak kompilator nie zmieni kolejności, możemy nigdy nie zauważyć tego problemu. W przypadku większości SMP ARM, nawet bez zmiany kolejności kompilatora, zmiana kolejności zostanie prawdopodobnie zauważona, prawdopodobnie po bardzo dużej liczbie udanych wykonań. O ile nie tworzysz programowania w języku asemblerajskim, SMP zazwyczaj częściej napotkają problemy, które zawsze występują.

Programowanie wolne od wyścigu danych

Na szczęście istnieje zwykle prosty sposób, aby uniknąć zastanowienia się nad tymi szczegółami. Jeśli przestrzegasz pewnych prostych zasad, zwykle możesz bezpiecznie zapomnieć całą poprzednią sekcję z wyjątkiem części dotyczącej „spójności sekwencyjnej”. Jeśli przypadkowo naruszysz te reguły, mogą pojawić się też inne komplikacje.

Współczesne języki programowania są oparte na stylu programowania „wolnym od wyścigu danych”. O ile obiecujesz nie wprowadzać „ras danych” i unikać kilku konstrukcji, które informują kompilator, że jest inaczej, kompilator i sprzęt obiecują sekwencyjnie spójne wyniki. Nie oznacza to jednak, że unikają zmiany kolejności dostępu do pamięci. Oznacza to, że jeśli ich przestrzegać, nie dowiesz się, że dostęp do pamięci jest zmieniany. To jak mówienie, że kiełbasa to pyszne i atrakcyjny jedzenie, o ile obiecujesz nie wchodzić do fabryki kiełbasek. Rasy danych ujawniają brzydką prawdę o zmienianiu kolejności pamięci.

Co to jest „wyścig danych”?

Wyścig danych ma miejsce, gdy co najmniej 2 wątki jednocześnie uzyskują dostęp do tych samych zwykłych danych i co najmniej 1 z nich je modyfikuje. Przez „zwykłe dane” rozumiemy coś, co nie jest obiektem synchronizacji przeznaczonym do komunikacji w wątkach. Mechanizmy muteks, zmienne warunku, zmienne Java i obiekty atomowe w języku C++ nie są zwykłymi danymi, a ich dostępy mogą ścigać się. Są one też używane do zapobiegania ścieżkom danych w przypadku innych obiektów.

Aby określić, czy 2 wątki jednocześnie mają dostęp do tej samej lokalizacji pamięci, możemy zignorować omówioną powyżej dyskusję o zmianie kolejności pamięci i założyć sekwencyjną spójność. W tym programie nie ma wyścigu danych, jeśli A i B są zwykłymi zmiennymi logicznymi, które na początku mają wartość fałsz:

Wątek 1	Wątek 2
if (A) B = true	if (B) A = true

Kolejność operacji nie jest zmieniana, więc oba warunki będą miały wartość fałsz i żadna zmienna nie zostanie nigdy zaktualizowana. W związku z tym nie ma wyścigu danych. Nie trzeba zastanawiać się, co się stanie, jeśli kolejność wczytywania elementów z A i zapisanych do B w wątku 1 zostanie w jakiś sposób. Kompilator nie może zmienić kolejności wątku Thread1 przez jego przepisanie jako „B = true; if (!A) B = false”. To byłoby jak zrobienie kiełbasy w środku miasta w świetle dziennym.

Wyścigi danych są oficjalnie zdefiniowane na podstawie podstawowych typów wbudowanych, takich jak liczby całkowite, odwołania lub wskaźniki. Przypisanie do elementu int podczas jednoczesnego czytania go w innym wątku to niewątpliwie wyścig danych. Jednak zarówno standardowe biblioteki C++, jak i biblioteki zbiorów Java, są napisane tak, aby można było wnioskować o rasy danych na poziomie biblioteki. Obiecują, że nie będą wprowadzać biegów danych, chyba że do tego samego kontenera będą mieć równocześnie dostępy, a co najmniej jeden z nich go aktualizuje. Zaktualizowanie obiektu set<T> w jednym wątku i jednoczesne czytanie go w innym pozwala bibliotece rozpocząć wyścig danych, więc nieformalnie można uznać je za „wyścig danych na poziomie biblioteki”. I odwrotnie – zaktualizowanie jednego elementu set<T> w jednym wątku i odczytanie innego obiektu w innym nie powoduje wyścigu danych, ponieważ w takim przypadku biblioteka nie zamierza wprowadzać wyścigu danych (niskiego poziomu).

Normalne jednoczesne korzystanie z różnych pól w strukturze danych nie jest w stanie wprowadzić rasy danych. Od tej reguły istnieje jednak ważny wyjątek: sąsiadujące sekwencje pól bitowych w językach C lub C++ są traktowane jako pojedyncza „lokalizacja pamięci”. Dostęp do dowolnego pola bitowego w takiej sekwencji jest traktowany jako dostęp do wszystkich z nich na potrzeby określania istnienia wyścigu danych. Odzwierciedla to brak możliwości aktualizowania przez typowe elementy poszczególnych bitów bez odczytania i przepisania sąsiedniego fragmentu. Programiści w Javie nie mają analogicznych obaw.

Unikanie ras danych

Współczesne języki programowania oferują szereg mechanizmów synchronizacji, które pozwalają uniknąć wyścigów danych. Najbardziej podstawowe narzędzia:

Zamki i mechanizmy wyciszające

Wyciszenia (C++11 std::mutex, pthread_mutex_t) lub synchronized bloki w języku Java można wykorzystać, aby uniemożliwić działanie określonej sekcji kodu jednocześnie z innymi sekcjami kodu uzyskującymi dostęp do tych samych danych. Takie i podobne obiekty określamy ogólnie jako „zamki”. Konsekwentne uzyskiwanie określonej blokady przed uzyskaniem dostępu do udostępnionej struktury danych i późniejszym jej zwolnieniem zapobiega wyścigom danych podczas uzyskiwania dostępu do struktury danych. Zapewnia to też niepodzielne aktualizacje i dostęp do nich, tj. żadna inna aktualizacja struktury danych nie może być przeprowadzana w środku. Jest to zdecydowanie najpopularniejsze narzędzie do zapobiegania rasom danych. Użycie bloków języka Java synchronized lub C++ lock_guard lub unique_lock zapewnia prawidłowe zwalnianie blokad w przypadku wystąpienia wyjątku.

Zmienne ulotne/atomowe

W języku Java dostępne są pola volatile, które obsługują dostęp równoczesny bez wprowadzania ras danych. Od 2011 r. języki C i C++ obsługują zmienne i pola atomic o podobnej semantyce. Są one zwykle trudniejsze w użyciu niż blokady, ponieważ zapewniają jedynie atomowy dostęp do jednej zmiennej. W C++ zwykle obejmuje to proste operacje odczytu, modyfikacji i zapisu, takie jak przyrosty. Java wymaga specjalnych wywołań metody). W przeciwieństwie do blokad zmiennych volatile i atomic nie można używać bezpośrednio, aby zapobiegać ingerencji innych wątków w dłuższe sekwencje kodu.

Pamiętaj, że volatile ma bardzo różne znaczenie w C++ i Javie. W C++ volatile nie blokuje wyścigów danych, choć starszy kod często używa go jako obejścia braku obiektów atomic. Nie jest to już zalecane. W C++ używaj zmiennej atomic<T> w przypadku zmiennych, do których jednocześnie ma dostęp wiele wątków. C++ volatile służy do rejestracji urządzeń i tym podobnych.

Zmienne atomic C/C++ lub Java volatile można wykorzystać, aby zapobiegać rasie danych w przypadku innych zmiennych. Jeśli zadeklarowano, że typ flag ma typ atomic<bool>, atomic_bool(C/C++) lub volatile boolean (Java), i początkowo ma wartość fałsz, ten fragment nie zawiera danych wyścigowych:

Wątek 1	Wątek 2
A = ...   flag = true	while (!flag) {} ... = A

Wątek 2 czeka na ustawienie ustawienia flag, więc dostęp do usługi A w wątku 2 musi nastąpić po przypisaniu użytkownika A w wątku 1, a nie równocześnie. W związku z tym w A nie ma wyścigu danych. Wyścig w flag nie jest liczony jako wyścig danych, ponieważ dostęp niestabilny/atomowy nie jest „zwykłym dostępem do pamięci”.

Implementacja jest wymagana, by zapobiegać lub ukrywać takiej kolejności pamięci, by kod podobny do poprzedniego testu lakmusowego działał zgodnie z oczekiwaniami. Zwykle dostęp do pamięci ulotnej/atomowej jest znacznie droższy niż dostęp standardowy.

Poprzedni przykład nie uwzględnia wyścigu danych, ale blokuje się razem z Object.wait() w języku Java lub ze zmiennymi warunku w C/C++. Zazwyczaj lepiej radzi sobie z tym, że nie trzeba czekać w pętli podczas rozładowywania baterii.

Kiedy zmiana kolejności pamięci staje się widoczna

Programowanie wolne od wyścigów danych zwykle pozwala nam uniknąć konieczności rozwiązywania problemów ze zmianą kolejności pamięci. Jest jednak kilka przypadków, w których zmiana kolejności jest widoczna:

1. Jeśli w Twoim programie występuje błąd, który powoduje niezamierzony wyścig danych, transformacje kompilatora i sprzętu mogą być widoczne, a jego działanie może dziwić. Jeśli na przykład w poprzednim przykładzie zapomnieliśmy zadeklarować zmienną flag, w wątku 2 może pojawić się niezainicjowany parametr A. Kompilator może też uznać, że flaga nie może się zmienić podczas pętli Thread 2 i przekształcić program na

   Wątek 1	Wątek 2
   A = ...   flag = true	reg0 = flag; podczas (!reg0) {} ... = A

   Podczas debugowania pętla może trwać nieprzerwanie, mimo że flag ma wartość prawda.
2. C++ zapewnia udogodnienia, które pozwalają w sposób wyraźny sprzyjać spójności sekwencyjnej, nawet jeśli nie ma rasy. Operacje atomowe mogą przyjmować jawne argumenty memory_order_.... I podobnie, pakiet java.util.concurrent.atomic obejmuje bardziej ograniczony zestaw podobnych obiektów, w szczególności lazySet(). Z kolei programiści w Javie czasami wykorzystują celowe biegi danych, aby uzyskać podobny efekt. Wszystkie one zapewniają wzrost wydajności przy dużych kosztach złożoności programowania. Omawiamy je tylko krótko poniżej.
3. Część kodów w językach C i C++ jest napisana w starszym stylu, co nie jest całkowicie zgodne z obecnymi standardami językowymi, w których zamiast zmiennych volatile są używane zmienne volatile, a kolejność pamięci jest wyraźnie zabroniona przez wstawianie tak zwanych granic lub barier.atomic Wymaga to jednoznacznego uzasadnienia w zakresie zmiany kolejności dostępu i interpretacji sprzętowych modeli pamięci. Styl programowania uwzględniający te wiersze jest wciąż używany w jądrorze Linuksa. Nie należy go używać w nowych aplikacjach na Androida. Nie zostało też szczegółowo omówione.

Ćwicz

Debugowanie problemów ze spójnością pamięci może być bardzo trudne. Jeśli brak blokady, deklaracja atomic lub volatile powoduje, że kod odczytuje nieaktualne dane, możesz nie być w stanie ustalić, dlaczego tak jest, analizując zrzuty pamięci za pomocą debugera. Zanim wyślesz zapytanie debugera, być może wszystkie rdzenie procesora zaobserwowały pełny zestaw dostępu, a zawartość pamięci i rejestry procesora będzie wyglądała na „niemożliwe”.

Czego nie robić w C

Podajemy kilka przykładów nieprawidłowego kodu wraz z prostymi sposobami ich naprawy. Zanim to zrobimy, musimy omówić szczegółowo, jak używać podstawowych funkcji językowych.

C/C++ i „lotny”

Deklaracje C i C++ volatile to specjalne narzędzie. Uniemożliwiają kompilatorowi zmianę kolejności i usuwanie dostępu volatile. Może to być przydatne w przypadku kodu uzyskującego dostęp do rejestrów urządzeń sprzętowych, pamięci zmapowanej na więcej niż 1 lokalizację lub w połączeniu z setjmp. Jednak C i C++ volatile, w przeciwieństwie do Javy volatile, nie są przeznaczone do komunikacji w wątkach.

W językach C i C++ kolejność dostępu do danych volatile może być zależna od danych nieulotnych – nie ma gwarancji atomu. Dlatego interfejsu volatile nie można używać do udostępniania danych między wątkami za pomocą kodu przenośnego, nawet w ramach jednoprocesora jednoprocesorowego. C volatile zwykle nie zapobiega zmianie kolejności dostępu przez sprzęt, więc sama w sobie jest jeszcze mniej przydatna w środowiskach wielowątkowych SMP. Z tego powodu C11 i C++11 obsługują obiekty atomic. Zamiast tego lepiej z nich korzystać.

Wiele starszych kodów w językach C i C++ nadal nadużywa volatile do komunikacji w wątkach. Często działa to prawidłowo w przypadku danych, które mieszczą się w rejestrze maszyny, o ile są używane z wyraźnymi granicami lub w przypadkach, gdy kolejność pamięci nie ma znaczenia. Nie ma jednak gwarancji, że będzie on poprawnie działać z przyszłymi kompilatorami.

Przykłady

W większości przypadków lepiej użyć blokady (np. pthread_mutex_t lub C++11 std::mutex), a nie operacji atomowej. Użyjemy jednak tej drugiej, żeby pokazać, jak można ją wykorzystać w praktycznej sytuacji.

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

Polega to na tym, że przydzielamy strukturę, inicjujemy jej pola, a na końcu ją „publikujemy”, zapisując w zmiennej globalnej. Od tego momentu jest on widoczny w każdym innym wątku, ale już jest w pełni zainicjowany.

Problem polega na tym, że przed zainicjowaniem pól można było zarejestrować magazyn na gGlobalThing. Zwykle dzieje się tak dlatego, że kompilator lub procesor zmienił kolejność magazynów na gGlobalThing i thing->x. Inny odczytywany wątek z thing->x może zobaczyć dane 5, 0, a nawet niezainicjowane dane.

Głównym problemem jest wyścig danych w gGlobalThing. Jeśli wątek 1 wywołuje initGlobalThing(), a wątek 2 wywołuje metodę useGlobalThing(), gGlobalThing może zostać odczytany podczas zapisywania.

Problem można rozwiązać, deklarując właściwość gGlobalThing jako atomową. W języku C++11:

atomic<MyThing*> gGlobalThing(NULL);

Dzięki temu zapisy będą widoczne dla innych wątków we właściwej kolejności. Gwarantuje też zapobieganie innym trybom awarii, które są dozwolone, ale raczej nie wystąpią na rzeczywistym sprzęcie z Androidem. Dzięki temu nie będziemy na przykład widzieć wskaźnika gGlobalThing, który został tylko częściowo napisany.

Czego nie należy robić w Javie

Nie omówiliśmy jeszcze niektórych funkcji języka Java, więc przyjrzymy się im najpierw.

Java z technicznego punktu widzenia nie wymaga, aby kod nie był śledzony w kontekście wyścigu danych. Jest też niewielka ilość bardzo starannie napisanego kodu w Javie, który działa poprawnie w przypadku wyścigów danych. Napisanie takiego kodu może się jednak okazać bardzo trudne, co omówimy tylko pokrótce. Aby pogorszyć sytuację, eksperci, którzy określili znaczenie takiego kodu, nie są już przekonani, że specyfikacja jest poprawna. (specyfikacja jest odpowiednia w przypadku kodu wolnego od wyścigów).

Na razie będziemy opierać się na modelu niezawierającym wyścigu danych, w przypadku którego Java zapewnia zasadniczo te same gwarancje co w językach C i C++. Również język zawiera elementy podstawowe, które wyraźnie ograniczają spójność sekwencyjną, zwłaszcza wywołania lazySet() i weakCompareAndSet() w komponencie java.util.concurrent.atomic. Na razie będziemy je zignorować, podobnie jak w przypadku języków C i C++.

„zsynchronizowane” i „ulotne” słowa kluczowe w Javie

Słowo kluczowe „zsynchronizowane” ma wbudowany mechanizm blokowania języka Java. Z każdym obiektem powiązany jest „monitor”, którego można używać do zapewniania wzajemnie wyłącznego dostępu. Jeśli dwa wątki będą próbowały zsynchronizować ten sam obiekt, jeden z nich będzie czekał na zakończenie działania drugiego.

Jak wspomnieliśmy, volatile T w Javie jest odpowiednikiem funkcji atomic<T> w języku C++11. Jednoczesne dostęp do pól volatile są dozwolone i nie powodują wyścigów danych. Ignorowanie lazySet() i in. oraz biegów danych to zadanie maszyny wirtualnej Java, aby wyniki były zawsze spójne.

W szczególności, jeśli wątek 1 zapisuje dane w polu volatile, a potem odczytuje to z tego samego pola i widzi nowo zapisaną wartość, w wątku 2 gwarantowane są również wszystkie zapisy dokonane wcześniej przez wątek 1. Jeśli chodzi o efekt pamięci, zapisywanie danych w wartościach zmiennych jest analogicznie do wersji monitora, a odczyt z takiego obiektu jest jak zapis na monitorze.

Jest jedna wyraźna różnica w stosunku do funkcji atomic w C++: jeśli zapiszemy volatile int x; w języku Java, to x++ będzie mieć taką samą wartość jak x = x + 1. Wykonuje ono obciążenie atomowe, zwiększa wynik, a następnie wykonuje magazyn atomowy. W przeciwieństwie do C++ przyrost wartości nie jest atomowy. Operacje przyrostu atomu są zamiast tego dostarczane przez java.util.concurrent.atomic.

Przykłady

Oto prosta, nieprawidłowa implementacja licznika monotonicznego: (Javatheory andPractice: Managing volatility).

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

Przyjmijmy, że funkcje get() i incr() są wywoływane z wielu wątków. Chcemy mieć pewność, że każdy wątek widzi bieżącą liczbę po wywołaniu funkcji get(). Najbardziej jasny problem polega na tym, że mValue++ to w rzeczywistości 3 operacje:

1. reg = mValue
2. reg = reg + 1
3. mValue = reg

Jeśli w incr() jednocześnie są uruchamiane 2 wątki, jedna z aktualizacji może zostać utracona. Aby przyrost ma charakter atomowy, musisz zadeklarować zdarzenie incr() „zsynchronizowane”.

Jest wciąż uszkodzony, zwłaszcza w przypadku SMP. Nadal trwa bieg danych, w którym get() ma dostęp do usługi mValue równocześnie z usługą incr(). W regułach Javy może się wydawać, że wywołanie get() ma zmieniać kolejność względem innego kodu. Jeśli np. odczytamy 2 liczniki z rzędu, wyniki mogą wydawać się niespójne, ponieważ zmieniliśmy kolejność wywołań get() przez sprzęt lub kompilator. Możemy rozwiązać ten problem, deklarując synchronizację get(). Po tej zmianie kod jest oczywiście poprawny.

Wprowadziliśmy jednak możliwość rywalizacji o blokadę, co może obniżyć skuteczność. Zamiast deklarować, że funkcja get() jest synchronizowana, możemy zadeklarować właściwość mValue z wartością „ulotne”. Uwaga: incr() musi nadal używać parametru synchronize, ponieważ mValue++ w przeciwnym razie nie jest jednoznaczną operacją niepodzielną. Pozwala to także uniknąć wszystkich wyścigów danych, co pozwala zachować spójność sekwencyjną. Działanie incr() będzie nieco wolniejsze, ponieważ wiąże się z narzutem wejścia i wyjścia z monitorowania oraz z narzutem związanym z magazynem ulotnym, ale get() działa szybciej, więc nawet w przypadku braku rywalizacji będzie to wygrana w przypadku, gdy odczyt będzie znacznie wyższy niż liczba zapisów. (Aby całkowicie usunąć zsynchronizowany blok, zapoznaj się z sekcją AtomicInteger).

Oto kolejny przykład podobny do wcześniejszych przykładów C:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

Ten sam problem co w kodzie C oznacza, że w sGoodies występuje wyścig danych. Z tego względu przypisanie sGoodies = goods może zostać zaobserwowane przed zainicjowaniem pól w goods. Jeśli zadeklarujesz element sGoodies ze słowem kluczowym volatile, zostanie przywrócona spójność sekwencyjna i działanie będzie działać zgodnie z oczekiwaniami.

Pamiętaj, że tylko odwołanie do sGoodies jest zmienne. Dostęp do znajdujących się w nim pól nie jest możliwy. Jeśli sGoodies ma wartość volatile i porządkowanie pamięci jest odpowiednio zachowane, nie będzie można równocześnie korzystać z tych pól. Instrukcja z = sGoodies.x wykonuje ładowanie zmienne o wartości MyClass.sGoodies, po którym następuje obciążenie nieulotne o wartości sGoodies.x. Jeśli utworzysz odwołanie lokalne MyGoodies localGoods = sGoodies, kolejne z = localGoods.x nie będą wczytywać żadnych zmiennych.

Częściej stosowanym idiomem w programowaniu w języku Java jest słynne „podwójnie sprawdzone blokowanie”:

class MyClass {
    private Helper helper = null;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

Chodzi o to, że chcemy mieć pojedyncze wystąpienie obiektu Helper powiązanego z wystąpieniem MyClass. Musimy go utworzyć tylko raz, więc tworzymy i zwracamy go za pomocą dedykowanej funkcji getHelper(). Aby uniknąć wyścigu, w którym instancja jest tworzona przez 2 wątki, musimy zsynchronizować proces tworzenia obiektu. Nie chcemy jednak płacić za blok z synchronizacją przy każdym wywołaniu, więc robimy to tylko wtedy, gdy helper ma obecnie wartość null.

Oto wyścig danych na polu helper. Można go ustawić równolegle z elementem helper == null w innym wątku.

Jeśli chcesz się dowiedzieć, dlaczego tak się nie dzieje, spróbuj napisać ten sam kod nieco przeredagowany, jak gdyby był skompilowany do języka podobnego do języka C. Dodałem kilka pól liczb całkowitych, które reprezentują działanie konstruktora Helper’s:

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

Nic nie stoi na przeszkodzie, aby sprzęt lub kompilator mógł zmienić kolejność magazynu na helper z użyciem pól x/y. Inny wątek może znaleźć wartość helper bez wartości null, ale jej pola nie są jeszcze ustawione i gotowe do użycia. Więcej informacji i więcej informacji o trybach awarii znajdziesz w dodatku w załączniku do deklaracji „Double Checking Locking is Broken” (Podwójna weryfikacja jest zepsuta). Więcej szczegółów znajdziesz w artykule 71 (Rozsądnie używaj leniwego inicjowania) w publikacji Effective Java, 2nd Edition Josha Blocha.

Problem ten można rozwiązać na dwa sposoby:

1. Wykonaj prostą czynność i usuń zewnętrzny czek. Dzięki temu nigdy nie sprawdzamy wartości helper poza blokiem zsynchronizowanym.
2. Deklarowanie zmienności parametru helper. Dzięki tej niewielkiej zmianie kod z przykładu J-3 będzie działać prawidłowo w Javie 1.5 i nowszych. (Poświęć chwilę, aby przekonać się, że to prawda).

Oto jeszcze jedna ilustracja funkcji volatile:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

Patrzymy na useValues(). Jeśli wątek 2 nie zaobserwował jeszcze aktualizacji do vol1, nie wie, czy ustawiono już data1 lub data2. Po aktualizacji vol1 wie, że data1 może być bezpiecznie otwierany i poprawnie odczytywany bez wprowadzania wyścigu danych. Nie można jednak wyciągać żadnych założeń dotyczących obiektu data2, ponieważ ten magazyn został wykonany po magazynie zmiennych.

Pamiętaj, że volatile nie może służyć do zapobiegania zmianie kolejności innych rywalizujących ze sobą dostępu do pamięci. Nie gwarantujemy, że wygenerowanie instrukcji ochrony pamięci dla maszyny. Można go używać do zapobiegania wyścigom danych przez wykonywanie kodu tylko wtedy, gdy inny wątek spełni określony warunek.

Co możesz zrobić

W języku C/C++ preferuj klasy synchronizacji C++11, takie jak std::mutex. Jeśli nie, użyj odpowiednich operacji pthread. Są to między innymi odpowiednie granice pamięci, poprawne (spójne sekwencyjnie, o ile nie określono inaczej) i wydajne działanie we wszystkich wersjach platformy Androida. Stosujcie je właściwie. Na przykład pamiętaj, że czas oczekiwania zmiennej warunku może nieumyślnie występować bez sygnału i powinny występować w pętli.

Najlepiej unikać bezpośredniego używania funkcji niepodzielnych, chyba że implementowana struktura danych jest bardzo prosta, np. licznik. Blokowanie i odblokowywanie muteksu pthread Projektowanie pozbawionych blokad w przypadku nieprostych struktur danych wymaga dużo większej uwagi, aby operacje wyższego poziomu na strukturze danych były atomowe (jako całość, a nie tylko ich jawnie atomowe elementy).

Jeśli stosujesz operacje atomowe, łagodne porządkowanie za pomocą funkcji memory_order... lub lazySet() może zwiększyć wydajność, ale wymaga dokładniejszego zrozumienia, niż przekazaliśmy do tej pory. Okazuje się, że znaczna część istniejącego kodu zawiera błędy. W miarę możliwości unikaj ich. Jeśli Twój przypadek użycia nie pasuje dokładnie do żadnego z opisów podanych w następnej sekcji, upewnij się, że jesteś ekspertem lub konsultujesz się z jego pracownikiem.

Unikaj używania volatile do komunikacji w wątkach w języku C/C++.

W Javie problemy z równoczesnością często najlepiej rozwiązać przy użyciu odpowiedniej klasy użytej z pakietu java.util.concurrent. Kod jest dobrze napisany i dokładnie przetestowany na SMP.

Chyba najbezpieczniejsze, co możesz zrobić, to uczynić obiekty stałe. Obiekty z klas, takich jak Java String i Integer, przechowują dane, których po utworzeniu obiektu nie można zmienić. Pozwala to uniknąć wyścigu danych w tych obiektach. Szczegółowe instrukcje znajdują się w książce Effective Java, 2nd. (Element 15: minimalizacja zmienności). Zwróć szczególną uwagę na to, jak ważne jest zadeklarowanie pól Java „final” (Bloch).

Nawet jeśli obiektu nie można zmienić, pamiętaj, że przekazanie go do innego wątku bez żadnej synchronizacji to wyścig danych. Czasami może to być akceptowalne w języku Java (zobacz poniżej), ale wymaga dużej ostrożności i może doprowadzić do uszkodzenia kodu. Jeśli nie jest ona szczególnie ważna dla wydajności, dodaj deklarację volatile. W C++ przekazywanie wskaźnika lub odniesienia do obiektu stałego bez odpowiedniej synchronizacji, jak w przypadku każdego wyścigu danych, jest błędem. W takim przypadku prawdopodobne jest, że sporadycznie doprowadzą do awarii, ponieważ z powodu zmiany kolejności sklepów w wątku odbierania może na przykład zobaczyć niezainicjowany wskaźnik tabeli metod.

Jeśli nie jest odpowiednia istniejąca klasa biblioteki ani klasa stała, użyj instrukcji Java synchronized lub kodu C++ lock_guard / unique_lock do ochrony dostępu do pól, do których dostęp ma więcej niż 1 wątek. Jeśli w Twojej sytuacji mechanizmy ignorowania nie sprawdzają się, zadeklaruj udostępnione pola volatile lub atomic, ale ze szczególnym uwzględnieniem interakcji między wątkami. Te deklaracje nie uchronią Cię przed typowymi równoczesnymi błędami programowania, ale pomogą Ci uniknąć tajemniczych błędów związanych z optymalizacją kompilatorów i błędami SMP.

Należy unikać „publikowania” odwołania do obiektu, tj. udostępniania go innym wątkom za pomocą jego konstruktora. Jest to mniej istotne w języku C++ lub jeśli przestrzegasz naszych porad dotyczących „braku wyścigów danych” w języku Java. Jest to jednak zawsze dobra rada, a także ma kluczowe znaczenie, jeśli kod Java jest uruchamiany w innych kontekstach, w których ma znaczenie model zabezpieczeń Java. Niezaufany kod może wywołać wyścig danych przez uzyskanie dostępu do „wycieku” odniesienia do obiektu. Bardzo ważne jest też, jeśli zdecydujesz się zignorować nasze ostrzeżenia i skorzystać z technik opisanych w następnej sekcji. Więcej informacji znajdziesz w sekcji (Safe Building Techniques in Java).

Więcej informacji o słabych zamówieniach pamięci

Kod C++11 i późniejsze zapewniają jawne mechanizmy łagodzenia sekwencyjnych gwarancji spójności w przypadku programów pozbawionych rasy danych. Jawne argumenty memory_order_relaxed, memory_order_acquire (tylko ładowanie) i memory_order_release(tylko magazyn) dla operacji atomowych zapewniają ściśle słabsze gwarancje niż domyślne, zwykle niejawne memory_order_seq_cst. memory_order_acq_rel zapewnia zarówno memory_order_acquire, jak i memory_order_release gwarancje na atomowe operacje odczytu i modyfikacji zapisu. Parametr memory_order_consume nie jest jeszcze wystarczająco dobrze określony lub zaimplementowany, aby był przydatny, i na razie należy go zignorować.

Metody lazySet w Java.util.concurrent.atomic są podobne do metod C++ memory_order_release. Zwykłe zmienne Javy są czasem używane jako zamienniki dostępu memory_order_relaxed, choć w rzeczywistości są jeszcze słabsze. W przeciwieństwie do C++ nie ma rzeczywistego mechanizmu nieuporządkowanego dostępu do zmiennych zadeklarowanych jako volatile.

Należy ich unikać, chyba że istnieją ważne powody związane z wydajnością. W przypadku słabo uporządkowanych architektur maszyn, takich jak ARM, ich zastosowanie pozwala zwykle zaoszczędzić kilkadziesiąt cykli maszynowych na każdą operację atomową. W przypadku procesorów x86 wygrana w wynikach jest ograniczona do sklepów i prawdopodobnie będzie mniej zauważalna. Wbrew pozorom korzyści mogą się zmniejszyć przy większej liczbie rdzeni, ponieważ system pamięci staje się czynnikiem ograniczającym.

Pełna semantyka słabo uporządkowanych atomów jest skomplikowana. Ogólnie rzecz biorąc, wymagają one dokładnego zrozumienia reguł językowych, których nie będziemy tu omawiać. Na przykład:

• Kompilator lub sprzęt może przenieść dostęp memory_order_relaxed do sekcji krytycznej (ale nie poza nią) objętej pozyskiwaniem i udostępnianiem blokady. Oznacza to, że 2 sklepy memory_order_relaxed mogą być widoczne w złej kolejności, nawet jeśli są rozdzielone sekcję krytyczną.
• Zwykła zmienna Java, której używa się jako wspólny licznik, może się zmniejszyć w innym wątku, mimo że jej wartość jest zwiększana o jeden inny wątek. Nie dotyczy to jednak kodu C++ atomowego memory_order_relaxed.

W ramach ostrzeżenia podajemy niewielką liczbę idiomów, które zdają się obejmować wiele zastosowań słabo uporządkowanych atomów. Wiele z nich ma zastosowanie tylko w C++.

Dostęp inny niż wyścig

Zmienna ma dosyć często charakter niepodzielny, ponieważ czasami jest odczytywana równocześnie z zapisem, jednak ten problem nie występuje we wszystkich dostępach. Na przykład zmienna może być niepodzielna, ponieważ jest odczytywana poza sekcją krytyczną, ale wszystkie aktualizacje są chronione blokadą. W takim przypadku odczyt, który jest chroniony przez tę samą blokadę, nie może być śledzony, ponieważ nie ma możliwości równoczesnych zapisów. W takim przypadku do dostępu niezwiązanego z wyścigami (w tym przypadku ładowanie) można dodać adnotację memory_order_relaxed bez zmiany poprawności kodu w C++. Implementacja blokady wymusza już wymaganą kolejność pamięci w odniesieniu do dostępu przez inne wątki, a memory_order_relaxed określa w zasadzie, że w przypadku dostępu niepodzielnego nie trzeba egzekwować żadnych dodatkowych ograniczeń dotyczących kolejności.

Nie ma do tego podobnego odpowiednika w Javie.

Wynik nie jest zależny od poprawności wyniku

Jeśli w przypadku obciążenia wyścigowego używamy tylko do wygenerowania podpowiedzi, zazwyczaj można też nie wymuszać kolejności pamięci dla tego obciążenia. Jeśli wartość nie jest wiarygodna, nie możemy też na podstawie wyniku wyciągnąć żadnych wniosków o innych zmiennych. Jeśli więc kolejność pamięci nie jest gwarantowana, nie ma nic złego w tym, że obciążenie jest dostarczane za pomocą argumentu memory_order_relaxed.

Typowym przykładem jest użycie C++ compare_exchange do atomowego zastąpienia x przez f(x). Początkowe obciążenie x przy obliczaniu danych f(x) nie musi być niezawodne. Jeśli się pomylimy, compare_exchange się nie powiedzie i spróbujemy ponownie. Przy wstępnym wczytywaniu elementu x może być używany argument memory_order_relaxed. W przypadku rzeczywistych wartości compare_exchange ma znaczenie tylko kolejność w pamięci.

Dane zmodyfikowane atomowo, ale nieprzeczytane

Czasami dane są modyfikowane równolegle przez wiele wątków, ale nie są badane do momentu zakończenia obliczania równoległego. Dobrym przykładem jest licznik, którego wartość zwiększa się atomowo (np. stosując fetch_add() w języku C++ lub atomic_fetch_add_explicit() w języku C) w wielu wątkach równolegle, ale wynik tych wywołań jest zawsze ignorowany. Wynikowa wartość jest odczytywana tylko na końcu, po zakończeniu aktualizacji.

W takim przypadku nie można stwierdzić, czy została zmieniona kolejność dostępu do danych, więc kod C++ może korzystać z argumentu memory_order_relaxed.

Często są to proste liczniki zdarzeń. Jest to dość powszechne, dlatego warto zwrócić na ten temat kilka uwag:

• Korzystanie z protokołu memory_order_relaxed poprawia wydajność, ale może nie rozwiązać najważniejszego problemu z wydajnością. Każda aktualizacja wymaga wyłącznego dostępu do wiersza pamięci podręcznej, w którym znajduje się licznik. Powoduje to braki w pamięci podręcznej za każdym razem, gdy nowy wątek uzyskuje dostęp do licznika. Jeśli aktualizacje są częste i naprzemienne w poszczególnych wątkach, znacznie szybciej można uniknąć aktualizacji wspólnego licznika za każdym razem, używając na przykład liczników lokalnych wątków i sumując je na końcu.
• Tę metodę można łączyć z poprzednią sekcją: podczas aktualizowania można odczytywać wartości przybliżone i nierzetelne jednocześnie ze wszystkimi operacjami korzystającymi z metody memory_order_relaxed. Ważne jest jednak, aby traktować wynikowe wartości jako całkowicie niewiarygodne. Gdy wydaje się, że liczba wzrosła jeden raz, nie oznacza to, że kolejny wątek osiągnie punkt, w którym został przeprowadzony. Przyrost mógł zostać zmieniony na wcześniejszy kod. Podobnie jak w podobnym przypadku, o czym wspomnieliśmy wcześniej, C++ gwarantuje, że drugie wczytanie takiego licznika nie zwróci wartości niższej niż wcześniejsze wczytanie w tym samym wątku. Oczywiście o ile nie przepełnił się licznik).
• Często zdarza się, że kod próbuje obliczać przybliżone wartości licznika, wykonując poszczególne atomowe (lub nie) odczyty i zapisy, ale nie wykonuje tego przyrostu jako całości atomowej. Zwykle jest to „wystarczająco blisko” w przypadku liczników skuteczności itp. Zwykle nie jest. Jeśli aktualizacje są wystarczająco częste (takie, które prawdopodobnie Cię interesują), zwykle duża część danych jest tracona. W przypadku urządzeń czterordzeniowych ponad połowa tych wartości może często zostać utracona. Łatwe ćwiczenie: stwórz scenariusz z 2 wątkami, w którym licznik jest aktualizowany milion razy, ale końcowa wartość licznika to 1.

Prosta komunikacja dotycząca flag

Magazyn memory_order_release (lub operacja odczytu, modyfikacji i zapisu) zapewnia, że jeśli następnie wczytanie memory_order_acquire (lub operacja odczytu, modyfikacji i zapisu) odczyta wartość zapisaną, będzie także obserwować wszystkie zapisy (zwykłe lub atomowe) poprzedzające magazyn A memory_order_release. I odwrotnie, żadne operacje wczytywania poprzedzające typ memory_order_release nie będą śledzić żadnych sklepów, które nastąpiły po wczytaniu memory_order_acquire. W przeciwieństwie do memory_order_relaxed pozwala to na przekazywanie informacji o postępach przechodzenia między wątkami.

Na przykład możemy przepisać powyższy przykład blokady w C++ jako

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

Magazyn obciążenia i wersji gwarantuje, że jeśli znajdziemy wartość helper o wartości innej niż null, jej pola również zostaną prawidłowo zainicjowane. Uwzględniliśmy też wcześniejszą obserwację, że w przypadku ładunków innych niż wyścigowe ładunki mogą używać parametru memory_order_relaxed.

Programista w języku Java może przedstawiać helper jako java.util.concurrent.atomic.AtomicReference<Helper> i używać lazySet() jako magazynu wersji. Operacje wczytywania nadal będą używać zwykłych wywołań get().

W obu przypadkach zmiany wydajności koncentrowały się na ścieżce inicjowania, co raczej nie ma kluczowego znaczenia dla wydajności. Bardziej zrozumiałym przejęciem może być:

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

Zapewnia to tę samą szybką ścieżkę, ale korzysta się z domyślnych, spójnych sekwencyjnie operacji na powolnej ścieżce, która nie ma kluczowego znaczenia dla wydajności.

Nawet w tym przypadku helper.load(memory_order_acquire) prawdopodobnie wygeneruje ten sam kod w ramach obecnych architektur obsługiwanych przez Androida jako zwykłe (sekwencyjne) odwołanie do elementu helper. Naprawdę najkorzystniejsza optymalizacja to wprowadzenie myHelper w celu wyeliminowania drugiego wczytywania, chociaż przyszły kompilator może robić to automatycznie.

Kolejność pozyskiwania i wycofywania produktów nie zapobiega znacznemu opóźnieniu w sklepach ani nie zapewnia, że sklepy staną się widoczne w innych wątkach w spójnej kolejności. W efekcie nie obsługuje on skomplikowanego, ale dość powszechnego wzorca kodowania, na przykład algorytmu wzajemnego wykluczania Dekkera. Wszystkie wątki ustawiają najpierw flagę informującą o potrzebie działania; jeśli wątek t zauważy, że żaden inny wątek nie próbuje coś zrobić, może kontynuować, wiedząc, że nic nie będzie zakłócać. Żaden inny wątek nie będzie kontynuowany, ponieważ flaga t jest nadal ustawiona. Nie uda się to, jeśli dostęp do flagi uzyskuje się za pomocą kolejności pozyskiwania/publikacji, ponieważ nie zapobiegnie to opóźnieniu flagi wątku u innych, ponieważ wykonali ją przez pomyłkę. Domyślna wartość memory_order_seq_cst blokuje to ustawienie.

Pola stałe

Jeśli pole obiektu zostanie zainicjowane przy pierwszym użyciu, a potem nigdy nie zostanie zmienione, możliwe jest zainicjowanie, a następnie odczyt za pomocą słabo uporządkowanych dostępu. W C++ można go zadeklarować jako atomic i uzyskać do niego dostęp za pomocą memory_order_relaxed lub w Javie, można go zadeklarować bez volatile i uzyskać do niego dostęp bez specjalnych środków. Wymaga to stosowania wszystkich tych blokad:

• Na podstawie wartości pola powinna być możliwe określenie, czy zostało już zainicjowane. Aby można było uzyskać dostęp do pola, wartość testowa i zwracana szybkiej ścieżki powinna odczytywać pole tylko raz. W Javie ten ostatni jest ważny. Nawet wtedy, gdy testy w polu zostaną zainicjowane, drugie wczytanie może odczytać wcześniejszą niezainicjowaną wartość. W C++ reguła „przeczytaj tylko raz” jest jedynie dobrą praktyką.
• Zarówno inicjowanie, jak i kolejne wczytywanie muszą mieć charakter niepodzielny, ponieważ częściowe aktualizacje nie powinny być widoczne. W przypadku Javy pole nie powinno być wartością long ani double. W języku C++ wymagane jest przypisanie atomowe. Jego utworzenie nie zadziała, ponieważ konstrukcja obiektu atomic nie jest atomowa.
• Powtarzane inicjowanie muszą być bezpieczne, ponieważ wiele wątków może jednocześnie odczytywać niezainicjowaną wartość. W C++ zwykle wynika to z wymagania, które można łatwo skopiować, stosowanego do wszystkich typów atomowych. Typy z zagnieżdżonymi wskaźnikami własnymi będą wymagały delegacji w konstruktorze kopiowania i nie da się tego łatwo skopiować. W przypadku Javy dopuszczalne są niektóre typy odwołań:
• Odwołania w Javie są ograniczone do typów stałych zawierających wyłącznie pola końcowe. Konstruktor typu stałego nie powinien publikować odwołania do obiektu. W tym przypadku reguły pola końcowego Javy gwarantują, że jeśli czytelnik zobaczy odniesienie, zobaczy też zainicjowane pola końcowe. Kod C++ nie ma analogii do tych reguł i z tego powodu wskaźniki do obiektów należących do Ciebie są niedopuszczalne (oprócz naruszenia wymagań dotyczących łatwego do skopiowania).

Uwagi końcowe

Chociaż dokument ten nie tylko zarysuje ścianę, to po prostu płytki śluz. To bardzo szeroki i głębokim zagadnienie. Obszary do dalszej eksploracji:

• Rzeczywiste modele pamięci Java i C++ są wyrażone w postaci relacji happens-before, która określa, kiedy 2 działania mają wystąpić w określonej kolejności. Kiedy definiowaliśmy rasę danych, nieformalnie rozmawialiśmy o dwóch operacjach dostępu do pamięci, które następuje „jednocześnie”. Oficjalnie oznacza to, że żadne z tych zdarzeń nie miało miejsca wcześniej. Warto poznać rzeczywiste definicje zdarzeń happens-before i synchronizes-with w modelu pamięci Java lub C++. Chociaż intuicyjne pojęcie „jednocześnie” jest w zasadzie dość dobre, te definicje są pomocne, zwłaszcza jeśli rozważasz użycie słabo uporządkowanych operacji atomowych w języku C++. (Obecna specyfikacja Java definiuje lazySet() bardzo nieformalnie).
• Dowiedz się, co kompilatory mogą robić, a co nie mogą robić podczas zmiany kolejności kodu. (Specyfikacja JSR-133 zawiera kilka świetnych przykładów przekształceń prawnych, które prowadzą do nieoczekiwanych wyników).
• Dowiedz się, jak pisać niezmienne klasy w Javie i C++. Jest to coś więcej niż tylko „po utworzeniu niczego nie zmieniaj”.
• Wewnętrznie zastosuj rekomendacje w sekcji „Równoczesność” dokumentu Effective Java, 2nd Edition. (Na przykład nie należy wywoływać metod, które powinny zostać zastąpione podczas korzystania z zsynchronizowanego bloku).
• Zapoznaj się z interfejsami API java.util.concurrent i java.util.concurrent.atomic, aby dowiedzieć się, co jest dostępne. Rozważ użycie adnotacji równoczesności, takich jak @ThreadSafe i @GuardedBy (z net.jcip.annotations).

W sekcji Dalsze czytanie w załączniku znajdują się linki do dokumentów i witryn internetowych, które pozwolą lepiej zrozumieć te tematy.

Dodatek

Wdrażanie magazynów synchronizacji

(Większość programistów się z niego nie zorientuje, ale dyskusja na ich podstawie daje wiele wskazań).

W przypadku małych typów wbudowanych, takich jak int, oraz sprzętu obsługiwanego przez Androida, zwykłe instrukcje wczytywania i przechowywania powodują, że sklep będzie widoczny w całości lub w ogóle dla innego podmiotu przetwarzającego dane z tej samej lokalizacji. Podstawowe pojęcie „atomia” jest więc stosowane bezpłatnie.

Jak już wspomnieliśmy, to nie wystarczy. Aby zapewnić spójność sekwencyjną, musimy też zapobiegać zmianie kolejności operacji i dbać o to, aby operacje dotyczące pamięci były widoczne dla innych procesów w spójnej kolejności. Okazuje się, że to drugie rozwiązanie działa automatycznie w przypadku sprzętu z Androidem, o ile dokonamy przemyślanych wyborów w zakresie egzekwowania tych zasad, więc w ogóle je pominiemy.

Kolejność operacji na pamięci jest zachowywana, ponieważ kompilator nie pozwala na zmianę kolejności, a także uniemożliwia zmianę kolejności przez sprzęt. Tutaj skoncentrujemy się na tym drugim.

Kolejność pamięci w przypadku ARMv7, x86 i MIPS jest egzekwowana za pomocą instrukcji „fence”, które z reguły zapobiegają pojawianiu się instrukcji występujących po ogrodzeniu przed instrukcjami poprzedzającymi go. Są to również instrukcje nazywane „barierami”, ale ich użycie niesie ze sobą ryzyko pomyłki związane z barierami w stylu pthread_barrier, które dają większe możliwości. Dokładne znaczenie instrukcji dotyczących ogrodzeń jest dość skomplikowanym zagadnieniem, które dotyczy sposobu, w jaki gwarancje dostarczane przez różne rodzaje ogrodzeń łączą się z innymi gwarancjami kolejności zapewnianymi zwykle przez sprzęt. Jest to ogólne omówienie, więc omówimy je poniżej.

Najbardziej podstawowym rodzajem gwarancji kolejności jest korzystanie z operacji atomowych w języku C++ memory_order_acquire i memory_order_release. Operacje w pamięci poprzedzające magazyn wersji powinny być widoczne po obciążeniu pozyskania. W ARMv7 jest to wymuszane przez:

• Przedstawienie instrukcji dotyczących płotu w sklepie. Zapobiega to zmianie kolejności wszystkich wcześniejszych ustawień dostępu do pamięci za pomocą instrukcji przechowywania. (Uniemożliwia to też ponowne zamawianie produktów z późniejszymi instrukcjami).
• stosowanie się do instrukcji wczytywania z odpowiednią instrukcją ogrodzeń, co zapobiega ponownemu zmianie ładunku przy kolejnym dostępie. (Jeszcze raz podkreślamy niepotrzebne porządkowanie stron z przynajmniej wcześniejszymi załadowaniami).

Te wszystkie elementy wystarczają do porządkowania C++ w celu pozyskania/wydania w C++. Są one niezbędne, ale niewystarczające w przypadku języka Java volatile lub C++ sekwencyjnego spójności atomic.

Aby zobaczyć, co jeszcze jest potrzebne, weź pod uwagę omówiony wcześniej fragment algorytmu Dekkera. flag1 i flag2 to zmienne C++ atomic lub Java volatile, z początku mają wartość false (fałsz).

Wątek 1	Wątek 2
flag1 = true if (flag2 == false)     critical-stuff	flag2 = true if (flag1 == false)     critical-stuff

Spójność sekwencyjna oznacza, że jedno z przypisań do flagn musi zostać wykonane najpierw i widoczne w teście w drugim wątku. Nie zauważymy więc, że te wątki będą jednocześnie wykonywać „krytyczne rzeczy”.

Jednak ogrodzenie wymagane w przypadku kolejności pozyskania i wydania dodaje granice tylko na początku i na końcu każdego wątku, co w tym przypadku nie pomaga. Musimy też upewnić się, że jeśli po volatile/atomic sklepie następuje volatile/atomic ładowanie, nie następuje zmiana kolejności obu sklepów. Zwykle jest to egzekwowane przez dodanie ogrodzenia nie bezpośrednio przed spójnym magazynem, ale także po nim. To ustawienie jest też znacznie silniejsze niż jest wymagane, ponieważ to ogrodzenie zwykle nakazuje wszystkie wcześniejsze poziomy dostępu do pamięci względem wszystkich późniejszych.

Moglibyśmy natomiast powiązać dodatkowe ogrodzenie z sekwencyjnymi ładowaniem. Sklepy pojawiają się rzadziej, więc opisana przez nas konwencja jest bardziej powszechna i stosowana na Androidzie.

Jak już wspomnieliśmy w poprzedniej sekcji, między tymi 2 operacjami musimy wstawić barierę przechowywania/obciążenia. Kod uruchamiany w maszynie wirtualnej na potrzeby dostępu zmiennego będzie wyglądał mniej więcej tak:

obciążenie ulotne	sklep zmienny
reg = A fence for "acquire" (1)	fence for "release" (2) A = reg fence for later atomic load (3)

Prawdziwe architektury maszyn zwykle udostępniają wiele typów płotów, porządkujących różne typy dostępu i różnych kosztów. Wybór między nimi jest subtelny, a na wpływ ma konieczność zapewnienia, że sklepy są widoczne dla innych rdzeni w spójnej kolejności, a kolejność pamięci narzucana przez kombinację wielu ogrodzeń. Więcej informacji znajdziesz na stronie Uniwersytetu w Cambridge poświęconej zebranym mapom atomu na rzeczywiste procesory.

W niektórych architekturach, zwłaszcza x86, bariery „acquire” i „release” są niepotrzebne, ponieważ sprzęt zawsze pośrednio wymusza odpowiednią kolejność. W systemie x86 tak naprawdę generowany jest tylko ostatni ogrodzenie (3). Podobnie w x86 atomowe operacje odczytu, modyfikacji i zapisu domyślnie obejmują silne ogrodzenie. Dzięki temu nigdy nie wymagają one ogrodzenia. W przypadku ARMv7 wszystkie omówione powyżej płoty są wymagane.

ARMv8 udostępnia instrukcje LDAR i STLR, które bezpośrednio egzekwują wymagania dotyczące zmiennych zmiennych w języku Java lub C++ sekwencyjnie spójnych obciążeń i magazynów. Pozwala to uniknąć zbędnych ograniczeń związanych z kolejnością wspomnianych powyżej. Wykorzystuje je 64-bitowy kod Androida na procesorach ARM. Skupiliśmy się na rozmieszczeniu ogrodzeń ARMv7, ponieważ rzuca więcej światła na rzeczywiste wymagania.

Więcej materiałów

Strony internetowe i dokumenty, które zawierają więcej szczegółów. Bardziej ogólnie przydatne artykuły znajdują się na górze listy.

Modele spójności pamięci współdzielonej: samouczek

Książka powstała w 1995 roku przez firmę Adve i Gharachorloo. Dokument ten jest dobrym punktem wyjścia dla osób, które chcą zagłębić się w modele spójności pamięci.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf

Bariery pamięci

Przydatny artykuł z podsumowaniem problemów.
https://en.wikipedia.org/wiki/Memory_barrier

Podstawowe informacje o Threads

Wprowadzenie do wielowątkowości programowania w językach C++ i Javy, autorstwa Hansa Boehma. Omówienie biegów danych i podstawowych metod synchronizacji.
http://www.hboehm.info/c++mm/threadsintro.html

Równoczesność Javy w praktyce

Ta książka została opublikowana w 2006 roku i szczegółowo porusza szeroki zakres tematów. Zdecydowanie zalecany dla każdego, kto tworzy wielowątkowy kod w Javie.
http://www.javaconcurrencyinpractice.com

Najczęstsze pytania na temat JSR-133 (Java Memory Model)

Krótkie wprowadzenie do modelu pamięci Java, w tym omówienie synchronizacji, zmiennych zmiennych i konstrukcji pól końcowych. (To trochę przestarzałe, zwłaszcza jeśli chodzi o inne języki).
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html

Ważność przekształceń programu w modelu pamięci Java

Bardziej techniczne wyjaśnienie pozostałych problemów z modelem pamięci Java. Problemy te nie mają zastosowania w przypadku programów niezawierających wyścigu na podstawie danych.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf

Omówienie pakietu java.util.concurrent

Dokumentacja pakietu java.util.concurrent. U dołu strony znajduje się sekcja zatytułowana „Właściwości spójności pamięci”, w której opisano gwarancje zapewniane przez różne klasy.
java.util.concurrent – podsumowanie pakietu

Teoria i praktyka Java: bezpieczne techniki konstrukcji w Javie

W tym artykule omawiamy szczegółowo zagrożenia związane ze ucieczkim odniesień podczas konstruowania obiektów oraz podajemy wskazówki dotyczące konstruktorów bezpiecznych dla wątków.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html

Teoria i ćwiczenie dotyczące Javy: zarządzanie zmiennością

Przydatny artykuł opisujący, co można, a czego nie można osiągnąć za pomocą pól zmiennych w języku Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html

Deklaracja „Double-Checked Locking is uszkodzony”

Szczegółowe wyjaśnienie Billa Pugh na różne sposoby, w jakie dokładnie sprawdzone zamek zostaje uszkodzone bez użycia volatile lub atomic. Obejmuje C/C++ i Javę.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

[ARM] Testy barierowego litmusa i książka kucharska

Dyskusja na temat problemów z architekturą ARM SMP przedstawiona za pomocą krótkich fragmentów kodu ARM. Jeśli przykłady na tej stronie są zbyt nieprecyzyjne lub chcesz przeczytać formalny opis instrukcji DMB, przeczytaj ten artykuł. Dodatkowo opisujemy tutaj instrukcje stosowania barier pamięci w kodzie wykonywalnym (przydatne, jeśli generujesz kod na bieżąco). Pamiętaj, że jest to wersja sprzed ARMv8, która również obsługuje dodatkowe instrukcje sortowania pamięci, i została przeniesiona na model pamięci o większej mocy. (więcej informacji znajdziesz w dokumencie „ARM® Architecture Reference Manual ARMv8 dla profilu architektury ARMv8-A”).
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf

Bariery pamięci jądra systemu Linux

Dokumentacja barier pamięci jądra systemu Linux. Zawiera kilka przydatnych przykładów i grafiki ASCII.
http://www.kernel.org/doc/documentation/memory-barriers.txt

ISO/IEC JTC1 SC22 WG21 (standardy C++) 14882 (język programowania C++), sekcja 1.10 i punkt 29 („Biblioteka operacji atomowych”)

Wersja robocza funkcji operacji atomowych w C++. Ta wersja jest zbliżona do standardu C++14, który obejmuje drobne zmiany w tym zakresie od C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(wprowadzenie: http://www.hpl.hp.com/tech08reports/2015/pl-pl)

ISO/IEC JTC1 SC22 WG14 (standardy C) 9899 (język programowania C) rozdział 7.16 („Atomics <stdatomic.h>”)

Wersja robocza normy działania atomowego ISO/IEC 9899-201x C. Szczegółowe informacje znajdziesz też w późniejszych raportach o błędach.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

Mapowania C/C++11 na procesory (U University of Cambridge)

Jaroslav Sevcik i Peter Sewell: kolekcja tłumaczeń matematyki C++ na różne zestawy instrukcji obsługi procesora.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

Algorytm Dekkera

„Pierwsze znane poprawne rozwiązanie problemu wzajemnego wykluczania w programowaniu równoczesnym”. Pełny algorytm w tym artykule w Wikipedii informuje o tym, jak trzeba go zaktualizować, aby współpracował z nowoczesnymi kompilatorami optymalizującymi i sprzętem SMP.
https://pl.wikipedia.org/wiki/Dekker_algorithm

Komentarze na temat ARM i alfa oraz dotyczące zależności

E-mail na liście adresowej jądra Catalin Marinas. Zawiera przydatne podsumowanie zależności adresów i ustawień kontroli.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html

Co każdy programista powinien wiedzieć o pamięci

Ulrich Drepper – bardzo długi i szczegółowy artykuł na temat różnych typów pamięci, a zwłaszcza pamięci podręcznej procesora.
http://www.akkadia.org/drepper/cpumemory.pdf

Uzasadnienie dotyczące słabo spójnego modelu pamięci ARM

Dokument został napisany przez Chong & Ishtiaq z firmy ARM, Ltd. Celem jest opisanie modelu pamięci ARM SMP w rygorystyczny, ale przystępny sposób. Użyta tutaj definicja „dostrzegalności” pochodzi z tej publikacji. Jest to wersja sprzed ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711

Książka kucharska JSR-133 dla autorów kompilatorów

Doug Lea napisał ten tekst jako uzupełnienie dokumentacji JSR-133 (Java Memory Model). Zawiera on początkowy zestaw wytycznych dotyczących implementacji modelu pamięci Java, z którego korzystało wielu autorów kompilatorów. W dalszym ciągu jest on powszechnie cytowany i prawdopodobnie może dostarczyć cennych informacji. Cztery opisane tu odmiany ogrodzeń nie pasują do architektur obsługiwanych na Androidzie, a powyższe mapowania C++11 są teraz lepszym źródłem precyzyjnych przepisów nawet dla Javy.
http://g.oswego.edu/dl/jmm/cookbook.html

x86-TSO: rygorystyczny, użyteczny model programowania dla wielu procesorów x86

Dokładny opis modelu pamięci x86. Dokładne opisy modelu pamięci ARM są niestety znacznie bardziej skomplikowane.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf