Mutual exclusion

related topics
{system, computer, user}
{math, number, function}
{theory, work, human}
{law, state, case}
{style, bgcolor, rowspan}

Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource. The critical section by itself is not a mechanism or algorithm for mutual exclusion. A program, process, or thread can have the critical section in it without any mechanism or algorithm which implements mutual exclusion.

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 synchronization of access to those resources is an acute problem because a thread can be stopped or started at any time.

To illustrate: suppose a section of code is altering 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, which is 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 shared data being accessed by critical sections of code, must therefore be protected, so that other processes which read from or write to the chunk of data are excluded from running.

A mutex is also a common name for a program object that negotiates mutual exclusion among threads, also called a lock.

Contents

Enforcing mutual exclusion

There are both software and hardware solutions for enforcing mutual exclusion. The different solutions are shown below.

Hardware solutions

On a uniprocessor system a common way to achieve mutual exclusion inside kernels is to disable interrupts for the smallest possible number of instructions that will prevent corruption of the shared data structure, the critical section. This prevents interrupt code from running in the critical section, that also protects against interrupt-based process-change.

In a computer in which several processors share memory, an indivisible test-and-set of a flag could be 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 section, it clears the flag. This is called a "spinlock" or "busy-wait".

Full article ▸

related documents
GW-BASIC
Core dump
Visual DialogScript
System analysis
Pentium FDIV bug
LZ77 and LZ78
Segmentation fault
Nautilus (file manager)
Remote procedure call
Application binary interface
Parasitic computing
HTTP 404
Abstract Window Toolkit
Allegro library
GTK+
Microsoft BASIC
QuickBASIC
Megabyte
Modifier key
ScriptBasic
PureBasic
XPCOM
Access control list
Wikipedia:Federal Standard 1037C terms/computer programming terms
Schematic
Source Mage GNU/Linux
ActiveX
IBM 1620 Model I
Monolithic kernel
Macro virus (computing)