2.1 Lock

A lock has two states: locked and unlocked. It also has two functions/methods: acquire and release. Acquire changes the lock from unlocked to locked, blocking until that can be done. Release changes the lock from locked to unlocked.

The most common use of locks is to implement mutual exclusion: a chunk of code (called a critical section) that only one thread can access at a time. This tends to look like

lock.acquire()

do things
using only one thread
at a time

lock.release()

Releasing after doing the work has potential problems if one of the things in the critical section can crash, so it’s often actually written as

lock.acquire()
try:
    do things
    using only one thread
    at a time
finally:
    lock.release()

The finally-based pattern is so common that it often has its own language-level syntax, such as in Java

synchronized(lock) {
    // do things
    // using only one thread
    // at a time
}
// lock has been released here

or in Python

with lock:
    ... # do things
    ... # using only one thread
    ... # at a time
# lock has been released here

2.2 Condition Variable

A condition variable is like a lock with a special temporary-release mode. It has acquire and release function/methods just like a lock, but also wait, notify, and notify_all methods

wait is like a temporary release: it releases the lock, then blocks until both (a) notified and (b) can reacquire.

This may seem strangely complicated, but it allows a particular pattern that is very useful, namely locking until some arbitrarily-complicated condition is met:

cv.acquire()
while not complicated_condition_is_met():
    cv.wait()

do things using only one thread at a time
that change the complicated condition for some thread

cv.notify_all()
cv.release()

Because the acquire/release pair is essential, it is often facilitated with try/finally or a language-level syntax like Python’s:

with cv:
    while not condition_met():
        cv.wait()
    ... # do things
    ... # using only one thread
    ... # at a time
    cv.notify_all()
# lock has been released here

food_station.acquire()
while not food_station.has_food():
    food_station.wait()
food_station.serve(me)
food_station.notify()
food_station.release()

food_station.acquire()
food_station.refill()
food_station.notify()
food_station.release()

2.3 Reader-writer lock

A reader-writer lock can be locked in two ways. If acquired in exclusive or write mode, it acts just like a regular lock. If acquired in shared or read mode, any number of threads can acquire it simultaneously, but all must release it before it can be acquired in exclusive/write mode.

Reader-writer locks are more common for file systems than for threads, where the file itself acts as the data you lock on. In both C (via #include <sys/file.h>) and Python (via import fcntl) the flock function takes two arguments: the file to lock or unlock and an enumeration value that is one of

• LOCK_UN to unlock
• LOCK_EX to lock in exclusive mode, blocking if any other thread has this locked in any mode
• LOCK_SH to lock in shared mode, blocking if another thread has this locked in exclusive mode

Reader-writer locks can be implemented for threads using a condition variable and a count of the number of readers holding the lock. Many reader-writer locks prioritize writers over readers by also having a count of the number of writers waiting for the lock. An example of such an implementation can be found on Wikipedia.

2.4 Semaphore

Semaphores were among the first synchronization primitives to be used in computing. They come in two types (binary and counting).

Binary semaphores are used as a type of communication between threads: one thread blocks on it, then later another thread unblocks it.

Counting semaphores are used like locks that can be acquired several times before they block.

I’ve never used either type of semaphore outside of low-level systems code like implementing operating-system functionality.

2.5 Barrier

A barrier acts in some ways like the opposite of a lock. A lock blocks if any other threads have acquired it; a barrier blocks until several threads are trying to pass it, then lets them all through at once.

Barriers are created with a count of the number $n$ of threads needed to pass the barrier and have just one function: wait, which blocks the first $n-1$ threads that call it and then lets them all unblock when the $n$th thread calls wait.

Barriers are less versatile than some other synchronization primitives, but very helpful in specific situations. Two specific situations I’ve seen barriers used in repeatedly are handling a setup phase before a work phase and collecting intermediate results before deciding what to do next.

Setup phase barriers look like this:

b = Barrier(n)
have n threads each do:
    setup
    b.wait()
    do work

In this design, all threads will finish their setup before any of them start working, ensuring that no work messages are dropped because they are sent to a thread that’s not set up yet or the like.

Intermediate result barriers look like this:

b = Barrier(n)
have n threads each do:
    do part of the job
    b.wait()
    if thread 1:
        look at preliminary results
        make a decision what to do next
    b.wait()
    do rest of job

In this design all threads finish the first part, then that completed first part is used by one thread, and only once that thread is done do the threads pick up with the next part of their work.