Monday, April 30, 2012

Print odd and even numbers using two threads

Once again this is question from one of the java interviewer. We have two threads, one thread prints odd number and another prints even number. Modify code in such a way that output on console will be 1,2,3,4,5,6,...
I solved similar problem on coderach using CyclicBarrier. Earlier problem requires one barrier point but for current problem, we need 2 barriers. Odd Thread prints between one barrier and even thread between another barrier.
public class OddEvenPrintTest {
 public static boolean print = false;
 public static void main(String args[]) throws Exception {
  Thread t;
  int runs = 10000000;  
  CyclicBarrier barrier = new CyclicBarrier(2);

  long time = System.currentTimeMillis();
  t = new Thread(new OddBarrierRunnable(runs, barrier), "OddThread");
  t.start();
  t = new Thread(new EvenCyclicRunnable(runs, barrier), "EvenThread");
  t.start();
  t.join();
  System.out.println("Time using cyclic barrier " + (System.currentTimeMillis() - time)+"ms for runs "+runs);

 }

}

class OddBarrierRunnable implements Runnable {
 CyclicBarrier barrier;
 int runs;

 public OddBarrierRunnable(int runs, CyclicBarrier barrier) {
  this.runs = runs;
  this.barrier = barrier;
 }

 public void run() {
  try {
   for (int i = 1, counter = 0; counter < runs; i += 2, counter++) {
    if (OddEvenPrintTest.print) {
     System.out.println(i);
    }
    barrier.await();
    barrier.await();

   }
  } catch (Exception e) {
   System.out.println("Opps. I was not expecting any exception here");
  }
 }
}

class EvenCyclicRunnable implements Runnable {
 CyclicBarrier barrier;
 int runs;

 public EvenCyclicRunnable(int runs, CyclicBarrier barrier) {
  this.runs = runs;
  this.barrier = barrier;
 }

 public void run() {
  try {
   for (int i = 2, counter = 0; counter < runs; i += 2, counter++) {
    barrier.await();
    if (OddEvenPrintTest.print) {
     System.out.println(i);
    }
    barrier.await();
   }
  } catch (Exception e) {
   System.out.println("Opps. I was not expecting any exception here");
  }
 }
}

and output for different runs
Time using cyclic barrier 3 ms for runs 10
Time using cyclic barrier 31 ms for runs 100
Time using cyclic barrier 45 ms for runs 1000
Time using cyclic barrier 279 ms for runs 10000
Time using cyclic barrier 1423 ms for runs 100000
Time using cyclic barrier 18313 ms for runs 1000000
Problem with above approach is for printing one odd even number pair using 2 threads, Threads will be blocked twice and which will involve thread context switches.

Implementation of java.util.concurrent.ConcurrentLinkedQueue helped me to think this problem as Non Blocking problem. Just to give you background about ConcurrentLinkedQueue implementation, it's not using any of the plain old wait/notify mechanism or java.util.concurrent.Lock which is introduced in Java 5. Both these mechanisms will park your thread if monitor is already acquired by another thread or Lock is acquired by another thread (tryLock() will not block your thread).

Coming back to our ConcurrentLinkedQueue implementation, it internally using java.util.concurrent.atomic.AtomicReferenceFieldUpdater to update head and tail node references. Instead of every thread competing to enter into critical section (which consist of updating head/tail pointer for poll/offer operation) and blocking if lock is acquired by another thread, every thread will try to update head/tail reference from it's current reference to new reference. AtomicReferenceFieldUpdater guarantees that only one thread can succeed and other threads will fail. other failed threads will keep on updating references until they succeed.

Lets get back to our problem. here I am using AtomicInteger and to maintain 4 states and transitions as mentioned below.
State Description Transition to
1 Lock acquired by Odd Thread 2
2 Lock released by Odd Thread 3
3 Lock acquired by Even Thread 0
0 Lock released by Even Thread 1
Odd Thread can acquire lock only when current state is 0. Once it will acquire lock (at line 29), it will update current state to 1 (ie. Odd thread is holding lock). Once odd thread holds lock, it prints odd value and then release lock by setting AtomicInteger value to 2( ie. Lock is released by Odd Thread. at line 34).

