multithreading - operativos - algoritmo de dekker

¿Por qué una validación de adquisición de C++ 11 no es suficiente para la sincronización de Dekker?

Question

La falla de la sincronización al estilo Dekker generalmente se explica con el reordenamiento de las instrucciones. Es decir, si escribimos

atomic_int X;
atomic_int Y;
int r1, r2;
static void t1() {
X.store(1, std::memory_order_relaxed)
r1 = Y.load(std::memory_order_relaxed);
}
static void t2() {
Y.store(1, std::memory_order_relaxed)
r2 = X.load(std::memory_order_relaxed);
}

Entonces las cargas se pueden reordenar con las tiendas, lo que lleva a r1==r2==0 .

Esperaba una valla de purchase_release para evitar este tipo de reordenamiento:

static void t1() {
X.store(1, std::memory_order_relaxed);
atomic_thread_fence(std::memory_order_acq_rel);
r1 = Y.load(std::memory_order_relaxed);
}
static void t2() {
Y.store(1, std::memory_order_relaxed);
atomic_thread_fence(std::memory_order_acq_rel);
r2 = X.load(std::memory_order_relaxed);
}

La carga no se puede mover por encima de la cerca y la tienda no se puede mover por debajo de la cerca, por lo que se debe evitar el mal resultado.

Sin embargo, los experimentos muestran que r1==r2==0 todavía puede ocurrir. ¿Hay una explicación basada en la reordenación para esto? ¿Dónde está el defecto en mi razonamiento?

Answer 1

memory_order_acq_rel realmente se comporta igual que adquirir y soltar valla en el mismo lugar. Pero el problema es que no impiden todo el reordenamiento posible, evitan que las cargas consiguientes o las tiendas anteriores se reordenen alrededor de la valla. Por lo tanto, las cargas anteriores y las tiendas consiguientes pueden pasar a través de la valla.

En la sincronización de Dekker, es importante evitar, por ejemplo, que la carga se reordene antes de la tienda en otro hilo, es decir, antes de la valla. Ahora, desenrolla tus bucles donde ocurre esta sincronización y verás que la carga de la iteración anterior puede pasar por alto la iteración actual.

memory_order_seq_cst funciona bien para la sincronización de Dekker porque evita cualquier reordenación en este punto. Por ejemplo, tbb usa el algoritmo de Dekker y mfence para el robo de trabajo.

Para una mejor comprensión, vea la gran animación de la conferencia de Herb Sutter " Atomic <> weapons 1/2 ", a las 0:43.

Answer 2

Según tengo entendido (principalmente leyendo el blog de Jeff Preshings ), una atomic_thread_fence(std::memory_order_acq_rel) evita cualquier reordenación excepto StoreLoad , es decir, todavía permite reordenar una Store con una Load posterior. Sin embargo, este es exactamente el reordenamiento que debe evitarse en su ejemplo.

Más precisamente, una atomic_thread_fence(std::memory_order_acquire) evita el reordenamiento de cualquier Load previa con cualquier Store posterior y cualquier Load posterior, es decir, evita que LoadLoad y LoadStore la valla.

Una atomic_thread_fence(std::memory_order_release) impide el reordenamiento de cualquier Store posterior con cualquier Store anterior y cualquier Load anterior, es decir, evita el reordenamiento de LoadStore y StoreStore través de la valla.

Una atomic_thread_fence(std::memory_order_acq_rel) luego evita la unión, es decir, previene LoadLoad , LoadStore y StoreStore , lo que significa que aún puede producirse StoreLoad .