Przygotowanie do SMP na Androida

Wersje platformy Android 3.0 i nowsze są zoptymalizowane pod kątem obsługi architektur wieloprocesorowych. W tym dokumencie opisujemy problemy, które mogą wystąpić podczas pisania kodu wielowątkowego dla symetrycznych systemów wieloprocesorowych w językach programowania C, C++ i Java (dla uproszczenia dalej nazywanym po prostu „Java”). Jest to wprowadzenie dla deweloperów aplikacji na Androida, a nie wyczerpujące omówienie tematu.

Wprowadzenie

SMP to skrót od „Symmetric Multi-Processor” (symetryczny wieloprocesor). Opisuje on architekturę, w której co najmniej 2 identyczne rdzenie procesora współdzielą dostęp do pamięci głównej. Do niedawna wszystkie urządzenia z Androidem były jednordzeniowe.

Większość urządzeń z Androidem (jeśli nie wszystkie) zawsze miała wiele procesorów, ale w przeszłości tylko jeden z nich był używany do uruchamiania aplikacji, podczas gdy inne zarządzały różnymi elementami sprzętowymi urządzenia (np. radiem). Procesory mogły mieć różne architektury, a programy działające na nich nie mogły używać pamięci głównej do komunikacji między sobą.

Większość sprzedawanych obecnie urządzeń z Androidem jest oparta na architekturze SMP, co nieco komplikuje pracę programistom. Sytuacje wyścigu w programie wielowątkowym mogą nie powodować widocznych problemów na komputerze z jednym procesorem, ale mogą regularnie powodować błędy, gdy co najmniej 2 wątki są uruchamiane jednocześnie na różnych rdzeniach. Co więcej, kod może być mniej lub bardziej podatny na błędy, gdy jest uruchamiany na różnych architekturach procesorów, a nawet na różnych implementacjach tej samej architektury. Kod, który został dokładnie przetestowany na x86, może nie działać prawidłowo na ARM. Kod może zacząć działać nieprawidłowo po ponownej kompilacji za pomocą nowszego kompilatora.

W dalszej części tego dokumentu wyjaśniamy, dlaczego tak jest i co musisz zrobić, aby Twój kod działał prawidłowo.

Modele spójności pamięci: dlaczego SMP są nieco inne

To szybkie i ogólne omówienie złożonego tematu. Niektóre obszary będą niekompletne, ale żaden z nich nie powinien wprowadzać w błąd ani być nieprawidłowy. Jak zobaczysz w następnej sekcji, szczegóły nie są tu zwykle istotne.

Więcej informacji na ten temat znajdziesz w sekcji Dodatkowe materiały na końcu dokumentu.

Modele spójności pamięci, często nazywane po prostu „modelami pamięci”, opisują gwarancje, jakie język programowania lub architektura sprzętowa dają w odniesieniu do dostępu do pamięci. Jeśli na przykład zapiszesz wartość pod adresem A, a następnie pod adresem B, model może zagwarantować, że każdy rdzeń procesora będzie widział te zapisy w tej kolejności.

Model, do którego przyzwyczajona jest większość programistów, to spójność sekwencyjna, która jest opisana w ten sposób (Adve i Gharachorloo):

• Wszystkie operacje na pamięci są wykonywane pojedynczo
• Wszystkie operacje w jednym wątku są wykonywane w kolejności opisanej przez program procesora.

Załóżmy na chwilę, że mamy bardzo prosty kompilator lub interpreter, który nie wprowadza żadnych niespodzianek: tłumaczy przypisania w kodzie źródłowym na instrukcje wczytywania i zapisywania w dokładnie odpowiadającej im kolejności, po jednej instrukcji na dostęp. Dla uproszczenia założymy też, że każdy wątek jest wykonywany na osobnym procesorze.

Jeśli spojrzysz na fragment kodu i zobaczysz, że wykonuje on pewne operacje odczytu i zapisu z pamięci, w przypadku architektury procesora o spójności sekwencyjnej wiesz, że kod wykona te operacje w oczekiwanej kolejności. Możliwe, że procesor faktycznie zmienia kolejność instrukcji i opóźnia odczyty i zapisy, ale kod uruchomiony na urządzeniu nie może stwierdzić, że procesor robi coś innego niż wykonywanie instrukcji w prosty sposób. (Zignorujemy operacje wejścia/wyjścia sterownika urządzenia mapowanego w pamięci).

Aby zilustrować te kwestie, warto rozważyć krótkie fragmenty kodu, które są często nazywane testami lakmusowymi.

Oto prosty przykład z kodem działającym w 2 wątkach:

W tym i wszystkich przyszłych przykładach testów litmus lokalizacje pamięci są reprezentowane przez wielkie litery (A, B, C), a rejestry procesora zaczynają się od „reg”. Cała pamięć jest początkowo zerowa. Instrukcje są wykonywane od góry do dołu. W tym przypadku wątek 1 zapisuje wartość 3 w lokalizacji A, a następnie wartość 5 w lokalizacji B. Wątek 2 wczytuje wartość z lokalizacji B do reg0, a następnie wczytuje wartość z lokalizacji A do reg1. (Zwróć uwagę, że zapisujemy w jednej kolejności, a odczytujemy w innej).

Zakłada się, że wątek 1 i wątek 2 są wykonywane na różnych rdzeniach procesora. Myśląc o kodzie wielowątkowym, zawsze należy przyjmować takie założenie.

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

Aby doszło do sytuacji, w której widzimy B=5, zanim zobaczymy zapis do A, odczyty lub zapisy musiałyby nastąpić w niewłaściwej kolejności. Na maszynie o spójności sekwencyjnej nie może się to zdarzyć.

Jednoprocesory, w tym x86 i ARM, są zwykle spójne sekwencyjnie. Wątki wydają się wykonywać w sposób przeplatany, ponieważ jądro systemu operacyjnego przełącza się między nimi. Większość systemów SMP, w tym x86 i ARM, nie jest sekwencyjnie spójna. Na przykład sprzęt często buforuje zapisy w drodze do pamięci, więc nie docierają one do niej natychmiast i nie są widoczne dla innych rdzeni.

Szczegóły znacznie się różnią. Na przykład x86, mimo że nie jest spójny sekwencyjnie, nadal gwarantuje, że reg0 = 5 i reg1 = 0 pozostaje niemożliwe. Magazyny są buforowane, ale ich kolejność jest zachowywana. Z kolei ARM nie ma takiej możliwości. Kolejność buforowanych operacji zapisu nie jest zachowywana, a operacje zapisu mogą nie docierać do wszystkich pozostałych rdzeni jednocześnie. Te różnice są ważne dla programistów asemblera. Jednak, jak zobaczymy poniżej, programiści C, C++ lub Javy mogą i powinni programować w sposób, który ukrywa takie różnice architektoniczne.

Do tej pory zakładaliśmy, że tylko sprzęt zmienia kolejność instrukcji. W rzeczywistości kompilator zmienia też kolejność instrukcji, aby zwiększyć wydajność. W naszym przykładzie kompilator może zdecydować, że jakiś późniejszy kod w wątku 2 potrzebuje wartości reg1 przed reg0, i dlatego najpierw wczyta reg1. Możliwe też, że jakiś wcześniejszy kod już wczytał A, a kompilator może zdecydować o ponownym użyciu tej wartości zamiast ponownego wczytywania A. W obu przypadkach wczytywanie do reg0 i reg1 może zostać zmienione.

Zmiana kolejności dostępu do różnych lokalizacji pamięci, zarówno na poziomie sprzętu, jak i kompilatora, jest dozwolona, ponieważ nie wpływa na wykonywanie pojedynczego wątku i może znacznie poprawić wydajność. Jak się przekonamy, przy odrobinie ostrożności możemy też zapobiec wpływowi na wyniki programów wielowątkowych.

