Clock Free App

In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread;^[1] for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress.

The word 'non-blocking' was traditionally used to describe telecommunications networks that could route a connection through a set of relays 'without having to re-arrange existing calls', see Clos network. Also, if the telephone exchange 'is not defective, it can always make the connection', see nonblocking minimal spanning switch.

Motivation[edit]

The traditional approach to multi-threaded programming is to use locks to synchronize access to shared resources. Synchronization primitives such as mutexes, semaphores, and critical sections 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 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 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 handlers: even though the 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 -- but this can be rectified easily by masking the interrupt request during the critical section^[2].

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.^[3]

Implementation[edit]

With few exceptions, non-blocking algorithms use atomicread-modify-write primitives that the hardware must provide, the most notable of which is compare and swap (CAS). Critical sections are almost always implemented using standard interfaces over these primitives (in the general case, critical sections will be blocking, even when implemented with these primitives). Until recently, all non-blocking algorithms had to be written 'natively' with the underlying primitives to achieve acceptable performance. However, the emerging field of software transactional memory promises standard abstractions for writing efficient non-blocking code.^[4][5]

Much research has also been done in providing basic data structures such as stacks, queues, sets, and hash tables. These allow programs to easily exchange data between threads asynchronously.

Additionally, some non-blocking data structures are weak enough to be implemented without special atomic primitives. These exceptions include:

• a single-reader single-writer ring bufferFIFO, with a size which evenly divides the overflow of one of the available unsigned integer types, can unconditionally be implemented safely using only a memory barrier
• Read-copy-update with a single writer and any number of readers. (The readers are wait-free; the writer is usually lock-free, until it needs to reclaim memory).
• Read-copy-update with multiple writers and any number of readers. (The readers are wait-free; multiple writers generally serialize with a lock and are not obstruction-free).

Several libraries internally use lock-free techniques,^[6][7][8] but it is difficult to write lock-free code that is correct.^{[9][10][11][12]}

Wait-freedom[edit]

Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom. An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.^[13]This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high.

Clock Free Online

It was shown in the 1980s^[14] that all algorithms can be implemented wait-free, and many transformations from serial code, called universal constructions, have been demonstrated. However, the resulting performance does not in general match even naïve blocking designs. Several papers have since improved the performance of universal constructions, but still, their performance is far below blocking designs.

Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown^[15] that the widely available atomic conditional primitives, CAS and LL/SC, cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.

But in practice these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2 KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems (typically the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required^{[citation needed]} is greater).

Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and Petrank^[16] presented a wait-free queue building on the CAS primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,^[17] which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank^[18] provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank^[19] provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.

'Non-blocking' was used as a synonym for 'lock-free' in the literature until the introduction of obstruction-freedom in 2003.^[20]

See also[edit]

References[edit]

1. ^Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Java concurrency in practice. Upper Saddle River, NJ: Addison-Wesley. p. 41. ISBN9780321349606.
2. ^Butler W. Lampson; David D. Redell (February 1980). 'Experience with Processes and Monitors in Mesa'. Communications of the ACM. 23 (2): 105–117. CiteSeerX10.1.1.142.5765. doi:10.1145/358818.358824.
3. ^Guillaume Marçais, and Carl Kingsford.'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'Jellyfish mer counter'.
4. ^Harris, Tim; Fraser, Keir (26 November 2003). 'Language support for lightweight transactions'(PDF). ACM SIGPLAN Notices. 38 (11): 388. CiteSeerX10.1.1.58.8466. doi:10.1145/949343.949340.
5. ^Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (June 15–17, 2005). 'Composable memory transactions'. Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois. New York, NY: ACM Press. pp. 48–60. doi:10.1145/1065944.1065952. ISBN978-1-59593-080-4.
6. ^libcds - C++ library of lock-free containers and safe memory reclamation schema
7. ^liblfds - A library of lock-free data structures, written in C
8. ^Concurrency Kit - A C library for non-blocking system design and implementation
9. ^Herb Sutter. 'Lock-Free Code: A False Sense of Security'. Archived from the original on 2015-09-01.
10. ^Herb Sutter. 'Writing Lock-Free Code: A Corrected Queue'. Archived from the original on 2008-12-05.
11. ^ Herb Sutter. 'Writing a Generalized Concurrent Queue'.
12. ^ Herb Sutter. 'The Trouble With Locks'.
13. ^ ^abAnthony Williams.'Safety: off: How not to shoot yourself in the foot with C++ atomics'.2015.p. 20.
14. ^Herlihy, Maurice P. (1988). Impossibility and universality results for wait-free synchronization. Proc. 7th Annual ACM Symp. on Principles of Distributed Computing. pp. 276–290. doi:10.1145/62546.62593. ISBN0-89791-277-2.
15. ^Fich, Faith; Hendler, Danny; Shavit, Nir (2004). On the inherent weakness of conditional synchronization primitives. Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC). pp. 80–87. doi:10.1145/1011767.1011780. ISBN1-58113-802-4.
16. ^Kogan, Alex; Petrank, Erez (2011). Wait-free queues with multiple enqueuers and dequeuers(PDF). Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. doi:10.1145/1941553.1941585. ISBN978-1-4503-0119-0.
17. ^Michael, Maged; Scott, Michael (1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 267–275. doi:10.1145/248052.248106. ISBN0-89791-800-2.
18. ^Kogan, Alex; Petrank, Erez (2012). A method for creating fast wait-free data structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. doi:10.1145/2145816.2145835. ISBN978-1-4503-1160-1.
19. ^Timnat, Shahar; Petrank, Erez (2014). A Practical Wait-Free Simulation for Lock-Free Data Structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 357–368. doi:10.1145/2692916.2555261. ISBN978-1-4503-2656-8.
20. ^Herlihy, M.; Luchangco, V.; Moir, M. (2003). Obstruction-Free Synchronization: Double-Ended Queues as an Example(PDF). 23rd International Conference on Distributed Computing Systems. p. 522.

External links[edit]