Load-link/store-conditional
Load-link (ładuj-połącz) i store-conditional (zapisz-warunkowo) – para instrukcji stosowanych w programowaniu wielowątkowym w celu synchronizacji. Instrukcja load-link (LL) zwraca bieżącą wartość lokacji pamięci, natomiast zastosowana po niej instrukcja store-conditional (SC) zapisująca nową wartość do tej samej lokacji zostanie wykonana wtedy i tylko wtedy, jeśli nie nastąpiły żadne inne aktualizacje pamięci w podanej lokacji od początku wywołania instrukcji load-link. Para takich instrukcji pozwala na realizację operacji atomowej read-modify-write, których przykładami mogą być test-and-set, fetch-and-add lub compare-and-swap.
Takie instrukcje były początkowo zaproponowane przez Jensena, Hagensena i Broughtona w Lawrence Livermore National Laboratory dla multiprocesora AAP w projekcie S-1. Inne nazwy stosowane dla instrukcji load-link to „load-linked”, „load and reserve” lub „load-locked”.
Porównanie LL/SC i compare-and-swap[edytuj | edytuj kod]
Jeśli nastąpi jakakolwiek zapis, to z definicji zagwarantowane jest, że instrukcja store-conditional się nie powiedzie, nawet jeśli wartość odczytana przez load-link jest odtworzona. Z uwagi na to para LL/SC jest silniejsza niż odczyt z następującą po nim instrukcją compare-and-swap (CAS), która nie jest w stanie wykryć zmian, jeśli w międzyczasie stara wartość zostanie odtworzona (problem ABA).
Rzeczywiste realizacje LL/SC nie zawsze kończą się sukcesem, jeśli nie ma współbieżnych zmian do obserwowanej lokacji. Dowolne wyjątkowe zdarzenie pomiędzy tymi dwiema operacjami, np. przełączanie kontekstu, inna instrukcja load-link, czy nawet (na wielu platformach) inna operacja czytania lub zapisu powoduje, że instrukcja store-conditional fałszywie zwraca niepowodzenie. W starszych implementacjach instrukcja zawodziła nawet w przypadku dowolnego sygnału z magistrali pamięci o aktualizacji wartości. Jest to często nazywane przez badaczy słabym LL/SC, ponieważ łamie to wiele teoretycznych algorytmów LL/SC. Słabość jest względna, więc niektóre algorytmy, mimo to, mogą z nich korzystać.
LL/SC jest trudniejsze w emulacji niż CAS. Dodatkowo zatrzymywanie uruchomionego programu między instrukcjami LL/SC, np. podczas pracy z debuggerem i wykonywaniu kodu instrukcja po instrukcji, może zakłócić przewidywany postęp, co czyni śledzenie trudnym.
Realizacje[edytuj | edytuj kod]
Wszystkie mikroprocesory DEC Alpha, PowerPC, MIPS i ARM dostarczają instrukcje LL/SC: ldl_l/stl_c i ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), i ldrex/strex (ARM wersja 6 i wyższe).
Większość platform dostarcza wiele zestawów instrukcji dla różnych rozmiarów danych, np. ldarx/stdcx dla danych podwójnej szerokości na PowerPC.
Niektóre procesory śledzą zmiany w obrębie całej linii pamięci podręcznej lub innej wielokrotności, z której dokonywany jest odczyt instrukcją load-link. W takim przypadku aktualizacja dowolnego fragmentu pamięci (czy to instrukcją store-conditional, czy tylko zwykłym zapisem) jest wystarczającym powodem aby następująca instrukcja store-conditional się nie powiodła.
Wszystkie powyższe platformy dostarczają słabe LL/SC.
Realizacja w ARM definiuje bloki zależne od platformy, w zakresach od 8 bajtów do 2048 bajtów, a dostęp LL/SC w dowolnym zadanym bloku się nie powiedzie jeśli między LL a SC wystąpi zwyczajny dostęp do pamięci w obrębie tego bloku. Ta implementacja jest najsilniejsza i najbardziej praktyczna.
Zobacz też[edytuj | edytuj kod]
Bibliografia[edytuj | edytuj kod]
- Eric H Jensen, Gary W. Hagensen, Jeffrey Broughton, A New Approach to Exclusive Data Access in Shared Memory Multiprocessors, [w:] Technical Report UCRL-97663, Lawrence Livermore National Laboratory, 13 listopada 1987 [dostęp 2012-12-04] [zarchiwizowane z adresu 2017-02-02] (ang.).