Najlepiej ilustruje to przykład.
Załóżmy, że mamy proste zadanie, które chcemy wykonywać wiele razy równolegle i chcemy globalnie śledzić liczbę wykonanych zadań, na przykład zliczanie odwiedzin na stronie internetowej.
Kiedy każdy wątek dojdzie do punktu, w którym zwiększa liczbę, jego wykonanie będzie wyglądać następująco:
- Odczytaj liczbę trafień z pamięci do rejestru procesora
- Zwiększ tę liczbę.
- Zapisz ten numer z powrotem do pamięci
Pamiętaj, że każdy wątek może zawiesić się w dowolnym momencie tego procesu. Więc jeśli wątek A wykona krok 1, a następnie zostanie zawieszony, a następnie wątek B wykona wszystkie trzy kroki, po wznowieniu wątku A jego rejestry będą miały niewłaściwą liczbę trafień: jego rejestry zostaną przywrócone, z radością zwiększy starą liczbę trafień i zapisz zwiększoną liczbę.
Ponadto w czasie zawieszenia wątku A mogła działać dowolna liczba innych wątków, więc liczba wątków A zapisanych na końcu może być znacznie poniżej prawidłowej liczby.
Z tego powodu należy upewnić się, że jeśli wątek wykonuje krok 1, musi wykonać krok 3, zanim jakikolwiek inny wątek będzie mógł wykonać krok 1, co można osiągnąć przez wszystkie wątki oczekujące na pojedynczą blokadę przed rozpoczęciem tego procesu i zwolnienie blokady dopiero po zakończeniu procesu, tak że ta „krytyczna sekcja” kodu nie może być niepoprawnie przeplatana, co prowadzi do błędnego zliczenia.
Ale co, jeśli operacja byłaby atomowa?
Tak, w krainie magicznych jednorożców i tęcz, gdzie inkrementacja jest atomowa, wówczas blokowanie nie byłoby konieczne w powyższym przykładzie.
Należy jednak pamiętać, że spędzamy bardzo mało czasu w świecie magicznych jednorożców i tęcz. W prawie każdym języku programowania operacja przyrostowa jest podzielona na trzy powyższe kroki. Dzieje się tak, ponieważ nawet jeśli procesor obsługuje operację przyrostu atomowego, operacja ta jest znacznie droższa: musi czytać z pamięci, modyfikować liczbę i zapisywać ją z powrotem do pamięci ... i zwykle operacja przyrostu atomowego jest operacją, która może zawieść, co oznacza, że powyższa prosta sekwencja musi zostać zastąpiona pętlą (jak zobaczymy poniżej).
Ponieważ nawet w kodzie wielowątkowym wiele zmiennych jest przechowywanych lokalnie dla jednego wątku, programy są znacznie wydajniejsze, jeśli przyjmą, że każda zmienna jest lokalna dla jednego wątku, i pozwolą programistom zająć się ochroną stanu wspólnego między wątkami. Zwłaszcza, że operacje atomowe zwykle nie wystarczają do rozwiązania problemów z wątkami, jak zobaczymy później.
Zmienne zmienne
Jeśli chcieliśmy uniknąć blokad tego konkretnego problemu, najpierw musimy zdać sobie sprawę, że kroki przedstawione w naszym pierwszym przykładzie nie są w rzeczywistości tym, co dzieje się we współczesnym skompilowanym kodzie. Ponieważ kompilatory zakładają, że tylko jeden wątek modyfikuje zmienną, każdy wątek zachowa własną buforowaną kopię zmiennej, dopóki rejestr procesora nie będzie potrzebny do czegoś innego. Tak długo, jak ma kopię w pamięci podręcznej, zakłada, że nie musi wracać do pamięci i czytać jej ponownie (co byłoby drogie). Nie będą też zapisywać zmiennej z powrotem do pamięci, dopóki jest ona przechowywana w rejestrze.
Możemy powrócić do sytuacji, którą podaliśmy w pierwszym przykładzie (z tymi samymi problemami związanymi z wątkami, które zidentyfikowaliśmy powyżej), zaznaczając zmienną jako niestabilną , co informuje kompilator, że ta zmienna jest modyfikowana przez innych i dlatego należy ją odczytać z lub zapisywane w pamięci za każdym razem, gdy jest otwierane lub modyfikowane.
Tak więc zmienna oznaczona jako lotna nie zabierze nas do krainy operacji przyrostu atomowego, zbliża nas tylko tak blisko, jak nam się wydawało.
Zrobienie przyrostu atomowego
Gdy użyjemy zmiennej zmiennej, możemy uczynić naszą operację przyrostową atomową za pomocą operacji warunkowego ustawiania niskiego poziomu, która jest obsługiwana przez większość współczesnych procesorów (często nazywana porównywaniem i ustawianiem lub porównywaniem i zamianą ). Takie podejście zastosowano na przykład w klasie AtomicInteger w Javie :
197 /**
198 * Atomically increments by one the current value.
199 *
200 * @return the updated value
201 */
202 public final int incrementAndGet() {
203 for (;;) {
204 int current = get();
205 int next = current + 1;
206 if (compareAndSet(current, next))
207 return next;
208 }
209 }
Powyższa pętla wielokrotnie wykonuje następujące kroki, aż do pomyślnego wykonania kroku 3:
- Odczytaj wartość zmiennej lotnej bezpośrednio z pamięci.
- Zwiększ tę wartość.
- Zmień wartość (w pamięci głównej) wtedy i tylko wtedy, gdy jej bieżąca wartość w pamięci głównej jest taka sama jak wartość, którą wstępnie odczytaliśmy, za pomocą specjalnej operacji atomowej.
Jeśli krok 3 nie powiedzie się (ponieważ wartość została zmieniona przez inny wątek po kroku 1), ponownie odczytuje zmienną bezpośrednio z pamięci głównej i próbuje ponownie.
Chociaż operacja porównywania i zamiany jest kosztowna, jest nieco lepsza niż stosowanie blokowania w tym przypadku, ponieważ jeśli wątek zostanie zawieszony po kroku 1, inne wątki, które osiągną krok 1, nie muszą blokować i czekać na pierwszy wątek, który może zapobiec kosztownemu przełączaniu kontekstu. Gdy pierwszy wątek zostanie wznowiony, nie powiedzie się przy pierwszej próbie zapisu zmiennej, ale będzie mógł kontynuować, ponownie czytając zmienną, co ponownie jest prawdopodobnie tańsze niż przełącznik kontekstu, który byłby konieczny przy blokowaniu.
Możemy więc dotrzeć do krainy przyrostów atomowych (lub innych operacji na jednej zmiennej) bez użycia rzeczywistych blokad, poprzez porównanie i zamianę.
Kiedy więc ryglowanie jest absolutnie konieczne?
Jeśli musisz zmodyfikować więcej niż jedną zmienną w operacji atomowej, wówczas konieczne będzie zablokowanie, nie znajdziesz do tego specjalnej instrukcji procesora.
Tak długo, jak pracujesz nad jedną zmienną i jesteś przygotowany na każdą pracę, którą wykonałeś, aby zawieść i musisz przeczytać zmienną i zacząć od nowa, porównanie i zamiana będą jednak wystarczające.
Rozważmy przykład, w którym każdy wątek najpierw dodaje 2 do zmiennej X, a następnie mnoży X przez dwa.
Jeśli X jest początkowo jeden i działają dwa wątki, oczekujemy, że wynikiem będzie (((1 + 2) * 2) + 2) * 2 = 16.
Jednakże, jeśli wątki się przeplatają, moglibyśmy, nawet przy wszystkich operacjach atomowych, zamiast tego, aby oba dodania występowały najpierw, a mnożenia następowały później, w wyniku czego (1 + 2 + 2) * 2 * 2 = 20.
Dzieje się tak, ponieważ mnożenie i dodawanie nie są operacjami przemiennymi.
Tak więc same operacje atomowe nie wystarczą, musimy uczynić kombinację operacji atomowymi.
Możemy to zrobić albo za pomocą blokowania do serializacji procesu, albo możemy użyć jednej zmiennej lokalnej do przechowywania wartości X, gdy rozpoczęliśmy nasze obliczenia, drugiej zmiennej lokalnej dla kroków pośrednich, a następnie użyć porównania i zamiany, aby ustaw nową wartość tylko wtedy, gdy bieżąca wartość X jest taka sama jak pierwotna wartość X. Jeśli zawiedziemy, będziemy musieli zacząć od nowa, czytając X i wykonując ponownie obliczenia.
Wiąże się to z kilkoma kompromisami: gdy obliczenia stają się dłuższe, staje się znacznie bardziej prawdopodobne, że bieżący wątek zostanie zawieszony, a wartość zostanie zmodyfikowana przez inny wątek przed wznowieniem, co oznacza, że awarie stają się znacznie bardziej prawdopodobne, co prowadzi do zmarnowania czas procesora. W skrajnym przypadku dużej liczby wątków z bardzo długimi obliczeniami, możemy mieć 100 wątków odczytających zmienną i zaangażowanych w obliczenia, w którym to przypadku tylko pierwszy, kto skończy, zapisuje nową wartość, pozostałe 99 nadal będzie dokończyć obliczenia, ale po zakończeniu odkryć, że nie mogą zaktualizować wartości ... w którym momencie odczytają wartość i rozpoczną obliczenia od nowa. Prawdopodobnie pozostałe 99 wątków powtórzy ten sam problem, marnując ogromne ilości czasu procesora.
Pełna serializacja sekcji krytycznej za pomocą zamków byłaby znacznie lepsza w tej sytuacji: 99 wątków zawiesiłoby się, gdy nie otrzymały zamka, i prowadziliśmy każdy wątek w kolejności przybycia do punktu zamka.
Jeśli serializacja nie jest krytyczna (jak w naszym przypadku inkrementacji), a obliczenia, które zostałyby utracone w przypadku niepowodzenia aktualizacji liczby, są minimalne, można skorzystać z operacji porównywania i zamiany, ponieważ ta operacja jest tańszy niż blokowanie.