Semaphores and locks

A Semaphore hands out permits: it limits how many tasks do something at the same time, or counts items between a producer and a consumer. A CriticalSection is a recursive lock owned by a task. Both suspend a task that has to wait, so its thread runs other tasks meanwhile, and both come with scope guards. Each primitive has a plain variant for any number of waiting tasks and an _s variant for at most one. The examples are small pieces of guide-semaphores-locks.cpp, a complete program that uses them from several tasks and checks the results.

Semaphores

Wait takes one permit and suspends the calling task while the count is 0. Release adds permits (one by default, or count) and resumes as many waiting tasks as it can serve. TryWait takes a permit if one is available and never suspends. The constructor takes the initial count (default 0).

• Any task or thread may release, not only one that waited. Release and TryWait never suspend and may be called from any thread; Wait needs a task or a converted thread.
• The count has no upper limit; keep it within the range of std::size_t.
• Semaphore serves any number of waiting tasks, without timeouts. Semaphore_s allows one waiting task at a time, is cheaper and offers Wait(Duration timeout), which returns false without taking a permit when it times out.

Limiting concurrency

A semaphore created with three permits lets three tasks into a section at a time. SemaphoreLock calls Wait in its constructor and Release in its destructor. It works with both Semaphore and Semaphore_s; the type follows from the argument:

// At most three downloads at a time; further callers suspend until a slot is free.
class Downloader
{
public:
    void Download(const Item& item) noexcept
    {
        SemaphoreLock slot(
            slots_); // Wait: suspends the task until a permit is free
        Transfer(item);
    } // ~SemaphoreLock: Release of the permit

private:
    Semaphore slots_{3}; // three permits, any number of waiting tasks
};

Any number of tasks may call Download; at most three are inside at the same time, and the others suspend until a permit is free. Use this to bound a resource, for example the number of connections or files open at once, or the memory held by the tasks of one stage.

Counting items

Unlike the Set calls of an auto-reset event, permits add up, so a semaphore can count items that one side produces and the other consumes:

// The producer stores orders in a fixed array and releases one permit per order;
// the single consumer takes one permit per order. Permits add up: no signal is
// lost.
struct OrderBook {
    Order       orders[100];
    Semaphore_s ready; // count 0; one waiter: the consumer
};

// Producer side: any task or thread.
void Publish(OrderBook& book, int index, const Order& order) noexcept
{
    book.orders[index] = order;
    book.ready.Release(); // order 'index' may be taken now
}

// Consumer side: the one task that waits.
void ProcessOrders(OrderBook& book, int count) noexcept
{
    for (int i = 0; i < count; ++i) {
        book.ready.Wait(); // suspends until order i is there
        Process(book.orders[i]);
    }
}

Release(count) adds several permits at once, for example after a batch of orders. With one consumer the cheaper Semaphore_s is enough. A ring buffer between two stages usually takes two semaphores, one counting filled slots and one counting free ones; see Task graphs.

Critical sections

CriticalSection is a mutual-exclusion lock owned by a task, not by a thread:

• Enter takes the lock, suspending the calling task while another task holds it. TryEnter never suspends and returns false if another task holds the lock.
• It is recursive: the owner may enter again and must call Leave as often as it entered.
• On the last Leave the lock is handed directly to a suspended task, which becomes the owner before it runs. Waiting tasks are served LIFO, without fairness.
• There are no timeouts, also not for CriticalSection_s.

CriticalSectionLock enters in its constructor and leaves in its destructor, for CriticalSection and CriticalSection_s alike:

// Stock levels shared by many tasks, guarded by a task-owned recursive lock.
struct DeliveryLine {
    int item;
    int quantity;
};

class Stock
{
public:
    void Add(int item, int quantity) noexcept
    {
        CriticalSectionLock lock(section_);
        levels_[item] += quantity;
    }

    // Books a whole delivery at once: holds the lock and calls Add, which enters
    // again.
    void AddDelivery(std::span<const DeliveryLine> lines) noexcept
    {
        CriticalSectionLock lock(section_);
        for (const DeliveryLine& line : lines)
            Add(line.item, line.quantity);
    }

    // A very short section: try up to 1000 times before suspending.
    int Level(int item) noexcept
    {
        SpinCriticalSectionLock lock(section_, 1000);
        return levels_[item];
    }

private:
    CriticalSection section_;
    int             levels_[16]{};
};

AddDelivery holds the lock and calls Add, which enters again; this is fine because the same task owns it. Other tasks see either none or all lines of a delivery.

Because the owner is a task, a task may hold the lock while it suspends, for example while it waits for I/O; other tasks that want the lock suspend in turn. Do not use a thread-owned lock (std::mutex, a Win32 CRITICAL_SECTION, SRWLOCK) across a point where a task suspends: the task may continue on another thread, and the waiting tasks block their threads instead of suspending.

Spinning guards

SpinSemaphoreLock and SpinCriticalSectionLock take a spinCount in addition. They first try up to spinCount times (TryWait or TryEnter, with YieldProcessor in between, keeping the thread) and only then fall back to the suspending Wait or Enter. A spinCount of 0 waits at once. Level in the example uses it.

Spinning pays off when the guarded section is a few instructions and the holder is running on another thread at that moment: the lock is free again after a few attempts, and the task saves the cost of suspending and being resumed. It wastes processor time when the holder runs long or is itself suspended (for example in I/O while holding the lock), because no amount of spinning helps then. Start with the plain guards and measure before you add spinning.

Choosing

The program calls these functions from several tasks at once, checks the results and prints:

downloads:  at most 3 at a time: yes
orders:     100 processed in order: yes
stock:      40000 and 80000
OK

See also

• Semaphore, Semaphore_s, SemaphoreLock, SpinSemaphoreLock, CriticalSection, CriticalSection_s, CriticalSectionLock, SpinCriticalSectionLock
• Suspending and resuming, Single-waiter variants, Lifetimes and sizing
• Events, Queues and stacks, Timeouts
• Samples: Producer/consumer