DynamicOrderDeadlock.java
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.atomic.*;
/**
* DynamicOrderDeadlock
* <p/>
* Dynamic lock-ordering deadlock
*
*/
public class DynamicOrderDeadlock {
private static final int NUM_THREADS = 20;
private static final int NUM_ACCOUNTS = 5;
private static final int NUM_ITERATIONS = 100;
private static final int MAX_MONEY = 1000;
public static void main(String[] args) {
final Random rnd = new Random();
final Account[] accounts = new Account[NUM_ACCOUNTS];
for (int i = 0; i < accounts.length; i++)
accounts[i] = new Account(rnd.nextInt(MAX_MONEY));
class TransferThread extends Thread {
public void run() {
for (int i = 0; i < NUM_ITERATIONS; i++) {
int fromAcct = rnd.nextInt(NUM_ACCOUNTS);
int toAcct = rnd.nextInt(NUM_ACCOUNTS);
DollarAmount amount = new DollarAmount(rnd.nextInt(1000));
try {
DynamicOrderDeadlock.transferMoney(accounts[fromAcct], accounts[toAcct], amount);
} catch (DynamicOrderDeadlock.InsufficientFundsException ignored) {
System.out.println("no money left.");
}
}
}
}
for (int i = 0; i < NUM_THREADS; i++)
new TransferThread().start();
System.out.println("Done.");
}
// Warning: deadlock-prone!
public static void transferMoney(Account fromAccount,
Account toAccount,
DollarAmount amount)
throws InsufficientFundsException {
synchronized (fromAccount) {
synchronized (toAccount) {
if (fromAccount.getBalance().compareTo(amount) < 0)
throw new InsufficientFundsException();
else {
fromAccount.debit(amount);
toAccount.credit(amount);
}
}
}
}
static class DollarAmount implements Comparable<DollarAmount> {
int amount;
public DollarAmount(int amount) {
this.amount = amount;
}
public DollarAmount add(DollarAmount d) {
this.amount += d.amount;
return this;
}
public DollarAmount subtract(DollarAmount d) {
this.amount -= d.amount;
return this;
}
public int compareTo(DollarAmount dollarAmount) {
return this.amount - dollarAmount.amount;
}
}
static class Account {
private DollarAmount balance;
private final int acctNo;
private static final AtomicInteger sequence = new AtomicInteger();
public Account(int money) {
acctNo = sequence.incrementAndGet();
balance = new DollarAmount(money);
}
void debit(DollarAmount d) {
balance = balance.subtract(d);
}
void credit(DollarAmount d) {
balance = balance.add(d);
}
DollarAmount getBalance() {
return balance;
}
int getAcctNo() {
return acctNo;
}
}
static class InsufficientFundsException extends Exception {
}
}
This example demonstrates a deadlock situation for money transfer between banking accounts. The main thread ticked start 20 threads, then print "Done" and exit. Each thread then handles 100 money transactions then exit. If all threads running money transfer finishes executing, the program exits normally. If any threads get into deadlock situation, the program hangs forever. You have to use Ctrl+C to exit.
This program can experience deadlock because it locks two accounts in a random order during money transfers. Each transfer operation locks the source account first and then the destination account. However, since both accounts are chosen randomly, two threads might pick the same pair of accounts in reverse order at the same time. For example, Thread A might lock Account 1 and try to lock Account 2, while Thread B locks Account 2 and tries to lock Account 1. In this situation, each thread holds one lock and waits for the other, resulting in both threads being blocked indefinitely. This is a classic deadlock scenario caused by inconsistent lock ordering. The problem can be avoided by enforcing a fixed global order when acquiring locks, such as always locking the account with the smaller account number first. This prevents circular waiting, which is one of the necessary conditions for deadlock to occur.
No comments:
Post a Comment