Editing Non-blocking algorithm (section)

== Motivation ==
{{Main|Lock (computer science)#Disadvantages|l1=Disadvantages of locks}}

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 can 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 (computer science)|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.

Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in [[interrupt handler]]s: even though the [[Pre-emptive multitasking|preempted]] thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock. While this can be rectified by masking interrupt requests during the critical section, this requires the code in the critical section to have bounded (and preferably short) running time, or excessive interrupt latency may be observed.<ref name="monit">{{cite journal | doi = 10.1145/358818.358824 | url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html | title = Experience with Processes and Monitors in Mesa | author = Butler W. Lampson | author-link = Butler W. Lampson |author2=David D. Redell |author2-link=David D. Redell | journal = Communications of the ACM | volume = 23 | issue = 2 | pages = 105–117 |date=February 1980| citeseerx = 10.1.1.142.5765 | s2cid = 1594544 }}</ref>

A lock-free data structure can be used to improve performance.
A lock-free data structure increases the amount of time spent in parallel execution rather than serial execution, improving performance on a [[multi-core processor]], because access to the shared data structure does not need to be serialized to stay coherent.<ref>
Guillaume Marçais, and Carl Kingsford.
[https://web.archive.org/web/20140518060917/http://bioinformatics.oxfordjournals.org/content/27/6/764.abstract "A fast, lock-free approach for efficient parallel counting of occurrences of k-mers"].
Bioinformatics (2011) 27(6): 764-770.
{{doi|10.1093/bioinformatics/btr011}}
[http://www.genome.umd.edu/jellyfish.html "Jellyfish mer counter"].
</ref>