Programmazione multiprocessore: stack senza serratura

Question

In preparazione per il mio prossimo esame Concurrent Systems, sto cercando di completare alcune domande dal libro "The Art of Multiprocessor Programming". Una domanda è bugging me:

Esercizio 129: Ha senso utilizzare lo stesso oggetto backoff condivisa per entrambe le spinte e pop nel nostro oggetto LockFreeStack? In quale altro modo possiamo strutturare il backoff nello spazio e nel tempo in EliminationBackOffStack ?.

Questa domanda mi infastidisce perché la prima cosa che mi viene in mente è che non ha senso perché tutto ciò che un backoff fa è aspettare un processo, quindi perché non condividerlo? La seconda parte della domanda mi sfugge totalmente e ogni aiuto è il benvenuto.

Il codice per la 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

Non sono sicuro se qualcuno dei miei sproloqui aiutano ma io premere il pulsante "Invia" in ogni caso.

La risposta dipende dall'implementazione di backoff(). Poiché l'obiettivo qui è quello di evitare la sincronizzazione, non ci sarà alcuna memoria locale - forse alcuni in un ThreadLocal. Se l'algoritmo di backoff utilizza un randomizzatore, sarà necessario rientrare anche in questo caso. Quindi molto probabilmente sei in grado di condividere tra pop e push - ora vuoi. Poiché push e pop stanno entrambi tentando di modificare il riferimento allo top, sarebbe positivo se il backoff fornisse numeri successivi di thread molto diversi. C'è più contesa intorno al push o al pop? Abbiamo bisogno di essere più aggressivi con l'uno o l'altro metodo? Se questo è uno stack generico, non lo saprai.

In termini di come il backoff può essere "ristrutturato", non sono nemmeno sicuro. Potresti usare un push o pop di successo come un'opportunità per rallentare i tempi di backoff? Che ne dici della differenza tra le attese di backoff casuale rispetto ai numeri primi in una sequenza assegnata da ThreadLocal?

Answer 2

Avvicinando la prima domanda da un punto di sincronizzazione, credo che avrebbe senso consentire lo stesso oggetto BackOff per entrambi i push e pop. Indipendentemente dall'implementazione di questa classe. La ragione di ciò è che se abbiamo uno stack dobbiamo mantenere uno stato coerente attraverso la rimozione e l'aggiunta di elementi allo stack. Se tuttavia, stavamo solo facendo una sbirciata (guardando il primo elemento o in cima alla pila) di quanto potremmo avere più di un oggetto BackOff guardandolo come letture non dovrebbe fare un blocco sulla fonte di dati in questione. La seconda domanda richiederà che il codice venga pubblicato per quella classe.

Answer 3

L'utilizzo di un backoff è eccessivo in questa situazione.

Qualsiasi applicazione del mondo reale dovrebbe impiegare più tempo a elaborare i nodi piuttosto che spingere le cose dentro e fuori dallo stack. L'operazione di stack per confronto dovrebbe essere molto breve. Ne consegue che è altamente improbabile che due thread accedano allo stack contemporaneamente. Tuttavia, a volte capita, quindi è necessario codice che è corretto.

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

IMHO: può essere ridotto a

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