What is a Mutex?
Mutual exclusion (often abbreviated to mutex) algorithms are
used in concurrent programming to avoid the simultaneous use of
un-shareable resources by pieces of computer code called critical
sections. Examples of such resources are fine-grained flags,
counters or queues, used to communicate between code that runs
concurrently, such as an application and its interrupt handlers.
The problem is acute because a thread can be stopped or started at
any time. To illustrate: suppose a section of code is mutating a
piece of data over several program steps, when another thread,
perhaps triggered by some unpredictable event, starts executing. If
this second thread reads from the same piece of data, the data, in
the process of being overwritten, is in an inconsistent and
unpredictable state. If the second thread tries overwriting that
data, the ensuing state will probably be unrecoverable. These
critical sections of code accessing shared data must therefore be
protected, so that other processes which read from or write to the
chunk of data are excluded from running. On a uniprocessor system
the common way to achieve mutual exclusion is to disable interrupts
for the smallest possible number of instructions that will prevent
corruption of the shared data structure, the so-called "critical
region". This prevents interrupt code from running in the critical
region. Beside this hardware supported solution, some software
solutions exist that use "busy-wait" to achieve the goal. Examples
of these algorithms include: * Dekker's algorithm * Peterson's
algorithm * Lamport's bakery algorithm In a computer in which
several processors share memory, an indivisible test-and-set of a
flag is used in a tight loop to wait until the other processor
clears the flag. The test-and-set performs both operations without
releasing the memory bus to another processor. When the code leaves
the critical region, it clears the flag. This is called a
"spinlock" or "busy-wait." Some computers have similar indivisible
multiple-operation instructions for manipulating the linked lists
used for event queues and other data structures commonly used in
operating systems. Most classical mutual exclusion methods attempt
to reduce latency and busy-waits by using queuing and context
switches. Some claim that benchmarks indicate that these special
algorithms waste more time than they save. Many forms of mutual
exclusion have side-effects. For example, classic semaphores permit
deadlocks, in which one process gets a semaphore, another process
gets a second semaphore, and then both wait forever for the other
semaphore to be released. Other common side-effects include
starvation, in which a process never gets sufficient resources to
run to completion, priority inversion in which a higher priority
thread waits for a lower-priority thread, and "high latency" in
which response to interrupts is not prompt. Much research is aimed
at eliminating the above effects, such as by guaranteeing
non-blocking progress. No perfect scheme is known.