Ponieważ kompilatory mogą również zmieniać kolejność dostępu do pamięci, ten problem nie jest nowy w przypadku SMP. Nawet w przypadku jednego procesora kompilator może zmienić kolejność wczytywania do reg0 i reg1 w naszym przykładzie, a wątek 1 może zostać zaplanowany między instrukcjami o zmienionej kolejności. Jeśli jednak kompilator nie zmieni kolejności, możemy nigdy nie zauważyć tego problemu. Na większości procesorów ARM SMP, nawet bez zmiany kolejności przez kompilator, zmiana kolejności prawdopodobnie będzie widoczna, być może po bardzo dużej liczbie udanych wykonań. Jeśli nie programujesz w asemblerze, SMP zazwyczaj zwiększa prawdopodobieństwo, że zobaczysz problemy, które występowały od samego początku.

Programowanie bez wyścigów danych

Na szczęście zwykle można łatwo uniknąć myślenia o tych wszystkich szczegółach. Jeśli będziesz przestrzegać kilku prostych zasad, możesz zapomnieć o całej poprzedniej sekcji z wyjątkiem części dotyczącej spójności sekwencyjnej. Niestety, jeśli przypadkowo naruszysz te zasady, mogą pojawić się inne komplikacje.

Nowoczesne języki programowania zachęcają do stosowania stylu programowania „bez wyścigu danych”. Jeśli nie wprowadzisz „wyścigów danych” i unikniesz kilku konstrukcji, które mówią kompilatorowi coś innego, kompilator i sprzęt obiecują zapewnić spójne wyniki. Nie oznacza to jednak, że unikają zmiany kolejności dostępu do pamięci. Oznacza to, że jeśli przestrzegasz reguł, nie będziesz w stanie stwierdzić, że dostęp do pamięci jest zmieniany. To tak, jakby powiedzieć, że kiełbasa jest pyszna i apetyczna, pod warunkiem, że nie odwiedzisz fabryki kiełbasy. Wyścigi danych ujawniają nieprzyjemną prawdę o zmianie kolejności pamięci.

Czym jest „wyścig danych”?

Wyścig danych występuje, 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 między wątkami. Muteksy, zmienne warunkowe, zmienne volatile w języku Java czy obiekty atomic w języku C++ nie są zwykłymi danymi, a dostęp do nich może być realizowany w ramach wyścigu. W rzeczywistości są one używane do zapobiegania wyścigom danych w innych obiektach.

Aby określić, czy 2 wątki jednocześnie uzyskują dostęp do tej samej lokalizacji w pamięci, możemy zignorować powyższą dyskusję na temat zmiany kolejności pamięci i założyć spójność sekwencyjną. Poniższy program nie zawiera wyścigu danych, jeśli A i B są zwykłymi zmiennymi logicznymi, które początkowo mają wartość false:

Ponieważ operacje nie są zmieniane, oba warunki będą miały wartość false i żadna zmienna nie zostanie zaktualizowana. Dlatego nie może dojść do wyścigu danych. Nie musimy się zastanawiać, co by się stało, gdyby wczytanie z A i zapisanie do B w wątku 1 zostały w jakiś sposób zmienione. Kompilator nie może zmienić kolejności wątku 1, przepisując go jako „B = true; if (!A) B = false”. To byłoby jak robienie kiełbasy w środku miasta w biały dzień.

Wyścigi danych są oficjalnie definiowane na podstawowych typach wbudowanych, takich jak liczby całkowite i odwołania lub wskaźniki. Przypisanie do int przy jednoczesnym odczycie w innym wątku jest ewidentnie wyścigiem danych. Jednak zarówno biblioteka standardowa C++, jak i biblioteki Java Collections są napisane tak, aby umożliwiać analizowanie wyścigów danych na poziomie biblioteki. Gwarantują, że nie spowodują wyścigów danych, chyba że wystąpią jednoczesne próby dostępu do tego samego kontenera, z których co najmniej jedna będzie go aktualizować. Aktualizowanie obiektu set<T> w jednym wątku przy jednoczesnym odczytywaniu go w innym wątku umożliwia bibliotece wprowadzenie wyścigu danych, co można nieformalnie określić jako „wyścig danych na poziomie biblioteki”. Z drugiej strony aktualizowanie jednego elementu set<T> w jednym wątku podczas odczytywania innego elementu w innym wątku nie powoduje wyścigu danych, ponieważ biblioteka gwarantuje, że w takim przypadku nie dojdzie do wyścigu danych (na niskim poziomie).

Zwykle jednoczesny dostęp do różnych pól w strukturze danych nie może powodować wyścigu danych. Istnieje jednak jeden ważny wyjątek od tej reguły: ciągłe sekwencje pól bitowych w języku C lub C++ są traktowane jako pojedyncza „lokalizacja pamięci”. Uzyskanie dostępu do dowolnego pola bitowego w takiej sekwencji jest traktowane jako uzyskanie dostępu do wszystkich pól bitowych w celu określenia, czy występuje wyścig danych. Wynika to z braku możliwości aktualizowania poszczególnych bitów przez typowy sprzęt bez odczytywania i ponownego zapisywania sąsiednich bitów. Programiści Javy nie mają takich problemów.

Unikanie wyścigów danych

Nowoczesne języki programowania udostępniają szereg mechanizmów synchronizacji, które pozwalają uniknąć wyścigów danych. Najbardziej podstawowe narzędzia to:

Blokady lub muteksy

Aby mieć pewność, że określona sekcja kodu nie będzie wykonywana równocześnie z innymi sekcjami kodu, które uzyskują dostęp do tych samych danych, można użyć

muteksów (std::mutex lub pthread_mutex_t w C++11) albo bloków synchronized w języku Java. Te i inne podobne funkcje będziemy ogólnie nazywać „blokadami”. Konsekwentne uzyskiwanie określonej blokady przed uzyskaniem dostępu do udostępnionej struktury danych i zwalnianie jej po zakończeniu zapobiega wyścigom danych podczas uzyskiwania dostępu do struktury danych. Zapewnia też, że aktualizacje i dostęp są niepodzielne, tzn. żadna inna aktualizacja struktury danych nie może zostać uruchomiona w trakcie. Jest to zdecydowanie najpopularniejsze narzędzie do zapobiegania wyścigom danych. Użycie bloków synchronized w języku Java lub lock_guard albo unique_lock w języku C++ zapewnia prawidłowe zwolnienie blokad w przypadku wyjątku.

Zmienne ulotne/niepodzielne

Java udostępnia pola volatile, które obsługują równoczesny dostęp bez wprowadzania wyścigów danych. Od 2011 roku języki C i C++ obsługują zmienne i pola atomic o podobnej semantyce. Zazwyczaj są trudniejsze w użyciu niż blokady, ponieważ zapewniają jedynie, że pojedyncze dostępy do jednej zmiennej są niepodzielne. (W C++ zwykle obejmuje to proste operacje odczytu, modyfikacji i zapisu, takie jak przyrosty. Java wymaga do tego specjalnych wywołań metod). W odróżnieniu od blokad zmiennych volatile lub atomic nie można używać bezpośrednio do uniemożliwiania innym wątkom zakłócania dłuższych sekwencji kodu.

Warto zauważyć, że volatile ma zupełnie inne znaczenie w C++ i Javie. W C++ volatile nie zapobiega wyścigom danych, chociaż starszy kod często używa go jako obejścia braku obiektów atomic. Nie jest to już zalecane. W C++ używaj atomic<T> w przypadku zmiennych, do których dostęp może mieć jednocześnie wiele wątków. C++ volatile jest przeznaczony do rejestrów urządzeń i podobnych zastosowań.

Zmienne C/C++ atomic lub zmienne Java volatile mogą być używane do zapobiegania wyścigom danych w innych zmiennych. Jeśli flag jest zadeklarowana jako typ atomic<bool> lub atomic_bool (C/C++) lub volatile boolean (Java) i początkowo ma wartość false, ten fragment kodu jest wolny od wyścigu danych:

