Deadlock e Livelock: come evitare la concorrenza nel mondo reale?

I deadlock possono verificarsi solo nei programmi simultanei (multi-thread) in cui i thread sincronizzano (utilizzano i blocchi) l'accesso a una o più risorse condivise (variabili e oggetti) o set di istruzioni (sezione critica).

Livelock si verificano quando proviamo a evitare deadlock utilizzando il blocco asincrono, in cui più thread competono per gli stessi set di blocco, evitiamo di acquisire i blocchi per consentire ad altri thread di andare prima con il blocco e alla fine non riusciremo mai ad acquisire un bloccare e procedere; causando fame. Vedi sotto per capire come un blocco aysnc che è una strategia per evitare Deadlock può essere la ragione di un Livelock

Ecco alcune delle soluzioni teoriche a Deadlock, e una di esse (la seconda) è la ragione principale per Livelocks

Approcci teorici

Non usare i lucchetti

Non è possibile quando due operazioni devono essere sincronizzate, ad esempio un semplice bonifico bancario, in cui addebitare un conto prima di poter accreditare l'altro account e non consentire a nessun altro thread di toccare il saldo nei conti fino a quando non viene eseguito il thread corrente.

Non bloccare i blocchi, se un thread non può acquisire un blocco, dovrebbe rilasciare i blocchi acquisiti in precedenza per riprovare più tardi

Ingombrante da implementare e può causare la fame (Livelock) in cui un thread lascia sempre i blocchi solo per riprovare e fare lo stesso. Inoltre, questo approccio può avere costi generali nel cambio di contesto di thread frequenti riducendo le prestazioni complessive di un sistema. Inoltre, non c'è modo per lo scheduler della CPU di implementare l'equità in quanto non sa quale thread ha effettivamente aspettato il blocco (i) più a lungo.

Consenti ai thread di richiedere sempre i blocchi in un ordine rigoroso

Più facile a dirsi che a farsi, per esempio. Se stiamo scrivendo una funzione per trasferire denaro dall'account A a B, possiamo scrivere qualcosa del genere

// al momento della compilazione, prendiamo il blocco sul primo argomento e poi sul secondo
trasferimento vuoto pubblico (Conto A, Conto B, denaro lungo) {
  sincronizzato (A) {
    sincronizzato (B) {
      A.add (quantità);
      B.subtract (quantità);
    }
  }
}
// in fase di esecuzione non è possibile tenere traccia di come verranno chiamati i nostri metodi
public void run () {
  nuovo thread (() -> this.transfer (X, Y, 10000)). start ();
  nuovo thread (() -> this.transfer (Y, X, 10000)). start ();
}
// questa corsa () creerà un deadlock
// il primo thread si blocca su X, attende Y
// il secondo thread si blocca su Y, attende X

Soluzione nel mondo reale

Siamo in grado di combinare approcci di ordinamento dei blocchi e blocchi temporizzati per arrivare a una vera soluzione di parole

Ordinamento dei blocchi determinato dall'azienda

Possiamo migliorare il nostro approccio discriminando tra A e B in base al numero di conto maggiore o minore.

// in fase di esecuzione, prendiamo prima il blocco sull'account con ID più piccolo
trasferimento vuoto pubblico (Conto A, Conto B, denaro lungo) {
  Conto finale prima = A.id 
  sincronizzato (primo) {
    sincronizzato (secondo) {
      first.add (quantità);
      second.subtract (quantità);
    }
  }
}
// in fase di esecuzione non è possibile tenere traccia di come verranno chiamati i nostri metodi
public void run () {
  nuovo thread (() -> this.transfer (X, Y, 10000)). start ();
  nuovo thread (() -> this.transfer (Y, X, 10000)). start ();
}

Ad esempio, se X.id = 1111 e Y.id = 2222, poiché consideriamo il primo account come quello con ID account più piccolo, l'ordine di blocco per le esecuzioni di trasferimento (Y, X, 10000) e trasferimento (X, Y, 10000) sarà lo stesso. X avendo un numero di conto inferiore a Y, entrambi i thread tenteranno di bloccare X prima di Y e solo uno di essi avrà successo e procederà al blocco Y terminando e rilasciando i blocchi su X e Y prima che gli altri thread acquisiscano blocchi e possano procedere.

Richieste di blocco TryLock / async di attesa determinate dal tempo

La soluzione dell'utilizzo di un ordinamento dei blocchi determinato dall'azienda funziona solo se per le relazioni associative in cui una logica in un luogo trasferisce (...), come nel nostro metodo, determina il modo in cui le risorse sono coordinate.

Potremmo finire con altri metodi / logiche, che finiscono per usare una logica di ordinamento incompatibile con il trasferimento (...). Per evitare deadlock in questi casi, è consigliabile utilizzare il blocco asincrono, in cui proviamo a bloccare una risorsa per tempo finito / realistico (tempo di transazione massimo) + tempo di attesa piccolo-casuale in modo che tutti i thread non provino acquisire troppo presto e non tutti allo stesso tempo rispettivamente evitando quindi Livelock (fame dovuta a tentativi non realizzabili di acquisire blocchi)

// assume l'account # getLock () ci dà il blocco dell'account (java.util.concurrent.locks.Lock)
// L'account potrebbe incapsulare il blocco, fornire lock () / unlock ()
public long getWait () {
/// restituisce la media mobile dei tempi di trasferimento per gli ultimi n trasferimenti + small-random-salt in millis, quindi tutti i thread in attesa di blocco non si svegliano contemporaneamente.
}
trasferimento vuoto pubblico (Lock lockF, Lock lockS, int amount) {
  Conto finale prima = A.id 
  booleano done = false;
  fare {
    provare {
      provare {
        if (lockF.tryLock (getWait (), MILLISECONDS)) {
          provare {
            if (lockS.tryLock (getWait (), MILLISECONDS)) {
              done = true;
            }
          } finalmente {
            lockS.unlock ();
          }
        }
      } catch (InterruptedException e) {
        lancia nuovo RuntimeException ("Annullato");
      }
    } finalmente {
      lockF.unlock ();
    }
  } while (! done);

}
// in fase di esecuzione non è possibile tenere traccia di come verranno chiamati i nostri metodi
public void run () {
    nuovo thread (() -> this.transfer (X, Y, 10000)). start ();
    nuovo thread (() -> this.transfer (Y, X, 10000)). start ();
}