While Odd thread is holding lock, even thread also tries to update value from 2 to 3 in infinite loop( at line 52). This operation will succeed only after Odd Thread updates value from 1 to 2(at line 34). Once Even thread done with it's turn, it updates value from 3 to 0 (at line 57).
public class OddEvenPrintTest {
 public static boolean print = false;
 public static void main(String args[]) throws Exception {
  AtomicInteger atomicInt = new AtomicInteger(0);
  Thread t;
  int runs = 10;
  long time = System.currentTimeMillis();
  new Thread(new OddAtomicRunnable(atomicInt, runs)).start();
  t = new Thread(new EvenAtomicRunnable(atomicInt, runs));
  t.start();
  t.join();
  System.out.println("Runs -"+runs);
  System.out.println("Time using Atomic " + (System.currentTimeMillis() - time)+"ms for runs "+runs);
 }
}


class OddAtomicRunnable implements Runnable {
 AtomicInteger atomicInt;
 int runs;

 public OddAtomicRunnable(AtomicInteger atomicInt, int runs) {
  this.atomicInt = atomicInt;
  this.runs = runs;
 }

 public void run() {
  for (int i = 1, counter = 0; counter < runs; i += 2, counter++) {
   while (!atomicInt.compareAndSet(0, 1)) {
   }
   if (OddEvenPrintTest.print) {
    System.out.println(i);
   }
   while (!atomicInt.compareAndSet(1, 2)) {
   }
  }
 }
}


class EvenAtomicRunnable implements Runnable {
 AtomicInteger atomicInt;
 int runs;

 public EvenAtomicRunnable(AtomicInteger atomicInt, int runs) {
  this.atomicInt = atomicInt;
  this.runs = runs;
 }

 public void run() {
  for (int i = 2, counter = 0; counter < runs; i += 2, counter++) {
   while (!atomicInt.compareAndSet(2, 3)) {
   }
   if (OddEvenPrintTest.print) {
    System.out.println(i);
   }
   while (!atomicInt.compareAndSet(3, 0)) {
   }
  }
 }
}

and here is the output for different runs
Time using Atomic 14 ms for runs 10
Time using Atomic 50 ms for runs 100
Time using Atomic 71 ms for runs 1000
Time using Atomic 100 ms for runs 10000
Time using Atomic 121 ms for runs 100000
Time using Atomic 249 ms for runs 1000000
Time required using AtomicInteger is definitely less than time it took using Cyclicbarrier.

Advantage of using AtomicInteger here:
  • This solution can be extended for many threads.
It also has some limitations as mentioned below:
  • make sure critical section needs to be really short. Runs in few CPU cycles. because other threads will be also competing for lock using busy waiting approach.
  • Any blocking operations like I/O, wait/notify should not be executed from Critical section.

Note:Tests conducted on fedora 13 Intel Core2 Duo machine with JDK 1.6.0_12

Sunday, April 1, 2012

Extract system properties from heap dump using Visual VM OQLand JavaScript

VisualVM is one of the great tool but still it's not popular in Java community.

One of the interesting feature of VisualVM is traversing heap dump. VisualVM supports OQL syntax similar to eclipse MAT. But java script support along with OQL sytax make it different.

Do you want to print system properties from heap dump? System Properties are internally maintained as hash Map. It's probably difficult to traverse such hash map using normal OQL syntax. But using VisualVM OQL syntax along with java script it's possible.

Load heap dump in visualVM and copy paste below javascript syntax into VisualVM -> HeapDump -> OQL Console (tab).

