本篇文章主要介绍了"Some notes on lock-free and wait-free algorithms"，主要涉及到algorithm,notes方面的内容，对于企业开发感兴趣的同学可以参考一下：
原文：http://www.rossbencina.com/code/lockfreeOver the past two decades the researc...
It would be useful to have a cross-platform library of lock-free primitives for implementing real-time applications on desktop operating systems. Such a library would include implementations of queues and stacks, low level atomic update operations and memory barriers. It may also be useful to include higher level infrastructure, such as a robust implementation of deferred C++ function calls (for example see the single reader, single writer prototype code here). The present author is seeking to find or develop a library released under a permissive open source license allowing use in closed-source applications. These requirements can be summarised as follows:
- Portability with support for (at least) the dominant desktop computing platforms (i.e. PPC, x86, Mac-OSX, Linux, Windows).
- Implementation of common lock-free data structures such as LIFO stack and FIFO queue.
- Licensed under a flexible license permitting use in both open-source and closed-source systems (e.g. LGPL or BSD licensed)
Thus far a library which fulfills the above requirements has not been identified. If you know of such a library, or are interested in contributing to the development of one, please let me know.
Existing source code and libraries.
The following is a list of open-source libraries which provide implementations of lock-free data structures. If you know of one which isn’t listed here, please let me know.
-
MidiShare Source Code is available under the GPL license. MidiShare includes implementations of lock-free FIFO queues and LIFO stacks.
-
Appcore is an SMP and HyperThread friendly library which uses Lock-free techniques to implement stacks, queues, linked lists and other useful data structures. Appcore appears currently to be for x86 computers running Windows. The licensing terms of Appcore are extremely unclear.
-
Noble – a library of non-blocking synchronisation protocols. Implements lock-free stack, queue, singly linked list, snapshots and registers. Noble is distributed under a license which only permits non-commercial academic use.
-
lock-free-lib published under the GPL or BSD license (your choice). Includes implementations of software transactional memory, multi-workd CAS primitives, skip lists, binary search trees, and red-black trees. For Alpha, Mips, ia64, x86, PPC, and Sparc.
-
Nonblocking multiprocessor/multithread algorithms in C++ (for MSVC/x86) posted by Joshua Scholar to musicdsp.org, and are presumably in the public domain. Included are queue, stack, reference-counted garbage collection, memory allocation, templates for atomic algorithms and types. This code is largely untested. A local mirror is here.
- Larry Bush’s implementation of Valois’ lock-free linked list in C++
-
Qprof includes the Atomic_ops library of atomic operations and data structures under an MIT-style license. Only available for Linux at the moment, but there are plans to support other platforms. download available here
-
Amino Concurrent Building Blocks provides lock free datastructures and STM for C++ and Java under an Apache Software (2.0) licence.
- I asked the experts on comp.programming.threads about the single-reader single-writer atomic FIFO which can be found in SuperCollider and PortAudio among other places. Here’s here’s what was said. In summary, without memory barriers the code is not SMP safe.
- Bob McGwier sent word that the DttSP Project is used by over 1000 amateur radio operators in their radios every single day. It uses jack ring buffers and non locking code. On Linux it uses the jack library for ring buffers (but used outside of jack). They did their own ring buffer implementation for the Windows port: ringb.c and ringb.h.
Brief literature survey
This is not an exhaustive list, but the hope is that enough core articles are linked to give a good introduction to the field. Most of the resources here can be turned up on google or citeseer with search terms such as “lock free”, “lock-free”, “wait free”, “lock free queue”, “non-blocking”, “atomic fifo”, etc.
