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 1000000Problem 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 |
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 1000000Time 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.
- 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
