MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Operating Systems  Module 5 – Synchronisation: races, locks, semaphores and monitors

Semaphores: counting, binary and ordering

Dijkstra's P and V, the invariant every semaphore keeps, and how one semaphore locks a critical section, counts resources or orders two threads.

  • Intermediate
  • 20 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Clang 21.0.0 and GCC 16.2.0
  • By MySmartCoPilot
Free: P waits and V signals, and the value never goes below 0 · One semaphore, three jobs: a lock, a counter and an order · A semaphore has no owner, and macOS has only named ones · Practise: make threads print a word in order. With a pass: 3 in-depth parts and 3 interview answers, about 13 minutes.

What you will learn

  • Define P and V and the invariant that every semaphore keeps
  • Use semaphores for mutual exclusion, resource counting and ordering between threads
  • Solve GATE-style questions on semaphore values and possible outputs
  • Use named POSIX semaphores portably, given that macOS rejects sem_init

Before you start

What you’ll learn · Before you start

What you will learn

  • Define P and V and the invariant that every semaphore keeps
  • Use semaphores for mutual exclusion, resource counting and ordering between threads
  • Solve GATE-style questions on semaphore values and possible outputs
  • Use named POSIX semaphores portably, given that macOS rejects sem_init

Before you start

On this page

Three threads that each print their letter twice can print AABBCC in 90 different orders; one semaphore around each thread’s two prints allows 6 of them when it starts at 1, and 54 when it starts at 2. A semaphore, which Dijkstra described in EWD 123, is a counter that a thread lowers with P, waiting while it is 0, and raises with V. A mutex lets one thread at a time into a critical section, and only its owner may release it; a semaphore is more general. With different starting values the same counter locks a critical section, counts free resources or makes one thread wait for another, and any thread may run either operation.

P waits and V signals, and the value never goes below 0

A semaphore: A counter that never goes below 0, changed by two indivisible operations: P waits until it is above 0 and lowers it by 1, and V raises it by 1. holds a whole number that never goes below 0. P waits until the value is above 0 and then lowers it by 1, as one indivisible step; V raises it by 1, which lets a waiting P complete. POSIX calls them sem_wait and sem_post. Since every completed P takes 1 and every V gives 1, a semaphore always keeps its semaphore invariant: The rule every semaphore keeps: its value equals the starting value plus the V operations minus the completed P operations, and is never below 0., where s₀ is the starting value and only completed P operations count:

s=s0+#V−#Pcompleted≥0s = s_0 + \#V - \#P_{\text{completed}} \geq 0

Step through two threads that use a semaphore that starts at 1 as a lock:

Interactive · message by message P and V on a semaphore that starts at 1 Step through two threads taking turns with one semaphore, and check at each step that the value equals 1 plus the V operations minus the completed P operations.
P and V on a semaphore that starts at 1, step 4 of 4. Messages so far: Thread A to Semaphore: P: 1 to 0; Thread B to Semaphore: P: waits; Thread A to Semaphore: V: wakes B; Thread B to Semaphore: V: 0 to 1.Thread AdoneSemaphorevalue 1, nobody waitsThread BdoneP: 1 to 0P: waitsV: wakes BV: 0 to 1

The drawing shows the whole scene; its 4 steps are listed below.

Every step as text
  1. A passes P. A's P finds the value 1, above 0, so it takes 1 and goes on. One P has completed and no V has run, so the value is 1 + 0 - 1 = 0.
  2. B waits at P. B's P finds 0, so it does not complete and B waits. The value stays 0; a waiting P is not counted.
  3. A's V lets B go. A leaves and runs V. The value becomes 1, and B's waiting P can now complete, taking it back to 0. One V and two completed P operations give 1 + 1 - 2 = 0.
  4. B's V. B leaves and runs V. Two V and two completed P operations give 1 + 2 - 2 = 1, the value the semaphore started with.

Checkpoint

Check: P, V and the semaphore invariant

  1. Question 1 of 2 A semaphore starts at 3. Four V operations and five P operations have completed. What is its value?

    Type a number.

    Show the answer

    Answer: 2

    The invariant gives 3 + 4 − 5 = 2.

  2. Question 2 of 2 A thread runs P on a semaphore whose value is 0. What happens?

    Choose one answer.

    Show the answer

    Answer: It waits until another thread's V raises the value, then lowers it to 0 again and goes on

    In the scene, B's P waited at 0 until A's V.

One semaphore, three jobs: a lock, a counter and an order

The starting value decides the job:

  • A lock starts at 1: P before the critical section and V after it, so one thread at a time is inside. This is a binary semaphore: A semaphore that starts at 1 and is used in P and V pairs, so that one thread at a time passes; unlike a mutex it has no owner..
  • A counter of resources starts at N, the number of free connections for example: P takes one, V gives it back, and at most N threads hold one at once. This is a counting semaphore: A semaphore that starts at N, the number of identical resources, so that at most N threads hold one at a time..
  • An order starts at 0: thread A runs V after its step and thread B runs P before its own, so B’s step always comes after A’s.

The program below runs three small semaphore programs in every possible order of their steps and prints what each can output. In the second and third, three threads each print their letter twice between P and V:

One program · 14 languages Every output of three semaphore programs

Python 3.14 · main.py

PAIRS = [f"P m; print {x}; print {x}; V m" for x in "ABC"]
PROGRAMS = [
    ("a signal from A to B", "s=0", ["print A; V s", "P s; print B", "print C"]),
    ("a binary semaphore", "m=1", PAIRS),
    ("a counting semaphore of 2", "m=2", PAIRS),
]


def explore(
    threads: list[list[list[str]]],
    pcs: list[int],
    sems: dict[str, int],
    out: str,
    outputs: set[str],
) -> None:
    moved = False
    for t, steps in enumerate(threads):
        if pcs[t] == len(steps):
            continue
        op, arg = steps[pcs[t]]
        if op == "P" and sems[arg] == 0:
            continue  # P waits while the semaphore is 0
        new_sems = dict(sems)
        if op != "print":
            new_sems[arg] += 1 if op == "V" else -1
        new_pcs = pcs.copy()
        new_pcs[t] += 1
        printed = arg if op == "print" else ""
        explore(threads, new_pcs, new_sems, out + printed, outputs)
        moved = True
    if not moved:
        outputs.add(out)


