import java.util.Random;
import java.util.concurrent.atomic.AtomicInteger;
/**
* InduceLockOrder
*
* Inducing a lock order to avoid deadlock
*
*/
public class InduceLockOrder {
private static final int NUM_THREADS = 20;
private static final int NUM_ACCOUNTS = 5;
private static final int NUM_ITERATIONS = 1000000;
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 {
InduceLockOrder.transferMoney(accounts[fromAcct], accounts[toAcct], amount);
} catch (InduceLockOrder.InsufficientFundsException ignored) {
//System.out.println("no money left.");
}
}
}
}
for (int i = 0; i < NUM_THREADS; i++)
new TransferThread().start();
System.out.println("Done.");
}
private static final Object tieLock = new Object();
public static void transferMoney(final Account fromAcct,
final Account toAcct,
final DollarAmount amount)
throws InsufficientFundsException {
class Helper {
public void transfer() throws InsufficientFundsException {
if (fromAcct.getBalance().compareTo(amount) < 0)
throw new InsufficientFundsException();
else {
fromAcct.debit(amount);
toAcct.credit(amount);
}
}
}
int fromHash = System.identityHashCode(fromAcct);
int toHash = System.identityHashCode(toAcct);
if (fromHash < toHash) {
synchronized (fromAcct) {
synchronized (toAcct) {
new Helper().transfer();
}
}
} else if (fromHash > toHash) {
synchronized (toAcct) {
synchronized (fromAcct) {
new Helper().transfer();
}
}
} else {
synchronized (tieLock) {
synchronized (fromAcct) {
synchronized (toAcct) {
new Helper().transfer();
}
}
}
}
}
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 program simulates money transfers between accounts using multiple threads while avoiding deadlock by imposing a consistent lock acquisition order. The main thread ticked start 20 threads, then print "Done" and exit. Each thread then handles 1000000 money transactions then exit. In each transfer, it compares the identity hash codes of the two account objects and locks them in ascending order, ensuring that no two threads acquire the same pair of locks in reverse. If two accounts have the same hash code (a rare but possible case), it uses a third tie-breaking lock to avoid deadlock. This strategy guarantees that all threads follow a global locking order, thereby eliminating the circular wait condition that causes deadlocks.
No comments:
Post a Comment