|
|
| (6 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}}
| + | 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. |
| | | | |
| | + | {{CodeToImplement|AtomicStack|constructor<br/>push<br/>peek<br/>pop|stack.atomic.exercise}} |
| | ====constructor and instance variables==== | | ====constructor and instance variables==== |
| − | | + | Be sure to initialize whatever state you need to implement a mutable thread-safe Stack using atomics. |
| − | 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 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 non-thread-safe Stack.
| |
| − | | |
| − | ====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====
| |
| − | The constructor
| |
| − | | |
| − | <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====
| |
| − | ====peek====
| |
| − | ====pop====
| |
| − | | |
| − | ===AtomicStack===
| |
| − | [https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/ThreadSafe.html @ThreadSafe]
| |
| − | | |
| − | {{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==== | | ====push==== |
| | ====peek==== | | ====peek==== |
| | ====pop==== | | ====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}} |
