Non-blocking synchronization

from Wikipedia, the free encyclopedia

Non-blocking algorithm ( English blocking non- or lock-free synchronization ) is a technique in computer science to parallel processes to be synchronized without specific program sections to lock the need. In particular, it is used to implement non-blocking data structures in parallel systems.

Blocking Techniques

In order to avoid inconsistencies in the course of parallel processes that access shared memory, locking techniques such as semaphores and mutexes are traditionally used, which define critical sections in which only one process has exclusive access to certain resources. If other processes want to enter a critical section at the same time, they are blocked.

This approach has a number of disadvantages.

  • Jam: it can jamming (deadlock) come when there are mutual dependencies between locks.
  • Loss of efficiency: The parallelism of the program is reduced (see Amdahl's law ) . In certain cases, this effect can be reduced by a finer granularity of the locking (e.g. locking access to individual elements of an object instead of locking the entire object).
  • Susceptibility to errors: The correct identification and blocking of the critical sections is not trivial and therefore error-prone. The expandability and maintainability of the program are also made more difficult.
  • Priority inversion: If one looks at the entire system, there is also the problem of priority inversion , whereby high-priority processes can be held up by simple processes by held locks. System- level locks also generally affect the real-time behavior of the system.

Non-blocking techniques

Non-blocking synchronization techniques bypass the definition of critical sections by ensuring that they never create inconsistencies. Data structures are modified exclusively through atomic operations . If the changes are small, such as in reference counting or in the manipulation of pointers, processor commands such as Compare-and-swap or Load-Link / Store-Conditional can be used. If the modifications are more extensive, they are first carried out on copies of the original objects. If the object was changed by other processes while the modification was being created, the operation initially fails and must be repeated.

Disadvantages of these techniques are:

  • Complexity: The need for atomic changes often leads to complex and difficult to understand algorithms. The implementation of efficient and universal non-blocking data structures is a current research area.
  • Starvation: The possibility of failure can lead to a situation in which a complex change is repeatedly made invalid by shorter changes and thus "starves" ( starvation ). Starvation is the downside of the deadlock in blocking synchronization.

In turn, the priority reversal problem is resolved and the algorithms are often more robust and efficient. The complex and difficult to maintain algorithms are also better encapsulated. They only need to be implemented once for each data type and can be reused.

Wait-free and lock-free semantics

In the literature, two degrees of guarantees about the runtime behavior of non-blocking algorithms are usually distinguished.

  1. Wait-free : All operations of all processes involved are carried out, regardless of the processes running in parallel in the system.
  2. Lock-free : No operation is held up, but possible overlaps with other processes can lead to delays.

However, the effort for wait-free implementations is very high. On the one hand, the implementation is highly complex; on the other hand, the memory and time requirements of such algorithms usually increase with the number of processes or threads involved . There are implementations for simple queues and stacks , but the topic is still a current research area. All wait-free algorithms are also lock-free.

The lock-free algorithms have already established themselves in practice as an alternative to locks .

See also

Individual evidence

  1. Alex Kogan and Erez Petrank. 2011. Wait-free queues with multiple enqueuers and dequeuers. In Proceedings of the 16th ACM symposium on Principles and practice of parallel programming (PPoPP '11). ACM, New York, NY, USA, pp. 223-234. doi : 10.1145 / 1941553.1941585