Wikipedia defines lock-free and wait-free algorithms as allowing "...multiple threads to read and write shared data concurrently without corrupting it. "Lock-free" refers to the fact that a thread cannot lock up: every step it takes brings progress to the system."
LOCK-FREE LINKED LISTS AND SKIP LISTS "Developing a correct and efficient memory management scheme is important to make a data structure practical. Developing such a scheme for a lock-free data structure is often quite a challenging task. The difficulty lies in determining how and when memory that was once occupied by parts of the data structure (e.g. nodes of a linked list), can be freed and reused, so that the processes that might still be accessing those parts are able to complete their operations correctly...We presented new algorithms implementing a lock-free linked list and a lock-free skip list. We proved their correctness and lock-freedom."
Lock-Free Reference Counting The goal of this work, therefore, is to allow programmers to exploit the advantages of GC in designing their lock-free data structure implementations, while avoiding its drawbacks. To this end, we provide a methodology that allows programmers to first solve the easier problem of designing a GC-dependent implementation, and to then apply our methodology in order to achieve a GC-independent one.
An older article: Lock-free Parallel Garbage Collection by Mark&Sweep.
Related to Lock Free Programming.
No comments:
Post a Comment