Classical synchronization problems

Prev: Basic synchronization patterns Next: Less classical synchronization problems

Producer-consumer problem

Assume that producers repeatedly run:

event = waitForEvent()
buffer.add(event)

Assume that consumers repeatedly run:

event = buffer.get()
event.process()

The synchronization constraints are:

1. While an item is being added to or removed from the buffer, the buffer is in an inconsistent state, so threads must have exclusive access to the buffer.
2. If a consumer thread arrives while the buffer is empty, it blocks until a producer adds a new item.

We need two semaphores. A mutex and a semaphore. The mutex guards access to the buffer (since both producers and consumers write to it), and otherwise it signals to items that an item is available. The consumer first waits for items, then waits for the mutex to become available. That keeps its ordering without backoff.

mutex = Semaphore(1)
items = Semaphore(0)

# Producer
event = waitForEvent()
mutex.wait()
buffer.add(event)
mutex.signal()
items.signal()   # announce that one item is now available

# Consumer
items.wait()     # blocks until count > 0, then decrement
mutex.wait()
event = buffer.get()
mutex.signal()
event.process()

Exercise

Add synchronization statements to the producer and consumer code to enforce the synchronization constraints.

Deadlock #4

This broken consumer tries to check items inside the mutex:

mutex.wait()
    items.wait()
    event = buffer.get()
mutex.signal()
event.process()

Why is this a bad idea?

Producer-consumer with a finite buffer

Add the additional constraint that if a producer arrives when the buffer is full, it blocks until a consumer removes an item.

Assume that the buffer size is known as bufferSize. You cannot write:

if items >= bufferSize:
    block()

because semaphores cannot be read directly.

Write producer-consumer code that handles the finite-buffer constraint.

Readers-writers problem

The synchronization constraints are:

1. Any number of readers can be in the critical section simultaneously.
2. Writers must have exclusive access to the critical section.

Exercise

Use semaphores to enforce these constraints, while allowing readers and writers to access the data structure, and avoiding the possibility of deadlock.

Starvation

Extend this solution so that when a writer arrives, the existing readers can finish, but no additional readers may enter.

Writer priority

Write a solution to the readers-writers problem that gives priority to writers. That is, once a writer arrives, no readers should be allowed to enter until all writers have left the system.

No-starve mutex

Here, “weak semaphores” means semaphores that satisfy Property 3 but not necessarily Property 4:

1. Property 3: if there are threads waiting on a semaphore when a thread executes signal, then one of the waiting threads has to be woken.
2. Property 4: if a thread is waiting at a semaphore, then the number of threads that will be woken before it is bounded.

Exercise

Write a solution to the mutual exclusion problem using weak semaphores. Your solution should provide the following guarantee: once a thread arrives and attempts to enter the mutex, there is a bound on the number of threads that can proceed ahead of it. You can assume that the total number of threads is finite.

Dining philosophers

The philosophers execute:

while True:
    think()
    get_forks()
    eat()
    put_forks()

The required constraints are:

1. Only one philosopher can hold a fork at a time.
2. It must be impossible for a deadlock to occur.
3. It must be impossible for a philosopher to starve waiting for a fork.
4. It must be possible for more than one philosopher to eat at the same time.

An initial attempt is:

def get_forks(i):
    fork[right(i)].wait()
    fork[left(i)].wait()
 
def put_forks(i):
    fork[right(i)].signal()
    fork[left(i)].signal()

Exercise

What is wrong with this solution?

Deadlock #5

Write a solution to this problem that prevents deadlock.

Hint: One way to avoid deadlock is to think about the conditions that make deadlock possible and then change one of those conditions. In this case, the deadlock is fairly fragile; a very small change breaks it.

Lefties and righties

Prove that if there is at least one leftie and at least one rightie, then deadlock is not possible.

Hint: Deadlock can only occur when all 5 philosophers are holding one fork and waiting forever for the other. Otherwise, one of them could get both forks, eat, and leave.

Tanenbaum’s solution

Either convince yourself that Tanenbaum’s solution prevents starvation or find a repeating pattern that allows a thread to starve while other threads make progress.

Cigarette smokers problem

The tempting but broken smoker code is:

# Smoker with matches
tobacco.wait()
paper.wait()
agentSem.signal()

# Smoker with tobacco
paper.wait()
match.wait()
agentSem.signal()

# Smoker with paper
tobacco.wait()
match.wait()
agentSem.signal()

Exercise

What is wrong with this solution?

Generalized Smokers Problem

Modify the previous solution to deal with the variation where the agent does not wait after putting out ingredients, so multiple instances of an ingredient might accumulate on the table.