Barreras de memoria frente a operaciones interbloqueadas

Question

Estoy tratando de mejorar mi comprensión de las barreras de memoria. Supongamos que tenemos un modelo de memoria débil y adaptamos Dekker's algorithm. ¿Es posible hacer que funcione correctamente bajo el modelo de memoria débil al agregar barreras de memoria?

creo que la respuesta es un no sorprendente. El motivo (si estoy en lo cierto) es que, aunque se puede utilizar una barrera de memoria para garantizar que una lectura no se mueva más allá de otra, no puede garantizar que una lectura no vea datos obsoletos (como la de un caché). Por lo tanto, podría ver algún momento en el pasado cuando la sección crítica se desbloqueó (por el caché de la CPU) pero en el momento actual otros procesadores podrían verlo como bloqueado. Si mi comprensión es correcta, se deben usar operaciones interconectadas, como las llamadas comúnmente prueba y ajuste o comparar y cambiar, para garantizar la concordancia sincronizada de un valor en una ubicación de memoria entre múltiples procesadores.

Por lo tanto, podemos esperar con razón que ningún débil sistema de modelo de memoria proporcionaría únicas barreras de memoria? El sistema debe proporcionar operaciones como test-and-set o compare-and-swap para ser útil.

Me doy cuenta de que los procesadores populares, incluido x86, proporcionan modelos de memoria mucho más fuertes que un modelo de memoria débil. Por favor, enfoca la discusión en modelos de memoria débil.

(Si el algoritmo de Dekker es una mala elección, elegir otro algoritmo de exclusión mutua donde las barreras de memoria pueden lograr con éxito la sincronización correcta, si es posible.)

Answer 1

Tiene razón en que una barrera de memoria no puede garantizar que una lectura vea los valores actualizados. Lo que sí hace es aplicar un orden entre operaciones, tanto en un solo hilo, como entre hilos.

Por ejemplo, si el subproceso A realiza una serie de tiendas y luego ejecuta una barrera de liberación antes de una tienda final a una ubicación de marca, lee la secuencia B y luego ejecuta una barrera de adquisición antes de leer los otros valores. las otras variables tendrán los valores almacenados por el subproceso a:

// initially x=y=z=flag=0 

// thread A 
x=1; 
y=2; 
z=3; 
release_barrier(); 
flag=1; 

// thread B 
while(flag==0) ; // loop until flag is 1 
acquire_barrier(); 
assert(x==1); // asserts will not fire 
assert(y==2); 
assert(z==3); 

por supuesto, es necesario asegurarse de que la carga y almacenar a flag es atómica (que las instrucciones de carga y almacenamiento sencillos son en CPUs más comunes, siempre que las variables estén adecuadamente alineadas). Sin el ciclo while en el hilo B, el hilo B bien puede leer un valor obsoleto (0) para flag, y por lo tanto no puede garantizar ninguno de los valores leídos para las otras variables.

Las cercas se pueden utilizar para imponer la sincronización en el algoritmo de Dekker.

Aquí hay un ejemplo de implementación en C++ (utilizando variables atómicas C++ 0x):

std::atomic<bool> flag0(false),flag1(false); 
std::atomic<int> turn(0); 

void p0() 
{ 
    flag0.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag1.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 0) 
     { 
      flag0.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 0) 
      { 
      } 
      flag0.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(1,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag0.store(false,std::memory_order_relaxed); 
} 

void p1() 
{ 
    flag1.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag0.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 1) 
     { 
      flag1.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 1) 
      { 
      } 
      flag1.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(0,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag1.store(false,std::memory_order_relaxed); 
} 

Para un análisis completo Ver mi entrada de blog en http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

Algunas barreras (como el isync PowerPC, y una carga .acq en ia64) también tienen un efecto en las cargas ubsequent. es decir: si una carga estaba disponible antes de la sincronización debido a la recuperación previa, debe descartarse. Cuando se usa adecuadamente, tal vez sea suficiente para que el algoritmo de Dekker funcione en un modelo de memoria débil.

También tiene la lógica de invalidación de caché que funciona para usted. Si sabe que su carga es actual debido a algo así como una isinc y que la versión en caché de los datos se invalida si otra CPU lo toca, ¿es suficiente?

preguntas interesantes a un lado, el algoritmo de Dekker es a todos los efectos prácticos mudos. Vas a querer utilizar interfaces de hardware atómicas y barreras de memoria para cualquier aplicación real, por lo que centrarme en cómo arreglar Dekker's con átomos no me parece que valga la pena;)

Answer 3

Digamos que pones una carga y la almacenas barrera después de cada declaración, y además se aseguró de que el compilador no reordenara sus tiendas. ¿No sería esto, en cualquier arquitectura razonable, proporcionar una coherencia estricta? Dekker trabaja en arquitecturas secuenciales consistentes. La consistencia secuencial es una condición más débil que la consistencia estricta.

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

Incluso en una CPU que tiene un modelo de consistencia débil, todavía se esperaría coherencia de caché. Creo que el descarrilamiento de las cosas es el comportamiento de las memorias intermedias de la tienda y las lecturas especificadas, y qué operaciones están disponibles para eliminar las escrituras almacenadas e invalidar las lecturas especulativas. Si no hay una valla de carga que pueda invalidar las lecturas especificadas, o si no hay una valla de escritura que vacía un buffer de la tienda, además de no poder implementar Dekker's, ¡no podrá implementar un mutex!

Así que aquí está mi reclamo. Si tiene una barrera de escritura disponible, y una barrera de lectura, y la memoria caché es coherente entre las CPU, entonces puede hacer que todos los códigos sean coherentes de forma secuencial al vaciar las escrituras (valla de la tienda) después de cada instrucción y las especulaciones (leer cerca) antes de cada instrucción. Por lo tanto, afirmo que no necesitas atómico para lo que estás hablando, y que puedes hacer lo que necesitas con Dekker solamente. Claro que no querrías.

BTW, Corensic, la empresa para la que trabajo, escribe geniales herramientas para depurar problemas de simultaneidad. Consulte http://www.corensic.com.