how to avoid deadlock

Dear experts

Is there anyway we can avoid the deadlock described in the classic deadlock described below?


Alphonse and Gaston are friends, and great believers in courtesy. A strict rule of courtesy is that when you bow to a friend, you must remain bowed until your friend has a chance to return the bow. Unfortunately, this rule does not account for the possibility that two friends might bow to each other at the same time. This example application, Deadlock, models this possibility:

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s"
                + "  has bowed to me!%n", 
                this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                + " has bowed back to me!%n",
                this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); }
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); }
        }).start();
    }
}

Open in new window


source taken from
https://docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html

Is there any way we can avoid this above deadlock using any programming constructs ?

thanks
royjaydAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

mccarlIT Business Systems Analyst / Software DeveloperCommented:
Is there any way we can avoid this above deadlock using any programming constructs ?

I think what they are trying to demonstrate it to NOT get into this situation in the first place rather there being any particular way of fixing this. What IS the situation that they are trying to describe? Well, basically what they are trying to get at is to always lock resources in the same order. In the above, the first thread attempts to lock "alphonse" first and then try "gaston" and the second thread attempts to lock "gaston" first and then try "alphonse". If you ever have a situation where you need to lock multiple resources always try to lock them in the same order to prevent this.

How to make the above code work? There are probably many ways but one way would be to serialize access to the entire resource locking sections, such as this...

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s"
                + "  has bowed to me!%n", 
                this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                + " has bowed back to me!%n",
                this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Object bowCoordinator = new Object();

        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { synchronized (bowCoordinator) { alphonse.bow(gaston); } }
        }).start();
        new Thread(new Runnable() {
            public void run() { synchronized (bowCoordinator) { gaston.bow(alphonse); } }
        }).start();
    }
}

Open in new window

dpearsonCommented:
As mccarl says, one way to avoid deadlocks is to "always acquire the locks in the same order".  There's no doubt that this will prevent the deadlock.  However, in practice I've always found it to almost impossible to achieve.  In a moderately complex system (with many synchronized statements and hence many locks) it quickly becomes equivalent to "always call all methods in the same order".

When you reduce it to that requirement, it starts to become clear how difficult this is to achieve as shared code is frequently called in different order from different parts of the code.

So personally, I prefer a different solution.  What I advocate to avoid deadlocks is "never maintain a lock while calling another method".  This also clearly prevents deadlocks and is very simple to implement.  The question is can you write useful multi-threaded code with this restriction in place?  After writing nothing but multi-threaded code for the last 5+ years I can safely say the answer is "yes".

Let's look at this particular case.  The requirement is that you should remain bowed until your counterpart has bowed back.  Well, there's no shared state required for this - so actually no need (that I can see) for the synchronized statements at all.  So solution #1 is to just remove the synchronized statements.  Clearly no deadlock and people who bow, triggering bowing back to them.

However, maybe that seems like a cheat.  So solution #2 is to make the state of "is bowing" explicit.  If so, we should not make that a boolean which is set inside the "bow" method and keep "bow" synchronized because then we'd have code like this:

		public synchronized  void bow(Friend bower) {
			m_IsBowing = true;
			System.out.format("%s: %s"
							+ "  is bowing %s to me!%n",
					this.name, bower.getName(), m_IsBowing.get());
			bower.bowBack(this);
			m_IsBowing = false ;
		}

Open in new window


which can still deadlock because it's calling synchronize (i.e. getting a lock) and then calling to another method.  (Violates my personal rule for how to avoid deadlocks).

So instead we should do this and use an AtomicInteger (effectively like short-hand for writing synchronize around the accesses to the variable) and count 1 each time a person bows and -1 each time they rise from that bow.  This way if A bows to B and B bows back, B's count goes to 2 for a bit.  This state can be happily shared between the threads and each thread can run with full concurrency and no deadlocks.

	static class Friend {
		private final AtomicInteger bows = new AtomicInteger(0) ;

		private final String name;
		public Friend(String name) {
			this.name = name;
		}
		public String getName() {
			return this.name;
		}
		public void bow(Friend bower) {
			bows.incrementAndGet() ;

			boolean isBowing = (bows.get() > 0) ;
			System.out.format("%s: is bowing to %s"
							+ " (and %s is bowing now %s)%n",
					this.name, bower.getName(), this.name, isBowing);
			bower.bowBack(this);

			bows.decrementAndGet() ;
		}
		public void bowBack(Friend bower) {
			bows.incrementAndGet() ;

			boolean isBowing = (bower.bows.get() > 0) ;
			System.out.format("%s: has bowed back to %s"
							+ " (and %s is bowing now %s) !%n",
					this.name, bower.getName(), bower.getName(), isBowing);

			bows.decrementAndGet() ;
		}
	}

Open in new window


I also tweaked the test code so you can easily have each bows 100s of times to the other:

	public static void main(String[] args) {
		final int count = 2 ;
		final Friend alphonse =
				new Friend("Alphonse");
		final Friend gaston =
				new Friend("Gaston");
		new Thread(new Runnable() {
			public void run() { for (int i = 0 ; i < count ; i++) alphonse.bow(gaston); }
		}).start();
		new Thread(new Runnable() {
			public void run() { for (int i = 0 ; i < count ; i++) gaston.bow(alphonse); }
		}).start();
	}

Open in new window


The result of this should be output like this:

Alphonse: is bowing to Gaston (and Alphonse is bowing now true)
Gaston: has bowed back to Alphonse (and Alphonse is bowing now true) !
Gaston: is bowing to Alphonse (and Gaston is bowing now true)
Alphonse: is bowing to Gaston (and Alphonse is bowing now true)
Alphonse: has bowed back to Gaston (and Gaston is bowing now true) !
Gaston: has bowed back to Alphonse (and Alphonse is bowing now true) !
Gaston: is bowing to Alphonse (and Gaston is bowing now true)
Alphonse: has bowed back to Gaston (and Gaston is bowing now true) !

where you can see that A & G are both bowing and bowing back to each other (not always at the same rate or in the same order - since it's two concurrent threads) but each time we see that "(and A is bowing now true)" - shows that at all times when G bows to A and then A bows back to G, G is still bowing (and vice versa).

If we ever see "and X is bowing now false" that would be a sign that they stood up before they'd fully received their "bow back".

Anyway - it's another take on solving this concurrency/deadlock thing.

Hope it helps,

Doug

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.