Ponieważ wątek 2 czeka na ustawienie flag, dostęp do A w wątku 2 musi nastąpić po przypisaniu do A w wątku 1, a nie równocześnie z nim. Dlatego nie ma wyścigu danych w A. Wyścig w flag nie jest traktowany jako wyścig danych, ponieważ dostęp do zmiennych ulotnych/niepodzielnych nie jest „zwykłym dostępem do pamięci”.

Implementacja jest wymagana, aby zapobiec zmianie kolejności pamięci lub ją ukryć w stopniu wystarczającym do tego, aby kod taki jak w poprzednim teście lakmusowym działał zgodnie z oczekiwaniami. Zwykle sprawia to, że dostęp do pamięci nietrwałej/niepodzielnej jest znacznie droższy niż zwykły dostęp.

Chociaż poprzedni przykład nie zawiera wyścigu danych, blokady wraz z Object.wait() w języku Java lub zmienne warunkowe w języku C/C++ zwykle stanowią lepsze rozwiązanie, które nie wymaga oczekiwania w pętli i nie powoduje rozładowywania baterii.

Kiedy zmiana kolejności wspomnień staje się widoczna

1. Jeśli program zawiera błąd powodujący niezamierzony wyścig danych, przekształcenia kompilatora i sprzętu mogą stać się widoczne, a działanie programu może być zaskakujące. Jeśli na przykład zapomnimy zadeklarować flag jako volatile w poprzednim przykładzie, wątek 2 może zobaczyć niezainicjowaną zmienną A. Kompilator może też uznać, że flaga nie może się zmienić podczas pętli wątku 2, i przekształcić program w taki sposób:

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

   Podczas debugowania możesz zauważyć, że pętla trwa w nieskończoność, mimo że flag ma wartość true.
2. C++ zapewnia funkcje umożliwiające jawne rozluźnienie spójności sekwencyjnej, nawet jeśli nie ma wyścigów. Operacje niepodzielne mogą przyjmować jawne argumenty memory_order_... Podobnie pakiet java.util.concurrent.atomic udostępnia bardziej ograniczony zestaw podobnych funkcji, zwłaszcza lazySet(). Programiści Javy czasami celowo używają wyścigów danych, aby uzyskać podobny efekt. Wszystkie te rozwiązania zwiększają wydajność, ale znacznie komplikują programowanie. Poniżej omawiamy je tylko krótko.
3. Niektóre kody C i C++ są napisane w starszym stylu, który nie jest całkowicie zgodny z obecnymi standardami językowymi, w których zamiast zmiennych atomic używane są zmienne volatile, a porządkowanie pamięci jest wyraźnie zabronione przez wstawianie tzw. barier lub blokad. Wymaga to wyraźnego rozumowania dotyczącego zmiany kolejności dostępu i zrozumienia modeli pamięci sprzętowej. Styl kodowania podobny do tego jest nadal używany w jądrze Linuksa. Nie należy go używać w nowych aplikacjach na Androida i nie będziemy go tu omawiać.

Ćwicz

Debugowanie problemów ze spójnością pamięci może być bardzo trudne. Jeśli brak deklaracji blokady, atomic lub volatile powoduje, że jakiś kod odczytuje nieaktualne dane, możesz nie być w stanie ustalić przyczyny, analizując zrzuty pamięci za pomocą debugera. Zanim będzie można wysłać zapytanie do debugera, wszystkie rdzenie procesora mogą już zaobserwować pełny zestaw dostępów, a zawartość pamięci i rejestrów procesora będzie wyglądać na stan „niemożliwy”.

Czego nie należy robić w C

Poniżej przedstawiamy kilka przykładów nieprawidłowego kodu wraz z prostymi sposobami ich poprawienia. Zanim to zrobimy, musimy omówić użycie podstawowej funkcji języka.

C/C++ i „volatile”

Deklaracje volatile w językach C i C++ to narzędzie o bardzo specjalnym przeznaczeniu. Zapobiegają zmianie kolejności lub usunięciu dostępu volatile przez kompilator. Może to być przydatne w przypadku kodu, który uzyskuje dostęp do rejestrów urządzeń, pamięci mapowanej na więcej niż 1 lokalizację lub w połączeniu z setjmp. Jednak C i C++volatile, w przeciwieństwie do Javyvolatile, nie są przeznaczone do komunikacji między wątkami.

W językach C i C++ dostęp do danych volatile może zostać zmieniony na dostęp do danych nietrwałych i nie ma gwarancji niepodzielności. Dlatego nie można używać volatile do udostępniania danych między wątkami w kodzie przenośnym, nawet na komputerze z jednym procesorem. volatile w języku C zwykle nie zapobiega zmianie kolejności dostępu przez sprzęt, więc samo w sobie jest jeszcze mniej przydatne w wielowątkowych środowiskach SMP. Dlatego C11 i C++11 obsługują obiekty atomic. Zamiast tego użyj tych opcji.

Wiele starszych kodów C i C++ nadal nadużywa volatile do komunikacji wątków. Często działa to prawidłowo w przypadku danych, które mieszczą się w rejestrze maszyny, pod warunkiem, że są używane z wyraźnymi barierami lub w przypadkach, gdy kolejność pamięci nie jest ważna. Nie ma jednak gwarancji, że będzie działać prawidłowo z przyszłymi kompilatorami.

Przykłady

W większości przypadków lepiej jest użyć blokady (np. pthread_mutex_t lub C++11 std::mutex) niż operacji niepodzielnej, ale użyjemy tej drugiej, aby zilustrować, 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
        ...
    }
}

Chodzi o to, że przydzielamy strukturę, inicjujemy jej pola, a na samym końcu „publikujemy” ją, zapisując w zmiennej globalnej. W tym momencie każdy inny wątek może go zobaczyć, ale to nie problem, ponieważ jest on w pełni zainicjowany, prawda?

Problem polega na tym, że zapis do pola gGlobalThing może zostać zaobserwowany przed zainicjowaniem pól, zwykle dlatego, że kompilator lub procesor zmienił kolejność zapisów do pól gGlobalThing i thing->x. Inny wątek odczytujący dane z thing->x może zobaczyć wartość 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 useGlobalThing(), gGlobalThing może być odczytywany podczas zapisywania.

Można to naprawić, deklarując gGlobalThing jako atomowy. W 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 niektórym innym trybom awarii, które są dozwolone, ale mało prawdopodobne na rzeczywistym sprzęcie z Androidem. Dzięki temu nie możemy na przykład zobaczyć wskaźnika gGlobalThing, który został zapisany tylko częściowo.

Czego nie należy robić w Javie

Nie omówiliśmy jeszcze niektórych istotnych funkcji języka Java, więc najpierw krótko je omówimy.

Z technicznego punktu widzenia Java nie wymaga, aby kod był wolny od wyścigów danych. Istnieje też niewielka ilość bardzo starannie napisanego kodu w języku Java, który działa prawidłowo w przypadku wyścigów danych. Jednak napisanie takiego kodu jest niezwykle trudne, dlatego poniżej omówimy to tylko krótko. Co gorsza, eksperci, którzy określili znaczenie tego kodu, nie uważają już, że specyfikacja jest prawidłowa. (Specyfikacja jest odpowiednia dla kodu bez wyścigów danych).

Na razie będziemy trzymać się modelu bez wyścigów danych, w którym Java zapewnia zasadniczo takie same gwarancje jak C i C++. Język ten udostępnia też pewne elementy podstawowe, które wyraźnie rozluźniają spójność sekwencyjną, zwłaszcza wywołania lazySet() i weakCompareAndSet() w java.util.concurrent.atomic. Podobnie jak w przypadku C i C++, na razie je zignorujemy.

słowa kluczowe „synchronized” i „volatile” w języku Java,