for name, start, code in PROGRAMS:
    sems = {k: int(v) for k, v in (pair.split("=") for pair in start.split())}
    threads = [[step.split() for step in text.split("; ")] for text in code]
    outputs: set[str] = set()
    explore(threads, [0] * len(threads), sems, "", outputs)
    first = " ".join(sorted(outputs)[:3])
    print(f"{name}: {len(outputs)} outputs are possible, such as {first}")

In Python: P waits by not being chosen: a thread whose next step is a P on a semaphore at 0 is skipped until a V raises it.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const PAIRS = ["A", "B", "C"].map((x) => `P m; print ${x}; print ${x}; V m`);
const PROGRAMS = [
  ["a signal from A to B", "s=0", ["print A; V s", "P s; print B", "print C"]],
  ["a binary semaphore", "m=1", PAIRS],
  ["a counting semaphore of 2", "m=2", PAIRS],
];

function explore(threads, pcs, sems, out, outputs) {
  let moved = false;
  threads.forEach((steps, t) => {
    if (pcs[t] === steps.length) return;
    const [op, arg] = steps[pcs[t]];
    if (op === "P" && sems[arg] === 0) return; // P waits while the semaphore is 0
    const newSems = { ...sems };
    if (op !== "print") newSems[arg] += op === "V" ? 1 : -1;
    const newPcs = [...pcs];
    newPcs[t]++;
    explore(threads, newPcs, newSems, out + (op === "print" ? arg : ""), outputs);
    moved = true;
  });
  if (!moved) outputs.add(out);
}

for (const [name, start, code] of PROGRAMS) {
  const sems = Object.fromEntries(start.split(" ").map((pair) => pair.split("=")));
  for (const k in sems) sems[k] = Number(sems[k]);
  const threads = code.map((text) => text.split("; ").map((step) => step.split(" ")));
  const outputs = new Set();
  explore(threads, Array(threads.length).fill(0), sems, "", outputs);
  const first = [...outputs].sort().slice(0, 3).join(" ");
  console.log(`${name}: ${outputs.size} outputs are possible, such as ${first}`);
}

In JavaScript: The semaphores are a plain object copied with spread syntax for each branch, and a Set keeps each output once.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Main {
  static final String[] PAIRS = {
    "P m; print A; print A; V m", "P m; print B; print B; V m", "P m; print C; print C; V m"
  };
  static final String[] NAMES = {
    "a signal from A to B", "a binary semaphore", "a counting semaphore of 2"
  };
  static final String[] STARTS = {"s=0", "m=1", "m=2"};
  static final String[][] CODES = {{"print A; V s", "P s; print B", "print C"}, PAIRS, PAIRS};

  static void explore(
      String[][][] threads, int[] pcs, Map<String, Integer> sems, String out, Set<String> outputs) {
    boolean moved = false;
    for (int t = 0; t < threads.length; t++) {
      if (pcs[t] == threads[t].length) continue;
      String op = threads[t][pcs[t]][0], arg = threads[t][pcs[t]][1];
      if (op.equals("P") && sems.get(arg) == 0) continue; // P waits while the semaphore is 0
      Map<String, Integer> newSems = new HashMap<>(sems);
      if (!op.equals("print")) newSems.merge(arg, op.equals("V") ? 1 : -1, Integer::sum);
      int[] newPcs = pcs.clone();
      newPcs[t]++;
      explore(threads, newPcs, newSems, out + (op.equals("print") ? arg : ""), outputs);
      moved = true;
    }
    if (!moved) outputs.add(out);
  }

  public static void main(String[] args) {
    for (int p = 0; p < NAMES.length; p++) {
      Map<String, Integer> sems = new HashMap<>();
      for (String pair : STARTS[p].split(" ")) {
        sems.put(pair.split("=")[0], Integer.parseInt(pair.split("=")[1]));
      }
      String[][][] threads = new String[CODES[p].length][][];
      for (int t = 0; t < threads.length; t++) {
        threads[t] =
            Arrays.stream(CODES[p][t].split("; ")).map(s -> s.split(" ")).toArray(String[][]::new);
      }
      TreeSet<String> outputs = new TreeSet<>();
      explore(threads, new int[threads.length], sems, "", outputs);
      String first = String.join(" ", outputs.stream().limit(3).toList());
      System.out.println(
          NAMES[p] + ": " + outputs.size() + " outputs are possible, such as " + first);
    }
  }
}

In Java: A TreeSet keeps the outputs sorted, and Map.merge adds 1 or -1 to a semaphore in the copied map.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <array>
#include <map>
#include <print>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using Thread = std::vector<std::array<std::string, 2>>; // {operation, argument}
struct Program {
  std::string name, start;
  std::vector<std::string> code;
};

const std::vector<std::string> kPairs{"P m; print A; print A; V m",
                                      "P m; print B; print B; V m",
                                      "P m; print C; print C; V m"};
const Program kPrograms[]{{"a signal from A to B",
                           "s=0",
                           {"print A; V s", "P s; print B", "print C"}},
                          {"a binary semaphore", "m=1", kPairs},
                          {"a counting semaphore of 2", "m=2", kPairs}};

void explore(const std::vector<Thread> &threads, std::vector<int> pcs,
             std::map<std::string, int> sems, const std::string &out,
             std::set<std::string> &outputs) {
  bool moved = false;
  for (size_t t = 0; t < threads.size(); t++) {
    if (pcs[t] == std::ssize(threads[t]))
      continue;
    const auto &[op, arg] = threads[t][pcs[t]];
    if (op == "P" && sems[arg] == 0)
      continue; // P waits while the semaphore is 0
    auto new_sems = sems;
    if (op != "print")
      new_sems[arg] += op == "V" ? 1 : -1;
    auto new_pcs = pcs;
    new_pcs[t]++;
    explore(threads, new_pcs, new_sems, out + (op == "print" ? arg : ""),
            outputs);
    moved = true;
  }
  if (!moved)
    outputs.insert(out);
}

