headerphoto

OpenMP

Synchronizacja dostępu do wspólnej pamięci operacyjnej

Programowanie maszyn z pamięcią współdzieloną wymaga określenia jasnych zasad dostępu do pamięci operacyjnej. Każdy wątek w systemie równoległym ma teoretycznie takie samo prawo do odczytu lub zapisu dowolnych komórek ze wspólnej pamięci operacyjnej. Nieuchronnie pojawia się problem odpowiedniej synchronizacji rozkazów płynących z różnych wątków, tak, aby nie dochodziło do niekontrolowanego zapisu lub odczytu danych z tych samych obszarów pamięci przez różne wątki. Najprostszym przykładem tego, jak zgubne efekty może przynieść niezsynchronizowany dostęp do wspólnej pamięci operacyjnej, może być prosta inkrementacja pewnej zmiennej w kodzie programu równoległego. Przypuśćmy, że mamy zmienną n=0. Celem programu jest rozwidlenie się na grupę wątków, których zadaniem jest odczytanie aktualnej wartości zmiennej n, dodanie do niej liczby 1 i zapisanie sumy z powrotem do zmiennej n.

Po uruchomieniu programu i rozwidleniu się procesu głównego na np. 2 wątki okazuje się, że wynikiem programu nie zawsze jest wartość zmiennej n=2 (jakby to wynikało z pobieżnej analizy kodu). Powodem takiego stanu rzeczy jest fakt, że oba wątki tak naprawdę nie wiedzą o swoim istnieniu. Każdy z nich uważa się za wątek główny programu i złudnie wierzy, że może bezkolizyjnie ingerować w dany obszar pamięci. Dochodzi więc do wyścigu wątków, w którym występuje niedozwolone w tym przypadku, naprzemienne wykonywanie instrukcji obu wątków. Wątki odczytują równolegle wartość zmiennej n (na początku równą 0), inkrementują ją o 1, a następnie zapisują po kolei sumę równą 1. Po zakończeniu programu, w zmiennej n zapisana jest liczba 1 zamiast 2. Wynik działania jest niepoprawny, ale z punktu widzenia jednego i drugiego wątku wszystko jest w porządku. Wszystkie trzy operacje (odczyt, dodawanie, zapis) wykonały się poprawnie. Problemem jest tylko to, że operacje te przeplatały się ze sobą nawzajem (w tym przypadku przeplotły się operacje odczytu wartości zmiennej n). Przy inkrementacji przeplot jest niedopuszczalny! Poniższa tabela prezentuje jeden z możliwych scenariuszy zachowania się dwóch wątków w programie inkrementującym zmienną n. Numery przy operacjach oznaczają kolejność, w jakiej instrukcje mogły zostać wykonane. Aktualna wartość zmiennej n, po wykonaniu każdej operacji znajduje się w oddzielnej kolumnie.


Tabela 1. Kolejność wykonywania instrukcji dwóch NIEzsynchronizowanych wątków.

WĄTEK 1
n
WĄTEK 2
n
1. odczytaj wartość zmiennej n (0) 2. odczytaj wartość zmiennej n
(0)
3. dodaj 1 do odczytanej wartości (0) 5. dodaj 1 do odczytanej wartości
(1)
4. zapisz sumę do zmiennej n
(wątek 2 nie dowie się o aktualizacji n,
bo wcześniej odczytał jej wartość)
(1) 6. zapisz sumę do zmiennej n
(1)
PO ZAKOŃCZENIU PRACY 1 WĄTKA -->

1
PO ZAKOŃCZENIU PRACY 2 WĄTKA -->

1
(ŹLE!)

Żeby program działał poprawnie, wątki musiałyby być zsynchronizowane w taki sposób, aby ich instrukcje nie przeplatały się ze sobą. Wątek 2 powinien zaczekać, aż wątek 1 skończy wykonywać zestaw swoich instrukcji. Dopiero potem wątek 2 może uruchamiać swoje instrukcje (tabela 2).


