Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Built-in Coloring for Highly-Concurrent Doubly-Linked Lists
event speaker icon
Eshcar Hilel (M.Sc. Thesis Seminar)
event date icon
Wednesday, 29.11.2006, 15:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. H. Attiya
We present a novel approach for lock-free implementations of concurrent data structures, based on dynamically maintaining a coloring of the data structure's items. Roughly speaking, the data structure's operations are implemented by acquiring virtual locks on several items of the data structure and then making the changes atomically; this simplifies the design and provides clean functionality. The virtual locks are managed with compare-and-swap or double-compare-and-swap primitives, and helping is used to guarantee progress; virtual locks are acquired according to a coloring order that decreases interference and increases concurrency. Coming back full circle, the legality of the coloring is preserved by having operations correctly update the colors of the items they modify. We demonstrate the benefits of the scheme with new nonblocking implementations of doubly-linked list data structures: A DCAS-based implementation of a doubly-linked list allowing insertions and removals anywhere, and CAS-based implementations in which removals are allowed only at the ends of the list (insertions can occur anywhere). In the talk, we will present general background on concurrent data structures and a summary of the recent work in this field. We will also discuss questions and open issues we plan to further explore in the area of lock-based and lock-free algorithms for concurrent data structures with locality properties.