int main() {
  for (const auto &[name, start, code] : kPrograms) {
    std::map<std::string, int> sems{
        {start.substr(0, 1), std::stoi(start.substr(2))}};
    std::vector<Thread> threads;
    for (const auto &text : code) {
      std::istringstream steps(text);
      Thread &thread = threads.emplace_back();
      for (std::string step; std::getline(steps, step, ';');)
        std::istringstream(step) >> thread.emplace_back()[0] >>
            thread.back()[1];
    }
    std::set<std::string> outputs;
    explore(threads, std::vector<int>(threads.size()), sems, "", outputs);
    auto it = outputs.begin();
    std::println("{}: {} outputs are possible, such as {} {} {}", name,
                 outputs.size(), *it, *std::next(it), *std::next(it, 2));
  }
}

In C++: std::set keeps the outputs sorted and unique; the vectors and the map are passed by value, so each branch has its own copy.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

string[] pairs =
[
    "P m; print A; print A; V m", "P m; print B; print B; V m", "P m; print C; print C; V m",
];
(string Name, string Start, string[] Code)[] programs =
[
    ("a signal from A to B", "s=0", ["print A; V s", "P s; print B", "print C"]),
    ("a binary semaphore", "m=1", pairs),
    ("a counting semaphore of 2", "m=2", pairs),
];

foreach (var (name, start, code) in programs)
{
    var sems = start.Split(' ').Select(p => p.Split('='))
        .ToDictionary(p => p[0], p => int.Parse(p[1]));
    var threads = code.Select(text => text.Split("; ").Select(s => s.Split(' ')).ToArray())
        .ToArray();
    var outputs = new SortedSet<string>(StringComparer.Ordinal);
    Explore(threads, new int[threads.Length], sems, "", outputs);
    var first = string.Join(" ", outputs.Take(3));
    Console.WriteLine($"{name}: {outputs.Count} outputs are possible, such as {first}");
}

static void Explore(
    string[][][] threads, int[] pcs, Dictionary<string, int> sems, string text,
    ISet<string> outputs)
{
    bool moved = false;
    for (int t = 0; t < threads.Length; t++)
    {
        if (pcs[t] == threads[t].Length)
        {
            continue;
        }
        var (op, arg) = (threads[t][pcs[t]][0], threads[t][pcs[t]][1]);
        if (op == "P" && sems[arg] == 0)
        {
            continue; // P waits while the semaphore is 0
        }
        var newSems = new Dictionary<string, int>(sems);
        if (op != "print")
        {
            newSems[arg] += op == "V" ? 1 : -1;
        }
        int[] newPcs = (int[])pcs.Clone();
        newPcs[t]++;
        Explore(threads, newPcs, newSems, text + (op == "print" ? arg : ""), outputs);
        moved = true;
    }
    if (!moved)
    {
        outputs.Add(text);
    }
}

In C#: A SortedSet with ordinal comparison keeps the outputs in the same order as the other languages.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static const char *const PAIRS[] = {"P m; print A; print A; V m",
                                    "P m; print B; print B; V m",
                                    "P m; print C; print C; V m"};
static const char *const SIGNAL[] = {"print A; V s", "P s; print B", "print C"};
static const struct {
  const char *name, *start, *const *code;
} PROGRAMS[] = {{"a signal from A to B", "s=0", SIGNAL},
                {"a binary semaphore", "m=1", PAIRS},
                {"a counting semaphore of 2", "m=2", PAIRS}};

static char steps[3][4][2][8]; // [thread][step]: the operation and its argument
static int lengths[3];
static char outputs[128][8];
static int found;

static void explore(int *pcs, int *sems, const char *out) {
  bool moved = false;
  for (int t = 0; t < 3; t++) {
    if (pcs[t] == lengths[t])
      continue;
    const char *op = steps[t][pcs[t]][0], *arg = steps[t][pcs[t]][1];
    if (*op == 'P' && sems[*arg - 'a'] == 0)
      continue; // P waits while the semaphore is 0
    int new_sems[26], new_pcs[3] = {pcs[0], pcs[1], pcs[2]};
    memcpy(new_sems, sems, sizeof new_sems);
    if (*op != 'p') // P or V; print starts with a lower-case p
      new_sems[*arg - 'a'] += *op == 'V' ? 1 : -1;
    new_pcs[t]++;
    char longer[8];
    snprintf(longer, sizeof longer, "%s%s", out, *op == 'p' ? arg : "");
    explore(new_pcs, new_sems, longer);
    moved = true;
  }
  bool seen = false; // keep each output once
  for (int i = 0; i < found && !moved; i++)
    seen = seen || strcmp(outputs[i], out) == 0;
  if (!moved && !seen)
    strcpy(outputs[found++], out);
}

static int by_text(const void *a, const void *b) { return strcmp(a, b); }

int main(void) {
  for (int p = 0; p < 3; p++) {
    int sems[26] = {0}, pcs[3] = {0};
    sems[PROGRAMS[p].start[0] - 'a'] = atoi(PROGRAMS[p].start + 2);
    for (int t = 0; t < 3; t++) {
      char text[64], *step = strtok(strcpy(text, PROGRAMS[p].code[t]), ";");
      for (lengths[t] = 0; step; step = strtok(NULL, ";"), lengths[t]++)
        sscanf(step, "%7s %7s", steps[t][lengths[t]][0],
               steps[t][lengths[t]][1]);
    }
    found = 0;
    explore(pcs, sems, "");
    qsort(outputs, found, sizeof outputs[0], by_text);
    printf("%s: %d outputs are possible, such as %s %s %s\n", PROGRAMS[p].name,
           found, outputs[0], outputs[1], outputs[2]);
  }
}

