Sponge Bob in Hall Monitor

Semaphore Project

by: burt rosenberg
at: university of miami
date: 7 oct 2021

Goals

• Understand the need and principles of synchronization
• To understand the monitor abstraction
• To gain experience with Mutex and Condition Variables
• To practice reasoning about concurrent processes.

Specific steps

1. Copy the [repo]/class/proj3 for template files into your proj3 directory. Add and make an initial commit.
2. All the code you need to change is in the file monitor.c.
3. There are mild tests provided in the Makefile. These are not to be considered comprehensive.
4. There is a basic solution just using locks, which is safe and live. It is a good first step.
5. There is the full solution using wait and signal, which is safe, live and efficient, as the thread does not repeatedly poll the ring buffer for its opportunity to queue or dequeue.

Discussion

While threads are convenient to work concurrently on a task, they present synchronization problems. In our cases, the threads will be working on a single shared ring buffer, and access must be synchronized else the program will not work as expected. The idea is to consider the ring buffer data structure as a lockable object, and to demand that threads acquire the lock before working on values on the data structure, and to be sure to release lock when those critical actions are completed.

A monitor is a software object that you can,

• Enter: that is, take the lock, and have exclusive access while holding the lock.
• Leave: that is, release the lock, so other threads can content for its acquisition.
• Wait: the lock is a schedulable object, and without leaving the monitor, but with releasing the lock, a thread can go into a wait state.
• Signal: a signal can be sent to one or all waiting threads, to leave their wait state, contend to reacquire the lock and continue on from where they called their wait.

Please reference POSIX Threads Programming from the Lawrence Livermore National Laboratory.

Constructing a Monitor

You are to wrap the ring buffer code in a monitor wrapper. Provided is the workable but not safe example. The code in monitor.c calls the ring buffer, with a bit of conditions to see if the ring buffer is empty or full.

This is not thread safe. Stage one is to use the mutex to lock the ring buffer data structure on entering the monitor code, and unlocking the code on leaving. You need to consider what to do if the ring buffer is locked, but is not ready to receive or provide a character. Hint: drop the lock (so other threads can have a chance at the buffer) then try again.

Stage two is to be more fancy, and once having acquired the lock, if the ring buffer is not ready, to wait, rather then leave. This is a more complicated solution which needs some questions answered. Where, for instance, do we signal? Should we signal or broadcast? The solution suggest a single condition variable. Should there be more? What can be assume upon reentering the monitor after being revived from a wake?

Producer–Consumer Problem

The problem you are being asked to solved is called the Producer–Consumer Problem. Each thread is either a producer, which adds characters to the ring buffer, or a consumer, which takes characters from the ring buffer. The producer might find the buffer full. Then it must wait. The consumer might find the ring buffer empty. Then it must wait.

A waiting consumer should be signaled at least by a producer putting something in the ring buffer. Likewise, a waiting producer should be signaled at least by a consumer taking something from the ring buffer. It is possible that signals are not created at the proper time, and the monitor will have a sort of deadlock. Threads will wait forever, and your program does not exit.

Overview of the code

The code takes a command sequence that gives instructions to producer and consumer threads. For w producer threads and r consumer threads, the command line is,

w-delay_1 repeat_1 characters_1  ... w-delay_w repeat_w characters_w r-delay_1 ... r-delay_r

The i-th producer thread will wait w-delay_i seconds before starting, then enqueue all the characters in characters_i, and do that repeat_i time, then enqueue a null character to the ring buffer.

The i-th consumer thread will wait r-delay_i seconds before starting, then dequeue from the ring buffer until some null characters are received. The rules are automatic that there must be no more consumer threads than producer threads, that all but the r-th consumer thread exits on the first null character consumed, and the r-th consumer threads exists after consuming exactly the null characters needed to balance the total null bytes enqueue by the producer threads.

Testing your the code

The first thing to note is that the given code does not work correctly. If you run the count target, it shows that on completion of the run, typically fewer characters were dequeued than enqueued. Because of concurrency, some characters were lost.

Correctness by testing is more random with this sort of code. A correct program should always terminate cleanly, with out hanging until a control-C, and the number of enqueues should equal the number of dequeues. There are obviously more requirements for correctness — that the dequeue stream logically follows from the enqueue stream. The tests provided do not test that requirement.

However, while it is easy to show that some codes are incorrect, some incorrect codes are correct enough that failure is rare. A proper test does stress the code, in the hope of uncovering a defect.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 7 oct 2021
update: 7 oct 2021