logoDiscussion 6 handout

Group members (names & NetIDs)

Objectives

Task 1: Threading And Concurrency

Unsynchronized attempt

Attempt to implement Barrier::await() without using synchronization (e.g. by “spinning”—checking for a condition in a loop to wait until it becomes true). Ignore postAction for now.

Run BarrierDemo again. What behavior do you see? (different groups may see different behavior)

Synchronization

Where is synchronization needed?

Synchronization is not required everywhere, even when a class is shared between threads. It is important to recognize in which situations synchronization is required, so you can confidently avoid race conditions without unnecessary overhead.

Is synchronization required in the constructor? If so, which object should be synchronized on? If not, justify why not.

Is synchronization required in totalThreads()? If so, which object should be synchronized on? If not, justify why not.

Is synchronization required in awaitingThreads()? If so, which object should be synchronized on? If not, justify why not.

Await

Fix your implementation of await() so that it uses synchronization to avoid race conditions and to block without “spinning”. Continue ignoring postAction for now.

Run BarrierDemo again. Is the requirement regarding subtask B being respected?

postAction

Implement the requirement related to postAction. Run BarrierDemo again. Is the behavior what you would expect?

Reference the state diagram from lecture 20. Which state is each thread in when postAction is executed? Use the portion numbers from your most recent run.

Going further

What would happen if more than totalThreads called await() on a Barrier?

Task 2: Iterators

Warmup: Circular linked list processing

Recall how we designed a generic class to represent linked-list nodes:

/** A node in a linked list. */
Node<T> {
    /** The value at this location in the list. */
    T value;

    /** The node after this one in the list; may be null. */
    Node<T> next;
}

Given a starting (“head”) node, you can process all elements in a linear linked list by advancing a “current node” variable to its next field until it is null. But in a circular linked list, the next field is never null; instead, the last node points back to the head node (we are assuming that the head node is on the circular portion—no “loops with tails”).

Write a loop to call a function process(String v) for every String value in a circular linked list whose head node (a Node<String>) is pointed to by a variable head.

Reference: Iteration using Iterators

If the type of the variable (or expression) xs implements Iterable<T>, then Java’s enhanced for-loop serves as “syntactic sugar,” transforming itself into a while-loop as follows:

Enhanced for-loop
for (T x : xs) {
    // LOOP BODY
}
Transformed while-loop
Iterator<T> it = xs.iterator();
while (it.hasNext()) {
    T x = it.next();
    // LOOP BODY
}

Two interfaces play a role in telling the compiler when this is possible:

Iterable
/** Implementing this interface allows an object to
 *  be the target of the enhanced for statement. */
interface Iterable<T> {
    /** Returns an iterator over elements. */
    Iterator<T> iterator();
}
Iterator
package java.util;

/** An iterator over a collection. */
interface Iterator<T> {
    /** Returns true if the iteration has more elements. */
    boolean hasNext();

    /** Returns the next element in the iteration.
     *  Effects: advances this iterator to the next element. */
    T next();
}

Task: Iterator for circular linked list

Our goal is to be able to write the following as a solution to the warmup exercise (wouldn’t this have made things easier for you in the client role?):

// `head` is a CNode<String>
for (String v : head) {
    process(v);
}

It should work for both linear and circular linked lists (we’ve renamed the node class to CNode to emphasize this possibility).

Part 1: Iterator design

We will need an implementation of Iterator<T>; let’s write a new class CNodeIterator<T> to serve that role. In order to perform its duties (yielding the next element and knowing when it’s done), it will need to store some state. Identify (and write specifications for) some fields that will help CNodeIterator do its job.

Part 2: Iterator definition

Download CNode.java and add it to a new project in IntelliJ.

In IntelliJ, create class CNodeIterator implementing Iterator<T>, add your proposed fields, and write a constructor. Leverage IntelliJ’s hints to create stubs for hasNext() and next().

Part 3: Iterator hasNext

Implement the hasNext() method (look at the loop guard from your warmup solution for inspiration). Trace execution on a circular list of size 1 to check your logic.

Part 4: Iterator next

Implement the next() method. Don’t forget about the throws clause.

Part 5: Iterable

Modify CNode.java so that it implements Iterable<T>, returning a new CNodeIterator that will yield that node’s value first.

Test your implementation by uncommenting the main() method in CNode.java.

Task 3 Optional: Hash Tables

Object diagram

Suppose we put the following key–value pairs into an instance of HashDict<String, Integer>:

Assume that buckets has a length of 4 and that modular hashing is used to derive an index from the hash code. Draw an object diagram for the dictionary instance. You may represent a LinkedList<T> as an object with a head field of type Node<T>, which has fields for data (a T) and next (a Node<T>).

Implementing operations

Get

Study the partial implementation of get(). What should be done for each Entry in the bucket that the requested key belongs in?

Complete the TODO accordingly

Put

Note that the implementation of put() has a similar structure to get(), but the method has different responsibilities in each case. Complete the first three TODOs by answering the question posed by each one.

Tip: try to avoid doing too much work in “special cases” if it is possible for that work to be handled in the general case. Bugs tend to hide in special cases.

What should happen when the bucket the key belongs in is null?

What should be done for each entry in the bucket that the key belongs in?

What should be done if we did not return in the above loop?

Testing

Run the HashDictTest test suite. You should pass all of the tests except the one checking the load factor limit. Notice how the tests are organized into a hierarchy of requirements that the class’s operations should fulfill. This is called “specification-style testing”, and it helps guide coverage while making failures easier to diagnose.

Resizing

In order to maintain good performance as the dictionary grows, the hash table must be dynamically resized. Implement the resize() method according to its specifications.

Next, return to put() and make use of this method to enforce the load factor invariant documented in the class description. When enforcing the load factor invariant, how much bigger should the new table be to ensure an amortized O(1) resizing cost?

Ensure that the entire test suite now passes.

Reflection

Handling the case where a bucket is null complicates the implementation of every operation in the class. Alternatively, we could have constructed a new empty list for every element whenever a new bucket array is allocated. Are there any drawbacks to this alternative approach?

Submission

Open the assignment page for “Discussion activity 6” in CMSX and turn in your solution in one document. Note that this is graded for participation and not credit.