In C: Semaphores are an array indexed by their one-letter names, and qsort orders the outputs at the end.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const PAIRS = [
    'P m; print A; print A; V m',
    'P m; print B; print B; V m',
    'P m; print C; print C; V m',
];
const PROGRAMS = [
    ['a signal from A to B', 's=0', ['print A; V s', 'P s; print B', 'print C']],
    ['a binary semaphore', 'm=1', PAIRS],
    ['a counting semaphore of 2', 'm=2', PAIRS],
];

/**
 * @param list<list<list<string>>> $threads
 * @param list<int> $pcs
 * @param array<string, int> $sems
 * @param array<string, true> $outputs
 */
function explore(array $threads, array $pcs, array $sems, string $out, array &$outputs): void
{
    $moved = false;
    foreach ($threads as $t => $steps) {
        if ($pcs[$t] === count($steps)) {
            continue;
        }
        [$op, $arg] = $steps[$pcs[$t]];
        if ($op === 'P' && $sems[$arg] === 0) {
            continue; // P waits while the semaphore is 0
        }
        $newSems = $sems;
        if ($op !== 'print') {
            $newSems[$arg] += $op === 'V' ? 1 : -1;
        }
        $newPcs = $pcs;
        $newPcs[$t]++;
        explore($threads, $newPcs, $newSems, $out . ($op === 'print' ? $arg : ''), $outputs);
        $moved = true;
    }
    if (!$moved) {
        $outputs[$out] = true;
    }
}

foreach (PROGRAMS as [$name, $start, $code]) {
    [$sem, $value] = explode('=', $start);
    $threads = [];
    foreach ($code as $text) {
        $threads[] = array_map(fn(string $s): array => explode(' ', $s), explode('; ', $text));
    }
    $outputs = [];
    explore($threads, array_fill(0, count($threads), 0), [$sem => (int) $value], '', $outputs);
    ksort($outputs, SORT_STRING);
    $first = implode(' ', array_slice(array_keys($outputs), 0, 3));
    $count = count($outputs);
    echo "$name: $count outputs are possible, such as $first\n";
}

In PHP: The outputs are the keys of an array, which keeps each one once; ksort with SORT_STRING orders them.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

use std::collections::{BTreeSet, HashMap};

const PAIRS: [&str; 3] = [
    "P m; print A; print A; V m",
    "P m; print B; print B; V m",
    "P m; print C; print C; V m",
];
const SIGNAL: [&str; 3] = ["print A; V s", "P s; print B", "print C"];

type Thread<'a> = Vec<(&'a str, &'a str)>;

/// Turns "P s; print B" into [("P", "s"), ("print", "B")].
fn steps(text: &str) -> Thread<'_> {
    text.split("; ").filter_map(|s| s.split_once(' ')).collect()
}

fn explore(
    threads: &[Thread],
    pcs: Vec<usize>,
    sems: HashMap<&str, i32>,
    out: String,
    outputs: &mut BTreeSet<String>,
) {
    let mut moved = false;
    for (t, steps) in threads.iter().enumerate() {
        if pcs[t] == steps.len() {
            continue;
        }
        let (op, arg) = steps[pcs[t]];
        if op == "P" && sems[arg] == 0 {
            continue; // P waits while the semaphore is 0
        }
        let mut new_sems = sems.clone();
        if op != "print" {
            *new_sems.get_mut(arg).unwrap() += if op == "V" { 1 } else { -1 };
        }
        let mut new_pcs = pcs.clone();
        new_pcs[t] += 1;
        let printed = if op == "print" { arg } else { "" };
        explore(threads, new_pcs, new_sems, out.clone() + printed, outputs);
        moved = true;
    }
    if !moved {
        outputs.insert(out);
    }
}

fn main() {
    let programs = [
        ("a signal from A to B", "s=0", SIGNAL),
        ("a binary semaphore", "m=1", PAIRS),
        ("a counting semaphore of 2", "m=2", PAIRS),
    ];
    for (name, start, code) in programs {
        let (sem, value) = start.split_once('=').unwrap();
        let sems = HashMap::from([(sem, value.parse().unwrap())]);
        let threads: Vec<Thread> = code.iter().map(|text| steps(text)).collect();
        let mut outputs = BTreeSet::new();
        let zeros = vec![0; threads.len()];
        explore(&threads, zeros, sems, String::new(), &mut outputs);
        let first: Vec<_> = outputs.iter().take(3).map(String::as_str).collect();
        let (n, first) = (outputs.len(), first.join(" "));
        println!("{name}: {n} outputs are possible, such as {first}");
    }
}

In Rust: A BTreeSet keeps the outputs sorted, and each step is a pair of string slices borrowed from the program text.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

const PAIRS = ["A", "B", "C"].map((x) => `P m; print ${x}; print ${x}; V m`);
const PROGRAMS: [string, string, string[]][] = [
  ["a signal from A to B", "s=0", ["print A; V s", "P s; print B", "print C"]],
  ["a binary semaphore", "m=1", PAIRS],
  ["a counting semaphore of 2", "m=2", PAIRS],
];

type Sems = Record<string, number>;

function explore(
  threads: string[][][],
  pcs: number[],
  sems: Sems,
  out: string,
  outputs: Set<string>,
) {
  let moved = false;
  threads.forEach((steps, t) => {
    if (pcs[t] === steps.length) return;
    const [op, arg] = steps[pcs[t]];
    if (op === "P" && sems[arg] === 0) return; // P waits while the semaphore is 0
    const newSems = { ...sems };
    if (op !== "print") newSems[arg] += op === "V" ? 1 : -1;
    const newPcs = [...pcs];
    newPcs[t]++;
    explore(threads, newPcs, newSems, out + (op === "print" ? arg : ""), outputs);
    moved = true;
  });
  if (!moved) outputs.add(out);
}

for (const [name, start, code] of PROGRAMS) {
  const sems: Sems = {};
  for (const [k, v] of start.split(" ").map((pair) => pair.split("="))) sems[k] = Number(v);
  const threads = code.map((text) => text.split("; ").map((step) => step.split(" ")));
  const outputs = new Set<string>();
  explore(threads, Array(threads.length).fill(0), sems, "", outputs);
  const first = [...outputs].sort().slice(0, 3).join(" ");
  console.log(`${name}: ${outputs.size} outputs are possible, such as ${first}`);
}

