Difference between revisions of "CSC352 Synchronization and Java Threads"

From dftwiki3
Jump to: navigation, search
(Reentrant Code/Reentrancy)
 
(30 intermediate revisions by the same user not shown)
Line 3: Line 3:
  
 
<bluebox>
 
<bluebox>
This page treats of the concepts of synchronization of parallel programs in general, applied to the Java platform in particular.
+
This page treats of the concepts of Java threads, and of the synchronization of the access to shared data between threads.
 
</bluebox>
 
</bluebox>
 
<br />
 
<br />
Line 15: Line 15:
 
* [[CSC352: Computing Pi and Synchronization| Computing Pi and Synchronization]] programs
 
* [[CSC352: Computing Pi and Synchronization| Computing Pi and Synchronization]] programs
 
<br />
 
<br />
 +
=Declaring a Thread in Java=
 +
<br />
 +
Here is a simple example program that starts one thread only.  The thread prints a message, waits one second, prints another message, then stops.
 +
<br />
 +
::<source lang="java">
 +
class MyThread extends Thread{ 
 +
    public void run(){ 
 +
System.out.println( "thread is running..." ); 
 +
 +
try {
 +
    Thread.sleep( 1000 ); // 1 sec
 +
}
 +
catch (InterruptedException ie) {
 +
            ie.printStackTrace();
 +
}
 +
 +
System.out.println( "thread is done..." );
 +
    } 
 +
}
 +
 +
public class SimpleThreadDemo {
 +
    public static void main(String args[]){ 
 +
// declare a new thread
 +
MyThread t1=new MyThread(); 
 +
 +
// start a new thread
 +
t1.start(); 
 +
 +
// wait for the thread to be done
 +
try {
 +
    t1.join();
 +
}
 +
catch (InterruptedException ie) {
 +
    ie.printStackTrace();
 +
}
 +
 +
// Exit
 +
System.out.println( "Done!" );
 +
 +
    } 
 +
}
 +
</source>
 +
<br />
 +
==Output==
 +
<br />
 +
 +
aurora:~/handout> java SimpleThreadDemo
 +
thread is running...
 +
thread is done...
 +
Done!
 +
aurora:~/handout>
 +
 +
<br />
 +
==Passing Arguments to Java Threads ==
 +
<br />
 +
To pass arguments to a thread, we simply need to pass them through the constructor, as illustrated in the example below.
 +
<br />
 +
::<source lang="java">
 +
/* SimpleThreadDemoWithArgs.java
 +
D. Thiebaut
 +
 +
Same as SimpleThreadDemo, but this one illustrates
 +
how main can pass arguments to the thread.
 +
 +
*/
 +
class MyThread extends Thread{ 
 +
    int Id = 0;  // The Id of the thread
 +
 +
    public MyThread( int id ){
 +
Id = id;
 +
    }
 +
 +
    public void run(){ 
 +
System.out.println( "thread "+Id+" is running..." ); 
 +
 +
try {
 +
    Thread.sleep( 1000 ); // 1 sec
 +
}
 +
catch (InterruptedException ie) {
 +
            ie.printStackTrace();
 +
}
 +
 +
System.out.println( "thread "+Id+" is done..." );
 +
    } 
 +
}
 +
 +
public class SimpleThreadDemoWithArgs {
 +
    public static void main(String args[]){ 
 +
// declare a new thread with Id 33
 +
MyThread t1=new MyThread( 33 );
 +
 +
// start a new thread
 +
t1.start(); 
 +
 +
// wait for the thread to be done
 +
try {
 +
    t1.join();
 +
}
 +
catch (InterruptedException ie) {
 +
    ie.printStackTrace();
 +
}
 +
 +
// Exit
 +
System.out.println( "Done!" );
 +
 +
    } 
 +
}
 +
</source>
 +
<br />
 +
==Output==
 +
<br />
 +
 +
aurora:~/handout> java SimpleThreadDemoWithArgs
 +
thread 33 is running...
 +
thread 33 is done...
 +
Done!
 +
aurora:~/handout>
 +
 
=It all starts at the Lowest Level: Assembly Language (again)=
 
=It all starts at the Lowest Level: Assembly Language (again)=
  
