DeadLock and its causes

"Hi, Amigo!"

"Today I'm going to tell you what deadlock is."

"Hey, you already told me about something like that."

"Yep, I did. But today we'll consider the topic in greater detail."

"In the simplest case, deadlock involves two threads and two mutex objects. A mutual lock occurs when:"

A) Each thread needs to acquire both mutexes.

B) The first thread has acquired the first mutex and is waiting for the second one to be released.

C) The second thread has acquired the second mutex and is waiting for the first one to be released.

"Here are some examples:

 public class Student
{
 private ArrayList friends = new ArrayList();

 public synchronized ArrayList getFriends()
 {
  synchronized(friends)
  {
   return new ArrayList(friends);
  }
 }

 public synchronized int getFriendsCount()
 {
  return friends.size();
 }

 public int addFriend(Student student)
 {
  synchronized(friends)
  {
   friends.add(student)
   return getFriendsCount ();
  }
 }
}

"Suppose a thread calls the getFriends method, acquires the this object's mutex, and then acquires the friends object's mutex."

"Meanwhile, a second thread calls the addFriend method, acquires the friends object's mutex, and then acquires the this object's mutex (during a call to getFriendsCount)."

"At first, everything will be fine, but as Murphy's Law states: anything that can go wrong will go wrong. A situation will inevitably arise where the first thread will only have time to acquire one mutex, and the second thread will acquire the second mutex at that very moment. They will hang like that, forever waiting for the other thread to release the mutex."

"I've decided to quote another simple example I found in a book:"

class KnightUtil
{
 public static void kill(Knight knight1, Knight knight2)
 {
  synchronized(knight1)
  {
   synchronized(knight2)
   {
    knight2.live = 0;
    knight1.experience += 100;
   }
  }
 }
}

"There's a game where two knights are fighting each other. One knight kills the other. This behavior is reflected in the kill method. Two knight objects are passed to it.

"First, we protect both objects so no one else can change them."

"The second knight dies (HP = 0)"

"The first knight gains 100 XP."

"Everything seems fine, but there may be situations where the second knight attacks the first at the same time. This method is also called for the second knight, but the knight objects are passed in a different order."

"You mean we don't even need multiple methods to get deadlock?"

"Right. Sometimes it only takes one simple method to cause threads, and the whole program, to hang."

"Yeah, I guess this phenomenon occurs more often than I thought. Thanks, Ellie."