variables volátiles y barrera de memoria en java

Question

Tengo una estructura de datos que consta de nodos vinculados. Puedes pensarlo como una simple LinkedList. Cada nodo de la lista consta de algún valor y un siguiente campo apunta al otro nodo o nulo si es el último nodo. El primer nodo funciona como raíz, no tiene ningún valor, solo apunta al siguiente nodo. Todos los otros nodos son prácticamente inmutables, una vez que se crean, ni su valor ni su próximo campo cambian durante la vida útil, a menos que la estructura esté siendo eliminada y se relacione con una situación específica.

Una (solo una) cadena agrega nuevos nodos al principio de la lista. Esto se logra construyendo un nuevo objeto, estableciendo sus campos y configurando el siguiente campo para el objeto apuntado por la raíz, luego estableciendo el próximo campo de la raíz para este nuevo nodo.

Los otros nodos exploran la estructura solo para realizar lecturas. Tienen una referencia al nodo raíz, luego pasan por los otros nodos hasta que encuentren lo que buscan o lleguen al final de la lista.

Mi pregunta es: ¿es suficiente hacer que el siguiente campo sea volátil? Desde mi comprensión del modelo de memoria Java, si el hilo principal (el que agrega nuevos nodos) realizará una escritura volátil al agregar un nuevo nodo, todo se sincronizará perfectamente y no se producirán incoherencias.

¿También es correcto suponer que en la arquitectura x86 las lecturas de una variable volátil no incurrirán en degradación del rendimiento? Como los otros hilos navegarán frecuentemente por la estructura leyendo el siguiente campo, es importante que esto se pueda hacer libremente sin barreras de memoria, etc.

También tengo una preocupación más. Los hilos que van a examinar la estructura también contendrán algunos nodos adicionales. Estos nodos serán completamente locales de subprocesos, es decir, solo los usará el subproceso que los creó y no se compartirán en absoluto. Para estos nodos adicionales, no es necesario que el siguiente campo sea volátil. Además, configurar el siguiente campo volátil emitirá una barrera de memoria que causará una pérdida de rendimiento indeseable. Me pregunto si hay alguna manera de evitar esto. Idealmente, sería perfecto si el próximo campo funcionara a veces como un campo volátil y, a veces como un campo normal;) o si tuviera un control total y pudiera emitir barreras de memoria por mi cuenta, siempre que lo necesite.

Editar:

También me preguntaba ¿Sería posible sincronizar alguna manera todas estas escrituras en una variable volátil diferente? Por ejemplo, ¿alguna otra variable estática completamente no relacionada? Dado que la escritura volátil vacía todas las escrituras pendientes, ¿no sería posible que el siguiente campo no sea volátil y en su lugar se escribiría una variable volátil diferente después de que el hilo de actualización haga todo el trabajo?

No parece muy seguro para mí, ya que no ocurre nada antes de la relación y las escrituras anteriores pueden volver a ordenarse. Las siguientes asignaciones de campo podrían reordenarse con las asignaciones de campos de valor que conducen a la iteración de subprocesos que observan el estado de objeto incoherente.

Pero tal vez es posible llegar a un esquema que sería seguro?¿Qué tal este:

hilo actualización primero construye un nuevo objeto, inicializa sus campos de valor, establece su campo siguiente al nodo apuntado por el nodo raíz, realiza una escritura volátil en alguna variable estática, establece el siguiente campo de el nodo raíz hasta el nodo de nueva creación

Answer 1

1.

Sobre la base de lo que se dice aquí

la construcción de un nuevo objeto, el establecimiento de sus campos y estableciendo el siguiente campo con el objeto señalado por la raíz, y después colocar el de raíz siguiente campo a este nuevo nodo.

Entonces sí, establecer el siguiente campo en volátil se sincronizará correctamente. Es importante entender por qué. Tienes tres juegos de escrituras antes de la mano, uno para el objeto nodo, uno para los campos y uno para los nodos siguientes (aunque no estoy completamente seguro de por qué lo haces, tal vez extraño entender algo).

Así que eso es 2 + (N número de campo) escribe. En este punto, no hay una relación de sucede antes y si el nodo se escribe normalmente no hay garantía. Tan pronto como escriba en el campo volátil, todas las escrituras anteriores ahora también serán visibles.

2.

lee volátil/escribe en un x86 (o cualquier caché coherente) sistema operativo tiene los siguientes atributos:

volatile-read: very close to a normal read 
volatile-write: about 1/3 the time of a synchronization write 
     (whether within intrinsic locking or j.u.c.Lock locking) 

3.

se parece deberás crear VolatileNode y Node. Hubo una propuesta para Java 7 a salir con un API Fences la que se puede especificar el estilo de lectura/escritura que desea ejecutar con una clase de utilidad estática pero no se ve como su liberación

Editar:

Thkala hizo un gran momento me siento vale la pena incluir

aunque cabe señalar que pre-JSR133 JVM (Java es decir < 5.0) no tiene la misma semántica

Así que lo que escribí no se aplica a las aplicaciones que se ejecutan en Java 1.4 o menos.

Answer 2

Hacer el campo volatilenext impondría una barrera de memoria en todos los instancias de la clase de nodo, no sólo el nodo raíz. Espero que sea más caro que usar synchronized en el nodo raíz. Además, la JVM puede optimizar las llamadas al método synchronized mucho mejor. Consulte también this y this.

Dicho esto, probablemente debería probar ambos y comparar/perfil para ver qué pasa.

Answer 3

Su nodo raíz en realidad no necesita ser un nodo. Solo necesita una referencia al primer nodo "real".

public class LinkedList { 
    private volatile Node firstNode; 
    ... 
    addNode(Node node) { 
    node.next = firstNode; 
    firstNode = node; 
    } 
} 

Así que no es necesario para que el campo next volátil en todos los nodos; los nodos no están sincronizados en absoluto. Puede usar esa clase para las listas vinculadas no sincronizadas si no le importa el costo del acceso volátil al primer nodo. O simplemente podría reescribir la clase con un no volátil firstNode para la versión no sincronizada.