|
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. Flowcharts are often used to graphically represent algorithms. ...
Parallel programming (also concurrent programming), is a computer programming technique that provides for the execution of operations concurrently, either within a single computer, or across a number of systems. ...
In computer programming a critical section is a piece of code that can only be executed by one process or thread at a time. ...
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. An interrupt handler, also known as an interrupt service routine, is a subroutine in an operating system or device driver whose execution is triggered by the reception of an interrupt. ...
A thread in computer science is short for a thread of execution. ...
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. In computer programming a critical section is a piece of code that can only be executed by one process or thread at a time. ...
A mutex is also a common name for a program object that negotiates mutual exclusion among threads, also called a lock. In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. ...
Introduction 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: A uniprocessor system refers to a system with a single processor. ...
In computing, an interrupt is an asynchronous signal from hardware or software indicating the need for attention. ...
To wait for an event by iterating through a tight loop or time-delayed loop that polls for the occurrence of the event on each pass rather than calling an interrupt and continuing execution on another part of the process. ...
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." Dekkers algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. ...
Petersons algorithm is a concurrent programming algorithm for mutual exclusion that allows just two processes to share a single-use resource without conflict, using only shared memory for communication. ...
Lamports bakery algorithm is a computer algorithm devised by computer scientist Dr Leslie Lamport, which is intended to improve the robustness of multiple thread-handling processes by means of mutual exclusion. ...
It has been suggested that this article or section be merged into Compare-and-swap. ...
In computer programming, flag refers to one or more bits that are used to store a binary value or code that has an assigned meaning. ...
In software engineering, a spinlock is a lock where the thread simply waits in a loop (spins) repeatedly checking until the lock becomes available. ...
To wait for an event by iterating through a tight loop or time-delayed loop that polls for the occurrence of the event on each pass rather than calling an interrupt and continuing execution on another part of the process. ...
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. In computer science, a linked list is one of the fundamental data structures used in computer programming. ...
A binary tree, a simple type of branching linked data structure. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
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. Latency is the time a message takes to traverse a system. ...
A context switch is the computing process of storing and restoring the state (context) of a CPU such that multiple processes can share a single CPU resource. ...
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. A semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to equivalent shared resources (e. ...
A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. ...
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ...
In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. ...
Much research is aimed at eliminating the above effects, such as by guaranteeing non-blocking progress. No perfect scheme is known. In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. ...
References - Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
- Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
- Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
See also Mutually exclusive In logic, two mutually exclusive (or mutual exclusive according to some sources) propositions are propositions that logically cannot both be true. ...
External links |
Feeds |
Contact