Discussion 11 handout

Objectives

• Appreciate how a Ring Buffer data structure can support the Bounded Buffer abstraction
• Implement a thread-safe mutable data structure using the Monitor pattern

Warmup: Unsafe concurrent code

Run the given BoundedBuffer class a couple of times. What range of undesirable behavior do you observe on your computer? (e.g. exceptions, invariant violations, hangs, etc.)

Making BoundedBuffer thread-safe

Your objective is to make the BoundedBuffer class thread-safe by applying the monitor pattern.

Synchronization documentation

The first step is to identify which fields of the class are mutable and not themselves thread-safe; these fields will need to be guarded by one or more locks (mutexes). This is part of the implementer’s spec and must be documented! We can achieve this succinctly using a “guarded by” clause in each field’s JavaDoc comment: the clause “guarded by: foo” means that a mutex must be acquired on object foo before the field may be accessed. For monitors, the appropriate lock object is this (remember: every Java Object has its own mutex and condition variable).

Add this clause for all fields where it is necessary. Are there any fields that do not need to be guarded?

Synchronizing methods

Next, any code in the class’s methods that accesses guarded fields must synchronize on the appropriate locks. Remember that when the synchronized keyword is used without an argument, it synchronizes on this by default, appropriate for the monitor pattern. Additionally, if nearly all of a method’s body must be run while holding the lock, then the synchronized keyword can be moved to the method declaration for convenience.

Add synchronized to methods where it is needed. While doing so, consider the following questions:

1. Does the constructor need to be synchronized? Why or why not?
2. Are there any regular methods that do not need to be synchronized? Why or why not?
3. You may find that you now have synchronized methods calling other synchronized methods. You might worry that the inner call would block because the lock is already taken by the outer method, but this is not a concern in Java. Why not?

Blocking

The thread-safe version of the class should block when the desired operation cannot currently be performed. (Note that blocking methods in Java are almost always marked by throws InterruptedException; this has already been done for you.) Blocking (and un-blocking) threads involves the use of condition variables, and for monitors, the object’s intrinsic condition variable (associated with its intrinsic mutex) should be used.

Replace the precondition checks with code that waits until the condition is satisfied. Don’t forget to notify other threads if conditions they were waiting for might have changed as a result of the operation. Once that’s done, remove the futile attempt at client-side blocking from the producer and consumer tasks.

Run the main() method with your changes. Has the undesired behavior gone away? Note that concurrency bugs can be subtle, rare, and system-dependent, so testing alone is insufficient evidence of their absence. Following reliable patterns and performing careful analysis are important when trying to write safe concurrent code.

Bonus: notify() vs. notifyAll()

Since each operation on our buffer only adds or removes a single element at a time, it seems wasteful to wake up all waiting threads when only one of them could now make progress. Would using notify() instead of notifyAll() be a safe optimization? If not, what would the failure mode look like?

Submission

1. Open the assignment page for “Discussion activity 11” in CMSX
2. [Recorder] Find the “Group Management” section and invite each group member
3. [Others] Refresh the page and accept your invitation
4. [Recorder] Take a picture of your work and save as either a JPEG or a PDF file named “discussion_responses”. After all invitations have been accepted, upload your picture as your group’s submission.
   • Recommended scanning apps: Microsoft Office Lens, Adobe Scan, Genius Scan, Evernote Scannable

Ensure that your group is formed and your work submitted before the Friday evening deadline.

Tips and reminders

• Discussion is not a race. Focus on the current activity being facilitated by your TA and engage your whole group to propose and explain ideas.
• Elect a recorder to maintain the “master” copy of your work (others are still encouraged to jot down ideas on scratch paper). Rotate this position each week.
• It is a violation of academic integrity to credit someone for work if they were not present when the work was done, and the whole group is accountable. Your CMS group must only include classmates who attended section with you on that day. Remember that our participation policies accommodate occasional absences without penalty.
• It is your individual responsibility to ensure that you are grouped on CMS and that your group’s work is submitted before the deadline. Log into CMS the day after section to ensure that everything is in order, and contact your groupmates if not. It would be prudent for multiple members to photograph the group’s work.
• Only one group member (typically the recorder) needs to upload a submission. But their submission must not be uploaded until after all group members have confirmed their membership in CMS (contact your TA if you have trouble grouping in CMS).