Load-link/store-conditional

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Load-link (ładuj-połącz) i store-conditional (zapisz-warunkowo) – w informatyce 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ę niepowiedzie, 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 wstanie 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]