Little book of semaphores Ch 3 - Basic Synchronisation Patterns

Rendezvous

Thread 1	Thread 2
statement a1	statement b1
statement a2	statement b2
We want the threads to wait for the other to complete the first statement i.e. {a1, b1} hb {a2, b2}. This is called a rendezvous pattern.

We can do this with 2 semaphores thread1_done and thread2_done. They are initialised with 0. The code will then look like:

Thread 1	Thread 2
statement a1	statement b1
thread1_done.signal()	thread2_done.signal()
thread2_done.wait()	thread1_done.wait()
statement a2	statement b2

Mutex

Initialise the semaphore to 1. To acquire the lock, do sem.wait() and to unlock do sem.signal().

Multiplex

Generalise mutex to allow a maximum of n threads to enter the critical section. Other threads have to wait.

To do this, simply initialise the semaphore to n. Each thread entering the critical section does a wait() call. The wait call doesn’t block for n threads and they are allowed to enter the critical section concurrently. When exiting, the threads call signal().

This is like having a number of tokens initially and each thread entering the critical section takes a token. When there are no tokens, the thread waits. A thread returns the token upon exiting the critical section.

Barrier

Generalise the rendezvous solution to n threads. At a point, each thread will have to wait for all others to arrive.

My Solution

Intiailise the semaphore to -n+1. The barrier will look like:

sem.signal()
sem.wait()
sem.signal()

Note that each thread will block on wait() call until all threads have called signal(), thus indicating they’ve arrived at the barrier. When one thread gets unblocked, it signals so one other can get unblocked and so on.

This should work if we can initialise semaphore to a negative value. It is inefficient since all threads don’t get unblocked at once when everyone has reached the barrier.

Book Solution

We maintain these variables:

count = 0 # Count the number of threads that have reached the barrier
mutex = Semaphore(1) # Mutex for count
barrier = Semaphore(0) # Locked until all threads arrive, then unlocked

The barrier code can then look like this:

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

Note: Accessing count outside of mutex lock looks dangerous, but is fine in this case (probably not in C++ particulary, but logically).

Turnstile

The pattern of wait() followed by signal() is called a turnstile. Only one thread is allowed to pass at a time.

• The barrier can be signalled multiple times as multiple thread could see count == n.
  • If we accessed count inside the mutex, only one thread will be able to signal
• Due to the above point, barrier’s state is not known at the time when all threads pass through. It will depend on the number of threads that signal the barrier.

Potential deadlock can happen if we move all the barrier signalling logic inside the mutex:

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

The first thread that enters will block on the barrier and it will be a deadlock.

Deadlock Source

A deadlock source is blocking on a semaphore while holding a mutex

Reusable Barrier

Rewrite the barrier so it is left in the initial state when all threads exit.

Attempt 1

The following solution is the first one that came to mind, however it is not correct.

# Rendezvous
 
mutex.wait()
	count = count + 1
	if count == n:
		barrier.signal()
mutex.signal()
 
barrier.wait()
barrier.signal()
 
# Critical point
 
mutex.wait()
	count = count - 1
	if count == 0:
		barrier.wait()
mutex.signal()

The first lock ensures only one thread is able to signal the barrier. Then the barrier semaphore stores 1. The last lock section ensures that the last thread passing through will set the barrier to 0. Since the last thread sets it to 0, all the threads are able to pass the turnstile successfully.

This solution is not correct as the barrier will run in a loop. This means that a thread passing through the last section will again go to the rendezvous.

Hint

The current problem is that one thread can restart the loop. To solve this, use 2 turnstiles

turnstile1 = Semaphore(0)
turnstile2 = Semaphore(1)
mutex = Semaphore(1)

Initially, the first turnstile is locked and the second is open. When all threads arrive at the first turnstile, we’ll lock the second turnstile and open the first. Then when all threads arrive at the second turnstile, we’ll lock the first and unlock the second allowing threads to enter the loop again

Attempt 2

# Rendezvous
 