function printProp(obj) {
    var ret = '';
        // count is proeprty of java.util.Properties 
        ret = 'Count = '+obj.count+"< br/>";
        // table is property of java.util.Properties which is table of java.util.HashTable.Entry
        tables = toArray(obj.table);

        //Iterate over table and print entries
        for(i = 0;i< tables.length;i++) {
               e = tables[i];
               //Iterate while e is not null
               while(e != null) {
                    if(e.key!= null) {
                        ret +=e.key.toString();
                    }else {
                        ret += 'null';
                    }
                    if(e.value!= null) {
                        ret +=" = "+e.value.toString();
                    }else {
                        ret +=" = null";
                    }
                    ret+="< br/>";
                    e = e.next;
               }
        }
    return ret;
}
// props is static attribute of java.lang.System which holds system Properties.
// pass props to printProp function.
printProp(heap.findClass("java.lang.System").props);

and here is output.

Count = 50
sun.cpu.isalist =
sun.desktop = gnome
sun.io.unicode.encoding = UnicodeLittle
sun.cpu.endian = little
java.vendor.url.bug = http://java.sun.com/cgi-bin/bugreport.cgi
file.separator = /
java.vendor = Sun Microsystems Inc.
sun.boot.class.path = /usr/java/jdk1.6.0_12/jre/lib/resources.jar:/usr/java/jdk1.6.0_12/jre/lib/rt.jar:/usr/java/jdk1.6.0_12/jre/lib/sunrsasign.jar:/usr/java/jdk1.6.0_12/jre/lib/jsse.jar:/usr/java/jdk1.6.0_12/jre/lib/jce.jar:/usr/java/jdk1.6.0_12/jre/lib/charsets.jar:/usr/java/jdk1.6.0_12/jre/classes
java.ext.dirs = /usr/java/jdk1.6.0_12/jre/lib/ext:/usr/java/packages/lib/ext
java.version = 1.6.0_12-ea
java.vm.info = mixed mode
user.language = en
java.specification.vendor = Sun Microsystems Inc.
java.home = /usr/java/jdk1.6.0_12/jre
sun.arch.data.model = 32
java.vm.specification.version = 1.0
java.class.path = /home/rohand/workspace/java5/bin:
user.name = rohand
file.encoding = UTF-8
java.specification.version = 1.6
java.awt.printerjob = sun.print.PSPrinterJob
user.timezone =
user.home = /home/rohand
os.version = 2.6.33.3-85.fc13.i686.PAE
sun.management.compiler = HotSpot Tiered Compilers
java.specification.name = Java Platform API Specification
java.class.version = 50.0
java.library.path = /usr/java/jdk1.6.0_12/jre/lib/i386/server:/usr/java/jdk1.6.0_12/jre/lib/i386:/usr/java/jdk1.6.0_12/jre/../lib/i386:/usr/lib/jvm/java-1.6.0-openjdk-1.6.0.0/jre/lib/i386/client:/usr/lib/jvm/java-1.6.0-openjdk-1.6.0.0/jre/lib/i386:/usr/lib/xulrunner-1.9.2:/usr/lib/xulrunner-1.9.2:/usr/java/packages/lib/i386:/lib:/usr/lib
sun.jnu.encoding = UTF-8
os.name = Linux
java.vm.specification.vendor = Sun Microsystems Inc.
java.io.tmpdir = /tmp
line.separator =

java.endorsed.dirs = /usr/java/jdk1.6.0_12/jre/lib/endorsed
os.arch = i386
java.awt.graphicsenv = sun.awt.X11GraphicsEnvironment
java.runtime.version = 1.6.0_12-ea-b03
java.vm.specification.name = Java Virtual Machine Specification
user.dir = /home/rohand/workspace/java5
sun.java.launcher = SUN_STANDARD
user.country = US
sun.os.patch.level = unknown
java.vm.name = Java HotSpot(TM) Server VM
file.encoding.pkg = sun.io
path.separator = :
java.vm.vendor = Sun Microsystems Inc.
java.vendor.url = http://java.sun.com/
sun.boot.library.path = /usr/java/jdk1.6.0_12/jre/lib/i386
java.vm.version = 11.2-b01
java.runtime.name = Java(TM) SE Runtime Environment

Screenshot of VisualVM OQL Syntax tab