Fun With Flags

Managing concurrency with better communication. And flags.

15 January 2019 • Tags: talks

Based on a talk presented at the Toronto Area Cocoa and WebObjects Developers Group (tacow).

The word semaphore has two parts: sema for “meaning” (like the word semantic) and phoros for “carry” (like a pheremone carrying a chemical signal).

Flag semaphores are a communication tool, carrying meaning across some distance.

You have to communicate one letter at a time which can be slow, but communication is silent and can be done so long as the sender and receiver are in visible range.

But what does communicating with flags have to do with concurrency?

Concurrency vs Synchronization

Concurrency is easy: you have multiple sequential processes, and they run independently of each other. In what order? Who cares, it’s concurrent!

If you do care about the order across processes, you need to introduce synchronization. And it turns out, synchronization is all about communication between these processes (or threads, or queues, etc.)

Concurrent sequential processes, synchronized

By communicating, we can create synchronization points to help us line up events on one process in relation to events in the other process.

What kind of communication do we need to send to manage multi-threaded computing and concurrent processes?

Locks, for example, can enforce mutual exclusion. Each process communicates with the lock to check whether it’s OK to continue.
Dispatch queues on Apple platforms manage sibling tasks. You can enqueue multiple things on a serial queue and it manages running them in order.
Operation queues are similar and let you specify dependencies. The operation manages the signaling needed to start task B when task A completes.

Semaphores offer another way to do this kind of communication and coordination.

Semaphores

A semaphore is like a lock with a counter. The simplest kind of semaphore is a binary semaphore, which acts like a lock. It’s “binary” since (if used properly) the value is either 0 or 1.

If the value is 1, the resource protected by the semaphore is available. If a task waits for the semaphore, the value goes down to 0.

If another task comes by and waits for the semaphore, it’s blocked and can’t continue since the value is 0.

When the first task completes it signals the semaphore, which increments the integer from 0 to 1. Then that waiting task wakes up, “acquires the lock” so to speak, and the semaphore value goes down to 0 again.

Bigger values

Simple locks and binary semaphores are on or off, but you can imagine initializing a semaphore with a value greater than 1.

Say you had a queue of URLs to download things from the internet. To avoid overwhelming the connection, you only want three active downloads at a time.

You could initialize a semaphore with a value of 3:

let allowDownload = DispatchSemaphore(value: 3)

Then on a background queue, start a download:

queue1.async {
  guard let url = urls.removeLast() else { return }

  allowDownload.wait()
  // start the download here
  // ...
  // download completed
  allowDownload.signal()
}

You could create any number of background queues or concurrent queues with hundreds of downloads but if they all use the semaphore properly, only three downloads at most will happen at one time.

Vs Locks

Semaphores are conceptually similar to locks with a counter, but there are some important differences too.

Thread safety

With most implementation of locks, you must acquire and then release the lock on the same thread or bad things might happen.

Semaphores have no such restriction — the atomicity of accessing and changing that integer value inside is part of the semaphore itself. That means you can wait and signal from different threads if that makes sense in your code.

Accessors

Locks often include API for peeking, or checking if the lock is available or not.

Semaphores usually have no way to read the value of the integer stored inside; they only offer the wait() and signal() functions.

POSIX semaphores are a notable exception here, as they include a sem_getvalue function to read the value. Semaphores in libdispatch have no way to do this.

Closing Words

Semaphores offer an interesting way to control access to a limited resource in a thread-safe way.

Compared to other techniques such as delegation, semaphores are decoupled. The waiting task and signaling task know nothing about each other since the messaging happens through the semaphore.

The communication happens just like a flag semaphore: signaling out there to the world, and waiting patiently for a response back.

I’m going into meetup and conference semi-retirement, so this will be my last public talk for a while. Thanks to the organizers (past and present) of tacow for the amazing community they’ve shepherded, and the always wonderful attendees for listening and making me miss being back home.

Greg Heo