Lab 6: Monitors and Thread Synchronization 2

	Sign In Sign-Up

Concurrent Programming with Java
Lab Manual, Version 1.0, F. Astha Ekadiyanto, 2002.

[Contents] [Next] [Previous]

Lab 6: Monitors and Thread Synchronization 2

Deadlock and Starvation Condition
Dining Philosophers synchronization scenario Demonstration
Challenge Lab.

Starvation and Deadlock Condition

Definitions:

Starvation is a situation where a process/thread is prevented from making progress because some other process has the resource it requires (resource could be the CPU, or a lock).

Deadlock is an ultimate form of starvation. It is a situation when all the processes/threads cannot progress (blocked).

There are four steps of condition that can lead to deadlock namely:

Serially reusable resources:
the processes involved share resources which they use under mutual exclusion.
Incremental acquisition:
processes hold on to resources already allocated to them while waiting to acquire additional resources.
No pre-emption:
once acquired by a process, resources cannot be pre-empted (forcibly withdrawn) but are only released voluntarily.
Wait-for cycle:
a circular chain (or cycle) of processes exists such that each process holds a resource which its successor in the cycle is waiting to acquire.

The codes below will simulate a simple deadlock scenario:

BlueJ Project: SimpleDeadlock

Class Name: Boy

public class Boy extends Thread
{
   String name,olddate,newdate; 

   Boy(String name, String olddate, String newdate)
   {
       this.name=name;
       this.olddate=olddate;
       this.newdate=newdate;
   }
   
   public void run()
   {
       System.out.println(name + " is about to call "+ olddate);
       synchronized(olddate)
       {
           System.out.println( name + " is cancelling dates with " + olddate);
           try { sleep(1000); } catch(InterruptedException e) {} 
           System.out.println( name + " is about to call his newdate.");
           synchronized(newdate)
           {
               System.out.println( name + " is asking " + newdate + " out.");
           }
       }
       System.out.println( name + " got a new date."); 
   } 
}

The codes above seems OK for a Thread called Boy to perform his "Making new date" procedure. The process is as follows:

Try to call and lock the olddate
Cancel the date with olddate
While still locking olddate, try to call and lock the newdate
ask the newdate out
Got newdate and release all locks

Over the whole world, the chance of successfully performing the process is almost 100 percent. But now comes the worse scenario. Suppose in the same time, two boys are performing the same process but with each other's girlfriend. The java application below will demonstrate:

Class Name: DeadlockDemo

public class DeadlockDemo
{
   public static void main(String args[])
   {
      String girl1 = "Jane";
      String girl2 = "Lucy";
      Boy boy1 = new Boy("John", girl1, girl2);
      Boy boy2 = new Boy("Tom", girl2, girl1);  
      boy1.start();
      boy2.start();
   }
}

Try to run the Application and you will end up with the results below:

D:\simpleDeadlock>java DeadlockDemo
John is about to call Jane
John is cancelling dates with Jane
Tom is about to call Lucy
Tom is cancelling dates with Lucy
John is about to call his newdate.
Tom is about to call his newdate.

What happened is, both John and Tom failed to call their newdates because they were locked. By the end, they both did not get a date at all and got blocked when calling :).

This is one of the deadlock example. The example seems very simple and obvious that it is easy to detect. In real problems, we often do not recognize them when coding a synchronized methods.

Note:

Java allows nested monitors which will not block a Thread when called. Observe to following code partition:

class TheObject
{
    synchronized void method1()
    {
         method2(); // calls method2
    }

    synchronized void method2() // introduce nested monitor when called from method1()
    {
         // execute something
    }
}

When a Thread calls TheObject.method1(), which in turn will reaccess call TheObject.method2(), the Thread will not be blocked since the monitor for TheObject is again the calling Thread itself. The Thread will only be blocked when calling TheObject.method2() and there is another Thread that is currently using TheObject.method1() (or TheObject.method1()) and owns the monitor.

[Contents] [Next] [Previous]