In TypeScript: A Record type holds the semaphores; otherwise the program is the JavaScript one.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"maps"
	"slices"
	"strconv"
	"strings"
)

var pairs = []string{
	"P m; print A; print A; V m", "P m; print B; print B; V m", "P m; print C; print C; V m",
}

var programs = []struct {
	name, start string
	code        []string
}{
	{"a signal from A to B", "s=0", []string{"print A; V s", "P s; print B", "print C"}},
	{"a binary semaphore", "m=1", pairs},
	{"a counting semaphore of 2", "m=2", pairs},
}

func explore(threads [][][]string, pcs []int, sems map[string]int, out string,
	seen map[string]bool) {
	moved := false
	for t, steps := range threads {
		if pcs[t] == len(steps) {
			continue
		}
		op, arg := steps[pcs[t]][0], steps[pcs[t]][1]
		if op == "P" && sems[arg] == 0 {
			continue // P waits while the semaphore is 0
		}
		newSems, newPcs, printed := maps.Clone(sems), slices.Clone(pcs), ""
		switch op {
		case "P":
			newSems[arg]--
		case "V":
			newSems[arg]++
		default:
			printed = arg
		}
		newPcs[t]++
		explore(threads, newPcs, newSems, out+printed, seen)
		moved = true
	}
	if !moved {
		seen[out] = true
	}
}

func main() {
	for _, p := range programs {
		name, value, _ := strings.Cut(p.start, "=")
		n, _ := strconv.Atoi(value)
		var threads [][][]string
		for _, text := range p.code {
			var steps [][]string
			for _, step := range strings.Split(text, "; ") {
				steps = append(steps, strings.Fields(step))
			}
			threads = append(threads, steps)
		}
		outputs := map[string]bool{}
		explore(threads, make([]int, len(threads)), map[string]int{name: n}, "", outputs)
		sorted := slices.Sorted(maps.Keys(outputs))
		fmt.Printf("%s: %d outputs are possible, such as %s\n",
			p.name, len(sorted), strings.Join(sorted[:3], " "))
	}
}

In Go: maps.Clone and slices.Clone copy the state for each branch, and slices.Sorted orders the keys of the output map.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let pairs = ["A", "B", "C"].map { "P m; print \($0); print \($0); V m" }
let programs = [
  ("a signal from A to B", "s=0", ["print A; V s", "P s; print B", "print C"]),
  ("a binary semaphore", "m=1", pairs),
  ("a counting semaphore of 2", "m=2", pairs),
]

func explore(
  _ threads: [[[String]]], _ pcs: [Int], _ sems: [String: Int], _ out: String,
  _ outputs: inout Set<String>
) {
  var moved = false
  for (t, steps) in threads.enumerated() where pcs[t] < steps.count {
    let (op, arg) = (steps[pcs[t]][0], steps[pcs[t]][1])
    if op == "P" && sems[arg] == 0 { continue }  // P waits while the semaphore is 0
    var newSems = sems
    if op != "print" { newSems[arg, default: 0] += op == "V" ? 1 : -1 }
    var newPcs = pcs
    newPcs[t] += 1
    explore(threads, newPcs, newSems, out + (op == "print" ? arg : ""), &outputs)
    moved = true
  }
  if !moved { outputs.insert(out) }
}

for (name, start, code) in programs {
  let pair = start.split(separator: "=").map(String.init)
  let threads = code.map { text in
    text.split(separator: ";").map { $0.split(separator: " ").map(String.init) }
  }
  var outputs = Set<String>()
  explore(
    threads, Array(repeating: 0, count: threads.count), [pair[0]: Int(pair[1]) ?? 0], "", &outputs)
  let first = outputs.sorted().prefix(3).joined(separator: " ")
  print("\(name): \(outputs.count) outputs are possible, such as \(first)")
}

In Swift: A Set collects the outputs, and the dictionary subscript with a default adds 1 or -1 to a semaphore.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

PAIRS = %w[A B C].map { |x| "P m; print #{x}; print #{x}; V m" }
PROGRAMS = [
  ['a signal from A to B', 's=0', ['print A; V s', 'P s; print B', 'print C']],
  ['a binary semaphore', 'm=1', PAIRS],
  ['a counting semaphore of 2', 'm=2', PAIRS]
].freeze

# The semaphores after a step: P takes 1, V gives 1 back, print leaves them alone.
def after(sems, step)
  op, arg = step
  return sems if op == 'print'

  sems.merge(arg => sems[arg] + (op == 'V' ? 1 : -1))
end

# A thread can move unless it has finished or its next step is a P on a semaphore at 0.
def movable?(steps, pos, sems)
  pos < steps.size && !(steps[pos][0] == 'P' && sems[steps[pos][1]].zero?)
end

# The positions of the threads after one of them takes a step.
def advance(pcs, thread)
  pcs.each_with_index.map { |pc, i| i == thread ? pc + 1 : pc }
end

# What a step prints: its letter for print, nothing for P and V.
def printed(step)
  step[0] == 'print' ? step[1] : ''
end

# Adds the output of every schedule from this point on to outputs.
def explore(threads, pcs, sems, out, outputs)
  runnable = threads.each_index.select { |t| movable?(threads[t], pcs[t], sems) }
  outputs << out if runnable.empty?
  runnable.each do |t|
    step = threads[t][pcs[t]]
    explore(threads, advance(pcs, t), after(sems, step), out + printed(step), outputs)
  end
end

PROGRAMS.each do |name, start, code|
  sem, value = start.split('=')
  threads = code.map { |text| text.split('; ').map(&:split) }
  outputs = Set.new
  explore(threads, [0] * threads.size, { sem => value.to_i }, '', outputs)
  puts "#{name}: #{outputs.size} outputs are possible, such as #{outputs.sort.first(3).join(' ')}"
end

In Ruby: Small methods compute the next semaphores and positions, and a Set keeps each output once.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

