Deadlocks & Livelocks - Comment éviter la concurrence dans le monde réel?

Les blocages peuvent se produire uniquement dans les programmes simultanés (multi-threads) où les threads synchronisent (utilisent des verrous) l'accès à une ou plusieurs ressources partagées (variables et objet) ou à un jeu d'instructions (section critique).

Les livelocks se produisent lorsque nous essayons d'éviter les blocages en utilisant le verrouillage asynchrone, lorsque plusieurs threads rivalisent pour le même verrou, évitent d'acquérir le (s) verrou (s) pour permettre à d'autres threads d'utiliser le verrou en premier, et ne parviennent finalement jamais à acquérir un verrou. verrouiller et continuer; provoquant la famine. Voir ci-dessous pour comprendre comment un verrouillage aysnc qui est une stratégie à éviter peut être la raison d'un Livelock.

Voici quelques-unes des solutions théoriques à Deadlocks, et l'une d'entre elles (la seconde) est la raison principale de Livelocks

Approches théoriques

Ne pas utiliser de serrures

Impossible lorsque deux opérations doivent être synchronisées, par exemple un simple virement bancaire, où vous débitez un compte avant de pouvoir créditer l'autre compte et ne laissez aucun autre thread toucher le solde des comptes tant que le thread actuel n'est pas terminé.

Ne bloquez pas les verrous. Si un thread ne peut pas obtenir de verrou, il doit libérer les verrous précédemment acquis pour réessayer ultérieurement.

Difficile à mettre en œuvre et peut provoquer la famine (Livelocks) où un thread laisse toujours les verrous aller seulement pour essayer à nouveau et faire de même. De plus, cette approche peut entraîner des surcharges lors de fréquents changements de contexte de thread, ce qui réduit les performances globales du système. En outre, l’équité d’implémentation de l’unité centrale n’est pas possible, car il ne sait pas quel thread attend les verrous le plus longtemps.

Laisser les threads toujours demander des verrous dans un ordre strict

Plus facile à dire qu'à faire, par exemple. Si nous écrivons une fonction pour transférer de l'argent d'un compte A à un compte B, nous pouvons écrire quelque chose comme:

// au moment de la compilation, on prend le premier argument, puis le second
virement public nul (compte A, compte B, argent long) {
  synchronisé (A) {
    synchronisé (B) {
      A.add (montant);
      B. soustraction (montant);
    }
  }
}
// au moment de l'exécution, nous ne pouvons pas savoir comment nos méthodes seront appelées
public void run () {
  new Thread (() -> this.transfer (X, Y, 10000)). start ();
  new Thread (() -> this.transfer (Y, X, 10000)). start ();
}
// this run () va créer une impasse
// le premier thread se verrouille sur X, attend Y
// le deuxième thread se verrouille sur Y, attend X

Solution du monde réel

Nous pouvons combiner les approches de commande de serrure et de serrure minutée pour arriver à une solution réelle

Ordre de verrouillage déterminé par l'entreprise

Nous pouvons améliorer notre approche en distinguant A et B en fonction du numéro de compte le plus grand ou le plus petit.

// au moment de l'exécution, nous prenons le verrou sur le compte avec l'identifiant le plus petit
virement public nul (compte A, compte B, argent long) {
  Compte final premier = A.id 
  synchronisé (premier) {
    synchronisé (seconde) {
      premier.add (montant);
      deuxième soustraction (quantité);
    }
  }
}
// au moment de l'exécution, nous ne pouvons pas savoir comment nos méthodes seront appelées
public void run () {
  new Thread (() -> this.transfer (X, Y, 10000)). start ();
  new Thread (() -> this.transfer (Y, X, 10000)). start ();
}

Par exemple, si X.id = 1111 et Y.id = 2222, étant donné que nous considérons le premier compte comme étant celui dont l'identifiant est le plus petit, l'ordre de verrouillage des exécutions de transfert (Y, X, 10000) et de transfert (X, Y, 10000) sera la même. X ayant un numéro de compte inférieur à Y, les deux threads essaieront de verrouiller X avant Y et un seul d'entre eux réussira.

Requêtes de verrouillage tryLock / async

La solution consistant à utiliser un ordre de verrouillage déterminé par l'entreprise ne fonctionne que dans le cas de relations associatives dans lesquelles une logique de transfert à un endroit (….), Telle que définie par notre méthode, détermine comment les ressources sont coordonnées.

Il se peut que nous ayons d'autres méthodes / logique, qui utilisent une logique de commande incompatible avec le transfert (…). Pour éviter le blocage dans de tels cas, il est conseillé d'utiliser le verrouillage asynchrone, dans lequel nous essayons de verrouiller une ressource pour un temps fini / réaliste (temps de transaction maximal) + petit temps d'attente aléatoire afin que tous les threads n'essayent pas acquérir trop tôt et pas tous en même temps respectivement, évitant ainsi Livelocks (famine due à des tentatives non viables d'acquérir des verrous)

// suppose que Account # getLock () nous donne le verrou du compte (java.util.concurrent.locks.Lock)
// Le compte peut encapsuler un verrou, fournir un verrou () / unlock ()
public long getWait () {
/// renvoie la moyenne mobile des temps de transfert pour les n derniers transferts + small-random-salt en millis afin que tous les threads en attente de verrouillage ne se réveillent pas en même temps.
}
virement void public (lock lockF, lock lockS, montant int) {
  Compte final premier = A.id 
  booléen fait = faux;
  faire {
    essayer {
      essayer {
        if (lockF.tryLock (getWait (), MILLISECONDS))) {
          essayer {
            if (lockS.tryLock (getWait (), MILLISECONDS))) {
              done = true;
            }
          } enfin {
            lockS.unlock ();
          }
        }
      } catch (InterruptedException e) {
        lancer la nouvelle RuntimeException ("Cancelled");
      }
    } enfin {
      lockF.unlock ();
    }
  } while (! fait);

}
// au moment de l'exécution, nous ne pouvons pas savoir comment nos méthodes seront appelées
public void run () {
    new Thread (() -> this.transfer (X, Y, 10000)). start ();
    new Thread (() -> this.transfer (Y, X, 10000)). start ();
}