4010-441 Principles of Concurrent System Design
Thread Safe Stack
This page is accessible at www.se.rit.edu/~se441/Assignments/ThreadSafeStack.html.
Overview
For this activity you will individually
design, implement, and test a thread-safe stack. You are free to work
with other class members, but everyone must submit his or her own
solution.
Design
IStack Interface
Your thread safe-class must implement the following interface:
public interface IStack {
public
void push(
String element ) ;
public
String pop( ) ;
}
TS_Stack Class
Create a public TS_Stack
class that implements the IStack
interface in line with following constraints:
- The stack itself will be implemented using the ArrayList
class, which is not thread-safe. Obviously, you have to provide proper
synchronization when accessing this component.
- On pop(),
the calling thread will wait if the stack is empty at time of call. The
thread will enter a wait loop until it finds the stack has a value in
it to be popped. Output from this method consists of messages of the
form:
- Thread
<name> waits in pop just prior to each time
it has to wait for the stack to hold values. Note that <name>
is the name of the Popper
thread.
- Thread
<name> pops <string> just
prior to returning to the caller. As above, <name>
is the name of the Popper
thread and <string>
is the string that is being popped.
- On push(String
element),
the calling thread will wait if the stack contains 5 (or more) values
at the time of the call. The thread will wait until it finds the stack
has fewer than 5 values, in which case it can push its argument element
on the stack. Output from this method consists of messages of the form:
- Thread
<name> waits in push just prior to each time
it has to wait for the stack to drop below values. Note that <name>
is the name of the Pusher
thread.
- Thread
<name> pushes <string> just
prior to returning to the caller. As above, <name>
is the name of the Pusher
thread and <string>
is the string that is being pushed.
- It should be obvious that proper synchronization, along
with wait
and notify
calls, are essential to a correct implementation.
Popper Class
The Popper
class extends Thread.
- public
Popper(String name, IStack stack)
- Initialize a new Popper
thread. The name
string is passed to the super
(Thread) class constructor. The stack is
saved in an instance variable of the Popper
object.
- public void run( )
- The Popper
thread continuously pops strings from the stack with
which it was configured, yielding the CPU via Thread.yield()
after each call to stack.pop.
Pusher Class
The Pusher
class extends Thread.
- public
Pusher(String name, IStack stack)
- Initialize a new Pusher
thread. The name
string is passed to the super
(Thread) class constructor. The stack is
saved in an instance variable of the Pusher
object.
- public void run( )
- The Pusher
thread pushes 15 strings on the stack with
which it was configured, yielding the CPU via Thread.yield()
after each call to stack.push().
The strings consist of the Pusher
thread's name and a sequence number (1 to 15). When all 15 strings have
been pushed, the Pusher
returns from run.
Driver Class
The driver class contains the public static void
main(...) method that
- Creates a single TS_Stack
object.
- Creates two Pusher
and two Popper
objects, each with a unique name but sharing the one TS_Stack.
- Starts the Popper
threads.
- Uses Thread.sleep
to sleep for 2000 milliseconds.
- Starts the Pusher
threads.
- Joins with the two Pusher
threads.
- Uses Thread.sleep
to delay 5000 milliseconds, then calls System.exit(0).
Done
correctly, when you run this program you should see an interleaving of
pushing and popping, but at the end 30 strings will have been pushed
and popped.
Deliverables
Submit a zip archive (and only a zip archive) named stack.zip, containing exactly five files, IStack.java,
TS_Stack.java, Popper.java, Pusher.java and Driver.java, to the Stack Activity
dropbox by due date. Of the 10 points available for this activity,
- 2 will be granted on an all-or-nothing basis
for a correct submission in accordance with the
preceding specification,
- 5 will be for functionality, based on both the
execution results and an inspection of the source code,
- 2 will be for
the quality of the solution (naming, spacing, indentation, etc.), and
- 1 will be based on whether or not the
internal documentation is of acceptable quality.
In all cases, points assigned represent your instructor's judgement as
a professional engineer, and are not subject to negotiation.