Ostatnimi czasy interesuje się algorytmami lock-free i wait-free. Dla ciekawych podrzucam kilka artykułów oraz krótka notkę wprowadzająca.
To ensure consistency of a shared data object in a concurrent environment,
the most common method is mutual exclusion, i.e. some form of locking. Mutual
exclusion degrades the system’s overall performance as it causes blocking,
i.e. other concurrent operations can not make any progress while the access to
the shared resource is blocked by the lock. Mutual exclusion can also cause
deadlocks, priority inversion and even starvation.
In order to address these problems, researchers have proposed non-blocking
algorithms for shared data objects. Non-blocking algorithms do not involve mutual
exclusion, and therefore do not suffer from the problems that blocking could
generate. Lock-free implementations are non-blocking and guarantee that regardless
of the contention caused by concurrent operations and the interleaving of
their sub-operations, always at least one operation will progress. However, there
is a risk for starvation as the progress of some operations could cause some other
operations to never finish. Wait-free algorithms are lock-free and moreover
they avoid starvation as well, as all operations are then guaranteed to finish
in a limited number of their own steps. Recently, some researchers also include
obstruction-free [3] implementations to the non-blocking set of implementations.
These kinds of implementations are weaker than the lock-free ones and do not
guarantee progress of any concurrent operation.
http://www.cs.brown.edu/~mph/Herlihy93/herlihy93methodology.pdf
http://www2.research.att.com/~bs/lock-free-vector.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.4693&rep=rep1&type=pdf
http://www.cse.chalmers.se/~tsigas/papers/NBMalloc-algorithmica.pdf