Słowo kluczowe „synchronized” zapewnia wbudowany mechanizm blokowania w języku Java. Z każdym obiektem jest powiązany „monitor”, który może służyć do zapewniania wzajemnie wykluczającego się dostępu. Jeśli 2 wątki próbują „zsynchronizować” ten sam obiekt, jeden z nich będzie czekać, aż drugi zakończy działanie.

Jak wspomnieliśmy powyżej, volatile T w języku Java jest odpowiednikiem atomic<T> w języku C++11. Jednoczesny dostęp do pól volatile jest dozwolony i nie powoduje wyścigów danych. Pomijając lazySet() i inne oraz wyścigi danych, zadaniem maszyny wirtualnej Javy jest zapewnienie, że wynik nadal będzie spójny sekwencyjnie.

W szczególności, jeśli wątek 1 zapisuje dane w polu volatile, a wątek 2 następnie odczytuje dane z tego samego pola i widzi nowo zapisaną wartość, wątek 2 ma również gwarancję, że zobaczy wszystkie zapisy dokonane wcześniej przez wątek 1. Jeśli chodzi o efekt pamięci, zapisywanie w zmiennej volatile jest analogiczne do zwolnienia monitora, a odczytywanie ze zmiennej volatile jest jak uzyskanie monitora.

Istnieje jedna istotna różnica w porównaniu z atomic w C++: jeśli w Javie napiszemy volatile int x;, to x++ jest tym samym co x = x + 1; wykonuje operację atomic load, zwiększa wynik, a następnie wykonuje operację atomic store. W przeciwieństwie do C++ przyrost jako całość nie jest atomowy. Operacje atomowego przyrostu są natomiast udostępniane przez java.util.concurrent.atomic.

Przykłady

Oto prosta, nieprawidłowa implementacja licznika monotonicznego: (Java theory and practice: Managing volatility).

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

Załóżmy, że funkcje get() i incr() są wywoływane z wielu wątków i chcemy mieć pewność, że każdy wątek widzi bieżącą liczbę, gdy wywoływana jest funkcja get(). Najbardziej rażącym problemem jest to, że mValue++ to w rzeczywistości 3 operacje:

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

Jeśli 2 wątki są wykonywane w incr() jednocześnie, jedna z aktualizacji może zostać utracona. Aby zwiększanie było niepodzielne, musimy zadeklarować metodę incr() jako „synchronized”.

Nadal jednak nie działa, zwłaszcza w trybie wieloosobowym. Nadal występuje wyścig danych, ponieważ get() może uzyskać dostęp do mValue jednocześnie z incr(). Zgodnie z regułami Javy wywołanie get() może wydawać się zmienione w stosunku do innego kodu. Jeśli na przykład odczytamy 2 liczniki z rzędu, wyniki mogą wydawać się niespójne, ponieważ wywołania get() zostały zmienione przez sprzęt lub kompilator. Możemy rozwiązać ten problem, deklarując, że metoda get() jest zsynchronizowana. Po tej zmianie kod jest oczywiście poprawny.

Niestety wprowadziliśmy możliwość rywalizacji o blokadę, co może obniżyć wydajność. Zamiast deklarować get() jako zsynchronizowaną, możemy zadeklarować mValue jako „volatile”. (Uwaga: incr() nadal musi używać synchronize, ponieważ w przeciwnym razie mValue++ nie jest pojedynczą operacją niepodzielną). Pozwala to też uniknąć wszystkich wyścigów danych, dzięki czemu zachowana jest spójność sekwencyjna. incr() będzie nieco wolniejsza, ponieważ wiąże się z narzutem wejścia/wyjścia monitora i narzutem związanym z pamięcią nietrwałą, ale get() będzie szybsza, więc nawet przy braku rywalizacji jest to korzystne, jeśli odczyty znacznie przewyższają zapisy. (Zobacz też AtomicInteger, aby dowiedzieć się, jak całkowicie usunąć zsynchronizowany blok).

Oto inny przykład, podobny do wcześniejszych przykładów w języku 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
            ....
        }
    }
}

Występuje tu ten sam problem co w kodzie C, czyli wyścig danych w sGoodies. W związku z tym przypisanie sGoodies = goods może zostać zaobserwowane przed inicjalizacją pól w goods. Jeśli zadeklarujesz sGoodies za pomocą słowa kluczowego volatile, spójność sekwencyjna zostanie przywrócona i wszystko będzie działać zgodnie z oczekiwaniami.

Pamiętaj, że tylko samo odwołanie sGoodies jest nietrwałe. Dostęp do pól wewnątrz niego nie jest. Gdy sGoodies jest volatile i kolejność pamięci jest prawidłowo zachowana, nie można uzyskać jednoczesnego dostępu do pól. Instrukcja z = sGoodies.x spowoduje wykonanie nietrwałego wczytania MyClass.sGoodies, a następnie trwałego wczytania sGoodies.x. Jeśli utworzysz odwołanie lokalne MyGoodies localGoods = sGoodies, kolejne odwołanie z = localGoods.x nie będzie wykonywać żadnych operacji wczytywania danych nietrwałych.

Bardziej powszechnym idiomem w programowaniu w języku Java jest niesławna „blokada z podwójnym sprawdzeniem”:

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, aby mieć pojedynczą instancję obiektu Helper powiązaną z instancją MyClass. Musimy utworzyć go tylko raz, więc tworzymy go i zwracamy za pomocą dedykowanej funkcji getHelper(). Aby uniknąć sytuacji, w której 2 wątki tworzą instancję, musimy zsynchronizować tworzenie obiektu. Nie chcemy jednak płacić za narzut związany z blokiem „synchronized” przy każdym wywołaniu, więc wykonujemy tę część tylko wtedy, gdy helper ma obecnie wartość null.

W tym przypadku występuje wyścig danych w polu helper. Można go ustawić jednocześnie z helper == null w innym wątku.

Aby zobaczyć, jak może to zawieść, rozważ ten sam kod, ale nieco zmieniony, tak jakby był skompilowany w języku podobnym do C (dodaliśmy kilka pól liczb całkowitych, aby przedstawić 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 uniemożliwia sprzętowi ani kompilatorowi zmiany kolejności zapisu w polu helper na zapis w polach x/y. Inny wątek może znaleźć obiekt helper, który nie ma wartości null, ale jego pola nie są jeszcze ustawione i gotowe do użycia. Więcej informacji i trybów awarii znajdziesz w sekcji „Double Checked Locking is Broken” w załączniku lub w punkcie 71 („Use lazy initialization judiciously”) w książce Josha Blocha Effective Java, 2nd Edition.

Możesz to naprawić na 2 sposoby:

1. Najprościej jest usunąć zewnętrzną kontrolę. Dzięki temu nigdy nie sprawdzamy wartości helper poza zsynchronizowanym blokiem.
2. Zadeklaruj helper jako volatile. Dzięki tej jednej niewielkiej zmianie kod z przykładu J-3 będzie działać prawidłowo w języku Java 1.5 i nowszych. (Możesz poświęcić chwilę, aby przekonać się, że to prawda).

Oto kolejny przykład działania 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
        }
    }
}

Jeśli w przypadku useValues() wątek 2 nie zaobserwował jeszcze aktualizacji do vol1, nie może wiedzieć, czy ustawiono już data1 lub data2. Gdy zobaczy aktualizację do vol1, będzie wiedzieć, że można bezpiecznie uzyskać dostęp do data1 i prawidłowo odczytać dane bez ryzyka wyścigu. Nie może jednak przyjąć żadnych założeń dotyczących data2, ponieważ ten zapis został wykonany po zapisie nietrwałym.

Pamiętaj, że nie można używać volatile, aby zapobiec zmianie kolejności innych dostępów do pamięci, które ze sobą konkurują. Nie ma gwarancji, że wygeneruje instrukcję bariery pamięci maszynowej. 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 zrobić

