Programación multiprocesador: pilas sin bloqueo

Question

En preparación para mi próximo examen de sistemas concurrentes, estoy tratando de completar algunas preguntas del libro de texto "El arte de la programación multiprocesador". Una pregunta que me está molestando:

Ejercicio 129: ¿Tiene sentido utilizar el mismo objeto BackOff compartida para ambos empuja y pop en nuestro objeto LockFreeStack? ¿De qué otra forma podríamos estructurar el retraso en el espacio y el tiempo en EliminationBackOffStack?

Esta pregunta me molesta porque la primera cosa que viene a la mente es que no tiene sentido, porque todo un objeto de retroceso no es hacer una espera de proceso, ¿por qué no compartirlo? La segunda parte de la pregunta me elude por completo y cualquier ayuda es bienvenida.

El código para el LockFreeStack:

public class LockFreeStack<T> { 

    AtomicReference<Node> top = new AtomicReference<Node>(null); 

    static final int MIN_DELAY = ...; 
    static final int MAX_DELAY = ...; 
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY); 

    protected boolean tryPush(Node node) { 
     Node oldTop = top.get(); 
     node.next = oldTop; 
     return(top.compareAndSet(oldTop, node)); 
    } 

    public void push(T value) { 
     Node node = new Node(value); 
     while (true) { 
      if (tryPush(node)) { 
       return; 
      } else { 
       backoff.backoff(); 
      } 
     } 
    } 

Answer 1

No está seguro de si alguno de mis divagaciones ayudar pero voy a pulsar el botón "Post" de todos modos.

La respuesta depende de la implementación de backoff(). Dado que el objetivo aquí es evitar la sincronización, no habrá ningún almacenamiento local, tal vez algunos en un ThreadLocal. Si el algoritmo de reducción utiliza un aleatorizador, también será necesario reentrada. Así que lo más probable es que capaz para compartirlo entre pop y push - ahora desea hacerlo. Como push y pop intentan alterar la referencia top, sería bueno si el backoff dio a los hilos sucesivos números muy diferentes. ¿Hay más contención sobre push o pop? ¿Necesitamos retroceder más agresivamente con uno u otro método? Si esto es una pila genérica, entonces no lo sabrás.

En términos de cómo se puede "reestructurar" el retraso, tampoco estoy seguro. ¿Podría usar un empuje o pop exitoso como una oportunidad para reducir el tiempo de retroceso? ¿Qué hay de la diferencia entre las esperas de espera aleatorias frente a los números primos en una secuencia asignada por ThreadLocal?

Answer 2

Al abordar la primera pregunta desde un punto de soporte de sincronización, creo que tendría sentido permitir el mismo objeto BackOff para empujes y saltos. Independientemente de la implementación de esta clase. La razón para esto es que si tenemos una pila, debemos mantener un estado consistente durante la eliminación y adición de elementos a la pila. Sin embargo, si solo estuviéramos mirando (mirando el primer elemento o la parte superior de la pila) podríamos tener más de un objeto BackOff mirándolo, ya que las lecturas no deberían bloquear la fuente de datos en cuestión. La segunda pregunta va a requerir que se publique el código para esa clase.

Answer 3

En este caso, el uso de un receso es una muerte excesiva.

Cualquier aplicación del mundo real debería pasar más tiempo procesando los nodos que empujando cosas dentro y fuera de la pila. La operación de pila por comparación debe ser muy corta. Se sigue que es muy poco probable que dos hilos accedan a la pila al mismo tiempo. Sin embargo, sucederá a veces, por lo que debe codificar cuál es el correcto.

public void push(T value) { 
    Node node = new Node(value); 
    while (!tryPush(node)) 
     backoff.backoff(); 
} 

mi humilde opinión: ¿Puede ser acortado a

public void push(T value) { 
    Node node = new Node(value); 
    while (!tryPush(node)); 
}