W jednym z poprzednich wpisów pisałem o problemie publikacji obiektu w programie wielowątkowym. Podałem wtedy bardzo prosty przykład kodu w pseudo asemblerze. Z kolei w języku C++ publikacja mogła by wyglądać następująco:
Jak już wiemy abyśmy mieli gwarancje że object będzie dostępny jak tylko zmienna gotowe zmieni wartość na true, musimy upewnić się, że zapisy nie zostaną przeniesione przed inne zapisy i odczyty nie zostaną przeniesione za inne odczyty. W przypadku języków C# czy Java coś takiego możemy wymusić za pomocą deklaracji gotowe jako volatile. Niestety albo na szczęście standard C++ nic takiego nie przewiduje. W takim razie co należy zrobić aby uzyskać możliwość publikowania obiektu?
Jeśli nasz program będzie uruchamiany wyłącznie na procesorach x86 możemy zadeklarować gotowe jako volatile. To w zupełności wystarczy, gdyż model tej architektury jest stosunkowo mocny (Po szczegóły odsyłam do moich poprzednich wpisów).
Jeśli nasz program będziemy kompilować wyłącznie w Visual C++ 2005 lub nowszym, podobnie jak w poprzednich punkcie mamy gwarancje że volatile zadziała. Także dla kompilacji pod IA64. Jest to specjalna właściwość kompilatora Microsoftu.
W pozostałych przypadkach musimy albo opakować odwołania do gotowe w sekcję krytyczną albo użyć specjalistycznej biblioteki, z funkcją która wymuszą odpowiednie memory barrier. (Co prowadzi do oszczędności czasu procesora w stosunku do sekcji krytycznej).
Odnosząc się do słówka volatile pozostają jeszcze dwa pytania. Czy w takim razie volatile jest prawie całkiem bezużyteczne? oraz co o volatile mówi przyszły standard C++ 0x? Na te pytania postaram się odpowiedzieć, w któryś z kolejnych postów.
Miesiąc temu poruszyłem problem “przestawiania operacji odczytu i zapisu” w procesorach z rodziny x86. Dzisiaj postaram się rozszerzyć ten temat na inne architektury. W tym wpisie będę odnosił się przede wszystkim do dokumentu Memory Barriers: a Hardware View for Software Hackers. Najbardziej istotny jest tutaj rozdział 7 i tabela 5 na stronie 16. Znajduje się tam porównanie różnych architektur pod kątem możliwych zamian kolejności operacji odczytu i zapisu. Nie zamierzam tutaj tłumaczyć całego rozdziału, skupię się tylko na kilku ważnych faktach:
Istnieją architektury ze zdecydowanie luźniejszym modelem pamięci niż ten w procesorach x86.
Niektóre architektury pozwalają na wybranie jednego z kilku możliwych modeli pamięci przez system operacyjny.
Niespójność widoku pamięci różnych wątków może wywodzić się nie tylko z istnienia write buffera ale także np z luźniejszego modelu synchronizacji pamięci cache.
Wykonanie instrukcji atomowej nie implikuje uzyskania “total order”
Do wymuszania zachowania kolejności określonych operacji służą instrukcje typu “memory barrier”. Architektury o luźniejszym modelu oferują przeważnie kilka różnych instrukcji tego typu do uzyskania różnego poziomu spójności widoków pamięci.
Ten kto obejrzał film z poprzedniego wpisu wie, że model pamięci x86 pozwala na bezpieczne publikowanie obiektu. Przez publikację obiektu należy rozumieć sytuację:
mov a, r1;
mov gotowe, 1;
W powyższych przykładach a i gotowe to zmienne w pamięci, r1 to rejestr procesora. Zakładamy, że obiekt gotowe przed rozpoczęciem wykonywania tego kodu zawierał wartość 0. Zakładamy też, że przypisanie wartości 1 do obiektu gotowe oznacza, że obiekt a zawiera już nową poprawną wartość i ta wartość może być odczytana przez inny wątek. W takim wypadku inny wątek programu może co jakiś czas odczytywać wartość gotowe aż odczyta wartość 1. Wtedy wie że obiekt a zawiera poprawną wartość i może ją odczytać. Niestety takie rozwiązanie nie zadziała np. na procesorach z rodziny Power PC. Dla nich proces publikacji powinien wyglądać tak:
mov a, r1;
lwsync; //memory barrier
mov gotowe, 1;
W następnym poście opiszę jak informacje zawarte w tym wpisie odnoszą się do publikowania obiektów w C++.
We wcześniejszych postach o widoku pamięci wątku i volatile wspomniałem o tym, że istnieje coś takiego jak write buffer. Jego zadaniem jest optymalizować zapis danych obliczonych przez procesor. Bez niego wydajność naszych maszyn byłaby dużo niższa. Niestety jego obecność powoduje zerwanie “sequential consistency”. Przykładowo sekwencja instrukcji:
a = r1; //zapis do pamięci
r2 = b; //odczyt z pamięci
(gdzie a i b to zmienne zlokalizowane w pamięci a r1, r2 to rejestry procesory) może być widziana na zewnątrz jako:
r2 = b;
a = r1;
Zapis został przeniesiony za instrukcję odczytu, gdyż procesor optymalizuje wykonanie programu poprzez użycie write buffer. Takie zamiany instrukcji nazywamy “memory ordering”. Optymalizując wielowątkowe programy na niskim poziomie powinniśmy wiedzieć jakie zmiany w kolejności odczytu i zapisu są możliwe na danym procesorze. Musimy także wiedzieć jak wymusić wykonanie instrukcji w określonym porządku tam gdzie jest to wymagane.
Poniżej znajduje się bardzo ciekawy wykład przedstawiony przez pracownika Intela. Tematem jest model pamięci architektury IA-32 uściślony przez Intela w 2008 roku.
Aby zrozumieć model pamięci w x86 trzeba zapamiętać i zrozumieć 8 następujących reguł:
Odczyty nie są przenoszone przed lub za inne odczyty.
Zapisy nie są przenoszone przed lub za inne zapisy.
Zapisy nie są przenoszone przed występuje przed nimi odczyty.
Odczyty mogą być przeniesione przed wcześniejsze zapisy. Nie dotyczy przypadku gdy odczyt i zapis do tyczy tej samej lokacji.
Jeśli w wieloprocesorowym systemie procesor0 zapisze 1 do lokacji x i następnie jeśli procesor1 zobaczy tą wartość i zapisze 1 do lokacji y to jeśli procesor2 zobaczy 1 w lokacji y to zobaczy też 1 w lokacji x. Zakładamy że lokacje x i y zawierały w stanie początkowym wartości 0.
Jeśli w wieloprocesorowym systemie procesor0 zapisał wartość do lokacji a, procesor1 zapisał wartość do lokacji b to dowolne inne dwa procesory zobaczą te zapisy w tej samej kolejności.
Jeśli w wieloprocesorowym systemie procesor0 wykonał operacje blokowaną (np. xchg czyli zapis i odczyt) na lokacji a i procesor1 wykonał operację blokowaną na lokacji b to dowolne dwa inne procesory zobaczą te operacje w tej samej kolejności.
Zapisy i odczyty nie są przenoszone przed lub za instrukcje blokowane.
Polecam obejrzeć dołączony film. Te zasady są tam dobrze objaśnione. W kolejnych postach opisze jak memory ordering wygląda na innych architekturach i co z tego wszystkiego wynika.
Ostatnio trafiłem na stronę bezpłatnych kursów publikowanych przez uczelnię MIT (Massachusetts Institute of Technology). Listę kursów można obejrzeć pod adresem: http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm. Gorąco polecam przejrzenie tej strony. Jest bardzo dużo różnych tematów, zarówno z dziedziny informatyki jak i innych.
Mnie szczególnie zainteresował kurs Multicore Programming Primer. Jak sama nazwa mówi jest on poświęcony programowaniu systemów wielordzeniowych. W ramach kursu dostępne są slajdy z prezentacji, video z prezentacji, przykładowe kody źródłowe programów czy quizy, które pomogą sprawdzić ile zapamiętaliśmy i zrozumieliśmy. W Multicore Programming Primer opisano m.in.:
Postawy związane z programowaniem systemów wielordzeniowych.
Procesor Cell (zawarty m.in. w konsoli PlayStation3). Procesor ten jest bardzo ciekawym przykładem, gdyż jego budowa wymusza określony sposób rozdzielania zadań na wątki czy komunikacji między wątkami. Wymaga od programisty zastanowienia się nad rzeczami, nad którym w ogóle nie trzeba zaprzątać sobie głowy pisząc program np pod Core 2 Duo czy Phenoma X4.
Języki programowania tworzone z myślą o procesorach wielordzeniowych: Cilk (rozszerzenie C) czy dość nietypowy StreamIt. Osobiście uważam że programowanie wielowątkowe powinno być integralną częścią języka, a nie dodatkiem w postaci zewnętrznych bibliotek (tak jak to jest w C++). Co więcej program jednowątkowy powinien być szczególnym przypadkiem programu wielowątkowego. Obecnie większość programów pisze się dokładnie odwrotnie.
Podstawy tworzenia kompilatorów, które automatycznie rozdzielają wykonanie kodu na wiele wątków. Ten temat szczególnie mnie zainteresował.
Windows 7 w wersji 64bit przynosi dobre wieści dla programistów aplikacji wielowątkowych i użytkowników, którzy chcieliby jak najlepiej wykorzystać swoje wielordzeniowe maszyny. W najnowszym systemie Microsoftu wbudowano mechanizm umożliwiający zarządzanie wątkami po stronie aplikacji. Oznacza to że: 1) przełączanie pomiędzy wątkami będzie szybsze i 2) aplikacja ma wpływ na to co się dzieje podczas przełączania wątków. Dla użytkownika końcowego oznacza to lepszą skalowalność programów na wiele rdzeni i możliwość uzyskania lepszej “płynności” (szczególnie przydatne np. w grach). W tej chwili najłatwiejszym sposobem wykorzystania User Mode Scheduling jest napisanie aplikacji z wykorzystaniem Concurrency runtime dostępnym w Visual Studio 2010 beta. Warto zwrócić uwagę że UMS jest dostępny tylko w 64bitowej wersji Windows 7 i Windows 2008 R2.
O volatile pisałem już w “programowaniu wielowątkowych gier w języku C++”. Niestety opis, który tam przedstawiłem jest dość pobieżny. Postanowiłem więc powrócić do tego tematu i opisać volatile dokładniej.
Tłumacząc z angielskiego volatile to “zmienny, niestabilny”. volatile w C++ jest kwalifikatorem typu a jego działanie jest określone w standardzie C++ jako: “volatile is a hint to the implementation to avoid aggressive optimization involving the object because the value of the object might be changed by means undetectable by an implementation.” Co oznacza mniej więcej że kompilator powinien zrezygnować z optymalizacji i przy każdym odwołaniu do tej zmiennej wczytać nową wartość z komórki pamięci.
Tylko czy to wystarcza aby zmienne volatile mogły służyć do synchronizacji wątków?
W tym poście opisze kwestie wykorzystania volatile do uzyskania operacji atomowych (A raczej tego że volatile z operacjami atomowymi nie ma nic wspólnego). W kolejnych wpisach przedstawię inne próby wykorzystania volatile do synchronizacji wątków.
Interesują nas operacje atomowe na liczbach całkowitych, o rozmiarze nie większym niż rejestry ogólnego przeznaczenia. Operacja atomowa to operacja, która zostaje wykonywana nieprzerwalnie dla każdego wątku, procesu. Wyobraźmy sobie dwa wątki które inkrementują zmienną a:
int a = 0;
Wątek1: a++; Wątek2: a++;
Przy stanie początkowym a wynoszącym 0 nie mamy żadnej pewności że po wykonaniu tych operacji a będzie miało wartość 2. Odwołując się do poprzedniego postu o widoku pamięci dla wątku przyczyną tego mogą być m.in optymalizacje kompilatora. Kompilator nie ma pojęcia że inny wątek też chce modyfikować tą samą zmienną. W efekcie każdy wątek może operować na lokalnej kopii zmiennej:
A co będzie jeśli zmienną a zadeklarujemy jako volatile?
Visual C++ 2005 w trybie Release z wyłączonymi optymalizacjami (-O0) instrukcję a++ przetworzył na 3 instrukcje x86 (załadowanie wartości do rejestru, inkrementacja na rejestrze, zapis do pamięci). Skoro procesor operuje na rejestrze to dalej każdy z wątków posiada własny niezsynchronizowany widok pamięci. Jak widać volatile nie wystarcza do uzyskania poprawnych operacji atomowych (Przykładowy możliwy przebieg programu przedstawiłem w “Programowanie wielowątkowych gier w języku C++”). Na szczęście coraz więcej programistów zdaje sobie z tego sprawę. Do niedawna panowała dość duża dezinformacja, która powstała głównie przez to że dla domyślnych ustawień komplacji (np Visual C++, Release -O2) instrukcja a++; była kompilowana do pojedynczej instrukcji add operującej bezpośrednio na pamięci. Na jednordzeniowych komputerach taki program wykonywał się zawsze poprawnie co mogło sprawiać wrażenie że takie konstrukcję są poprawne. Należy jednak pamiętać że
Kompilator może posłużyć się pomocniczym rejestrem do wykonania operacji. Opis volatile mówi tylko o każdorazowym pobraniu wartości z pamięci przy odwołaniu do zmiennej. Nie zabrania tymczasowego użycia rejestru.
Nawet jeśli kompilator wygeneruje instrukcję “add na pamięci” to na systemie wielordzeniowym dalej to nie jest poprawna instrukcja atomowa. Instrukcje a++; mogą być wykonane przez każdy z wątków równocześnie. Dodatkowo wynik operacji trafia najpierw do “write buffer” skąd nie jest widoczny dla innych wątków. Ze względu na wydajność procesory nie rozwiązują tych dwóch problemów automatycznie. Konieczne jest wykonanie maszynowej instrukcji “lock”, która nie jest dodawana przez żaden z kompilatorów.
Do tematu volatile i operacji atomowych powróce jeszcze w przyszłości.
Na wstępie zachęcam do przeczytania artykułu, o którym pisałem w poprzednim poście. Osobom nie zorientowanym w temacie programowania wielowątkowego znacząco ułatwi zrozumienie tego co będę chciał poniżej przedstawić.
Aby zrozumieć co oznacza “widok pamięci wątku” warto przeanalizować krótki program w języku C++:
int a;
// --- instrukcje ---
a += 2;
a += 3;
Zakładamy:
a jest zmienną, dla której została zaalokowana komórka w pamięci komputera
wartość tej komórki przed wykonaniem instrukcji (3) wynosi 0 (tzn że wartość a wynosi 0)
tylko jeden wątek wykonuje kod przedstawiony powyżej, żaden inny wątek nie modyfikuje a
rozpatrujemy program napisany w języku C++, skompilowany i uruchomiony na popularnych procesorach rodziny x86 (Athlon 64, Core 2, Pentium itp …)
Należy się zastanowić kiedy wynik instrukcji (3) zostanie zapisany do komórki pamięci komputera i dlaczego należy się tym przejmować. Są ku temu 4 powody:
Kompilator zoptymalizował kod i postanowił połączyć intrukcje (3) i (4) w jedną instrukcję a+=5; Z punktu widzenia programu w języku C++ jest to równoznaczne. W efekcie, do pamięci może nigdy nie zostać zapisana wartość 2, pojawi się dopiero wartość 5.
Kompilator postanowił zapisać wartość sumy z instrukcji (3) do rejestru procesora. Pozwoli to na zoptymalizowanie wykonania kolejnych instrukcji na zmiennej a. W końcu zapis i odczyt z rejestru jest znacznie szybszy niż odwołania do pamięci. W przedstawionym przypadku zapis do pamięci może się odbyć po wykonaniu instrukcji (3) i (4) jako skopiowanie wyniku z rejestru procesora do pamięci. Podobnie jak w pkt 1. w komórce pamięci może nastąpić zmiana bezpośrednio z wartości 0 na 5.
“Kompilator wysyła” do pamięci wynik wykonania instrukcji (3) czy to poprzez instrukcję add operującą bezpośrednio na pamięci czy to poprzez sekwencję instrukcji add na rejestrze i move czyli przeniesienia wartości z rejestru do pamięci. Problem w tym że te operacje w rzeczywistości nie powodują bezpośredniego zapisu do pamięci komputera. Procesor także posiada mechanizmy, które mają zwiększyć szybkość wykonywania programów. W rzeczywistości nowa wartość trafia najpierw do “write buffer” gdzie czeka na przesłanie dalej, podczas gdy procesor zajmuje się już wykonaniem kolejnych instrukcji. Write buffer to bardzo mały bufor pamięci. Jak tylko jest możliwość przesłania danych do cache procesora opuszczają one write buffer.
Pamięć procesora jest przeważnie znacznie wolniejsza niż sam procesor a samo przesłanie danych wiąże się z dość dużymi opóźnieniami. Z tego powodu procesor został wyposażony w zintegrowaną pamięć zwaną pamięcią cache. Ostatnio używane dane są buforowane w tej pamięci przez co znacznie skraca się ponowny czas dostępu do nich. Również z powodu optymalizacji nowe dane najpierw zostają zapisane do pamięci cache, a dopiero gdy jest taka potrzebna trafiają do pamięci RAM komputera. Na szczęście nie musimy się martwić jak to dokładnie działa. Synchronizacja pamięci cache odbywa się w całości na poziomie sprzętowym, według protokołów MESI i MOESI (w zależności od procesora). Jeśli procesor potrzebuje dane, które znajdują się w pamięci cache innego procesora to zostaną przesłane do tego pierwszego bez żadnej programowej ingerencji.
O ile o optymalizacjach kompilatora i istnieniu pamięci cache procesora wiedzą chyba prawie wszyscy programiści o tyle niewiele osób zdaje sobie sprawę z istnienia “write bruffera”. Mam takie wrażenie przeglądając kody źródłowe niektórych programów i czytając artykuły o programowaniu wielowątkowym w C++. Zwracam szczególną uwagę na to że pamięć cache to co innego niż write buffer, to pierwsze jest synchronizowane sprzętowo, to drugie jest synchronizowane programowo.
Wracając do tytułu posta. Każdy z wątków wykonywanych w ramach jednego procesu może inaczej widzieć w danym momencie pamięć komputera. Różnice wychodzą właśnie z tymczasowych wartości, które znajdują się w rejestrach czy write bufferze. Należy oczywiście zwrócić uwagę na fakt że stan pamięci cache nie wpływa na widok wątku. Jak już wcześniej napisałem synchronizacja pamięci cache odbywa się w całości sprzętowo niewidocznie dla programisty.
Dopóki korzystamy z funkcji pokroju EnterCryticalSection, InterlockedIncrement nie musimy w ogóle zdawać sobie sprawy z tego o czym tutaj napisałem. Jeśli jednak chcemy zrozumieć jak te funkcje działają, chcemy napisać podobne funkcje albo po prostu chcemy nasz program zoptymalizować warto rozumieć te mechanizmy. W następnych postach będę wielokrotnie odwoływał się do tego artykułu, żeby wyjaśnić kiedy pewne optymalizacje są poprawne a kiedy nie i dlaczego.