Discussion 13: Synchronized Buffers

In today’s discussion, you’ll get some practice with synchronization in Java and reasoning about multithreaded programs. You’ll be working with a concurrent ring buffer, a fixed-size queue where producers add items and consumers remove them. When multiple producer and consumer threads operate on the same resource, synchronization is required to prevent race conditions.

Learning Outcomes

  1. Identify race conditions in a given piece of concurrent code and list the possible states the program can be in after it executes.
  2. Use Java's Thread class to write concurrent code.
  3. Explain the semantics of locks in Java and write code involving synchronization.
  4. Explain how condition variables can be used to synchronize modifications of a shared resource.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool; it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going, so we can make adjustments in future classes. Your grade in discussion is based on your attendance, active participation, and completion of that day’s activity. More information about the grading and expectations can be found in the syllabus.

Since discussion activities are not graded for correctness, we do not restrict what resources you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from thinking critically to “puzzle” them out.

Unsynchronized Ring Buffer

Download Starter Code download

We’ll be working with RingBuffer.java first; this contains a non-synchronized, non-blocking implementation of a ring buffer backed by an array. Take a minute to inspect the code, in particular the enqueue() and dequeue() methods.

This implementation will behave as intended if it is run by a single-threaded program, but may exhibit incorrect behavior if there are multiple producer and consumer threads. To see this, you’ll work through an example and identify the possible race conditions.

Exercise 1: Explaining Race Conditions
What are race conditions? Why haven't we needed to worry about them until this point in the semester?
Exercise 2: Identifying Race Conditions
Suppose we have a RingBuffer object buffer containing Integers, and the current state of the array backing store for our buffer looks like this:

You can also assume that, at this point, iHead == 0 and iTail == 3. Then, suppose the following enqueue calls are executed on separate threads: 
1
2

new Thread(() -> buffer.enqueue(3)).start();
new Thread(() -> buffer.enqueue(4)).start();

1
2

new Thread(() -> buffer.enqueue(3)).start();
new Thread(() -> buffer.enqueue(4)).start();
Draw the possible states of the buffer (specifically, the backing array and iTail) after these calls are executed.

Synchronized Ring Buffer

Now look at the ConcurrentRingBuffer.java file in the release code. Once completed, this class will model a ring buffer that can be safely accessed concurrently by multiple threads.

Exercise 3: Concurrency Benefits
What benefits does a concurrent ring buffer offer over the simple data structure from before? Give two examples where we'd prefer the concurrency-friendly implementation.

While most of this class has been written (and is very similar to the RingBuffer from before), it is missing thread-safe definitions of enqueue() and dequeue() (TODOs 1-2). These implementations should block if there is nothing to be done; that is, if there is no space in the queue to add a new element, or if there is no element in the queue to be consumed.

Note: Synchronization is the topic of Lecture 27, so you will need ideas (such as "blocking") and constructs that we haven't yet discussed in class. We wanted to introduce this activity in discussion to give you some practice with these skills that you'll need for the final exam.
Exercise 4: Synchronization in Java
Look up each of the following keywords and methods in the Lecture 27 notes. In your own words, give a 1-2 sentence description of what each construct does and why it's useful to achieve proper concurrency.

synchronized:

wait():

notifyAll():

Exercise 5: Synchronized Code
(It's alright if you don't have time for this during class; you only need to submit your written answers to the first four exercises. It may be good to revisit this coding exercise after Lecture 27 to apply what you learn.)

Complete the definitions of the enqueue() and dequeue() methods according to their specifications. Use the wait() and notifyAll() methods to achieve proper synchronization.

Run the program and observe its output. The output may vary across runs, since it is dependent on what order the threads are scheduled in for execution (which we do not control here). However, you should see that elements are always dequeued in the same order in which they are enqueued. It will also be useful to look at the main() method and understand what it's doing; if you'd like, you can also play around with the size of the buffer and the number of producer and consumer threads, and observe how that affects the program's behavior.

Submission

At the end of class, your group’s primary author should create a PDF with your written answers and upload this to the “Discussion 13” Gradescope assignment, tagging all other members of the group onto the submission.