Discussion 10 handout

Group members (names & NetIDs)

Objectives

Orientation

Download the dis10 project code and open it as a project in IntelliJ as you would an assignment.

The file “BoundedQueue.java” is an interface for the Bounded Queue ADT, which is essentially a queue with a capacity restriction. The file “RingBufferBQ.java” contains two classes: (1) the RingBufferBQ class uses a Ring Buffer data structure to implement a bounded queue, and (2) the RingBufferBQIterator class is a skeleton for an iterator for the RingBufferBQ class.

RingBufferBQIterator is an inner class of RingBufferBQ, which is a new Java feature for us. You may have seen “static nested classes” before, such as declaring a “Node” class inside of a “Tree” class to encapsulate the helper class. But non-static inner classes are special. Every instance (object) of an inner class is “attached to” (contains an implicit reference to) a specific instance (object) of its outer class. In other words, every RingBufferBQIterator knows which RingBufferBQ created it. Consequently, the fields of the outer object are in scope when writing code for the inner class, meaning that the iterator can access the fields of its buffer (even the private ones) as if they were its own.

Next, review the fields of RingBufferBQ. Its state includes an array store, which stores the values. The length of store is the capacity of the ring buffer, and array indices that don’t contain elements should contain null.

Then, review the count field of RingBufferBQIterator. It keeps track of the number of elements iterated by the RingBufferBQIterator object.

Task 1: Implementing RingBufferBQ.get()

First, let’s make sure we can obtain values from a RingBufferBQ.

Implement the RingBufferBQ.get() method according to the specification. Don’t forget to call checkInvariant() before returning to check that your changes did not break the class invariant. (Hint: Use modular arithmetic to find the new value of iHead!)

Check your work using the tests in RingBufferBQTest before proceeding.

Task 2: Implementing RingBufferBQIterator

Clients using a bounded FIFO queue typically only need the put() and get() methods. However, there may be some circumstances where they would like to examine all of the contents of the queue, in order, without removing anything. But clients can’t see the private fields of a queue object, so they can’t write a traditional for-loop (and even if they could, we wouldn’t want to make every client duplicate the tricky modular arithmetic). Fortunately, we know a better way: if the queue implements the Iterable interface, then clients can use an “enhanced for-loop” to iterate over the elements without needing to know anything about the class invariants.

Our RingBufferBQ already implements Iterable (see its iterator() method), but it depends on the RingBufferBQIterator class (the modular arithmetic logic still needs to go somewhere). Your job is to implement this class, which, per the Iterator interface, means implementing the hasNext() and next() methods. Then you’ll test it out by writing an enhanced for-loop as a client.

Note: Iterators usually make the assumption that the collection they are iterating over does not change between when the iterator is constructed and the end of the loop that is using it. So while completing this task, you should assume that iHead and size do not change while an iterator instance is in use.

Part A: HasNext

Implement the RingBufferBQIterator.hasNext() method (TODO 2A) according to the specification. Trace execution on a Ring Buffer of size 1 to check your logic.

Part B: Next

Implement the RingBufferBQIterator.next() method (TODO 2B) according to the specification. Don’t forget about the throws clause.

Part C: Testing with Enhanced for-loops

Run the tests in the RingBufferBQIteratorTest test suite. Your implementation should pass all of the existing tests.

Once you pass all existing tests, write a test in RingBufferBQIteratorTest.testEnhancedForLoop() that uses an Enhanced for-loop to traverse the elements in a RingBufferBQ.

Task 3: Attempting concurrency handling in RingBufferBQ

Let’s put our iterator aside for now and consider a common use of bounded buffers: the producer–consumer setting. Imagine multiple programs trying to cooperate on some task. Some programs are responsible for producing inputs for other programs, which then consume them (in between, the inputs are placed in a queue). Think about a fast food restaurant with multiple fry cooks making french fries and multiple cashiers serving those fries to customers.

There will be situations in which some programs need to wait for other programs before they can make progress. For example, if the queue is empty, then consumers must wait for producers to add more elements. On the other hand, if the queue is full, then producers need to wait for consumers to take away some elements. The key idea idea here is waiting or (“blocking”); how can we achieve that?

For today’s discussion, you’ll try the “obvious” approach, sometimes called a “spin loop,” and you will see why it’s not a valid solution for multi-threaded programs, as it is vulnerable to race conditions. (In the next lecture you’ll learn about a more appropriate solution using synchronization).

A “spin loop” tries to wait for a Boolean condition COND to be false by repeatedly evaluating it and checking its value. For example:

while (COND) { /* empty loop body */ }

Presumably COND depends on mutable state that is shared between threads (otherwise how could it ever change?), which means that unsynchronized code that uses it is subject to race conditions. Let’s observe this by adding spin loops in RingBufferBQ in an attempt to provide “blocking” behavior, and then running a producer–consumer program where multiple threads access and modify a single RingBufferBQ object.

Part A: Spinning behavior for put()

Complete TODO 3A in RingBufferBQ.put().

Part B: Spinning behavior for get()

Complete TODO 3B in RingBufferBQ.get().

Part C: Run and observe behavior

The main() method uses the producer/consumer model to run 10 threads that interact with one RingBufferBQ object. The producer threads call put() to populate the buffer, and the consumer threads call get() to obtain elements from the buffer.

Note that the job of the consumers is to add up numbers from the queue. If this program works correctly, what would you expect the sum of all of the consumers’ results to be?

Now run the main() method. Try it more than once, and have multiple group members try it. List the range of behaviors you observe. (Note: If all consumer threads produced a “Consumer done” message, do the results from the consumers add up to what you’d expect?)

Challenge: Brainstorm a possible sequence of events across several threads that could explain some of the behaviors you saw.