W C/C++ preferuj klasy synchronizacji C++11, takie jak std::mutex. Jeśli nie, użyj odpowiednich operacji pthread. Obejmują one odpowiednie bariery pamięci, które zapewniają prawidłowe (sekwencyjnie spójne, chyba że określono inaczej) i wydajne działanie na wszystkich wersjach platformy Androida. Pamiętaj, aby używać ich prawidłowo. Pamiętaj na przykład, że oczekiwanie na zmienną warunkową może zostać przerwane bez sygnału, dlatego powinno być umieszczone 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 wymaga pojedynczej operacji atomowej i często kosztuje mniej niż pojedynczy brak w pamięci podręcznej, jeśli nie ma rywalizacji, więc nie zaoszczędzisz wiele, zastępując wywołania muteksu operacjami atomowymi. Projektowanie nietrywialnych struktur danych bez blokad wymaga znacznie większej uwagi, aby operacje wyższego poziomu na strukturze danych były atomowe (jako całość, a nie tylko ich jawnie atomowe części).

Jeśli używasz operacji niepodzielnych, rozluźnienie kolejności za pomocą memory_order… lub lazySet() może przynieść korzyści pod względem wydajności, ale wymaga głębszego zrozumienia, niż do tej pory przekazaliśmy. Okazuje się, że duża część istniejącego kodu, który ich używa, zawiera błędy. W miarę możliwości unikaj takich sytuacji. Jeśli Twój przypadek użycia nie pasuje dokładnie do żadnego z tych opisanych w następnej sekcji, upewnij się, że jesteś ekspertem lub skonsultuj się z ekspertem.

Unikaj używania volatile do komunikacji między wątkami w C/C++.

W języku Java problemy z współbieżnością najlepiej rozwiązywać, używając odpowiedniej klasy narzędziowej z pakietu java.util.concurrent. Kod jest dobrze napisany i przetestowany na SMP.

Być może najbezpieczniejszym rozwiązaniem jest ustawienie obiektów jako niezmiennych. Obiekty z klas takich jak String i Integer w języku Java przechowują dane, których nie można zmienić po utworzeniu obiektu, co eliminuje możliwość wystąpienia wyścigu danych w przypadku tych obiektów. Książka Effective Java, 2nd Ed. zawiera szczegółowe instrukcje w rozdziale „Item 15: Minimize Mutability”. Zwróć szczególną uwagę na znaczenie deklarowania pól Java jako „final” (Bloch).

Nawet jeśli obiekt jest niezmienny, pamiętaj, że przekazanie go do innego wątku bez żadnej synchronizacji jest wyścigiem danych. W przypadku Javy może to być czasami dopuszczalne (patrz poniżej), ale wymaga dużej ostrożności i prawdopodobnie spowoduje, że kod będzie niestabilny. Jeśli nie jest to bardzo ważne dla wydajności, dodaj deklarację volatile. W C++ przekazywanie wskaźnika lub odwołania do niezmiennego obiektu bez odpowiedniej synchronizacji, podobnie jak w przypadku każdego wyścigu danych, jest błędem. W takim przypadku istnieje duże prawdopodobieństwo, że dojdzie do sporadycznych awarii, ponieważ np. wątek odbierający może zobaczyć niezainicjowany wskaźnik tabeli metod z powodu zmiany kolejności zapisu.

Jeśli nie można użyć istniejącej klasy biblioteki ani klasy niezmiennej, należy użyć instrukcji synchronized w języku Java lub lock_guard / unique_lock w języku C++, aby chronić dostęp do każdego pola, do którego może uzyskać dostęp więcej niż 1 wątek. Jeśli w Twojej sytuacji muteksy się nie sprawdzą, zadeklaruj pola współdzielone jako volatile lub atomic, ale musisz bardzo uważać, aby zrozumieć interakcje między wątkami. Te deklaracje nie uchronią Cię przed typowymi błędami programowania współbieżnego, ale pomogą Ci uniknąć tajemniczych awarii związanych z optymalizacją kompilatorów i problemami z SMP.

Należy unikać „publikowania” odwołania do obiektu, czyli udostępniania go innym wątkom, w jego konstruktorze. Jest to mniej istotne w przypadku C++ lub jeśli zastosujesz się do naszej porady „żadnych wyścigów danych” w przypadku Javy. Zawsze warto jednak o tym pamiętać, a staje się to kluczowe, jeśli kod Java jest uruchamiany w innych kontekstach, w których model zabezpieczeń Java ma znaczenie, a niezaufany kod może spowodować wyścig danych, uzyskując dostęp do „wyciekającego” odwołania do obiektu. Jest to również bardzo ważne, jeśli zignorujesz nasze ostrzeżenia i użyjesz niektórych technik opisanych w następnej sekcji. Szczegółowe informacje znajdziesz w artykule (Safe Construction Techniques in Java).

Więcej informacji o słabych kolejnościach pamięci

C++11 i nowsze wersje zapewniają wyraźne mechanizmy łagodzenia gwarancji spójności sekwencyjnej w przypadku programów bez wyścigów danych. Argumenty memory_order_relaxed, memory_order_acquire (tylko wczytywanie) i memory_order_release (tylko zapisywanie) dla operacji niepodzielnych zapewniają ściśle słabsze gwarancje niż domyślny, zwykle niejawny argument memory_order_seq_cst. memory_order_acq_rel zapewnia gwarancje memory_order_acquire i memory_order_release w przypadku niepodzielnych operacji odczytu, modyfikacji i zapisu. Właściwość memory_order_consume nie jest jeszcze wystarczająco dobrze określona ani wdrożona, aby była przydatna, i na razie należy ją ignorować.

Metody lazySet w Java.util.concurrent.atomic są podobne do pamięci memory_order_release w C++. Zwykłe zmienne Javy są czasami używane jako zamiennik dostępu memory_order_relaxed, chociaż 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.

Zasadniczo należy ich unikać, chyba że istnieją istotne powody związane z wydajnością, aby ich używać. W przypadku architektur maszynowych o słabym porządkowaniu, takich jak ARM, ich użycie pozwala zwykle zaoszczędzić kilkadziesiąt cykli maszynowych na każdą operację niepodzielną. W przypadku x86 wzrost wydajności jest ograniczony do operacji zapisu i prawdopodobnie będzie mniej zauważalny. Może to być nieco sprzeczne z intuicją, ale korzyści mogą się zmniejszać wraz ze wzrostem liczby rdzeni, ponieważ system pamięci staje się czynnikiem ograniczającym.

Pełna semantyka słabo uporządkowanych operacji niepodzielnych 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ą) ograniczonej przez pozyskanie i zwolnienie blokady. Oznacza to, że 2 operacje zapisu memory_order_relaxed mogą stać się widoczne w niewłaściwej kolejności, nawet jeśli są rozdzielone sekcją krytyczną.
• Zwykła zmienna Java, gdy jest używana jako wspólny licznik, może wydawać się innemu wątkowi malejąca, mimo że jest zwiększana tylko przez jeden inny wątek. Nie dotyczy to jednak operacji niepodzielnych w C++memory_order_relaxed.

Mając to na uwadze, przedstawiamy kilka idiomów, które wydają się obejmować wiele przypadków użycia słabo uporządkowanych operacji atomowych. Wiele z nich dotyczy tylko języka C++.

Dostęp do treści niezwiązanych z wyścigami

Dość często zmienna jest niepodzielna, ponieważ czasami jest odczytywana jednocześnie z zapisem, ale nie wszystkie dostępy mają ten problem. Na przykład zmienna może wymagać niepodzielności, ponieważ jest odczytywana poza sekcją krytyczną, ale wszystkie aktualizacje są chronione przez blokadę. W takim przypadku odczyt, który jest chroniony przez tę samą blokadę, nie może powodować wyścigu, ponieważ nie może być równoczesnych zapisów. W takim przypadku dostęp bez wyścigu (w tym przypadku wczytywanie) można oznaczyć adnotacją memory_order_relaxed bez wpływu na poprawność kodu C++. Implementacja blokady wymusza już wymagane porządkowanie pamięci w odniesieniu do dostępu przez inne wątki, a memory_order_relaxed określa, że w przypadku dostępu niepodzielnego nie trzeba wymuszać żadnych dodatkowych ograniczeń porządkowania.

