Difference between revisions of "Atomic Stack Assignment"

From CSE231 Wiki
Jump to navigation Jump to search
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
=Motivation=
 
=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.
+
We will build a thread-safe implementation of a Stack using atomics.
 
=Background=
 
=Background=
==Implicit Locks==
 
[https://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html synchronized methods]
 
 
 
==Atomics==
 
==Atomics==
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html AtomicReference<V>]
 
[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html AtomicReference<V>]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html#get-- get()]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html#get-- get()]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html#compareAndSet-V-V- compareAndSet(expect, update)]
 
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html#compareAndSet-V-V- compareAndSet(expect, update)]
 
=Node and Stack Interfaces=
 
==interface Node==
 
<nowiki>public interface Node<E> {
 
E value();
 
Optional<Node<E>> nextNode();
 
}</nowiki>
 
 
==interface Stack==
 
<nowiki>public interface Stack<E> {
 
void push(E value);
 
Optional<E> peek();
 
Optional<E> pop();
 
}</nowiki>
 
 
==Example==
 
===empty===
 
<nowiki>Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);</nowiki>
 
 
[[File:Stack_empty.svg]]
 
 
In this state, <code>stack.peek()</code> will return <code>Optional.empty()</code> and <code>stack.pop()</code> will also return <code>Optional.empty()</code>.
 
 
===push A, B, C, D, E===
 
<nowiki>Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);
 
stack.push("A");
 
stack.push("B");
 
stack.push("C");
 
stack.push("D");
 
stack.push("E");</nowiki>
 
 
[[File:Stack_edcba.svg]]
 
 
In this state, <code>stack.peek()</code> will return <code>Optional.of("E")</code>.
 
 
===push A, B, C, D, E, pop===
 
<nowiki>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();</nowiki>
 
 
[[File:Stack_dcba.svg]]
 
 
In this state, <code>optOfE</code> will hold <code>Optional.of("E")</code> and <code>stack.peek()</code> will return <code>Optional.of("D")</code>.
 
  
 
=Code To Implement=
 
=Code To Implement=
==Node==
 
<nowiki>public interface Node<E> {
 
E value();
 
  
Optional<Node<E>> nextNode();
+
==AtomicStack==
}</nowiki>
+
While ConcurrentStack could simply rely on synchronized to provide thread-safety, AtomicStack must change its data structure. To be {{ThreadSafeLink}}, AtomicStack must correctly use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html AtomicReference<V>].  
===DefaultNode===
 
The mighty [https://en.wikipedia.org/wiki/Cons 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 [https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/Immutable.html @Immutable] class DefaultNode which implements interface Node.
 
 
 
{{CodeToImplement|DefaultNode|value<br/>nextNode|stack.node.exercise|main}}
 
 
 
====constructor and instance variables====
 
 
 
The constructor
 
 
 
<nowiki>public DefaultNode(E value, Optional<Node<E>> nextNode)</nowiki>
 
 
 
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 <code>final</code>.
 
 
 
====value====
 
 
 
return the value.
 
 
 
====nextNode====
 
 
 
return the next node.
 
 
 
===DefaultNodeCreator===
 
====apply====
 
return a new instance of DefaultNode with the provided parameters.
 
 
 
==Stack==
 
<nowiki>public interface Stack<E> {
 
void push(E value);
 
 
 
Optional<E> peek();
 
 
 
Optional<E> pop();
 
}</nowiki>
 
 
 
===NotThreadSafeStack===
 
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/NotThreadSafe.html @NotThreadSafe]
 
 
 
{{CodeToImplement|NotThreadSafeStack|constructor<br/>nodeConstructor<br/>push<br/>peek<br/>pop|stack.notthreadsafe.exercise}}
 
 
 
====constructor and instance variables====
 
 
 
The constructor
 
 
 
<nowiki>public NotThreadSafeStack(BiFunction<E, Optional<Node<E>>, Node<E>> nodeCreator)</nowiki>
 
  
is passed a nodeCreatorThe excessive over use of abstraction is in place to help the testing alert you to potential bugs in your code earlier.
+
Do NOT hold any [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic locks (via synchronized)] or hold any explicit [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html Locks]It would be wasteful (and missing the point) to pay the lock overhead when the AtomicReference will get the job done.
  
