Difference between revisions of "Atomic Stack Assignment"

From CSE231 Wiki
Jump to navigation Jump to search
 
(31 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
=Motivation=
 +
We will build a thread-safe implementation of a Stack using atomics.
 +
=Background=
 +
==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#get-- get()]
 +
: [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html#compareAndSet-V-V- compareAndSet(expect, update)]
 +
 
=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===
 
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/Immutable.html @Immutable] class DefaultNode.
 
 
 
{{CodeToImplement|DefaultNode|value<br/>nextNode|stack.node.exercise|main}}
 
 
 
==constructor==
 
==value==
 
==nextNode==
 
  
==Stack==
+
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.
  <nowiki>public interface Stack<E> {
 
void push(E value);
 
  
Optional<E> peek();
+
{{CodeToImplement|AtomicStack|constructor<br/>push<br/>peek<br/>pop|stack.atomic.exercise}}
 +
====constructor and instance variables====
 +
Be sure to initialize whatever state you need to implement a mutable thread-safe Stack using atomics.
  
Optional<E> pop();
+
====push====
}</nowiki>
+
====peek====
===NotThreadSafeStack===
+
====pop====
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/NotThreadSafe.html @NotThreadSafe]
 
===ConcurrentStack===
 
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/ThreadSafe.html @ThreadSafe]
 
===AtomicStack===
 
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/ThreadSafe.html @ThreadSafe]
 
  
 
=Testing=
 
=Testing=
{{TestSuite|StackTestSuite|stack.exercise}}
 
==DefaultNode==
 
{{TestSuite|_DefaultNodeTestSuite|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===
+
=Pledge, Acknowledgments, Citations=
{{TestSuite|_AtomicStackSequentialTestSuite|stack.atomic.exercise}}
+
{{Pledge|atomic-stack}}
===parallel===
 
{{TestSuite|_AtomicStackParallelTestSuite|stack.atomic.exercise}}
 

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