Assignment 4

Due Date: April 10, 2012

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

Following our general description of implementing a lock-free queue, implement
a non-blocking lock-free concurrent stack algorithm using the AtomicReference class
to represent the top element in the stack. You need to provide operations to concurrently push and
pop elements off the stack; since this is a lock-free algorithm, your solution should not
involve the use of locks or synchronization (other than compareAndSet).