Java Synchronized Threads

To understand the concept of synchronized threads, I have written the following sample classes. The java class, SyncThread, is implemented using Synchronized run method, while the second doesn't use a Synchronized method. In the SyncTest, two objects of the SyncThread are created. Both of the objects tries to access the same method, i.e, run().

The possible outputs for the synchronized and unsynchronized 'run' is given below the code.

/* 
 * Thread using Synchronized method
 */

class SyncThread implements Runnable {
 Thread t;
 static int count = 0;
 
 SyncThread(String tName) {
  t = new Thread(this, tName);
 }
 synchronized public void run() {
  count++;
  System.out.println(t + " count : " + count);
 }
}

In the above code, count is incremented inside a synchronized method. Let's consider this area as a critical region. Using a synchronized method ensures that the region is handled by a monitor (semaphore). So, once an object accesses this method, no other objects will be able to access it.

/* 
 * Thread without using Synchronized method 
 */
class UnSyncThread implements Runnable {
 Thread t;
 static int count = 0;
 
 UnSyncThread(String tName) {
  t = new Thread(this, tName);
 }
 
 public void run() {
  count++;
  System.out.println(t + " count : " + count);
 }
}

Since the above code doesn't implement a synchronized 'run', it could result in the Output Case 1 (see the bottom of the page for the outputs). A thread could be preempted while it is still inside the 'run' method. This could create a race condition (as given in the output).

/*
 * CLass to test the SyncThreads.
 */
public class SyncTest {
 public static void main(String args[]) {
  SyncThread st2 = new SyncThread("st2");
  SyncThread st1 = new SyncThread("st1");
  
  /* Try declaring the below ones
   * for testing unsynchronized threads
   */
  //UnSyncThread st1 = new UnSyncThread("st1");
  //UnSyncThread st2 = new UnSyncThread("st2");
  
  st1.t.start();
  st2.t.start();
 }
}

Output Case 1:

Thread[st1,5,main] count : 2

Thread[st2,5,main] count : 2

Output Case 2 : ( with synced run methods )

Thread[st1,5,main] count : 1

Thread[st2,5,main] count : 2

Output Case 3: ( with synced run methods )

Thread[st2,5,main] count : 2

Thread[st1,5,main] count : 1

Tower of Hanoi

Tower of Hanoi is an old and popular problem. The description of the problem is given here - http://en.wikipedia.org/wiki/Tower_of_Hanoi. The solution for this problem can be designed in various ways, few of which are listed in the above wiki page. I have coded a recursive solution to solve the problem. You can find many other solutions in the web as well.

The aim of coding for this particular solution is inspired by the SICP (Structure and Interpretation of Computer Programs) MIT video lectures by Prof. Abelson and Gerald Jay. The aim is to understand the recursive nature of the program.

The program is available at my bitbucket collection - click here (takes you to the page containing the code).

In order to understand the recursive nature of the program. you can compile it with debugging symbols -

gcc -g towers_of_hanoi.cpp

and then use the gdb debugger (learn it) to trace through the different stacks (a, b, c).

gdb a.out

Also, use backtrace (bt) command in gdb to trace through the system stack to get a better understanding of how the code implements the solution.