Little book of semaphores Ch 1

1.3, page 3

Two events are concurrent if we cannot tell if one will happen before the other.

Semaphore, page 7

A semaphore is a integer, along with these properties:

• it can be initialised to whatever. After that, it can only be incremented or decremented. Current value can’t be taken
• when a thread decrements the semaphore: if it becomes negative, the thread sleeps
• when a thread increments, it wakes up a waiting thread, if any.

The functions operating on a semaphore can be called signal()/wait() or increment()/decrement().

Chapter 2, Basic Synchronization 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

Attemp