Locking Strategies and Deadlocks

1. Overview

In concurrent computing, a deadlock is a state in which each member of a group is waiting for another member, including itself, to take action, such as sending a message or more commonly releasing a lock. Deadlock is a common problem in multiprocessing systems, parallel computing, and distributed systems, where software and hardware locks are used to arbitrate shared resources and implement process synchronization.

2. Locking Strategies

2.1 Coarse-Grained Locking

public class SharedClass {
	private DatabaseConnection dbConnection;
    private List<Task> tasksQueue;
    
    public synchronized Item getItemFromDB() {
    	...
    }
    public synchronized void addTaskToQueue() {
    	...
    }
}

2.2 Fine-Grained Locking

public class SharedClass {
	private DatabaseConnection dbConnection;
    private List<Task> tasksQueue;
    
    public Item getItemFromDB() {
    	synchronized(dbConnection) {
        	...
        }    	
    }
    public void addTaskToQueue() {
    	synchronized(tasksQueue) {
        	...
        }
    }
}

3. Deadlock

public class deadlockDemo {

    public static void main(String[] args) {
        Intersection intersection = new Intersection();
        Thread trainAThread = new Thread(new TrainA(intersection));
        Thread trainBThread = new Thread(new TrainB(intersection));

        trainAThread.start();
        trainBThread.start();
    }
    public static class TrainB implements Runnable {
        private Intersection intersection;
        private Random random = new Random();

        public TrainB(Intersection intersection) {
            this.intersection = intersection;
        }

        @Override
        public void run() {
            long sleepingTime = random.nextInt(5);
            try {
                Thread.sleep(sleepingTime);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            intersection.takeRoadB();
        }
    }
    public static class TrainA implements Runnable {
        private Intersection intersection;
        private Random random = new Random();

        public TrainA(Intersection intersection) {
            this.intersection = intersection;
        }

        @Override
        public void run() {
            long sleepingTime = random.nextInt(5);
            try {
                Thread.sleep(sleepingTime);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            intersection.takeRoadA();
        }
    }
    public static class Intersection {
        private Object roadA = new Object();
        private Object roadB = new Object();
        public void takeRoadA() {
            synchronized (roadA) {
                System.out.println("Road A is locked by thread " + Thread.currentThread().getName());

                synchronized (roadB) {
                    System.out.println("Train is passing through road A");
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
        public void takeRoadB() {
            synchronized (roadB) {
                System.out.println("Road A is locked by thread " + Thread.currentThread().getName());
                synchronized (roadA) {
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
    }
}

3.1 Deadlock Condition

If we have a situation where all of those conditions are met then a deadlock is possible and is only a matter of time

3.1.1 Mutual Exclusion

Only one thread can have exclusive access to a resource

3.1.2 Hold and Wait

At least one thread is holding a resource and is waiting for another resource

3.1.3 Non-preemptive allocation

A resource is released only after the thread is done using it

3.1.4 Circular wait

A chain of at least two threads each one is holding one resource and waiting for another resource

3.2 Solution to Deadlock

3.2.1 Avoid Circular wait

• Enforce a strict order in lock acquisition
• Easy to do with a small number of locks
• Maybe hard to accomplish if there are many locks in different places

public class deadlockDemo {

    public static void main(String[] args) {
        Intersection intersection = new Intersection();
        Thread trainAThread = new Thread(new TrainA(intersection));
        Thread trainBThread = new Thread(new TrainB(intersection));

        trainAThread.start();
        trainBThread.start();
    }
    public static class TrainB implements Runnable {
        private Intersection intersection;
        private Random random = new Random();

        public TrainB(Intersection intersection) {
            this.intersection = intersection;
        }

        @Override
        public void run() {
            long sleepingTime = random.nextInt(5);
            try {
                Thread.sleep(sleepingTime);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            intersection.takeRoadB();
        }
    }
    public static class TrainA implements Runnable {
        private Intersection intersection;
        private Random random = new Random();

        public TrainA(Intersection intersection) {
            this.intersection = intersection;
        }

        @Override
        public void run() {
            long sleepingTime = random.nextInt(5);
            try {
                Thread.sleep(sleepingTime);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            intersection.takeRoadA();
        }
    }
    public static class Intersection {
        private Object roadA = new Object();
        private Object roadB = new Object();
        public void takeRoadA() {
            synchronized (roadA) {
                System.out.println("Road A is locked by thread " + Thread.currentThread().getName());

                synchronized (roadB) {
                    System.out.println("Train is passing through road A");
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
        public void takeRoadB() {
            synchronized (roadA) {
                System.out.println("Road A is locked by thread " + Thread.currentThread().getName());
                synchronized (roadB) {
                    try {
                        Thread.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
    }
}

3.2.2 Other techniques

• Deadlock detection - Watchdog
• Thread interruption which is not possible with synchronized
• tryLock operations which are not possible with synchronized

4. Reference

https://en.wikipedia.org/wiki/Deadlock

https://www.usna.edu/Users/cs/aviv/classes/ic221/s16/lec/29/lec.html