Line 21: Line 139:
 
     public void run() {
 
     public void run() {
 
     &nbsp;&nbsp;&nbsp;                  for ( int i=0; i<N; i++ )
 
     &nbsp;&nbsp;&nbsp;                  for ( int i=0; i<N; i++ )
     &nbsp;&nbsp;&nbsp;                           sum ++;
+
     &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;                          sum ++;
 
                 }
 
                 }
 
   
 
   
Line 33: Line 151:
 
: What makes the code fail?  What is the processor missing?
 
: What makes the code fail?  What is the processor missing?
 
; Question 4
 
; Question 4
: What is a way around the problem, such that two parallel update of the variable '''sum''' will increment it by 2, every time?
+
: What is a way around the problem, such that two parallel updates of the variable '''sum''' will increment it by 2 every time?
  
 
<br />
 
<br />
  
=Demo=
+
=How to Synchronize Access to Shared Variables=
 +
<br />
 +
First we're going to look at what NOT to do, understand why, and see what tools Java gives us to get around the problem.
 
<br />
 
<br />
 
==A Badly Synchronized Parallel Program==
 
==A Badly Synchronized Parallel Program==
<source lang="java" highlight="13-26">
+
<br />
 +
::<source lang="java" highlight="13-26">
 
/*
 
/*
 
  * UnsynchronizedThreadExample.java
 
  * UnsynchronizedThreadExample.java
Line 121: Line 242:
 
* ''Intrinsic Lock'' = ''Monitor Lock'' =''Monitor'' (most common definition)
 
* ''Intrinsic Lock'' = ''Monitor Lock'' =''Monitor'' (most common definition)
 
* In Java each object contains a '''Lock'''
 
* In Java each object contains a '''Lock'''
* ''Exclusive access''' to the object can be performed by ''acquiring'' the lock.
+
* ''Exclusive access'' to the object can be performed by ''acquiring'' the lock.
 
* A thread ''locking'' an object must ''release'' it when it's done updating it.
 
* A thread ''locking'' an object must ''release'' it when it's done updating it.
 +
<br />
 +
==Example With Locks==
 +
<br />
 +
::<source lang="java">
 +
/*
 +
SynchronizedLockThreadExample.java
 +
D. Thiebaut
 +
 +
This threaded java code uses locks to serialize access to the
 +
shared variable.
 +
 +
*/
 +
import java.util.concurrent.locks.ReentrantLock;
 +
 +
public class SynchronizedLockThreadExample {
 +
 +
        static long sum = 0;
 +
        private ReentrantLock lock = new ReentrantLock();
 +
 +
        class PiThreadGood extends Thread {
 +
                private long N;                  // the total number of samples/iterations
 +
 +
                public PiThreadGood( int Id, long N ) {
 +
                        super( "Thread-"+Id ); // give a name to the thread
 +
                        this.N          = N;
 +
                }
 +
                       
 +
                @Override
 +
                public void run() {
 +
    for ( long i=0; i<N; i++ ) {
 +
 +
lock.lock();
 +
try{
 +
    sum++;
 +
} finally {
 +
    lock.unlock();
 +
}
 +
    }
 +
                }
 +
        }
 +
 +
        public void process( long N ) {
 +
            long startTime = System.currentTimeMillis();
 +
            PiThreadGood t1 = new PiThreadGood( 0, N );
 +
            PiThreadGood t2 = new PiThreadGood( 1, N );
 +
               
 +
            //--- start two threads ---
 +
            t1.start();
 +
            t2.start();
 +
               
 +
            //--- wait till they finish ---
 +
            try {
 +
                t1.join();
 +
                t2.join();
 +
            } catch (InterruptedException e) {
 +
                e.printStackTrace();
 +
            }
 +
               
 +
            System.out.println( "sum = " + sum );
 +
            System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
 +
        }
 +
   
 +
    public static void main(String[] args) {
 +
        long N = 1000000000l;
 +
        SynchronizedLockThreadExample S = new SynchronizedLockThreadExample();
 +
        S.process( N );
 +
    }
 +
 +
}
 +
 +
</source>
 +
<br />
 +
==Output==
 +
<br />
 +
aurora:~/handout> java SynchronizedLockThreadExample
 +
sum = 2000000000
 +
Execution time: 14972 ms
 +
aurora:~/handout>
 +
<br />
 +
=Synchronized Sections=
 +
<br />
 +
