Atomic Stack Assignment

Motivation

We will build three implementations of a Stack. One non-thread safe implementation, one thread-safe implementation using synchronized methods, and finally one thread-safe implementation using atomics.

Background

Implicit Locks

synchronized methods

Atomics

AtomicReference<V>

get()

compareAndSet(expect, update)

Node and Stack Interfaces

interface Node

public interface Node<E> {
	E value();
	Optional<Node<E>> nextNode();
}

interface Stack

public interface Stack<E> {
	void push(E value);
	Optional<E> peek();
	Optional<E> pop();
}

Example

empty

Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);

In this state, stack.peek() will return Optional.empty() and stack.pop() will also return Optional.empty().

push A, B, C, D, E

Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");

In this state, stack.peek() will return Optional.of("E").

push A, B, C, D, E, pop

Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");
Optional<String> optOfE = stack.pop();

In this state, optOfE will hold Optional.of("E") and stack.peek() will return Optional.of("D").

Code To Implement

Node

public interface Node<E> {
	E value();

	Optional<Node<E>> nextNode();
}

DefaultNode

The mighty cons cell goes back to the early days of computing. People have been building amazing systems with this data structure since the 1950s.

We will build an @Immutable class DefaultNode which implements interface Node.

class:	DefaultNode.java
methods:	value nextNode
package:	stack.node.exercise
source folder:	main/src/main/java

constructor and instance variables

The constructor

public DefaultNode(E value, Optional<Node<E>> nextNode)

is passed a value and a nextNode. Hang on to this data in instance variables. As instances of DefaultNode are to be immutable, the instance variables should be marked as final.

value

return the value.

nextNode

return the next node.

DefaultNodeCreator

apply

return a new instance of DefaultNode with the provided parameters.

Stack

public interface Stack<E> {
	void push(E value);

	Optional<E> peek();

	Optional<E> pop();
}

NotThreadSafeStack

@NotThreadSafe

class:	NotThreadSafeStack.java
methods:	constructor nodeConstructor push peek pop
package:	stack.notthreadsafe.exercise
source folder:	student/src/main/java

constructor and instance variables

The constructor

public NotThreadSafeStack(BiFunction<E, Optional<Node<E>>, Node<E>> nodeCreator)

is passed a nodeCreator. The excessive over use of abstraction is in place to help the testing alert you to potential bugs in your code earlier.

Be sure to hang onto the nodeCreator in a final instance variable along with whatever other state you need to implement a mutable non-thread-safe Stack.

nodeCreator

return the nodeCreator which was passed to your constructor.

ConcurrentStack

To be @ThreadSafe, one must hold intrinsic lock (via synchronized) on the ConcurrentStack instance for each of the methods which read and/or write to mutable data.

class:	ConcurrentStack.java
methods:	constructor nodeConstructor push peek pop
package:	stack.concurrent.exercise
source folder:	student/src/main/java

constructor and instance variables

The constructor

public ConcurrentStack(BiFunction<E, Optional<Node<E>>, Node<E>> nodeCreator)

is passed a nodeCreator. The excessive over use of abstraction is in place to help the testing alert you to potential bugs in your code earlier.

Be sure to hang onto the nodeCreator in a final instance variable along with whatever other state you need to implement a mutable thread-safe Stack.

nodeCreator

return the nodeCreator which was passed to your constructor.

AtomicStack

While ConcurrentStack could simply rely on synchronized to provide thread-safety, AtomicStack must change its data structure. To be @ThreadSafe, AtomicStack must correctly use AtomicReference<V>.

Do NOT hold any intrinsic locks (via synchronized). It would be wasteful (and missing the point) to pay the lock overhead when the AtomicReference will get the job done.

class:	AtomicStack.java
methods:	constructor nodeConstructor push peek pop
package:	stack.atomic.exercise
source folder:	student/src/main/java

constructor and instance variables

The constructor

public AtomicStack(BiFunction<E, Optional<Node<E>>, Node<E>> nodeCreator)

is passed a nodeCreator. The excessive over use of abstraction is in place to help the testing alert you to potential bugs in your code earlier.

Be sure to hang onto the nodeCreator in a final instance variable along with whatever other state you need to implement a mutable thread-safe Stack using atomics.

nodeCreator

return the nodeCreator which was passed to your constructor.

Distasters To Investigate

ParallelPushStackDisasterClient

class:	ParallelPushStackDisasterClient.java	DEMO:
methods:	main
package:	stack.notthreadsafe.disaster
source folder:	src/main/java

ParallelPushAndPopStackDisasterClient

class:	ParallelPushAndPopStackDisasterClient.java	DEMO:
methods:	main
package:	stack.notthreadsafe.disaster
source folder:	src/main/java

Testing

class:	StackTestSuite.java
package:	stack.exercise
source folder:	testing/src/test/java

DefaultNode

class:	_DefaultNodeTestSuite.java
package:	stack.node.exercise
source folder:	testing/src/test/java

DefaultNodeCreator

class:	_DefaultNodeCreatorTestSuite.java
package:	stack.node.exercise
source folder:	testing/src/test/java

NotThreadSafeStack

class:	_NotThreadSafeStackTestSuite.java
package:	stack.notthreadsafe.exercise
source folder:	testing/src/test/java

ConcurrentStack

class:	__ConcurrentStackTestSuite.java
package:	stack.concurrent.exercise
source folder:	testing/src/test/java

sequential

class:	_ConcurrentStackSequentialTestSuite.java
package:	stack.concurrent.exercise
source folder:	testing/src/test/java

parallel

class:	_ConcurrentStackParallelTestSuite.java
package:	stack.concurrent.exercise
source folder:	testing/src/test/java

AtomicStack

class:	__AtomicStackTestSuite.java
package:	stack.atomic.exercise
source folder:	testing/src/test/java

sequential

class:	_AtomicStackSequentialTestSuite.java
package:	stack.atomic.exercise
source folder:	testing/src/test/java

parallel

class:	_AtomicStackParallelTestSuite.java
package:	stack.atomic.exercise
source folder:	testing/src/test/java

Pledge, Acknowledgments, Citations

file:

atomic-stack-pledge-acknowledgments-citations.txt

More info about the Honor Pledge