mutex.wait()
	count = count + 1
	if count == n:
		turnstile2.wait() # Lock the second turnstile
		turnstile1.signal() # Open the first turnstile
mutex.signal()
 
turnstile1.wait()
turnstile1.signal()
 
mutex.wait()
	count = count - 1
	if count = 0:
		turnstile1.wait() # Lock the first turnstile as all threads have passed it
		turnstile2.signal() # Open the second turnstile
mutex.signal()
 
turnstile2.wait()
turnstile2.signal()

Two-phase barrier

This solution is sometimes called a two-phase barrier as it forces all of the threads to wait twice

The above solution is correct due to:

• turnstile1 is locked initially, no thread can pass it.
• count is incremented while holding a mutex, and so only the last thread passing through can unlock the first turnstile. It also locks the second turnstile
• When all threads pass through the first turnstile, they start decrementing count.
• Only the last thread passing through lock the first turnstile and unlocks the second.
• Also, we always the lock one turnstile before unlocking the other. This makes sure threads can’t pass the other turnstile after passing through the first.

Loaded Turnstile

The turnstile has a problem that one thread passing through signals other which then passes and signals another. This causes many more context switches than necessary. Ideally all threads should be able to pass through once the turnstile is unlocked.

We can use turnstile.signal(n) to increment turnstile by n instead of 1. Then the code for waiting at the turnstile would just call wait() instead of wait() + signal().

Note that incrementing by n is not a standard feature. It can easily be done in a loop. While it won’t be atomic, it doesn’t matter in this case.

Queue

Semaphores can represent a queue. Suppose we two kinds of threads, leaders and followers. When a leader arrives, it checks to see if there is a follower waiting. If so, the leader and followers proceed, otherwise it also waits. Similarly when a follower arrives, it waits if there’s no leader. If there is, all of them proceed.

Attempt 1

# Initialise
leader_turnstile = Semaphore(0)
follower_turnstile = Semaphore(0)
 
# Leader thread
follower_turnstile.signal() # Unlock the follower turnstile
leader_turnstile.wait()
leader_turnstile.signal()
 
# Follower Thread
leader_turnstile.signal() # Unlock the leader turnstile
follower_turnstile.wait()
follower_turnstile.signal()

Initially, both turnstiles are locked. When a leader arrives it opens the follower turnstile and when a follower arrives it opens the leader turnstile. So when both have arrived, both the turnstiles are opened.

Book Solution

It’s similar to my attempt, except it clarifies the problem a bit more that we’re trying to pair up leaders and followers. So, one follower should signal one leader and vice versa.

# Initialise
leader_queue = Semaphore(0)
follower_queue = Semaphore(0)
 
# Leader thread
follower_queue.signal() # one follower can pass through
leader_queue.wait() # Wait for one follower to pass through
dance()
 
# Follower thread
leader_queue.signal() # One leader can pass through
follower_queue.wait() # Wait for one leader to pass through
dance()

Exclusive Queue

The above code doesn’t ensure that dance() is called by 1 leader concurrently with 1 follower. Once pairs of followers pass through, then multiple leaders can call dance() concurrently while followers wait. Here, we enforce that 1 leader can execute dance() concurrently with 1 follower only.

Attempt 1

Only one leader can execute dance seems like classic mutual exclusion. So here is the solution using mutexes.

# Initialise
leader_queue = Semaphore(0)
follower_queue = Semaphore(0)
leader_mutex = Semaphore(1)
follower_mutex = Semaphore(1)
 
# Leader thread
follower_queue.signal() # one follower can pass through
leader_queue.wait() # Wait for one follower to pass through
 
leader_mutex.wait()
	dance()
leader_mutex.signal()
 
# Follower thread
leader_queue.signal() # One leader can pass through
follower_queue.wait() # Wait for one leader to pass through
 
follower_mutex.wait()
	dance()
follower_mutex.signal()
dance()

Book Solution

Seems a bit opaque, not writing it down.