Vermeiden Sie Deadlock-Beispiel

Question

Ich frage mich, was die alternativen Möglichkeiten sind, Deadlock in dem folgenden Beispiel zu vermeiden. Das folgende Beispiel zeigt ein typisches Bankkonto, bei dem ein Deadlock-Problem auftritt. Was sind einige bessere Ansätze, um es in der Praxis zu lösen?

class Account { 
    double balance; 
    int id; 
    public Account(int id, double balance){ 
      this.balance = balance; 
      this.id = id; 
    } 
    void withdraw(double amount){ 
      balance -= amount; 
    } 
    void deposit(double amount){ 
      balance += amount; 
    } 
} 
class Main{ 
    public static void main(String [] args){ 
      final Account a = new Account(1,1000); 
      final Account b = new Account(2,300); 
      Thread a = new Thread(){ 
       public void run(){ 
        transfer(a,b,200); 
       } 
      }; 
      Thread b = new Thread(){ 
       public void run(){ 
        transfer(b,a,300); 
       } 
      }; 
      a.start(); 
      b.start(); 
    } 
    public static void transfer(Account from, Account to, double amount){ 
      synchronized(from){ 
       synchronized(to){ 
        from.withdraw(amount); 
        to.deposit(amount); 
       } 
      } 
    } 
} 

Ich frage mich, wird es aus der Sackgasse Problem lösen, wenn ich in meiner Übertragungsmethode die verschachtelte Aussperrung trennen wie die folgenden

synchronized(from){ 
     from.withdraw(amount); 
} 
synchronized(to){ 
     to.deposit(amount); 
} 

Answer 1

sortieren Konten. Die tote Sperre ergibt sich aus der Reihenfolge der Konten (a, b vs b, a).

So versuchen:

public static void transfer(Account from, Account to, double amount){ 
     Account first = from; 
     Account second = to; 
     if (first.compareTo(second) < 0) { 
      // Swap them 
      first = to; 
      second = from; 
     } 
     synchronized(first){ 
      synchronized(second){ 
       from.withdraw(amount); 
       to.deposit(amount); 
      } 
     } 
} 

Answer 2

Neben der Lösung der Sperre Sie bestellen auch bevor Sie irgendwelche Kontoüberträge Deadlock können auf einem privaten statischen endgültigen Sperrobjekt durch Synchronisation vermeidet.

Diese Lösung hat das Problem, dass eine private statische Sperre das System auf "sequenzielle" Übertragungen beschränkt.

Ein anderes sein kann, wenn jedes Konto eine ReentrantLock hat:

private final Lock lock = new ReentrantLock(); 




