Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Synchronization primitive
A **synchronization primitive** is a building block used to coordinate access to shared state between concurrent threads or processes, so that operations which must not interleave arbitrarily don't. Without one, two threads reading and writing the same data can produce a race condition: the final result depends on the unpredictable order in which their instructions happen to execute, rather than on the logic of the program.

Synchronization primitives split roughly into two roles. **Mutual exclusion** primitives ensure only one thread at a time executes a given piece of code or touches a given piece of data. **Communication/coordination** primitives let threads or processes signal each other and pass data, rather than just excluding each other. The two roles overlap in practice (many primitives do a bit of both), but it's a useful lens for telling them apart.

## Mutual exclusion

 - [[sync-mutex]] — the simplest mutual-exclusion lock: one owner at a time, and only the owner may release it.
 - [[sync-semaphore]] — a counting generalization of a mutex, allowing up to N holders and no fixed notion of ownership.
 - [[sync-monitor]] — a mutex bundled with condition variables, giving a structured way to wait for a condition while holding the lock.

## Communication and coordination

 - [[sync-csp]] — Communicating Sequential Processes: independent processes coordinate purely by sending messages over channels, with no shared memory at all.
 - [[sync-linda]] — Linda's tuple space model: processes coordinate by reading and writing tuples to a shared associative memory, rather than sending messages directly to each other.
 - [[sync-mbox]] — a mailbox: a bounded, addressed queue that one process delivers messages into and another consumes from.

## A common thread

Every primitive above is ultimately implemented on top of the same handful of hardware guarantees: an [[atomics|atomic]] read-modify-write instruction (compare-and-swap, test-and-set, or similar) plus a way to block a thread and later wake it (a futex on Linux, or the OS scheduler more generally). The primitives differ in the abstraction they present to the programmer, not in what the hardware underneath is doing.