val pairs = listOf("A", "B", "C").map { "P m; print $it; print $it; V m" }
val programs =
    listOf(
        Triple("a signal from A to B", "s=0", listOf("print A; V s", "P s; print B", "print C")),
        Triple("a binary semaphore", "m=1", pairs),
        Triple("a counting semaphore of 2", "m=2", pairs),
    )

fun explore(
    threads: List<List<List<String>>>,
    pcs: IntArray,
    sems: Map<String, Int>,
    out: String,
    outputs: MutableSet<String>,
) {
    var moved = false
    for ((t, steps) in threads.withIndex()) {
        if (pcs[t] == steps.size) continue
        val (op, arg) = steps[pcs[t]]
        if (op == "P" && sems[arg] == 0) continue // P waits while the semaphore is 0
        val newSems = sems.toMutableMap()
        if (op != "print") newSems[arg] = sems.getValue(arg) + if (op == "V") 1 else -1
        val newPcs = pcs.copyOf()
        newPcs[t]++
        explore(threads, newPcs, newSems, out + if (op == "print") arg else "", outputs)
        moved = true
    }
    if (!moved) outputs.add(out)
}

fun main() {
    for ((name, start, code) in programs) {
        val (sem, value) = start.split("=")
        val threads = code.map { text -> text.split("; ").map { it.split(" ") } }
        val outputs = mutableSetOf<String>()
        explore(threads, IntArray(threads.size), mapOf(sem to value.toInt()), "", outputs)
        val first = outputs.sorted().take(3).joinToString(" ")
        println("$name: ${outputs.size} outputs are possible, such as $first")
    }
}

In Kotlin: A mutable set collects the outputs, sorted() orders them at the end, and toMutableMap copies the semaphores for each branch.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const pairs = [
  'P m; print A; print A; V m',
  'P m; print B; print B; V m',
  'P m; print C; print C; V m',
];
const programs = [
  ('a signal from A to B', 's=0', ['print A; V s', 'P s; print B', 'print C']),
  ('a binary semaphore', 'm=1', pairs),
  ('a counting semaphore of 2', 'm=2', pairs),
];

void explore(
  List<List<List<String>>> threads,
  List<int> pcs,
  Map<String, int> sems,
  String out,
  Set<String> outputs,
) {
  var moved = false;
  for (var t = 0; t < threads.length; t++) {
    if (pcs[t] == threads[t].length) continue;
    final [op, arg] = threads[t][pcs[t]];
    // P waits while the semaphore is 0
    if (op == 'P' && sems[arg] == 0) continue;
    final newSems = {...sems};
    if (op != 'print') newSems[arg] = sems[arg]! + (op == 'V' ? 1 : -1);
    final newPcs = [...pcs];
    newPcs[t]++;
    final printed = op == 'print' ? arg : '';
    explore(threads, newPcs, newSems, out + printed, outputs);
    moved = true;
  }
  if (!moved) outputs.add(out);
}

void main() {
  for (final (name, start, code) in programs) {
    final [sem, value] = start.split('=');
    final threads = [
      for (final text in code) [for (final s in text.split('; ')) s.split(' ')],
    ];
    final outputs = <String>{};
    final pcs = List.filled(threads.length, 0);
    explore(threads, pcs, {sem: int.parse(value)}, '', outputs);
    final first = (outputs.toList()..sort()).take(3).join(' ');
    print('$name: ${outputs.length} outputs are possible, such as $first');
  }
}

In Dart: List patterns take each step apart, as in final [op, arg] = step.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

a signal from A to B: 3 outputs are possible, such as ABC ACB CAB
a binary semaphore: 6 outputs are possible, such as AABBCC AACCBB BBAACC
a counting semaphore of 2: 54 outputs are possible, such as AABBCC AABCBC AABCCB

The signal leaves 3 outputs, all with A before B. The binary semaphore keeps each pair together, so only the 6 orders of the three pairs remain. The counting semaphore of 2 lets two pairs interleave but never three: of the 90 ways to order AABBCC it rules out the 36 that begin with A, B and C in some order, which leaves 54.

Checkpoint

Check: A semaphore as a lock, a counter and an order

  1. Question 1 of 2 Thread B must not start step 2 until thread A has finished step 1. What starting value and steps do that?

    Choose one answer.

    Show the answer

    Answer: Start at 0; A runs V after step 1, and B runs P before step 2

    This is the signal of the first program in the block: A before B in all 3 outputs.

  2. Question 2 of 2 Why does the counting semaphore of 2 rule out exactly the outputs that begin with A, B and C in some order?

    Choose one answer.

    Show the answer

    Answer: Those are the only outputs in which three threads are between their two prints at once

    90 orders of AABBCC minus the 6 × 6 = 36 that begin with three different letters leaves 54.

A semaphore has no owner, and macOS has only named ones

Unlike a mutex, a semaphore records no owner, and any thread may run V. That makes it the tool for signalling, and risky as a lock: a stray V from the wrong thread lets a second thread into the critical section without any error. A mutex, which knows its owner, can report that mistake; a semaphore cannot.

POSIX has two kinds. An unnamed semaphore lives in memory that the threads or processes share and is set up with sem_init; a named semaphore: A POSIX semaphore opened by a name such as /order with sem_open, so that unrelated threads or processes can share it; it lasts until sem_unlink removes the name., with a name such as /order, is opened with sem_open and removed with sem_unlink. macOS marks sem_init as deprecated, and on this Mac it fails with ENOSYS, while named semaphores work:

sem_probe.c: sem_init refused, and a named semaphore that orders two threads C · posix/sem_probe.c 
// macOS rejects unnamed POSIX semaphores and accepts named ones, which also work
// between threads: here a named semaphore makes thread B wait for thread A.
#include <errno.h>
#include <fcntl.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>

// sem_init is deprecated on macOS; the pragma lets this program call it anyway.
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"

static sem_t *ready;

static void *second(void *arg) {
  (void)arg;
  sem_wait(ready); // P: waits until A has posted
  puts("B: after A, in every run");
  return NULL;
}

