Deadlock nel codice Java con i semafori e acquisire (int)

Question

Ho il seguente codice Java:

import java.util.concurrent.*; 

class Foo{ 
    static Semaphore s = new Semaphore(1); 

    public void fun(final char c, final int r){ 
     new Thread(new Runnable(){ 
      public void run(){ 
       try{ 
        s.acquire(r); 
        System.out.println(c+"_"+r); 
        s.release(r+1); 
       } catch(Exception e){ e.printStackTrace(); } 
      } 
     }).start(); 
    } 
} 

class ths{ 
    public static void main(String[]args) throws Exception{ 
     Foo f = new Foo(); 
     f.fun('B',2); 
     f.fun('F',6); 
     f.fun('A',1); 
     f.fun('C',3); 
     f.fun('D',4); 
     f.fun('E',5); 
    } 
} 

Idealmente, questo dovrebbe stampare A_1 attraverso F_6 in ordine e di uscita, ma per qualche ragione che non capita . Generalmente stampa A_1 e B_2 e quindi rimane bloccato.

Non riesco a trovare nulla di chiaramente sbagliato nel mio codice. Eventuali suggerimenti?

Answer 1

Il problema di base è che acquire(int permits) non garantisce che tutti i permessi vengano acquisiti contemporaneamente. Potrebbe acquisire meno permessi e quindi bloccare mentre attende il resto.

Consideriamo il tuo codice. Quando, diciamo, sono disponibili tre permessi, non c'è nulla che garantisca che saranno dati al thread C. Potrebbero, infatti, essere dati al thread D per soddisfare parzialmente la sua richiesta acquire(4), risultando in un deadlock.

Se si modifica il codice in questo modo, questo risolve il problema per me:

public void fun(final char c, final int r){ 
    new Thread(new Runnable(){ 
     public void run(){ 
      try{ 
       while (!s.tryAcquire(r, 1, TimeUnit.MILLISECONDS)) {}; 
       System.out.println(c+"_"+r); 
       s.release(r+1); 
      } catch(Exception e){ e.printStackTrace(); } 
     } 
    }).start(); 
} 

(Il secondo pensiero, quanto sopra è anche rotto dal momento che non c'è alcuna garanzia che il thread corretto sarà mai ottenere i permessi - potrebbe continuare a provare e scadere indefinitamente.)

Answer 2

Semaphorefa acquisire tutti i permessi in una volta, altrimenti non sarebbe un vero semaphore. MA: anche la versione Java ha una coda di attesa interna. E il comportamento di tale coda è NONserve il miglior adattamento delle risorse attualmente libere ma più o meno raccogliere i permessi fino a quando la richiesta del primo nella coda può essere consentita. Ma prima che un thread immetta in coda, viene eseguito un controllo se i permessi disponibili consentono al thread di evitare di entrare nella coda.

ho modificato il codice per dimostrare che il comportamento di coda:

import java.util.concurrent.*; 
public class SemaphoreTest{ 
    static Semaphore s = new Semaphore(0); 

    public void fun(final char c, final int r) throws Exception { 
     new Thread(new Runnable(){ 
      public void run(){ 
       try{ 
        System.out.println("acquire "+r); 
        s.acquire(r); 
        System.out.println(c+"_"+r); 
       } catch(Exception e){ e.printStackTrace(); } 
      } 
     }).start(); 
     Thread.sleep(500); 
    } 

    public static void main(String[]args) throws Exception{ 
     SemaphoreTest f = new SemaphoreTest(); 

     f.fun('B',2); 
     f.fun('F',6); 
     f.fun('A',1); 
     f.fun('C',3); 
     f.fun('D',4); 
     f.fun('E',5); 

     while(s.hasQueuedThreads()){ 
      Thread.sleep(1000); 
      System.out.println("release "+1+", available "+(s.availablePermits()+1)); 
      s.release(1); 
     } 
    } 
} 

Fondamentalmente sono state fatte le seguenti modifiche:

• Inizia con 0 permessi - permettere a nessuno di entrare per primo nella coda.
• "Definisci" l'ordine di accodamento assegnando ogni thread a 500 ms dopo Thread.start.
• Ogni thread chiamerà acquire ma non release.
• Il filo principale alimenterà il semaforo lentamente con un permesso dopo l'altro.

Questo darà questa uscita deterministico:

acquire 2 
acquire 6 
acquire 1 
acquire 3 
acquire 4 
acquire 5 
release 1, available 1 
release 1, available 2 
B_2 
release 1, available 1 
release 1, available 2 
release 1, available 3 
release 1, available 4 
release 1, available 5 
release 1, available 6 
F_6 
release 1, available 1 
A_1 
release 1, available 1 
release 1, available 2 
release 1, available 3 
C_3 
release 1, available 1 
release 1, available 2 
release 1, available 3 
release 1, available 4 
D_4 
release 1, available 1 
release 1, available 2 
release 1, available 3 
release 1, available 4 
release 1, available 5 
E_5 
release 1, available 1 

che significa: Ogni thread è risvegliato, se

• è alla testa della coda.
• sufficienti permessi sono stati accumulati.