Non-blocking algorithm
Non-blocking synchronization (English non-blocking or lock- free synchronization) is a technique in computer science to synchronize parallel processes without having to block certain sections of the program. In particular it is used to implement a non-blocking data structures in parallel systems.
Blocking techniques
To avoid inconsistencies in the process of parallel processes that access shared memory, locking techniques such as semaphores and mutexes are traditionally used, define the critical sections in which only one process gets exclusive access to certain resources. Want other processes occur simultaneously in a critical section, it will be blocked.
This approach has a number of disadvantages.
- Jamming: It can deadlocks ( deadlock ) come when there are interdependencies between locks.
- Loss of efficiency: The parallelism of the program is reduced (see Amdahlsches Act). In certain cases, this effect can be reduced by a finer granularity of the blocking (e.g., disabling access to individual elements of an object, rather than blocking of the entire object).
- Susceptibility to error: The correct identification and blocking of critical sections is not trivial and thus error-prone. Also the extensibility and maintainability of the program is difficult.
- Priority inversion: Looking at the entire system, is added the problem of priority inversion, where high-priority processes can be stopped by simple processes by Held Locks. System-level locks generally also affect the real-time behavior of the system.
Non-blocking techniques
Non-blocking synchronization techniques circumvent the definition of critical sections in that they create inconsistencies at any time. Data structures are modified exclusively by atomic operations. If the changes are small, as in the reference count or in the manipulation of pointers, processor instructions such as compare- and- swap or Load-Link/Store-Conditional can be used. Are the modifications extensive, they are first performed on copies of the original objects. If the object was changed during the creation of modification by other processes, the operation will initially fail and must be repeated.
Disadvantages of these techniques are:
- Complexity: The necessity of atomic changes often leads to complex and difficult to understand algorithms. The implementation of efficient and universal non-blocking data structures is an active field of research.
- Starvation: The possibility of failure can lead to a situation in which a complex change is always being made invalid by changes shorter and thereby " starving " (English starvation ). Starving is the flip side of the deadlock in the blocking synchronization.
In turn, the problem of priority inversion is dissolved, and the algorithms are often robust and efficient. The complex and difficult maintainable algorithms are also better encapsulated. You only need to be implemented once for each data type, and can be reused.
Wait- free and lock- free semantics
In the literature, mostly two degrees of guarantees about the runtime behavior of non-blocking algorithms can be distinguished.
The cost of wait- free implementations is very high. Firstly, the implementation is highly complex, on the other hand, the memory and time requirements of such algorithms usually rises with the number of processes or threads involved. There are implementations for simple queues and stacks, but the topic is still a current research topic. All wait- free algorithms are lock- free.
The lock- free algorithms, however, have already established in practice as an alternative to locks.