int main(void) {
  sem_t unnamed;
  if (sem_init(&unnamed, 0, 0) == -1)
    printf("sem_init: %s\n", strerror(errno));

  char name[32];
  snprintf(name, sizeof name, "/order-%d", (int)getpid());
  ready = sem_open(name, O_CREAT | O_EXCL, 0600, 0);
  if (ready == SEM_FAILED) {
    printf("sem_open: %s\n", strerror(errno));
    return 1;
  }
  sem_unlink(name); // the name goes now; the semaphore lives until it is closed
  puts("sem_open: a named semaphore, value 0");

  pthread_t b;
  pthread_create(&b, NULL, second, NULL);
  puts("A: first");
  sem_post(ready); // V: lets B go on
  pthread_join(b, NULL);
  sem_close(ready);
  return 0;
}

Output

sem_init: Function not implemented
sem_open: a named semaphore, value 0
A: first
B: after A, in every run

Recorded with Apple clang version 21.0.0 (clang-2100.3.34.2) on macOS 26 arm64. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined sem_probe.c -o sem_probe && ./sem_probe

Code that must run on macOS as well as Linux therefore uses named semaphores, or the platform’s own, such as Apple’s dispatch semaphores.

Checkpoint

Check: Semaphores without owners, and POSIX semaphores on macOS

  1. Question 1 of 2 A binary semaphore guards a critical section, and a bug runs one extra V on an error path. What can happen?

    Choose one answer.

    Show the answer

    Answer: Two threads can be inside at once, and nothing reports the mistake

    An error-checking mutex would have returned EPERM to the thread that did not own it.

  2. Question 2 of 2 What did sem_init return on this lesson's Mac?

    Choose one answer.

    Show the answer

    Answer: -1 with ENOSYS, function not implemented

    Named semaphores, opened with sem_open, worked in the same program.

Practise: make threads print a word in order

The exercise uses the program’s notation. Write a function that, for any word, gives the starting values and the steps of one thread per letter so that every schedule prints the word:

Exercise · Easy · Python

Make threads print a word in order with semaphores

Each thread prints one letter of a word, and the scheduler may run their steps in any order. A step is a string: "P s" waits until semaphore s is above 0 and takes 1 from it, "V s" adds 1 to it, and "print X" prints the letter X.

Write chain(word). It returns two things: a dictionary with the starting value of each semaphore you use, and a list with one thread's steps for each letter of the word, in order. Thread 1 prints the first letter, thread 2 the second, and so on. In every possible schedule the output must be the word, with no thread left waiting for ever, and you may use at most one semaphore fewer than the word has letters. The tests try every schedule.

Starter code · order.py 

def chain(word):
    """Returns the semaphores' starting values and one thread's steps for each letter of word."""
    start = {}  # for example {"s1": 0}
    threads = [[f"print {letter}"] for letter in word]
    return start, threads
The sample tests · test_order.py 
from order import chain


def run_all(start, threads):
    """Tries every schedule; returns the set of outputs and how many schedules got stuck."""
    outputs, stuck = set(), 0
    pending = [([0] * len(threads), dict(start), "")]
    while pending:
        pcs, sems, out = pending.pop()
        moves = []
        for t, steps in enumerate(threads):
            if pcs[t] < len(steps):
                op, arg = steps[pcs[t]].split()
                if op != "P" or sems[arg] > 0:
                    moves.append((t, op, arg))
        if not moves:
            if all(pcs[t] == len(steps) for t, steps in enumerate(threads)):
                outputs.add(out)
            else:
                stuck += 1
        for t, op, arg in moves:
            new_pcs, new_sems = pcs.copy(), dict(sems)
            new_pcs[t] += 1
            if op in ("P", "V"):
                new_sems[arg] += 1 if op == "V" else -1
            pending.append((new_pcs, new_sems, out + (arg if op == "print" else "")))
    return outputs, stuck


def test_three_letters_in_order():
    """prints ABC in every schedule, with no thread stuck"""
    assert run_all(*chain("ABC")) == ({"ABC"}, 0)


def test_four_letters_in_order():
    """prints DCBA in every schedule, with no thread stuck"""
    assert run_all(*chain("DCBA")) == ({"DCBA"}, 0)


def test_one_letter_needs_no_semaphore():
    """prints a single letter with no semaphore at all"""
    start, threads = chain("Q")
    assert start == {}
    assert run_all(start, threads) == ({"Q"}, 0)


def test_each_thread_prints_its_own_letter():
    """has thread i print the i-th letter, once"""
    _, threads = chain("MAP")
    for letter, steps in zip("MAP", threads):
        assert [s for s in steps if s.startswith("print")] == [f"print {letter}"]


def test_few_semaphores_and_only_started_ones():
    """uses at most one semaphore fewer than the letters, all of them started"""
    start, threads = chain("WXYZ")
    used = {s.split()[1] for steps in threads for s in steps if not s.startswith("print")}
    assert len(start) <= 3
    assert used <= set(start)
A hint

A semaphore that starts at 0 makes a thread wait at its P until another thread's V. Between each pair of neighbouring letters, put a V after the first thread's print and a P before the next thread's print, on a semaphore of their own.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Then work through the self-check below, which puts first the idea that your earlier answers suggest needs most work.

Practice that adapts to you

Practise this lesson