Locks allow fine-grain control of shared variables and data structures, but maintaining them correctly in the code requires very careful attention, especially if the locked section calls other functions, and several conditions may exist for releasing the lock.
 +
 +
Fortunately, Java offers a simpler (though less flexible) way of locking whole methods or sections of code with the keyword '''synchronized'''.
 +
 
* The keyword '''synchronized( )''' is used to  
 
* The keyword '''synchronized( )''' is used to  
 
** define an object whose lock is going to be used  
 
** define an object whose lock is going to be used  
Line 133: Line 339:
 
<br />
 
<br />
 
<source lang="java" highlight="3-5">
 
<source lang="java" highlight="3-5">
  public void addNewCustomer( String name ) {
+
  public void addNewCustomerMethod( String name ) {
 
     name = name.trim().toUpper();
 
     name = name.trim().toUpper();
 
     synchronized( this ) {
 
     synchronized( this ) {
Line 142: Line 348:
 
<br />
 
<br />
 
<br />
 
<br />
 +
 
==Example 2==
 
==Example 2==
 
Assume that you do not need to trim() or change the strings to uppercase, then the whole body of the method is a critical section.  In this case you can make the whole method '''synchronized''':
 
Assume that you do not need to trim() or change the strings to uppercase, then the whole body of the method is a critical section.  In this case you can make the whole method '''synchronized''':
Line 147: Line 354:
 
<br />
 
<br />
 
<source lang="java" highlight="1-3">
 
<source lang="java" highlight="1-3">
  public synchronized void addNewCustomer( String name ) {
+
  public synchronized void addNewCustomerMethod( String name ) {
 
           myList.add( name );
 
           myList.add( name );
 
  }
 
  }
Line 153: Line 360:
 
<br />
 
<br />
 
<br />
 
<br />
 +
 
==Example 3==
 
==Example 3==
 
In some cases you may have several variables/data structures that you need to modify, but they do not depend on each other, and updating one is a completely independent operation from updating the other.  In this case you can create your own '''locks'''.  This example is take from the [http://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html Oracle tutorial pages]:
 
In some cases you may have several variables/data structures that you need to modify, but they do not depend on each other, and updating one is a completely independent operation from updating the other.  In this case you can create your own '''locks'''.  This example is take from the [http://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html Oracle tutorial pages]:
Line 206: Line 414:
 
|-
 
|-
 
|
 
|
 +
  
 
===Challenge 3===
 
===Challenge 3===
Line 211: Line 420:
 
[[Image:QuestionMark4.jpg|right|120px]]
 
[[Image:QuestionMark4.jpg|right|120px]]
 
<br />
 
<br />
Modify the program so that the computation return is actually an approximation of Pi and not 2,000,000.
+
Modify the program so that the computation returned is actually an approximation of Pi and not 2,000,000. Measure it's '''speedup ''' as a function of the number of threads ''N'', for ''N'' ranging from 1 to 10.
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 
<br />
 
<br />
 
<br />
 
<br />
 
<br />
 
<br />
 
<br />
 
<br />
 +
 +
===Solutions===
 +
You can find solutions to these challenges [[CSC352:_Java_Threads_and_Synchronization_Examples| here]].
 
<br />
 
<br />
  
 +
<br />
 
<br />
 
<br />
  
Line 225: Line 442:
 
* When a thread is stopped because it has attempted to lock an object but an other thread held the lock, we say that this thread is '''stalled'''.
 
* When a thread is stopped because it has attempted to lock an object but an other thread held the lock, we say that this thread is '''stalled'''.
 
* When a shared object is the object that is most utilized by thread, it is said to be the '''bottleneck''' object.
 
* When a shared object is the object that is most utilized by thread, it is said to be the '''bottleneck''' object.
 +
* '''Liveliness''': the ability of a threaded/parallel application to execute in a timely manner.  When an application does not present liveliness of operation, it is usually due to one of several potential problems
 +
** '''Deadlock'''
 +
** '''Starvation'''
 +
** '''Livelock'''
 +
* '''Deadlock''': a situation where two or more threads are blocked forever, waiting on each other.
 +
* '''Starvation''': a situation where a thread is unable to get access to a resource and is unable to progress.  This is often due to greedy threads.
 +
* '''Livelock''': a situation where threads are not blocked, are running, but are waiting on each other before continuing.  This often occurs because a thread my test whether a resource is available or not using a non-blocking function, and will busy itself with other work if the resource is not available.
 +
[[Image:DiningPhilosophersApplet.png|right|250px]]
 +
* [http://en.wikipedia.org/wiki/Dining_philosophers_problem The dining philosophers problem], and the associated [http://elvis.rowan.edu/~hartley/ConcProgJava/Applets/diningPhilosophers.html applet]
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<bluebox>
 +
Important Rule for avoiding deadlocks: If a thread needs several locks to operate, it should try acquiring all of them, one after the other.  If it can't acquire one of them, it should '''release them all''', wait some random amount of time, and try again.  This will prevent the dining-philosopher potential deadlock.
 +
</bluebox>
 
<br />
 
<br />
=Reentrant Code/Reentrancy=
 
 
<br />
 
<br />
A thread might acquire a lock, do some work on the locked data structure, and call another method that needs to be synchronized as well.  Java allows a thread to automatically ''re-acquire'' a lock that it holds.  This property is called '''reentrancy''' of the code.
+
<br />
 +
<br />
 +
<br />
 +
 
 +
* '''Sleep''': A thread can sleep for some interval of time using the '''sleep''' function
 +
 +
  sleep( m );  // where m is some integer number of milliseconds
 +
 
 +
Note that the operating system is in charge of figuring out how close to ''m'' milliseconds the thread actually sleeps.  Usually the amount of sleep it is '''&gt;''' ''m'' ms, never exact to that amount.
 +
 
 +
*'''Reentrant Code/Reentrancy''': A thread might acquire a lock, do some work on the locked data structure, and call another method that needs to be synchronized as well.  Java allows a thread to automatically ''re-acquire'' a lock that it holds.  This property is called '''reentrancy''' of the code.

Latest revision as of 12:40, 7 February 2017

--D. Thiebaut (talk) 14:10, 9 September 2013 (EDT)


This page treats of the concepts of Java threads, and of the synchronization of the access to shared data between threads.



References

A good source of information for the material presented here is

The programs covered in this page can be found in this page:


Declaring a Thread in Java


Here is a simple example program that starts one thread only. The thread prints a message, waits one second, prints another message, then stops.

class MyThread extends Thread{  
    public void run(){  
	System.out.println( "thread is running..." );  

	try {
	    Thread.sleep( 1000 ); // 1 sec
	}
	catch (InterruptedException ie) {
            ie.printStackTrace();
	}

	System.out.println( "thread is done..." );
    }  
}

public class SimpleThreadDemo {
    public static void main(String args[]){  
	// declare a new thread
	MyThread t1=new MyThread();  

	// start a new thread
	t1.start();  

	// wait for the thread to be done
	try {
	    t1.join();
	}
	catch (InterruptedException ie) {
	    ie.printStackTrace();
	}

	// Exit
	System.out.println( "Done!" );

    }  
}


Output


aurora:~/handout> java SimpleThreadDemo
thread is running...
thread is done... 
Done!
aurora:~/handout>


Passing Arguments to Java Threads


To pass arguments to a thread, we simply need to pass them through the constructor, as illustrated in the example below.

/* SimpleThreadDemoWithArgs.java
 D. Thiebaut

 Same as SimpleThreadDemo, but this one illustrates 
 how main can pass arguments to the thread.

*/
class MyThread extends Thread{  
    int Id = 0;  // The Id of the thread

    public MyThread( int id ){
	Id = id;
    }

    public void run(){  
	System.out.println( "thread "+Id+" is running..." );  

	try {
	    Thread.sleep( 1000 ); // 1 sec
	}
	catch (InterruptedException ie) {
            ie.printStackTrace();
	}

	System.out.println( "thread "+Id+" is done..." );
    }  
}

public class SimpleThreadDemoWithArgs {
    public static void main(String args[]){  
	// declare a new thread with Id 33
	MyThread t1=new MyThread( 33 ); 

	// start a new thread
	t1.start();  

	// wait for the thread to be done
	try {
	    t1.join();
	}
	catch (InterruptedException ie) {
	    ie.printStackTrace();
	}

	// Exit
	System.out.println( "Done!" );

    }  
}


Output


aurora:~/handout> java SimpleThreadDemoWithArgs
thread 33 is running...
thread 33 is done... 
Done!
aurora:~/handout>

It all starts at the Lowest Level: Assembly Language (again)

Let's look at a different parallel computation of Pi. Imagine that the two threads in the ParallelPi program updated a global sum variable by doing something like this?

    public void run() {
                          for ( int i=0; i<N; i++ )
                                     sum ++;
               }

where sum is a static variable defined in the thread class. Since only 1 such variable will exist, all the thread objects will have access to just one variable, which plays the role of our global variable. The actual program can be found here.

Question 1
Figure out the assembly language for the java statement above
Question 2
Assume that main memory is a stack of index cards. One index card is sum. Two people in the class represent two different processors. Their notebook represent their registers. Execute these instructions simultaneously and figure out if there's a way for their simultaneous operation to fail.
Question 3
What makes the code fail? What is the processor missing?
Question 4
What is a way around the problem, such that two parallel updates of the variable sum will increment it by 2 every time?


How to Synchronize Access to Shared Variables


First we're going to look at what NOT to do, understand why, and see what tools Java gives us to get around the problem.

A Badly Synchronized Parallel Program


/*
 * UnsynchronizedThreadExample.java
 * D. Thiebaut
 * Undocumented code that computes Pi with 2 threads, but is terribly
 * flawed in the way it updates the global sum...
 */
package DT;

public class UnsynchronizedThreadExample {

        static int sum = 0;
        
        class PiThreadBad extends Thread {
                private int N;                  // the total number of samples/iterations 

                public PiThreadBad( int Id, int N ) {
                        super( "Thread-"+Id ); // give a name to the thread
                        this.N          = N;
                }
                        
                @Override
                public void run() {
                        for ( int i=0; i<N; i++ )
                                sum ++;
                }
        }

        public void process( int N ) {
            long startTime = System.currentTimeMillis();
            PiThreadBad t1 = new PiThreadBad( 0, N );
            PiThreadBad t2 = new PiThreadBad( 1, N );
                
            //--- start two threads ---
            t1.start();
            t2.start();
                
            //--- wait till they finish ---
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
                
            System.out.println( "sum = " + sum );
            System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
        }
    
    public static void main(String[] args) {
        int N = 100000000;
        UnsynchronizedThreadExample U = new UnsynchronizedThreadExample();
        U.process( N );
    }

}


Output

java DT.UnsynchronizedThreadExample 
sum = 198846243
Execution time: 25 ms


Critical Section

A series of instructions that are executed in an atomic fashion.

Question
We have seen this before, but just to make sure we all remember this: how can we create a critical section in assembly?


More challenging question
What should happen in Java when two threads attempt to modify a shared resource (variable or object). Specifically, what should happen with the thread that is first to grab the resource, and what should happen with the slower thread?


The Concept of a Lock

  • Intrinsic Lock = Monitor Lock =Monitor (most common definition)
  • In Java each object contains a Lock
  • Exclusive access to the object can be performed by acquiring the lock.
  • A thread locking an object must release it when it's done updating it.


Example With Locks


/*
SynchronizedLockThreadExample.java
D. Thiebaut

This threaded java code uses locks to serialize access to the
shared variable.

 */
import java.util.concurrent.locks.ReentrantLock;

public class SynchronizedLockThreadExample {

        static long sum = 0;
        private ReentrantLock lock = new ReentrantLock();

        class PiThreadGood extends Thread {
                private long N;                  // the total number of samples/iterations 

                public PiThreadGood( int Id, long N ) {
                        super( "Thread-"+Id ); // give a name to the thread
                        this.N          = N;
                }
                        
                @Override
                public void run() {
		    for ( long i=0; i<N; i++ ) {

			lock.lock();
			try{
			    sum++;
			} finally {
			    lock.unlock();
			}
		    }
                }
        }

        public void process( long N ) {
            long startTime = System.currentTimeMillis();
            PiThreadGood t1 = new PiThreadGood( 0, N );
            PiThreadGood t2 = new PiThreadGood( 1, N );
                
            //--- start two threads ---
            t1.start();
            t2.start();
                
            //--- wait till they finish ---
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
                
            System.out.println( "sum = " + sum );
            System.out.println( "Execution time: " + (System.currentTimeMillis()-startTime) + " ms" );
        }
    
    public static void main(String[] args) {
        long N = 1000000000l;
        SynchronizedLockThreadExample S = new SynchronizedLockThreadExample();
        S.process( N );
    }

}


Output


aurora:~/handout> java SynchronizedLockThreadExample
sum = 2000000000
Execution time: 14972 ms
aurora:~/handout> 


Synchronized Sections


Locks allow fine-grain control of shared variables and data structures, but maintaining them correctly in the code requires very careful attention, especially if the locked section calls other functions, and several conditions may exist for releasing the lock.

Fortunately, Java offers a simpler (though less flexible) way of locking whole methods or sections of code with the keyword synchronized.

  • The keyword synchronized( ) is used to
    • define an object whose lock is going to be used
    • define a section of code between { and } that is critical and should be executed in an atomic matter (but atomicity is not actually required any longer... can you see why?)


Example 1

Assume that you create your own list that will contain Strings. You use ArrayList<String> as your basic data structure, name it myList, and add more functionality with additional methods. This list will typically be instantiated as a single object, and shared by several threads that will attempt to add new strings to it in parallel.

 public void addNewCustomerMethod( String name ) {
     name = name.trim().toUpper();
     synchronized( this ) {
          myList.add( name );
     }
 }



Example 2

Assume that you do not need to trim() or change the strings to uppercase, then the whole body of the method is a critical section. In this case you can make the whole method synchronized:

 public synchronized void addNewCustomerMethod( String name ) {
          myList.add( name );
 }



Example 3

In some cases you may have several variables/data structures that you need to modify, but they do not depend on each other, and updating one is a completely independent operation from updating the other. In this case you can create your own locks. This example is take from the Oracle tutorial pages:

public class MsLunch {
    private long c1 = 0;
    private long c2 = 0;
    private Object lock1 = new Object();
    private Object lock2 = new Object();

    public void inc1() {
        synchronized(lock1) {
            c1++;
        }
    }

    public void inc2() {
        synchronized(lock2) {
            c2++;
        }
    }
}



Challenge 1

QuestionMark1.jpg


Modify the flawed program above that computes Pi by using some form of lock. Verify that it outputs the correct value of 2,000,000.

Challenge 2

QuestionMark2.jpg


Measure the execution time of your solution. Compare it to the original computation of Pi of a few lectures ago. Comment on your discovery!




Challenge 3

QuestionMark4.jpg


Modify the program so that the computation returned is actually an approximation of Pi and not 2,000,000. Measure it's speedup as a function of the number of threads N, for N ranging from 1 to 10.







Solutions

You can find solutions to these challenges here.



Some comments and definitions


  • When a thread is stopped because of a particular condition that it is waiting on (for example a queue is empty and the thread is designed to pull elements from the queue and process them), then the thead is said to be blocked.
  • When a thread is stopped because it has attempted to lock an object but an other thread held the lock, we say that this thread is stalled.
  • When a shared object is the object that is most utilized by thread, it is said to be the bottleneck object.
  • Liveliness: the ability of a threaded/parallel application to execute in a timely manner. When an application does not present liveliness of operation, it is usually due to one of several potential problems
    • Deadlock
    • Starvation
    • Livelock
  • Deadlock: a situation where two or more threads are blocked forever, waiting on each other.
  • Starvation: a situation where a thread is unable to get access to a resource and is unable to progress. This is often due to greedy threads.
  • Livelock: a situation where threads are not blocked, are running, but are waiting on each other before continuing. This often occurs because a thread my test whether a resource is available or not using a non-blocking function, and will busy itself with other work if the resource is not available.
DiningPhilosophersApplet.png
















Important Rule for avoiding deadlocks: If a thread needs several locks to operate, it should try acquiring all of them, one after the other. If it can't acquire one of them, it should release them all, wait some random amount of time, and try again. This will prevent the dining-philosopher potential deadlock.






  • Sleep: A thread can sleep for some interval of time using the sleep function
 sleep( m );   // where m is some integer number of milliseconds

Note that the operating system is in charge of figuring out how close to m milliseconds the thread actually sleeps. Usually the amount of sleep it is > m ms, never exact to that amount.

  • Reentrant Code/Reentrancy: A thread might acquire a lock, do some work on the locked data structure, and call another method that needs to be synchronized as well. Java allows a thread to automatically re-acquire a lock that it holds. This property is called reentrancy of the code.