Be sure to hang onto the nodeCreator in a <code>final</code> instance variable along with whatever other state you need to implement a mutable non-thread-safe Stack.
+
{{CodeToImplement|AtomicStack|constructor<br/>push<br/>peek<br/>pop|stack.atomic.exercise}}
 
 
====nodeCreator====
 
 
 
return the nodeCreator which was passed to your constructor.
 
 
 
====push====
 
====peek====
 
====pop====
 
===ConcurrentStack===
 
To be [https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/ThreadSafe.html @ThreadSafe], one must hold [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic lock (via synchronized)] on the ConcurrentStack instance for each of the methods which read and/or write to mutable data.
 
 
 
{{CodeToImplement|ConcurrentStack|constructor<br/>nodeConstructor<br/>push<br/>peek<br/>pop|stack.concurrent.exercise}}
 
 
====constructor and instance variables====
 
====constructor and instance variables====
The constructor
+
Be sure to initialize whatever state you need to implement a mutable thread-safe Stack using atomics.
 
 
<nowiki>public ConcurrentStack(BiFunction<E, Optional<Node<E>>, Node<E>> nodeCreator)</nowiki>
 
 
 
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 <code>final</code> 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.
 
  
 
====push====
 
====push====
 
====peek====
 
====peek====
 
====pop====
 
====pop====
 
===AtomicStack===
 
To be [https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/ThreadSafe.html @ThreadSafe], one must correctly use [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html AtomicReference<V>].
 
 
Do NOT hold any [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html 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.
 
 
{{CodeToImplement|AtomicStack|constructor<br/>nodeConstructor<br/>push<br/>peek<br/>pop|stack.atomic.exercise}}
 
====constructor and instance variables====
 
The constructor
 
 
<nowiki>public AtomicStack(BiFunction<E, Optional<Node<E>>, Node<E>> nodeCreator)</nowiki>
 
 
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 <code>final</code> 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.
 
 
====push====
 
====peek====
 
====pop====
 
 
=Distasters To Investigate=
 
==ParallelPushStackDisasterClient==
 
{{CodeToInvestigate|ParallelPushStackDisasterClient|main|stack.notthreadsafe.disaster|main}}
 
 
==ParallelPushAndPopStackDisasterClient==
 
{{CodeToInvestigate|ParallelPushAndPopStackDisasterClient|main|stack.notthreadsafe.disaster|main}}
 
  
 
=Testing=
 
=Testing=
{{TestSuite|StackTestSuite|stack.exercise}}
 
==DefaultNode==
 
{{TestSuite|_DefaultNodeTestSuite|stack.node.exercise}}
 
 
==DefaultNodeCreator==
 
{{TestSuite|_DefaultNodeCreatorTestSuite|stack.node.exercise}}
 
 
==NotThreadSafeStack==
 
{{TestSuite|_NotThreadSafeStackTestSuite|stack.notthreadsafe.exercise}}
 
==ConcurrentStack==
 
{{TestSuite|__ConcurrentStackTestSuite|stack.concurrent.exercise}}
 
===sequential===
 
{{TestSuite|_ConcurrentStackSequentialTestSuite|stack.concurrent.exercise}}
 
===parallel===
 
{{TestSuite|_ConcurrentStackParallelTestSuite|stack.concurrent.exercise}}
 
 
==AtomicStack==
 
 
{{TestSuite|__AtomicStackTestSuite|stack.atomic.exercise}}
 
{{TestSuite|__AtomicStackTestSuite|stack.atomic.exercise}}
===sequential===
 
{{TestSuite|_AtomicStackSequentialTestSuite|stack.atomic.exercise}}
 
===parallel===
 
{{TestSuite|_AtomicStackParallelTestSuite|stack.atomic.exercise}}
 
 
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
 
{{Pledge|atomic-stack}}
 
{{Pledge|atomic-stack}}

Latest revision as of 02:25, 23 April 2024

Motivation

We will build a thread-safe implementation of a Stack using atomics.

Background

Atomics

AtomicReference<V>

get()
compareAndSet(expect, update)

Code To Implement

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) or hold any explicit Locks. It would be wasteful (and missing the point) to pay the lock overhead when the AtomicReference will get the job done.

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

constructor and instance variables

Be sure to initialize whatever state you need to implement a mutable thread-safe Stack using atomics.

push

peek

pop

Testing

class: __AtomicStackTestSuite.java Junit.png
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