9 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 9 Which POSIX functions are P and V?

    Choose one answer.

    Show the answer

    Answer: sem_wait is P and sem_post is V

    POSIX names them for what they do; Dijkstra named them P and V.

  2. Question 2 of 9 Why does the invariant count only completed P operations?

    Choose one answer.

    Show the answer

    Answer: A P that waits has taken nothing yet, so it has not changed the value

    Dijkstra calls semaphores essentially non-negative integers, and POSIX's sem_wait never takes the value below 0.

  3. Question 3 of 9 A semaphore started at 2. Its value is now 1, and 6 V operations have run. How many P operations have completed?

    Type a number.

    Show the answer

    Answer: 7

    1 = 2 + 6 − P, so P = 7.

  4. Question 4 of 9 What starting value makes a semaphore a lock for a critical section?

    Choose one answer.

    Show the answer

    Answer: 1

    A semaphore that starts at 1 and is used in P and V pairs is a binary semaphore.

  5. Question 5 of 9 A pool has 5 connections. What starting value and use limit the threads that hold one at a time?

    Choose one answer.

    Show the answer

    Answer: Start at 5; P before taking a connection, V after giving it back

    The value is always the number of free connections.

  6. Question 6 of 9 In the block, three threads each print their letter twice under one binary semaphore. How many outputs are possible?

    Type a number.

    Show the answer

    Answer: 6

    The semaphore keeps each pair together, so the outputs are the 3! = 6 orders of AA, BB and CC.

  7. Question 7 of 9 Why is a semaphore, not a mutex, the tool for one thread to signal another?

    Choose one answer.

    Show the answer

    Answer: Any thread may run V, while only a mutex's owner may unlock it

    The ordering pattern of the second section relies on exactly that.

  8. Question 8 of 9 Code must run on macOS and Linux and use a POSIX semaphore between threads. Which kind works on both?

    Choose one answer.

    Show the answer

    Answer: A named semaphore opened with sem_open

    On Apple systems dispatch semaphores are the other choice.

  9. Question 9 of 9 What does a mutex give a lock that a binary semaphore cannot?

    Choose one answer.

    Show the answer

    Answer: An owner, so mistakes such as an unlock by another thread can be reported

    That is why the lesson uses mutexes for locks and semaphores for signals and counts.

GATE-style semaphore problems: final values, possible outputs and extreme values, worked Pro

Semaphore problems of the exam kind come in a few forms, and each has a method that settles it without guessing. This part works final values with the invariant, possible outputs with schedules and counting, and the largest and smallest value of a variable that threads update under a counting semaphore.

In this part:

  • Final values from the invariant
  • Possible outputs: show a schedule, or rule one out
  • The largest and smallest value of a shared variable

about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

POSIX semaphores in practice: between processes, their names, and what each platform offers Pro

A semaphore is most useful where a mutex cannot go: between processes, and between a thread that produces and one that waits. This part orders two processes with a named semaphore, covers the life of a semaphore’s name, and compares the semaphores each platform offers.

In this part:

  • A named semaphore between two processes
  • The life of a semaphore’s name
  • Unnamed semaphores in shared memory, and waiting without blocking
  • What each platform offers

1 runnable example (C) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Patterns built from semaphores, and the order that deadlocks them Pro

A few semaphore patterns cover most uses, and each has a version that deadlocks. This part builds a rendezvous and shows the order that breaks it, builds a barrier for N threads, and limits concurrency with a counting semaphore without leaking its permits.

In this part:

  • A rendezvous, and the order that deadlocks it
  • A barrier for N threads
  • Why a binary semaphore makes a poor mutex
  • A throttle that does not leak

1 diagram · about 4 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

The warm-up is answered in full here:

  1. Fresher to mid · Warm-up

    What is the difference between a binary semaphore and a mutex, and when do you use each?

    Both let one thread at a time past a point, but a mutex has an owner and a semaphore does not. Only the thread that locked a mutex may unlock it, so the system can report a foreign or double unlock, as an error-checking mutex does with EPERM, and can lend the owner a waiting thread's priority. A semaphore is a counter that any thread may raise with V, which makes it the tool for signalling between threads, such as "the data is ready", and for counting resources, such as free connections. Use a mutex to protect a critical section, and a semaphore when one thread must wait for another or when up to N threads may hold something at once.

Three harder questions follow: a semaphore lock that lets two threads in, a connection limit that slowly locks up, and a rendezvous that hangs. Decide where you would start on two of them; every choice says why it helps or not:

Checkpoint

Your first decision

  1. Question 1 of 2 A critical section guarded by a binary semaphore sometimes has two threads inside under load. What do you check first?

    Choose one answer.

    Show the answer

    Answer: Every V, for one that runs without a matching P, for example on an error path

    A mutex would turn the stray unlock into an error, which is a reason to use one for locking.

  2. Question 2 of 2 A service limits itself to 20 concurrent calls with a counting semaphore, and after days of uptime every call waits. What do you look at first?

    Choose one answer.

    Show the answer

    Answer: The paths that run P, for any that can leave without the matching V

    The value plus the permits in use must always equal the starting value; a leak breaks that.

  1. Mid to senior

    A cache is guarded by a semaphore that starts at 1, with sem_wait before each update and sem_post after it. Under load, two threads are sometimes inside at once and the cache is corrupted. How do you find the cause and fix it?

    First step and follow-ups

  2. Mid to senior

    A service limits itself to 20 concurrent calls to a payment provider with a counting semaphore. After several days every request hangs, although the provider is healthy. Explain the likely cause, how to confirm it and how to prevent it.

    First step and follow-ups

  3. Fresher to mid

    Two threads must both finish set-up before either starts work. Each waits on the other's semaphore, both starting at 0, and then posts its own. The program hangs every time. Explain why and fix it.

    First step and follow-ups

Key takeaways

  • P waits for a value above 0 and lowers it; V raises it; the value is always the start plus V operations minus completed P operations.
  • Start at 1 for a lock, at N for a counter of resources, and at 0 to make one thread wait for another.
  • A semaphore has no owner, which suits signalling and makes it risky as a lock.
  • On macOS use named semaphores or dispatch semaphores, since sem_init fails there.

Terms in this lesson

binary semaphore
A semaphore that starts at 1 and is used in P and V pairs, so that one thread at a time passes; unlike a mutex it has no owner.
counting semaphore
A semaphore that starts at N, the number of identical resources, so that at most N threads hold one at a time.
named semaphore
A POSIX semaphore opened by a name such as /order with sem_open, so that unrelated threads or processes can share it; it lasts until sem_unlink removes the name.
semaphore
A counter that never goes below 0, changed by two indivisible operations: P waits until it is above 0 and lowers it by 1, and V raises it by 1.
semaphore invariant
The rule every semaphore keeps: its value equals the starting value plus the V operations minus the completed P operations, and is never below 0.

References

Report a problem with this lesson