XYZ CODE: DeadlockAvoidance.java

DeadlockAvoidance.java

import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import static java.util.concurrent.TimeUnit.NANOSECONDS;

/**
 * DeadlockAvoidance
 * <p/>
 * Avoiding lock-ordering deadlock using tryLock
 *
 */
public class DeadlockAvoidance {

    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;

    private static final long TIMEOUT = 100;
    private static final TimeUnit TIMEUNITS = NANOSECONDS;

    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 {
                        DeadlockAvoidance.transferMoney(accounts[fromAcct], accounts[toAcct], amount, TIMEOUT, TIMEUNITS);
                    } catch (DeadlockAvoidance.InsufficientFundsException ignored) {
                        //System.out.println("no money left.");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    //System.out.println("transfered " + amount.amount);
                }
            }
        }
        for (int i = 0; i < NUM_THREADS; i++)
            new TransferThread().start();
        
        System.out.println("Done.");
    }

    private static Random rnd = new Random();

    public static boolean transferMoney(Account fromAcct,
                                 Account toAcct,
                                 DollarAmount amount,
                                 long timeout,
                                 TimeUnit unit)
            throws InsufficientFundsException, InterruptedException {
        long fixedDelay = getFixedDelayComponentNanos(timeout, unit);
        long randMod = getRandomDelayModulusNanos(timeout, unit);
        long timeoutNanos = unit.toNanos(timeout);
        long startTime = System.nanoTime();

        while (true) {
            if (fromAcct.lock.tryLock()) {
                try {
                    if (toAcct.lock.tryLock()) {
                        try {
                            if (fromAcct.getBalance().compareTo(amount) < 0)
                                throw new InsufficientFundsException();
                            else {
                                fromAcct.debit(amount);
                                toAcct.credit(amount);
                                return true;
                            }
                        } finally {
                            toAcct.lock.unlock();
                        }
                    }
                } finally {
                    fromAcct.lock.unlock();
                }
            }
            if (System.nanoTime() - startTime >= timeoutNanos)
                return false;
            NANOSECONDS.sleep(fixedDelay + rnd.nextLong() % randMod);
        }
    }

    private static final int DELAY_FIXED = 1;
    private static final int DELAY_RANDOM = 2;

    static long getFixedDelayComponentNanos(long timeout, TimeUnit unit) {
        return DELAY_FIXED;
    }

    static long getRandomDelayModulusNanos(long timeout, TimeUnit unit) {
        return DELAY_RANDOM;
    }


    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 {
        public Lock lock;
        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);
            lock = new ReentrantLock();
        }

        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 demonstrates a deadlock-avoidance strategy using explicit locks (ReentrantLock) and tryLock() from Java's Lock interface, as discussed in Chapter 13 of Java Concurrency in Practice. Multiple threads attempt to transfer money between shared Account objects, each protected by its own lock. To prevent classic deadlock scenarios caused by circular lock dependencies, the program uses tryLock() with a timeout and randomized backoff: if both account locks cannot be acquired promptly, the thread releases any held lock, waits briefly, and retries. This lock acquisition loop ensures progress without indefinite blocking, illustrating a robust non-blocking synchronization pattern ideal for high-concurrency financial systems.

XYZ CODE

DeadlockAvoidance.java

No comments:

Post a Comment