W języku Java nie ma odpowiednika tej funkcji.

Wynik nie jest uznawany za poprawny

Gdy używamy wyścigu tylko do wygenerowania wskazówki, zwykle nie trzeba wymuszać żadnego porządkowania pamięci. Jeśli wartość jest niewiarygodna, nie możemy też wiarygodnie wykorzystać wyniku do wyciągania wniosków na temat innych zmiennych. Dlatego nie ma problemu, jeśli kolejność pamięci nie jest gwarantowana, a operacja wczytywania jest dostarczana z argumentem memory_order_relaxed.

Typowym przykładem jest użycie funkcji compare_exchange w C++ do niepodzielnego zastąpienia x przez f(x). Początkowe wczytywanie x w celu obliczenia f(x) nie musi być niezawodne. Jeśli popełnimy błąd, compare_exchange się nie powiedzie i spróbujemy ponownie. W przypadku początkowego wczytywania x można użyć argumentu memory_order_relaxed. Istotne jest tylko porządkowanie pamięci dla rzeczywistego compare_exchange.

Dane zmodyfikowane niepodzielnie, ale nieprzeczytane

Czasami dane są modyfikowane równolegle przez wiele wątków, ale nie są sprawdzane, dopóki obliczenia równoległe nie zostaną zakończone. Dobrym przykładem jest licznik, który jest niepodzielnie zwiększany (np. za pomocą fetch_add() w C++ lub atomic_fetch_add_explicit() w C) przez wiele wątków równolegle, ale wynik tych wywołań jest zawsze ignorowany. Wynikowa wartość jest odczytywana dopiero na końcu, po zakończeniu wszystkich aktualizacji.

W takim przypadku nie można stwierdzić, czy dostęp do tych danych został zmieniony, więc kod C++ może używać argumentu memory_order_relaxed.

Typowym przykładem są proste liczniki zdarzeń. Ponieważ jest to tak powszechne, warto poczynić kilka obserwacji na temat tego przypadku:

• Użycie 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 linii pamięci podręcznej, w której znajduje się licznik. Powoduje to brak 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 między wątkami, znacznie szybciej jest unikać aktualizowania udostępnionego licznika za każdym razem, na przykład przez użycie liczników lokalnych wątków i zsumowanie ich na końcu.
• Tę technikę można połączyć z poprzednią sekcją: można jednocześnie odczytywać przybliżone i niewiarygodne wartości podczas ich aktualizowania, przy czym wszystkie operacje korzystają z memory_order_relaxed. Ważne jest jednak, aby traktować uzyskane wartości jako całkowicie niewiarygodne. To, że liczba została zwiększona raz, nie oznacza, że inny wątek osiągnął punkt, w którym nastąpiło zwiększenie. Zamiast tego przyrost mógł zostać zmieniony we wcześniejszym kodzie. (Podobnie jak w przypadku wspomnianym wcześniej, C++ gwarantuje, że drugie wczytanie takiego licznika nie zwróci wartości mniejszej niż wcześniejsze wczytanie w tym samym wątku. chyba że licznik się przepełnił).
• Często można znaleźć kod, który próbuje obliczyć przybliżone wartości liczników, wykonując pojedyncze odczyty i zapisy (niekoniecznie niepodzielne), ale nie wykonuje przyrostu jako całości niepodzielnej. Zwykle argumentuje się, że jest to „wystarczająco blisko” w przypadku liczników wydajności lub podobnych zastosowań. Zwykle nie. Gdy aktualizacje są wystarczająco częste (co prawdopodobnie Cię interesuje), zwykle tracona jest duża część zliczeń. Na urządzeniu z 4-rdzeniowym procesorem może zostać utracona ponad połowa zliczeń. (Proste ćwiczenie: utwórz scenariusz z 2 wątkami, w którym licznik jest aktualizowany milion razy, ale jego ostateczna wartość wynosi 1).

Prosta komunikacja dotycząca zgłaszania treści

Operacja zapisu memory_order_release (lub operacja odczytu, modyfikacji i zapisu) gwarantuje, że jeśli następnie operacja odczytu memory_order_acquire (lub operacja odczytu, modyfikacji i zapisu) odczyta zapisaną wartość, będzie ona również obserwować wszystkie operacje zapisu (zwykłe lub niepodzielne), które poprzedzały operację zapisu memory_order_release. Z kolei żadne operacje wczytywania poprzedzające memory_order_release nie będą obserwować żadnych operacji zapisu, które nastąpiły po wczytaniu memory_order_acquire. W odróżnieniu od memory_order_relaxed umożliwia to używanie takich operacji niepodzielnych do przekazywania informacji o postępach jednego wątku do innego.

Możemy na przykład przepisać powyższy przykład blokady z podwójnym sprawdzeniem w języku C++ w ten sposób:

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;
    }
};

Operacje acquire load i release store zapewniają, że jeśli zobaczymy niepustą wartość helper, zobaczymy też jej prawidłowo zainicjowane pola. Uwzględniliśmy też wcześniejszą obserwację, że obciążenia niezwiązane z wyścigami mogą używać memory_order_relaxed.

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

W obu przypadkach nasze dostrajanie wydajności koncentrowało się na ścieżce inicjowania, która raczej nie ma kluczowego znaczenia dla wydajności. Bardziej czytelny kompromis może wyglądać tak:

    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 z domyślnych, spójnych sekwencyjnie operacji na wolnej ś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 architekturach obsługiwanych obecnie przez Androida co zwykłe (sekwencyjnie spójne) odwołanie do helper. Najbardziej korzystną optymalizacją może być wprowadzenie myHelper, aby wyeliminować drugie wczytywanie, chociaż przyszły kompilator może to zrobić automatycznie.

Porządkowanie typu acquire/release nie zapobiega widocznemu opóźnieniu operacji zapisu i nie gwarantuje, że operacje zapisu będą widoczne dla innych wątków w spójnej kolejności. W rezultacie nie obsługuje on skomplikowanego, ale dość powszechnego wzorca kodowania, którego przykładem jest algorytm wzajemnego wykluczania Dekkera: wszystkie wątki najpierw ustawiają flagę wskazującą, że chcą coś zrobić. Jeśli wątek t zauważy, że żaden inny wątek nie próbuje nic zrobić, może bezpiecznie kontynuować, wiedząc, że nie będzie żadnych zakłóceń. Żaden inny wątek nie będzie mógł kontynuować, ponieważ flaga t jest nadal ustawiona. To nie zadziała, jeśli flaga jest dostępna przy użyciu kolejności pobierania/zwalniania, ponieważ nie zapobiega to późniejszemu udostępnieniu flagi wątku innym osobom, po tym jak błędnie kontynuowały działanie. Domyślna wartość memory_order_seq_cst uniemożliwia to.

Pola niezmienne

Jeśli pole obiektu jest inicjowane przy pierwszym użyciu, a potem nigdy nie jest zmieniane, można je zainicjować, a następnie odczytać przy użyciu dostępu o słabym uporządkowaniu. W C++ można ją zadeklarować jako atomic i uzyskać do niej dostęp za pomocą memory_order_relaxed, a w Javie można ją zadeklarować bez volatile i uzyskać do niej dostęp bez specjalnych środków. Wymaga to spełnienia wszystkich tych warunków:

