Discussion 13: Synchronization

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 there are multiple producer and consumer threads operating on the same resource, synchronization is required to prevent race conditions.

Learning Outcomes

Identify race conditions in a given piece of concurrent code and list the possible states the program can be in after it executes.
Use Java’s Thread class to write concurrent code.
Explain the semantics of locks in Java and write code involving synchronization.
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, meaning 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 entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that 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 critically thinking to “puzzle” them out.

Working together in small groups is encouraged during discussion!

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: 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. Your task is to implement thread-safe enqueue() and dequeue() functions (TODOs 1-2). Your 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.

Before you start coding: identify the synchronization methods that you will need for your implementation, and make sure you can explain what they do.

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.