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