• Wartość pola powinna wskazywać, czy zostało ono już zainicjowane. Aby uzyskać dostęp do pola, test szybkiej ścieżki i wartość zwracana powinny odczytywać pole tylko raz. W przypadku Javy ten drugi jest niezbędny. Nawet jeśli test pola wykaże, że jest ono zainicjowane, drugie wczytanie może odczytać wcześniejszą niezainicjowaną wartość. W C++ reguła „odczytaj raz” jest jedynie dobrą praktyką.
• Zarówno inicjowanie, jak i kolejne wczytywania muszą być niepodzielne, co oznacza, że częściowe aktualizacje nie powinny być widoczne. W przypadku Javy pole nie powinno być typu long ani double. W przypadku C++ wymagane jest przypisanie niepodzielne. Konstruowanie go na miejscu nie zadziała, ponieważ konstrukcja atomic nie jest niepodzielna.
• Powtarzające się inicjalizacje muszą być bezpieczne, ponieważ wiele wątków może jednocześnie odczytywać niezainicjowaną wartość. W C++ wynika to zwykle z wymogu „trywialnej kopiowalności” nałożonego na wszystkie typy niepodzielne. Typy z zagnieżdżonymi wskaźnikami własnymi wymagałyby cofnięcia przydziału w konstruktorze kopiującym i nie byłyby trywialnie kopiowalne. W przypadku Javy akceptowane są niektóre typy referencyjne:
• Odwołania w języku Java są ograniczone do typów niezmiennych zawierających tylko pola final. Konstruktor typu niezmiennego nie powinien publikować odwołania do obiektu. W tym przypadku reguły pól finalnych w języku Java zapewniają, że jeśli czytnik zobaczy odwołanie, zobaczy również zainicjowane pola finalne. C++ nie ma odpowiednika tych reguł, a wskaźniki do obiektów będących własnością są niedopuszczalne również z tego powodu (oprócz naruszenia wymagań dotyczących „trywialnego kopiowania”).

Notatki o zamknięciu

Chociaż ten dokument nie tylko powierzchownie opisuje temat, nie jest on zbyt szczegółowy. To bardzo szeroki i głęboki temat. Obszary, które warto zbadać:

