Takashi's Notes

Basic synchronization patterns

5 min read

Basic synchronization patterns

Prev: Semaphores Next: Classical synchronization problems

Rendezvous

Exercise

Generalize the signal pattern so that it works both ways. Thread A has to wait for Thread B and vice versa. Given this code:

# Thread A
statement a1
statement a2
# Thread B
statement b1
statement b2

Guarantee that a1 happens before b2 and b1 happens before a2.

In writing your solution:

  1. Specify the names and initial values of your semaphores.
  2. Do not enforce too many constraints. We do not care about the order of a1 and b1; either order should be possible.

You can use two semaphores:

a_sema = Semaphore(0)
b_sema = Semaphore(0)

run a1
a_sema.signal()
b_sema.wait()
run a2

run b1
b_sema.signal()
a_sema.wait()
run b2

Mutex

Exercise

Add semaphores to the following example to enforce mutual exclusion to the shared variable count.

# Thread A
count = count + 1
# Thread B
count = count + 1

Use a mutex:

mutex = Semaphore(1)

Each thread would look like this:

mutex.wait()
count = count + 1
mutex.signal()

Multiplex

Exercise

Generalize the previous solution so that it allows multiple threads to run in the critical section at the same time, but it enforces an upper limit on the number of concurrent threads. In other words, no more than n threads can run in the critical section at the same time.

Initialize the semaphore’s size to N.

Barrier

Exercise

Generalize the rendezvous solution. Every thread should run the following code:

rendezvous
critical point

The synchronization requirement is that no thread executes critical point until after all threads have executed rendezvous.

You can assume that there are threads and that this value is stored in a variable, n, that is accessible from all threads.

When the first threads arrive they should block until the th thread arrives, at which point all the threads may proceed.

# Each thread
rendezvous
 
mutex.wait()
count += 1
mutex.signal()
 
if count == n:
    barrier.signal()   # last thread unlocks the gate
 
barrier.wait()         # wait for the gate
barrier.signal()       # pass it on to the next thread
 
critical point

Barrier non-solution

What is wrong with this solution?

rendezvous
 
mutex.wait()
    count = count + 1
mutex.signal()
 
if count == n:
    barrier.signal()
 
barrier.wait()
 
critical point

The bug is that barrier.wait() doesn’t signal afterwards. Only one thread gets through.

Deadlock #2

For the same code above:

  1. Does this code always create a deadlock?

As long as there is only one thread, there’s no deadlock.

  1. Can you find an execution path through this code that does not cause a deadlock?

With more than one thread, there’s always a deadlock.

  1. Fix the problem.

Signal after the wait.

Reusable barrier

Exercise

Rewrite the barrier solution so that after all the threads have passed through, the turnstile is locked again.

After all threads pass through, the turnstile is locked by the last thread.

# Each thread
rendezvous
 
mutex.wait()
count += 1
mutex.signal()
 
if count == n:
    barrier.signal()
 
barrier.wait()
barrier.signal()
 
critical point
 
mutex.wait()
count -= 1
mutex.signal()
 
if count == 0:
    barrier.wait()   # last one out locks the turnstile again

Reusable barrier non-solution #1

What is the problem with this attempt?

rendezvous
 
mutex.wait()
    count += 1
mutex.signal()
 
if count == n:
    turnstile.signal()
 
turnstile.wait()
turnstile.signal()
 
critical point
 
mutex.wait()
count -= 1
mutex.signal()
 
if count == 0:
    turnstile.wait()

A fast thread can lap all the other threads.

Reusable barrier problem #1

Fix the problem from the previous attempt.

The way to fix it is to create another semaphore that locks out those who finished until all the threads have finished.

Reusable barrier non-solution #2

Identify and fix the problem in this attempt:

rendezvous
 
mutex.wait()
    count += 1
    if count == n:
        turnstile.signal()
mutex.signal()
 
turnstile.wait()
turnstile.signal()
 
critical point
 
mutex.wait()
    count -= 1
    if count == 0:
        turnstile.wait()
mutex.signal()

Remember that this barrier will be inside a loop. After executing the last line, each thread will go back to the rendezvous.

Queue

Exercise

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor.

  1. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits.
  2. When a follower arrives, it checks for a leader and either proceeds or waits, accordingly.

Write code for leaders and followers that enforces these constraints.

leaders = Semaphore(0)
followers = Semaphore(0)
 
# Leader code:
 
followers.wait()
leaders.signal()
 
# Follower code:
 
followers.signal()
leaders.wait()

Exclusive queue

Add the additional constraint that each leader can invoke dance() concurrently with only one follower, and vice versa. In other words, you have to dance with the one that brought you.

Write a solution to this “exclusive queue” problem.

The follower waits for its leader and the leader picks a follower.

follower_map = {}
 
# Follower waits
sem = Semaphore(0)
follower_map[my_id].wait()
 
# Leader picks a follower
follower_map[my_id].signal()

Graph View

Backlinks