Verhindern von Deadlock in einer Scheinbankdatenbank

Question

Dies ist ein falsches Bankdatenbankproblem mit Deadlock. Ich habe bereits, was ich denke, ist die Antwort, aber ich bin neugierig, ob dies eine gute Lösung ist. Die Frage stellt, ist die folgende: (oder Prozesse)

Wie Sie Deadlock im folgenden Code verhindern ?:

void transaction(Account from, Account to, double amount) 
{ 
    Semaphore lock1, lock2; 
    lock1 = getLock(from); 
    lock2 = getLock(to); 

    wait(lock1); 
     wait(lock2); 

      withdraw(from, amount); 
      deposit(to, amount); 

     signal(lock2); 
    signal(lock1); 
} 

Die Art und Weise dieses Deadlock ist über zwei Threads werden kann Aufruf der Transaktion() -Methode zur gleichen Zeit mit gegnerischen Konten, dh:

Transaktion (Einsparungen, Prüfung, 1); in Thread 1 und

Transaktion (Überprüfung, Einsparungen, 2); in Thread 2.

Von meinem schlechten Verständnis, denke ich, was passiert und warum es festgefahren ist, weil die Sperre Reihenfolge nicht befolgt wird, da beide Threads versuchen, eine Sperre (von einander?) zu bekommen.

Meine quick and dirty Lösung wäre, die Schleusen außerhalb der Funktion Transaktion zu bewegen(), wo es so aussehen würde, wenn sie aufgerufen:

//somewhere in main 
    Semaphore lock1, lock2; 
    lock1 = getLock(from); 
    lock2 = getLock(to); 

    wait(lock1); 
     wait(lock2); 

     transaction(checking, savings, 2); 

     signal(lock2); 
    signal(lock1); 
    //..... 

mit der Transaktion wie folgt aussehen:

void transaction(Account from, Account to, double amount) 
{ 
    withdraw(from, amount); 
    deposit(to, amount); 
} 

So können sie nie gleichzeitig ausgeführt werden, da die Transaktion technisch der kritische Abschnitt ist. Wenn dies ein Java-Programm wäre, könnten Sie auch Monitore verwenden, indem Sie das Wort nach void in die Funktionsdeklaration einfügen? Funktioniert das? Das scheint ein klügerer Weg zu sein.

Ich mag das auch nicht verstehen, also fühlen Sie sich frei, mich zu schulen, besonders wenn meine Erklärungen nicht genau sind. Vielen Dank.

Answer 1

denke ich, was los ist und warum es festgefahren zu werden, ist, weil die Sperre Ordnung, da beide Threads nicht befolgt versucht werden erhalten hier ein Schloss

Das Problem, wie Sie, dass ein Thread wie erwähnen ist:

wait(fromLock); 
    wait(toLock); 

, während ein anderer dies tun könnte:

wait(toLock); 
    wait(fromLock); 

was zu einem Deadlock führen kann.

Was Sie tun müssen, ist sicherzustellen, dass sie immer in der gleichen Reihenfolge sperren. Sie könnten irgendwie die ID des Kontos verwenden, um die Reihenfolge der Sperren herauszufinden:

if (from.id < to.id) { 
    wait(fromLock) 
    wait(toLock) 
     transaction(checking, savings, 2); 
    signal(toLock); 
    signal(fromLock); 
} else { 
    wait(toLock) 
    wait(FromLock) 
     transaction(checking, savings, 2); 
    signal(FromLock); 
    signal(toLock); 
} 

Ich glaube, das wird alle Deadlocks auflösen. Sie können auch eine Überprüfung für die from und to die gleiche Entität sein.

Answer 2

Die Trennung dieses kritischen Abschnitts in zwei Abschnitte:

void transaction(Account from, Account to, double amount) 
{ 
    Semaphore lock1, lock2; 
    lock1 = getLock(from); 
    lock2 = getLock(to); 

    wait(lock1); 
      withdraw(from, amount); 
    signal(lock1); 


    wait(lock2);  
      deposit(to, amount); 
    signal(lock2); 
} 

die beste Lösung in der realen Welt sein, weil diesen kritischen Abschnitt zu trennen, sie führt nicht zu einem unerwünschten Zustand zwischen (das heißt, es wird nie eine Situation geben, in der mehr Geld abgezogen wird, als es möglich ist).

Die einfache Lösung, um den kritischen Abschnitt in einem Stück zu lassen, ist sicherzustellen, dass die Sperranordnung in allen Transaktionen identisch ist. In diesem Fall können Sie die Sperren sortieren und die kleinere zum Sperren auswählen.

Weitere Informationen über Deadlock sehen meine Frage in diesen Situationen zu verhindern - Multiple mutex locking strategies and why libraries don't use address comparison

Answer 3

Keine Transaktion sollte jemals an einer Sperre festhalten, während sie auf eine andere wartet. Wenn es eine der benötigten Sperren nicht erhalten kann, sollte es alle diejenigen freigeben, die es erworben hat.