Difference between revisions of "Stack Assignment"

From CSE231 Wiki
Jump to navigation Jump to search
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 an initial not-thread-safe implementation of a Stack.  This exercise will allow us to gain experience building a data structure and see how it performs when used in a parallel for which it was not designed.  Later in the semester we will build two thread-safe implementations: one [[Concurrent_Stack_Assignment|concurrent]] and one [[Concurrent_Stack_Assignment|atomic]].  Your work on this exercise will pay dividends on these later exercises.
 +
 
 
=Background=
 
=Background=
 
<youtube>wjI1WNcIntg</youtube>
 
<youtube>wjI1WNcIntg</youtube>

Revision as of 21:03, 1 February 2023

Motivation

We will build an initial not-thread-safe implementation of a Stack. This exercise will allow us to gain experience building a data structure and see how it performs when used in a parallel for which it was not designed. Later in the semester we will build two thread-safe implementations: one concurrent and one atomic. Your work on this exercise will pay dividends on these later exercises.

Background

interface Stack

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

Example

empty

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

Stack empty.svg

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<>();
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");

Stack edcba.svg

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

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

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

Stack dcba.svg

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

Code To Implement

Node

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 Node.

class: DefaultNode.java Java.png
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.

Stack

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

	Optional<E> peek();

	Optional<E> pop();
}

NotThreadSafeStack

@NotThreadSafe

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

instance variables

What state do you need to keep track of to support a mutable non-thread-safe Stack?

push

peek

pop

Distasters To Investigate

ParallelPushStackDisasterClient

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

ParallelPushAndPopStackDisasterClient

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

Testing

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

DefaultNode

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

NotThreadSafeStack

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

Pledge, Acknowledgments, Citations

file: atomic-stack-pledge-acknowledgments-citations.txt

More info about the Honor Pledge