Non-blocking algorithm: Difference between revisions

Revision as of 18:27, 27 April 2017

Revision as of 16:04, 15 November 2017

Line 14:

The traditional approach to multi-threaded programming is to use [[Lock (computer science)|locks]] to synchronize access to shared [[resource (computer science)|resources]]. Synchronization primitives such as [[mutual exclusion|mutexes]], [[Semaphore (programming)|semaphores]], and [[critical section]]s are all mechanisms by which a programmer can ensure that certain sections of code do not execute concurrently, if doing so would corrupt shared memory structures. If one thread attempts to acquire a lock that is already held by another thread, the thread will block until the lock is free.

Blocking a thread iscan be undesirable for many reasons. An obvious reason is that while the thread is blocked, it cannot accomplish anything: if the blocked thread had been performing a high-priority or [[real-time computing|real-time]] task, it would be highly undesirable to halt its progress.

Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as [[deadlock]], [[livelock]], and [[priority inversion]]. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for [[parallel computing|parallelism]], and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.