Programowanie współbieżne, Języki programowania, Aplikacje, Gry

Volatile a operacje atomowe w C++

Lipiec 29th, 2008 Marcin Borowiec

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.

Widok wątku na pamięć

Lipiec 15th, 2008 Marcin Borowiec

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:

  1. 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.
  2. 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.
  3. „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.
  4. 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.

Programowanie wielowątkowych gier w języku C++

Lipiec 7th, 2008 Marcin Borowiec

Dziś dodałem pierwszy artykuł do działu publikacje.

„Programowanie wielowątkowych gier w języku C++” zawiera m.in:

  • Podstawy teoretyczne dotyczące synchronizacji wątków
  • Opis jednych z wielu metod synchronizacji wątków w języku C++
  • Zwrócenie uwagi na często pojawiające się błędy w programowaniu w języku C++ (volatile, itp …).
  • Przedstawienie modelu pamięci programowania aplikacji w C++  (niezbędne do zrozumienia zasad pisania poprawnych programów)
  • Krótki zarys OpenMP
  • Uwagi dla programistów gier

Bezpośredni link do artykułu: pwgwjcpp

Co z Paper Ball?

Lipiec 6th, 2008 Marcin Borowiec

Na wstępie chciałem podziękować wszystkim osobom, które aktywnie wspierały mnie przy tworzeniu dotychczasowych wersji Paper Ball (począwszy od betatesterów, poprzez osoby, które kupiły wersję pro, po osoby, które wyraziły opinie o grze). Dzięki! Dla wszystkich zainteresowanych Paper Ball mam trzy wiadomości.

Po pierwsze: Począwszy od dzisiaj Paper Ball 2004Pro staje się w całości darmowe. Na stronie w tej chwili dostępna jest tylko wersja Pro. Użytkownicy wersji podstawowej mogą ją odinstalować i na jej miejsce zainstalować nową wersję. Paper Ball 2004Pro to 6 poziomów trudności i tryb sieciowy.

Po drugie: Nie wykluczam udostępnienia kodu źródłowego gry. Wymaga to jednak przygotowania kilku rzeczy, na które potrzebuje czasu. Jeśli jednak będą zainteresowani postaram się ten czas znaleźć.

Po trzecie: Niestety nie jestem w stanie dokończyć rozpoczętej już w 2003 roku nowej znacznie rozbudowanej wersji gry. Założenia były nie adekwatne do czasu, którym dysponowałem. Chciałbym jednak żeby powstała nowa wersja o podobnej funkcjonalności jak 2004Pro + to co najbardziej wam w niej brakowało:

  • możliwość cofania ruchów
  • nowy znacznie inteligentniejszy algorytm gracza komputerowego z implementacja w pełni wykorzystującą obecne procesory wielordzeniowe
  • wersja na Smartphone i Palmtopy

Może jest ktoś kto mógłby pomóc taką grę zrobić? Chodzi mi głównie o GUI i tryb sieciowy. Ja mógłbym napisać nowy algorytm AI. Niestety kod z wersji 2004 nie nadaje się do rozwijania więc gra będzie musiała być napisana od 0.

Czas na Web 2.0

Lipiec 5th, 2008 Marcin Borowiec

Witam wszystkich czytelników po dość długiej przerwie w aktualizacjach. Mam nadzieje że zmiany (te które już się pojawiły i te które dopiero się pojawią) zrekompensują długi okres oczekiwania. Z braku czasu na tworzenie skryptów i modernizacje layoutu  zdecydowałem się użyć gotowy system zarządzania treścią (CMS). Ułatwi mi to znacznie aktualizowanie strony, a to powinno spowodować że kolejne wpisy na stronie będą przybywać dużo dużo szybciej. Wszystkie newsy i wpisy z księgi gości zostały przeniesione ze starej strony. Była to dobra okazja do usunięcia spamu 😉

Nowa strona to nie tylko nowy CMS ale i zmiana formy dotychczasowej „zwyczajnej strony domowej” na bloga. Na blogu będą pojawiać się newsy dotyczące moich nowych produktów jak i krótkie artykuły techniczne dotyczące głównie programowania aplikacji wielowątkowych. Chociaż nie wykluczam poszerzenia tematu blogu. Pojawia się także nowy dział publikacje. Znajdą się tam artykuły mojego autorstwa, zarówno te adresowane bezpośrednio do czytelników blogu jak i wersje elektroniczne materiałów drukowanych. Jak przystało na stronę Web 2.0 udostępnia ona możliwość komentowania praktycznie wszystkiego co zostało na stronie umieszczone jak i śledzenia zawartości przez czytniki RSS do czego oczywiście zachęcam.