Basic synchronization patterns

This chapter presents a series of basic synchronization problems and shows ways of using semaphores to solve them. These problems include serialization and mutual exclusion, which we have already seen, along with others.

• Signaling
• Rendezvous
• Mutex
• Multiplex
• Barrier
• Reusable barrier
• Queue
• Fifo queue

Signaling

Possibly the simplest use for a semaphore is signaling, which means that one thread sends a signal to another thread to indicate that something has happened.

Signaling makes it possible to guarantee that a section of code in one thread will run before a section of code in another thread; in other words, it solves the serialization problem.

Assume that we have a semaphore named sem with initial value 0, and that Threads A and B have shared access to it.

Thread A

statement a1

sem.signal()

Thread B

sem.wait()

statement b1

The word statement represents an arbitrary program statement. To make the example concrete, imagine that a1 reads a line from a file, and b1 displays the line on the screen. The semaphore in this program guarantees that Thread A has completed a1 before Thread B begins b1.

Here’s how it works: if thread B gets to the wait statement first, it will find the initial value, zero, and it will block. Then when Thread A signals, Thread B proceeds.

Similarly, if Thread A gets to the signal first then the value of the semaphore will be incremented, and when Thread B gets to the wait, it will proceed immediately. Either way, the order of a1 and b1 is guaranteed.

This use of semaphores is the basis of the names signal and wait, and in this case the names are conveniently mnemonic. Unfortunately, we will see other cases where the names are less helpful.

Speaking of meaningful names, sem isn’t one. When possible, it is a good idea to give a semaphore a name that indicates what it represents. In this case a name like a1Done might be good, so that a1done.signal() means “signal that a1 is done,” and a1done.wait() means “wait until a1 is done.”

Rendezvous

Generalize the signal pattern so that it works both ways. Thread A has to wait for Thread B and vice versa. In other words, given this code

Thread A

statement a1

statement a2

Thread B

statement b1

statement b2

we want to guarantee that a1 happens before b2 and b1 happens before a2. In writing your solution, be sure to specify the names and initial values of your semaphores (little hint there).

Your solution should not enforce too many constraints. For example, we don’t care about the order of a1 and b1. In your solution, either order should be possible.

This synchronization problem has a name; it’s a rendezvous. The idea is that two threads rendezvous at a point of execution, and neither is allowed to proceed until both have arrived.

Mutex

A second common use for semaphores is to enforce mutual exclusion. We have already seen one use for mutual exclusion, controlling concurrent access to shared variables. The mutex guarantees that only one thread accesses the shared variable at a time.

A mutex is like a token that passes from one thread to another, allowing one thread at a time to proceed. For example, in The Lord of the Flies a group of children use a conch as a mutex. In order to speak, you have to hold the conch. As long as only one child holds the conch, only one can speak³.

Similarly, in order for a thread to access a shared variable, it has to “get” the mutex; when it is done, it “releases” the mutex. Only one thread can hold the mutex at a time.

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

Multiplex

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.

This pattern is called a multiplex. In real life, the multiplex problem occurs at busy nightclubs where there is a maximum number of people allowed in the building at a time, either to maintain fire safety or to create the illusion of exclusivity.

At such places a bouncer usually enforces the synchronization constraint by keeping track of the number of people inside and barring arrivals when the room is at capacity. Then, whenever one person leaves another is allowed to enter.

Enforcing this constraint with semaphores may sound difficult, but it is almost trivial.

Barrier

Consider again the Rendezvous problem from Section [rendezvous]. A limitation of the solution we presented is that it does not work with more than two threads.

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 n threads and that this value is stored in a variable, n, that is accessible from all threads.

When the first n − 1 threads arrive they should block until the nth thread arrives, at which point all the threads may proceed.

Reusable barrier

Often a set of cooperating threads will perform a series of steps in a loop and synchronize at a barrier after each step. For this application we need a reusable barrier that locks itself after all the threads have passed through.

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

Barrier objects

It is natural to encapsulate a barrier in an object. I will borrow the Python syntax for defining a class:

class Barrier:
    def __init__(self, n):
        self.n = n
        self.count = 0
        self.mutex = Semaphore(1)
        self.turnstile = Semaphore(0)
        self.turnstile2 = Semaphore(0)

    def phase1(self):
        self.mutex.wait()
            self.count += 1
            if self.count == self.n:
                self.turnstile.signal(self.n) 
        self.mutex.signal()
        self.turnstile.wait()            

    def phase2(self):
        self.mutex.wait()
            self.count -= 1
            if self.count == 0:
                self.turnstile2.signal(self.n)
        self.mutex.signal()
        self.turnstile2.wait()

    def wait(self):
        self.phase1()
        self.phase2()

The __init__ method runs when we create a new Barrier object, and initializes the instance variables. The parameter n is the number of threads that have to invoke wait before the Barrier opens.

The variable self refers to the object the method is operating on. Since each barrier object has its own mutex and turnstiles, self.mutex refers to the specific mutex of the current object.

Here is an example that creates a Barrier object and waits on it:

barrier = Barrier(n)        # initialize a new barrier
barrier.wait()              # wait at a barrier

Optionally, code that uses a barrier can call phase1 and phase2 separately, if there is something else that should be done in between.

Queue

Semaphores can also be used to represent a queue. In this case, the initial value is 0, and usually the code is written so that it is not possible to signal unless there is a thread waiting, so the value of the semaphore is never positive.

For example, imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits.

Similarly, 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.

Fifo queue

If there is more than one thread waiting in queue when a semaphore is signaled, there is usually no way to tell which thread will be woken. Some implementations wake threads up in a particular order, like first-in-first-out, but the semantics of semaphores don’t require any particular order. Even if your environment doesn’t provide first-in-first-out queueing, you can build it yourself.

use semaphores to build a first-in-first-out queue. Each time the Fifo is signaled, the thread at the head of the queue should proceed. If more than one thread is waiting on a semaphore, you should not make any assumptions about which thread will proceed when the semaphore is signaled.

For bonus points, your solution should define a class named Fifo that provides methods named wait and signal.