Tabela 2. Kolejność wykonywania instrukcji dwóch poprawnie zsynchronizowanych wątków

WĄTEK 1
n
WĄTEK 2
n
1. odczytaj wartość zmiennej n (0) 4. odczytaj wartość zmiennej n
(1)
2. dodaj 1 do odczytanej wartości (0) 5. dodaj 1 do odczytanej wartości
(1)
3. zapisz sumę do zmiennej n (1) 6. zapisz sumę do zmiennej n
(2)
PO ZAKOŃCZENIU PRACY 1 WĄTKA -->

1
PO ZAKOŃCZENIU PRACY 2 WĄTKA -->

2
(DOBRZE!)

Jak więc widać, są pewne operacje, które nie mogą być wykonywane równocześnie przez różne wątki. Są to tzw. instrukcje atomowe, które należy traktować ze szczególną uwagą, ponieważ mogą stać się źródłem bardzo poważnych błędów w programach równoległych (o ile nie zostaną należycie potraktowane), co z resztą dało się zauważyć na przykładzie programu inkrementującego wartość zmiennej n.

Jest kilka sposobów na wyeliminowanie ryzyka uszkodzeń lub inaczej, naruszenia spójności danych współdzielonych przez wiele wątków. Pierwszym z nich jest określenie fragmentu kodu, który może być wykonywany tylko przez jeden wątek w danym momencie czasu. Ten specyficzny obszar to tzw. sekcja krytyczna. Programista definiuje ten obszar za pomocą dyrektywy OMP CRITICAL.

#pragma omp critical
 {
    // ... instrukcje wykonywane w danym momencie czasu
    //     tylko przez jeden wątek
 }

Sekcja krytyczna skutecznie eliminuje niepożądane przeploty instrukcji różnych wątków, jednak niestety jest dosyć kosztownym zabiegiem programistycznym. Program ze zbyt rozbudowanymi sekcjami krytycznymi może wykonywać się nawet wolniej niż jego odpowiednik uruchamiany sekwencyjnie bez użycia wątków. Dlatego zaleca się ostrożność w stosowaniu tej metody synchronizacji.

Alternatywą dla sekcji krytycznych jest wyznaczenie tylko ściśle określonych operacji, przy których wątki mają zostać zsynchronizowane. Takimi operacjami może być inkrementacja, dekrementacja czy przypisanie wartości (czyli wszystkie operacje atomowe). Stąd dyrektywę realizującą to zadanie nazwano OMP ATOMIC.

#pragma omp atomic
   n++;     // instrukcja atomowa może być wykonana tylko
            // przez jeden wątek w danej chwili

Warto zaznaczyć, że operacje atomowe są bardzo często wspomagane sprzętowo, dlatego ich wykonywanie odbywa się znacznie szybciej niż sekcji krytycznych. Oczywiście nie należy przesadzać z ich ilością w kodzie programu. Mimo, że jest to bardzo efektywna metoda synchronizacji wątków, to należy (tak jak w przypadku sekcji krytycznych) bardzo rozsądnie nią dysponować. Stosowanie zbyt wielu instrukcji atomowych może doprowadzić do sytuacji, w której procesory będą tracić zbyt wiele czasu na obsługę synchronizacji, kosztem właściwego zadania obliczeniowego.

Bardzo interesującym sposobem synchronizacji grupy wątków jest bariera (Rys. 1). Polega ona na wydzieleniu pewnego obszaru w kodzie programu zakończonego punktem zbiorczym dla wszystkich wątków (tzw. barierą). Jeżeli wątek dotrze do granic obszaru, zostaje tymczasowo uśpiony i czeka na przybycie reszty wątków z grupy. Gdy uczyni to ostatni, najwolniejszy wątek, wybudzone zostają wszystkie uśpione wątki, a co za tym idzie wznawiane zostają obliczenia równoległe na dalszym fragmencie kodu.


Rys. 1. Synchronizacja za pomocą dyrektywy OMP BARRIER.