public static void transfer(Account from, Account to, double amount) 
{ 
     while(true) 
     { 
      if(from.lock.tryLock()){ 
      try { 
       if (to.lock.tryLock()){ 
        try{ 
         from.withdraw(amount); 
         to.deposit(amount); 
         break; 
        } 
        finally { 
         to.lock.unlock(); 
        } 
       } 
      } 
      finally { 
       from.lock.unlock(); 
      } 

      int n = number.nextInt(1000); 
      int TIME = 1000 + n; // 1 second + random delay to prevent livelock 
      Thread.sleep(TIME); 
     } 

} 

Deadlock nicht in diesem Ansatz tritt auf, weil Schlösser nie auf unbestimmte Zeit gehalten werden. Wenn die Sperre des aktuellen Objekts akquiriert wird, aber die zweite Sperre nicht verfügbar ist, wird die erste Sperre aufgehoben und der Thread schläft für eine bestimmte Zeit, bevor er versucht, die Sperre wiederzuerlangen.

Answer 3

Dies ist eine klassische Frage. Ich sehe zwei mögliche Lösungen:

1. Um Konten zu sortieren und zu synchronisieren, die eine ID niedriger als eine andere hat. Diese Methode wird in der Bibel der Concurrency Java Concurrency in Practice in Kapitel 10 erwähnt. In diesem Buch verwenden Autoren Systemhashcode, um die Konten zu unterscheiden. Siehe java.lang.System#identityHashCode.
2. Die zweite Lösung wird von Ihnen erwähnt - ja Sie können verschachtelte synchronisierte Blöcke vermeiden und Ihr Code wird nicht zu Deadlock führen. Aber in diesem Fall kann die Verarbeitung einige Probleme haben, denn wenn Sie Geld vom ersten Konto abheben, kann das zweite Konto für eine signifikante Zeit gesperrt werden und wahrscheinlich müssen Sie Geld auf das erste Konto zurückzahlen. Das ist nicht gut und weil diese verschachtelte Synchronisation und die Sperre von zwei Accounts ist besser und häufiger verwendete Lösung.

Answer 4

Es gibt drei Anforderungen, die Sie erfüllen müssen:

1. Konsequent den Inhalt eines Kontos durch den angegebenen Betrag reduzieren.
2. Erhöhen Sie den Inhalt des anderen Kontos konsistent um den angegebenen Betrag.
3. Wenn einer der oben genannten erfolgreich ist, muss der andere auch erfolgreich sein.

Sie können 1. und 2. durch Atomics Verwendung erreichen, aber Sie werden etwas anderes, dass double verwenden, da es keine AtomicDouble ist. AtomicLong wäre wahrscheinlich Ihre beste Wette.

Sie sind also mit Ihrer dritten Voraussetzung - wenn der andere erfolgreich ist müssen erfolgreich sein. Es gibt eine einfache Technik, die hervorragend mit Atomics funktioniert und die getAndAdd Methoden verwendet.

class Account { 
    AtomicLong balance = new AtomicLong(); 
} 

... 
Long oldDebtor = null; 
Long oldCreditor = null; 
try { 
    // Increase one. 
    oldDebtor = debtor.balance.getAndAdd(value); 
    // Decrease the other. 
    oldCreditor = creditor.balance.gtAndAdd(-value); 
} catch (Exception e) { 
    // Most likely (but still incredibly unlikely) InterruptedException but theoretically anything. 
    // Roll back 
    if (oldDebtor != null) { 
    debtor.getAndAdd(-value); 
    } 
    if (oldCreditor != null) { 
    creditor.getAndAdd(value); 
    } 
    // Re-throw after cleanup. 
    throw (e); 
} 

Answer 5

Sie können auch für jedes Konto (in der Account-Klasse) eine separate Sperre erstellen und dann vor der Transaktion beide Sperren erwerben. Werfen Sie einen Blick:

private boolean acquireLocks(Account anotherAccount) { 
     boolean fromAccountLock = false; 
     boolean toAccountLock = false; 
     try { 
      fromAccountLock = getLock().tryLock(); 
      toAccountLock = anotherAccount.getLock().tryLock(); 
     } finally { 
      if (!(fromAccountLock && toAccountLock)) { 
       if (fromAccountLock) { 
        getLock().unlock(); 
       } 
       if (toAccountLock) { 
        anotherAccount.getLock().unlock(); 
       } 
      } 
     } 
     return fromAccountLock && toAccountLock; 
    } 

Nach zwei Sperren können Sie die Übertragung ohne Sorge über sicher tun.

public static void transfer(Acc from, Acc to, double amount) { 
     if (from.acquireLocks(to)) { 
      try { 
       from.withdraw(amount); 
       to.deposit(amount); 
      } finally { 
       from.getLock().unlock(); 
       to.getLock().unlock(); 
      } 
     } else { 
      System.out.println(threadName + " cant get Lock, try again!"); 
      // sleep here for random amount of time and try do it again 
      transfer(from, to, amount); 
     } 
    } 

Answer 6

Hier ist die Lösung für das Problem angegeben.

import java.util.Random; 
import java.util.concurrent.locks.Lock; 
import java.util.concurrent.locks.ReentrantLock; 

public class FixDeadLock1 { 

    private class Account { 

     private final Lock lock = new ReentrantLock(); 

     @SuppressWarnings("unused") 
     double balance; 
     @SuppressWarnings("unused") 
     int id; 

     public Account(int id, double balance) { 
      this.balance = balance; 
      this.id = id; 
     } 

     void withdraw(double amount) { 
      this.balance -= amount; 
     } 

     void deposit(double amount) { 
      balance += amount; 
     } 
    } 

    private class Transfer { 

     void transfer(Account fromAccount, Account toAccount, double amount) { 
      /* 
      * synchronized (fromAccount) { synchronized (toAccount) { 
      * fromAccount.withdraw(amount); toAccount.deposit(amount); } } 
      */ 

      if (impendingTransaction(fromAccount, toAccount)) { 
       try { 
        System.out.format("Transaction Begins from:%d to:%d\n", 
          fromAccount.id, toAccount.id); 
        fromAccount.withdraw(amount); 
        toAccount.deposit(amount); 
       } finally { 
        fromAccount.lock.unlock(); 
        toAccount.lock.unlock(); 
       } 

      } else { 
       System.out.println("Unable to begin transaction"); 
      } 

     } 

     boolean impendingTransaction(Account fromAccount, Account toAccount) { 

      Boolean fromAccountLock = false; 
      Boolean toAccountLock = false; 

      try { 
       fromAccountLock = fromAccount.lock.tryLock(); 
       toAccountLock = toAccount.lock.tryLock(); 
      } finally { 
       if (!(fromAccountLock && toAccountLock)) { 
        if (fromAccountLock) { 
         fromAccount.lock.unlock(); 
        } 
        if (toAccountLock) { 
         toAccount.lock.unlock(); 
        } 
       } 
      } 

      return fromAccountLock && toAccountLock; 
     } 

    } 

    private class WrapperTransfer implements Runnable { 
     private Account fromAccount; 
     private Account toAccount; 
     private double amount; 

     public WrapperTransfer(Account fromAccount,Account toAccount,double amount){ 
      this.fromAccount = fromAccount; 
      this.toAccount = toAccount; 
      this.amount = amount; 
     } 

     public void run(){ 
      Random random = new Random(); 
      try { 
       int n = random.nextInt(1000); 
       int TIME = 1000 + n; // 1 second + random delay to prevent livelock 
       Thread.sleep(TIME); 
      } catch (InterruptedException e) {} 
      new Transfer().transfer(fromAccount, toAccount, amount); 
     } 

    } 

    public void initiateDeadLockTransfer() { 
     Account from = new Account(1, 1000); 
     Account to = new Account(2, 300);  
     new Thread(new WrapperTransfer(from,to,200)).start(); 
     new Thread(new WrapperTransfer(to,from,300)).start(); 
    } 

    public static void main(String[] args) { 
     new FixDeadLock1().initiateDeadLockTransfer(); 
    } 

}