• Rzeczywiste modele pamięci Java i C++ są wyrażone w postaci relacji happens-before, która określa, kiedy 2 działania na pewno wystąpią w określonej kolejności. Definiując wyścig danych, nieformalnie mówiliśmy o 2 operacjach dostępu do pamięci, które odbywają się „jednocześnie”. Oficjalnie oznacza to, że żadne z nich nie następuje przed drugim. Warto poznać rzeczywiste definicje relacji happens-before i synchronizes-with w modelu pamięci Javy lub C++. Chociaż intuicyjne pojęcie „jednocześnie” jest ogólnie wystarczające, te definicje są pouczające, zwłaszcza jeśli rozważasz użycie słabo uporządkowanych operacji niepodzielnych w C++. (Obecna specyfikacja Javy definiuje lazySet() tylko bardzo nieformalnie).
• Dowiedz się, co kompilatory mogą, a czego nie mogą robić podczas zmiany kolejności kodu. (Specyfikacja JSR-133 zawiera kilka świetnych przykładów legalnych przekształceń, które prowadzą do nieoczekiwanych wyników).
• Dowiedz się, jak pisać niezmienne klasy w językach Java i C++. (To coś więcej niż tylko „nie zmieniaj niczego po utworzeniu”).
• Zapoznaj się z zaleceniami w sekcji dotyczącej równoczesności w książce Effective Java, wydanie 2. (Na przykład unikaj wywoływania metod, które mają zostać zastąpione w zsynchronizowanym 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 dotyczących równoczesności, takich jak @ThreadSafe i @GuardedBy (z net.jcip.annotations).

Sekcja Dodatkowe materiały w załączniku zawiera linki do dokumentów i witryn, które pomogą Ci lepiej zrozumieć te tematy.

Dodatek

Implementowanie magazynów synchronizacji

(Większość programistów nie będzie musiała tego implementować, ale dyskusja jest pouczająca).

W przypadku małych typów wbudowanych, takich jak int, i sprzętu obsługiwanego przez Androida zwykłe instrukcje wczytywania i zapisywania zapewniają, że zapis będzie widoczny w całości lub wcale dla innego procesora wczytującego tę samą lokalizację. Dzięki temu podstawowe pojęcie „niepodzielności” jest dostępne bezpłatnie.

Jak widzieliśmy wcześniej, to nie wystarczy. Aby zapewnić spójność sekwencyjną, musimy też zapobiegać zmianie kolejności operacji i zadbać o to, aby operacje na pamięci były widoczne dla innych procesów w spójnej kolejności. Okazuje się, że ta druga opcja jest automatyczna na sprzęcie obsługującym Androida, pod warunkiem że dokonamy rozsądnych wyborów w przypadku pierwszej opcji, więc w dużej mierze ją tutaj ignorujemy.

Kolejność operacji na pamięci jest zachowywana przez uniemożliwienie zmiany kolejności przez kompilator i sprzęt. Tutaj skupimy się na tym drugim.

Porządkowanie pamięci w architekturach ARMv7, x86 i MIPS jest wymuszane za pomocą instrukcji „fence”, które w przybliżeniu zapobiegają wyświetlaniu instrukcji następujących po instrukcji „fence” przed instrukcjami, które ją poprzedzają. (Są one również powszechnie nazywane instrukcjami „bariery”, ale może to prowadzić do pomyłki z barierami w stylu pthread_barrier, które robią znacznie więcej). Dokładne znaczenie instrukcji barier jest dość skomplikowanym tematem, który musi uwzględniać sposób, w jaki gwarancje zapewniane przez wiele różnych rodzajów barier współdziałają ze sobą, oraz sposób, w jaki łączą się z innymi gwarancjami kolejności zwykle zapewnianymi przez sprzęt. To jest ogólne omówienie, więc nie będziemy się zagłębiać w szczegóły.

Najbardziej podstawowy rodzaj gwarancji kolejności jest zapewniany przez operacje atomowe memory_order_acquire i memory_order_release w C++: operacje na pamięci poprzedzające operację zapisu typu release powinny być widoczne po operacji odczytu typu acquire. W przypadku ARMv7 jest to wymuszane przez:

• poprzedzenie instrukcji zapisu odpowiednią instrukcją bariery. Zapobiega to zmianie kolejności wszystkich wcześniejszych dostępów do pamięci za pomocą instrukcji zapisu. (Uniemożliwia to również niepotrzebnie zmianę kolejności za pomocą późniejszej instrukcji zapisu).
• Po instrukcji wczytywania należy umieścić odpowiednią instrukcję bariery, aby zapobiec zmianie kolejności wczytywania przy kolejnych dostępach. (oraz ponownie niepotrzebne porządkowanie, przynajmniej w przypadku wcześniejszych wczytań).

Razem wystarczą do uporządkowania operacji pobierania/zwalniania w C++. Są one niezbędne, ale niewystarczające w przypadku sekwencyjnie spójnych atomic w języku Java volatile lub C++.

Aby zobaczyć, czego jeszcze potrzebujemy, rozważmy fragment algorytmu Dekkera, o którym krótko wspomnieliśmy wcześniej. flag1 i flag2 to zmienne C++ atomic lub Java volatile, które początkowo mają wartość false.

Spójność sekwencyjna oznacza, że jedno z przypisań do flagn musi zostać wykonane jako pierwsze i być widoczne dla testu w drugim wątku. Dlatego nigdy nie zobaczymy, jak te wątki wykonują „critical-stuff” jednocześnie.

Jednak bariery wymagane do uporządkowania typu acquire-release dodają bariery tylko na początku i na końcu każdego wątku, co w tym przypadku nie pomaga. Musimy też zadbać o to, aby w przypadku, gdy po zapisie volatile/atomic następuje wczytanie volatile/atomic, nie doszło do zmiany kolejności tych operacji. Zwykle jest to wymuszane przez dodanie bariery nie tylko przed sekwencyjnie spójnym zapisem, ale też po nim. (Jest to znacznie silniejsze niż wymagane, ponieważ ta bariera zwykle porządkuje wszystkie wcześniejsze dostępy do pamięci w stosunku do wszystkich późniejszych).

Zamiast tego możemy powiązać dodatkową barierę z sekwencyjnie spójnymi wczytaniami. Ponieważ sklepy są rzadziej używane, opisana przez nas konwencja jest bardziej powszechna i używana na Androidzie.

Jak widzieliśmy we wcześniejszej sekcji, między tymi 2 operacjami musimy wstawić barierę zapisu/odczytu. Kod wykonywany w maszynie wirtualnej w celu uzyskania dostępu do pamięci nietrwałej będzie wyglądał mniej więcej tak:

Rzeczywiste architektury maszyn zwykle zapewniają wiele typów barier, które porządkują różne typy dostępu i mogą mieć różne koszty. Wybór między nimi jest subtelny i wpływa na niego potrzeba zapewnienia, że zapisy są widoczne dla innych rdzeni w spójnej kolejności, a kolejność pamięci narzucona przez kombinację wielu barier jest prawidłowo skomponowana. Więcej informacji znajdziesz na stronie Uniwersytetu Cambridge, na której zebrano mapowania operacji niepodzielnych na rzeczywiste procesory.

W niektórych architekturach, zwłaszcza x86, bariery „acquire” i „release” są niepotrzebne, ponieważ sprzęt zawsze domyślnie wymusza wystarczające uporządkowanie. Dlatego na x86 generowana jest tylko ostatnia bariera (3). Podobnie w przypadku x86 operacje niepodzielnego odczytu, modyfikacji i zapisu domyślnie zawierają silną barierę. Dlatego nie wymagają żadnych ogrodzeń. W przypadku ARMv7 wymagane są wszystkie omówione powyżej bariery.

ARMv8 udostępnia instrukcje LDAR i STLR, które bezpośrednio wymuszają wymagania dotyczące zmiennych volatile w Javie lub sekwencyjnie spójnych operacji wczytywania i zapisywania w C++. Pozwala to uniknąć wspomnianych wyżej niepotrzebnych ograniczeń dotyczących zmiany kolejności. 64-bitowy kod Androida na ARM używa tych instrukcji. Zdecydowaliśmy się skupić na umieszczaniu barier w ARMv7, ponieważ pozwala to lepiej zrozumieć rzeczywiste wymagania.

Więcej informacji

strony internetowe i dokumenty, które zawierają bardziej szczegółowe lub obszerne informacje; Artykuły o bardziej ogólnym charakterze znajdują się bliżej góry listy.

Shared Memory Consistency Models: A Tutorial

Ten artykuł, napisany w 1995 roku przez Adve i Gharachorloo, to dobry punkt wyjścia, jeśli chcesz dowiedzieć się więcej o modelach spójności pamięci.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf

Bariery pamięci

Nice little article summarizing the issues.
https://en.wikipedia.org/wiki/Memory_barrier

Podstawowe informacje o wątkach

Wprowadzenie do programowania wielowątkowego w językach C++ i Java, Hans Boehm. Omówienie wyścigów danych i podstawowych metod synchronizacji.
http://www.hboehm.info/c++mm/threadsintro.html

Java Concurrency In Practice

Ta książka, opublikowana w 2006 roku, szczegółowo omawia wiele różnych tematów. Pozycja zdecydowanie zalecana dla każdego, kto pisze kod wielowątkowy w języku Java.
http://www.javaconcurrencyinpractice.com

JSR-133 (Java Memory Model) FAQ

Przystępne wprowadzenie do modelu pamięci Javy, w tym wyjaśnienie synchronizacji, zmiennych volatile i konstrukcji pól final. (Nieco przestarzały, zwłaszcza w części dotyczącej innych języków).
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html

Validity of Program Transformations in the Java Memory Model

Dość techniczne wyjaśnienie pozostałych problemów z modelem pamięci Javy. Te problemy nie dotyczą programów, w których nie występuje wyścig 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. W dolnej części strony znajduje się sekcja „Memory Consistency Properties” (Właściwości spójności pamięci), która wyjaśnia gwarancje zapewniane przez różne klasy.
java.util.concurrent Podsumowanie pakietu

Java Theory and Practice: Safe Construction Techniques in Java

W tym artykule szczegółowo omówiono zagrożenia związane z wyciekiem odwołań podczas tworzenia obiektów i podano wytyczne dotyczące konstruktorów bezpiecznych wątkowo.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html

Java Theory and Practice: Managing Volatility

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

Deklaracja „Double-Checked Locking is Broken”

Szczegółowe wyjaśnienie Billa Pugha dotyczące różnych sposobów, w jakie blokowanie z podwójnym sprawdzeniem jest uszkodzone bez volatile lub atomic. Dotyczy to języków C/C++ i Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

[ARM] Barrier Litmus Tests and Cookbook

Omówienie problemów z ARM SMP zilustrowane krótkimi fragmentami kodu ARM. Jeśli przykłady na tej stronie są dla Ciebie zbyt ogólne lub chcesz zapoznać się z formalnym opisem instrukcji DMB, przeczytaj ten artykuł. Opisuje też instrukcje używane do barier pamięci w kodzie wykonywalnym (może być przydatne, jeśli generujesz kod na bieżąco). Pamiętaj, że jest to starsze niż ARMv8, który obsługuje też dodatkowe instrukcje porządkowania pamięci i przeszedł na nieco silniejszy model pamięci. (Szczegółowe informacje znajdziesz w dokumencie „ARM® Architecture Reference Manual ARMv8, for ARMv8-A architecture profile”:
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 grafikę 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 klauzula 29 („Atomic operations library”)

Wersja robocza standardu funkcji operacji niepodzielnych w C++. Ta wersja jest zbliżona do standardu C++14, który zawiera niewielkie zmiany w tym obszarze w porównaniu z C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(wprowadzenie: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf)

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

Wersja robocza standardu funkcji operacji atomowych 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

Mapowanie C/C++11 na procesory (University of Cambridge)

Zbiór tłumaczeń operacji atomowych C++ na różne popularne listy instrukcji procesora autorstwa Jaroslava Sevcika i Petera Sewella.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

Algorytm Dekkera

„Pierwsze znane poprawne rozwiązanie problemu wzajemnego wykluczania w programowaniu współbieżnym”. Artykuł w Wikipedii zawiera pełny algorytm wraz z omówieniem, jak należałoby go zaktualizować, aby działał z nowoczesnymi kompilatorami optymalizującymi i sprzętem SMP.
https://en.wikipedia.org/wiki/Dekker's_algorithm

Komentarze dotyczące ARM i Alpha oraz zależności adresów

E-mail Catalin Marinas na liście adresowej arm-kernel. Zawiera dobre podsumowanie zależności adresów i kontroli.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html

What Every Programmer Should Know About Memory

Bardzo długi i szczegółowy artykuł Ulricha Dreppera o różnych typach pamięci, zwłaszcza o pamięciach podręcznych procesora.
http://www.akkadia.org/drepper/cpumemory.pdf

Rozumowanie dotyczące modelu pamięci ARM o słabej spójności

Ten artykuł został napisany przez Chonga i Ishtiaqa z firmy ARM, Ltd. Opisuje on model pamięci ARM SMP w rygorystyczny, ale przystępny sposób. Definicja „obserwowalności” użyta w tym miejscu pochodzi z tego artykułu. Przypominamy, że jest to starsze niż ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711

The JSR-133 Cookbook for Compiler Writers

Doug Lea napisał ten artykuł jako uzupełnienie dokumentacji JSR-133 (Java Memory Model). Zawiera on początkowy zestaw wytycznych dotyczących implementacji modelu pamięci Javy, który był używany przez wielu autorów kompilatorów i jest nadal powszechnie cytowany i prawdopodobnie przydatny. Niestety 4 omówione tu rodzaje barier nie pasują do architektur obsługiwanych przez Androida, a powyższe mapowania C++11 są teraz lepszym źródłem precyzyjnych przepisów, nawet w przypadku Javy.
http://g.oswego.edu/dl/jmm/cookbook.html

x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors

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