Loop di sincronizzazione stallo

Question

devo le seguenti classi in Java

public class Counter { 
    private int value; 

    public Counter(int value) { 
     this.value = value; 
    } 
    public void setValue(int value) { 
     this.value = value; 
    } 
    public void decrement() { 
     this.value--; 
    } 
    public int getValue() { 
     return this.value; 
    } 
} 

public class Cell extends Thread { 

    private Object sync; 
    private Counter counter; 

    public Cell(Object sync, Counter counter) { 
     this.sync = sync; 
     this.counter = counter; 
    } 

    public void run() { 
     for (int r=0; r<Simulation.ROUND_NUM; r++) { 

      // do something 

      synchronized(counter) { 
       counter.decrement(); 
       counter.notifyAll(); 
      } 
      synchronized(sync) { 
       try { 
        sync.wait(); 
       } 
       catch (Exception ex) {} 
      } 

     } 
    } 
} 

public class Simulation extends Thread { 

    public static final int THREAD_NUM = 5; 
    public static final int ROUND_NUM = 5; 

    public Object sync = new Object(); 
    private Counter counter = new Counter(THREAD_NUM); 

    public void run() { 

     for (int i=0; i<THREAD_NUM; i++) { 
      Cell c = new Cell(sync,counter); 
      c.start(); 
     } 

     for (int i=0; i<ROUND_NUM; i++) { 
      synchronized(counter) { 
       while(counter.getValue() != 0) { 
        try { 
         counter.wait(); 
        } 
        catch (Exception ex) {} 
       } 
       counter.setValue(THREAD_NUM); 
      } 

      synchronized(sync) { 
       sync.notifyAll(); 
      } 
     } 
    } 
} 

L'obiettivo è quello di evitare di eseguire la prossima iterazione del ciclo in ogni thread cellulare, fino a che ogni discussione cellulare sarà fatto ad ogni iterazione. A volte la mia soluzione porta a un punto morto. Non riesco a capire perché. Si prega di aiutare

Answer 1

Nel codice, sembra che non ci sia alcuna garanzia che quando sync.notifyAll() viene eseguito, tutti i thread di celle hanno ottenuto sync.wait(). Questo si riferisce all'ultimo thread Cell (il quinto nel tuo esempio) che deve afferrare il blocco per sync per poterlo attendere. Ma il thread di simulazione sta anche provando la stessa cosa senza fare in modo che tutti stiano aspettando. Quella condizione di competizione fa in modo che la Simulazione aggiri il lucchetto prima che l'ultima cella sia in grado di fare lo stesso e aspettare.

Poiché l'ultima cella non è in attesa, non viene notificata, quindi tutto si blocca. Puoi testare questo aggiungendo un System.out.println() come prima riga in ogni blocco synchronized (sync) e scrivendo "waiting sync" e "notifying sync" di conseguenza. Vedrai che solo 4 thread sono in attesa di sincronizzazione quando lo avvisi.

Per assicurarsi che tutti sono in attesa quando gli Notifica Simulator, hanno i due blocchi sincronizzati in Cell#run() nidificate:

public class Counter { 
    private int value; 

    public Counter(int value) { 
     this.value = value; 
    } 

    public void setValue(int value) { 
     this.value = value; 
    } 

    public void decrement() { 
     this.value--; 
    } 

    public int getValue() { 
     return this.value; 
    } 

    public static void main(String[] args) { 
     new Simulation().start(); 
    } 
} 

class Cell extends Thread { 

    private Object sync; 
    private Counter counter; 

    public Cell(Object sync, Counter counter) { 
     this.sync = sync; 
     this.counter = counter; 
    } 

    public void run() { 
     for (int r = 0; r < Simulation.ROUND_NUM; r++) { 

      // do something 

      synchronized (sync) { 
       synchronized (counter) { 
        counter.decrement(); 
        counter.notifyAll(); 
       } 
       try { 
        sync.wait(); 
       } catch (Exception ignored) {} 
      } 


     } 
    } 
} 

class Simulation extends Thread { 

    public static final int THREAD_NUM = 900; 
    public static final int ROUND_NUM = 30; 

    public Object sync = new Object(); 
    private Counter counter = new Counter(THREAD_NUM); 

    public void run() { 

     for (int i = 0; i < THREAD_NUM; i++) { 
      Cell c = new Cell(sync, counter); 
      c.start(); 
     } 

     for (int i = 0; i < ROUND_NUM; i++) { 
      synchronized (counter) { 
       while (counter.getValue() != 0) { 
        try { 
         counter.wait(); 
        } catch (Exception ex) { 
        } 
       } 
       counter.setValue(THREAD_NUM); 
      } 

      synchronized (sync) { 
       sync.notifyAll(); 
      } 
     } 
    } 
} 

Answer 2

Prima di tutto si poteva fare uso della classe AtomicInteger invece della classe Counter che hai creato. La classe AtomicInteger è thread-safe in modo da poter utilizzare azioni atomiche come decrementoAndGet e incrementAndGet.

Per ottenere la funzionalità di attesa fino al completamento di ciascuna delle celle, è possibile utilizzare uno CountDownLatch come menzionato in un commento precedente o anche oggetti concorrenti come CyclicBarriers per interrompere l'esecuzione fino a quando tutti i thread di celle si uniscono sulla barriera. Attraverso alcuni di questi oggetti concorrenti dovrebbe essere più facile controllare più thread. Anche l'utilizzo della semplice sincronizzazione funziona bene, in genere è necessario fare più codice e pensare per assicurarsi che tutto funzioni correttamente.

Answer 3

Il codice può deadlock perché non state facendo alcuna garanzia che i fili cellulari saranno effettivamente nel blocco wait() nel momento in cui si verifica notifyAll. Di seguito è una sequenza di eventi che potrebbero causare questo problema:

1. La simulazione avvia tutti i thread e blocchi in attesa di un valore 0.
2. Ogni thread in sequenza chiamate decremento, allora counter.notifyAll, e quindi perde la sua porzione di tempo
3. Il filo conduttore è stato notificato, si sveglia, trova il contatore è a 0, chiama sync.notifyAll, loop all'inizio e attende indefinitamente.
4. Ogni thread in sequenza viene assegnato un intervallo di tempo, avanza in attesa() e attende indefinitamente.

Answer 4

Bellissimo esempio! Non è deadlock, poiché per definizione ciò può verificarsi solo quando un thread contiene più di un blocco simultaneamente e un altro tenta di acquisire gli stessi blocchi in un ordine diverso.
Sospetto che il problema qui sia causato da risvegli spuri che si verificano negli oggetti Cell (se si verificava un risveglio spurio nell'oggetto Simulation non avrebbe alcun effetto quando l'attesa() viene chiamata in un ciclo che causerà l'attesa per essere reinserita).
Un risveglio spurio in una cella causerà un ulteriore decremento. Questo a sua volta farà passare il test while(counter.getValue() != 0).
Modificare questa condizione in while(counter.getValue() >= 0) e le deadlock devono scomparire. Per favore fateci sapere se funziona.

Answer 5

Questo non è un punto morto. Il thread principale può perdere una notifica sul contatore e sarà bloccato su counter.wait() dopo che è stato letto a 0. Utilizzare lo strumento JDK JDK per analizzare i thread in una situazione come questa.