Fetch-and-add
Fetch-and-add (pobierz i dodaj) – specjalna instrukcja procesora, która pozwala na modyfikację pamięci w niepodzielny sposób. Ma ona zastosowanie przy implementacji wzajemnego wykluczania i algorytmów współbieżnych w systemach wieloprocesorowych.
W systemach jednoprocesorowych do realizacji sekcji krytycznej wystarcza wyłączenie/zablokowanie obsługi przerwań przed jej rozpoczęciem. Jednak w systemach wieloprocesorowych, nawet przy zablokowanych przerwaniach, dwa lub więcej procesorów może dokonywać operacji dostępu do tej samej lokacji w pamięci w tym samym czasie. Instrukcja fetch-and-add pozwala procesorowi na atomowe zwiększenie wartości w pamięci, zapobiegając kolizjom od innych procesorów.
Realizacja edytuj
Instrukcja fetch-and-add zachowuje się jak funkcja poniżej. Najistotniejsze jest to, że cała funkcja jest wykonana jako operacja atomowa. Żaden proces nie może przerwać działania funkcji i zarejestrować stan, który istnieje podczas jej wykonywania. Poniższy kod tylko wyjaśnia zachowanie instrukcji fetch-and-add. Jego realizacja rzeczywista wymaga wsparcia sprzętowego i nie może być zaimplementowana jako funkcja wysokiego poziomu.
<< operacja atomowa >>
function FetchAndAdd(address location) {
int value := *location
*location := value + 1
return value
}
x86 edytuj
W architekturze x86 od wersji procesora 8086 istnieje instrukcja ADD, w której jednym z argumentów docelowych może być adres w pamięci. Jeśli ową instrukcję poprzedzi się prefiksem LOCK, to jej działanie stanie się operacją atomową w systemach wieloprocesorowych. Jednak za jej pomocą nie można odczytać oryginalnej wartości z pamięci (chociaż można odczytać pewne flagi). Tę możliwość wprowadzono dopiero w procesorze 486 za pomocą instrukcji XADD.
Języki wysokiego poziomu edytuj
C++ edytuj
Początkowo standard języka C++ nie definiował metody dla operacji fetch-and-add. Taka funkcjonalność była dostępna dzięki wsparciu systemu operacyjnego[1], bądź jako rozszerzenie kompilatora[2]. Wraz z pojawieniem się C++11, pojawiły się standardowe mechanizmy[3] ułatwiające korzystanie z wątków takie jak: atomic_fetch_add, atomic_fetch_add_explicit.
.NET Framework (C#) edytuj
W bibliotece standardowej jest dostępna metoda Interlocked.Increment[4], która implementuje funkcjonalność fetch-and-add.
Java edytuj
Począwszy od wersji 1.5, biblioteka standardowa zawiera pakiet java.util.concurrent.atomic, w którym znajdują się klasy AtomicInteger i AtomicLong zawierające metodę getAndIncrement będącymi implementacją fetch-and-add[5].
Zobacz też edytuj
Przypisy edytuj
- ↑ InterlockedIncrement function (Windows). [w:] MSDN [on-line]. [dostęp 2012-11-27].
- ↑ _InterlockedIncrement. [w:] MSDN [on-line]. [dostęp 2012-11-27].
- ↑ Atomic operations library. 2012-11-02. [dostęp 2012-11-27]. (ang.).
- ↑ Interlocked.Increment Method. [w:] MSDN [on-line]. [dostęp 2012-11-27].
- ↑ Package java.util.concurrent.atomic. [dostęp 2012-11-27].
Bibliografia edytuj
- Maurice Herlihy. Wait-free synchronization. „ACM Trans. Program. Lang. Syst.”. 13 (1), s. 124–149, styczeń 1991. DOI: 10.1145/114005.102808. [dostęp 2012-11-24]. (ang.).