Assignment 3

Due Date: April 7, 2008

In this assignment, you will use Java's atomic variable classes
(AtomicXXX in java.util.concurrent.atomic) that provide
efficient CAS operations on numeric and reference types
to build non-blocking, lock-free data structures.

Part 1

Below is a thread-safe implementation of a pseudo-random
number generator:

public class ReentrantLockPseudoRandom extends PseudoRandom {
    private final Lock lock = new ReentrantLock(false);
    private int seed;

    ReentrantLockPseudoRandom (int seed) {
        this.seed = seed;
    }

     public int nextInt (int n) {
        lock.lock();
        try {
           int s = seed;
           seed = calculateNext(s);
           int remainder = s % n;
           return remainder > 0 ? remainder : remainder + n;
        } finally {
                     lock.unlock();
        }
   }
}

Write a test driver that repeatedly invokes an instance of the generator. The test
driver should perform some number of busy-work iterations (that should be
customizable); the computation performed by these iterations should operate
only on thread-local data.

Part 2

Provide an implementation of a non-blocking pseudo-random number generator
that uses the AtomicInteger class to provide lock-free access to the seed.

Part 3

Modify the test driver so that it invokes each of these implementations in turn.
Measure the performance of the two implementations by varying the number of
threads that invoke the generator from within the driver.

How does performance vary as contention increases? Contention is inversely
correlated to the percentage of time spent performing thread-local computation.

Part 4

Using the pseudo-code given in class, implement a non-blocking lock-free
queue algorithm using the AtomicReference class to represent pointers to
nodes in the queue. To simplify the problem, you do not need to consider
ABA issues.

Part 5 (Extra Credit)

Implement a classical blocking queue algorithm, and compare the performance
of the implementation in Part 4 as contention on the queue increases.