The Taub Faculty of Computer Science Events and Talks
Shahar Timnat (CS, Technion)
Thursday, 01.12.2011, 12:30
The linked-list data structure is fundamental and ubiquitous. Lock-free
versions of the linked-list are well known. However, the existence
of a practical wait-free linked-list has been open.
A wait-free data-structure is a structure in which each thread is guaranteed to
finish each method in a bounded number of steps, regardless of contention and
of the scheduling in the system.
We describe a practical wait-free linked-list based on the lock-free
linked-list algorithm of Harris. We have also extended this design
to work in the fast-path-slow-path methodology in order to achieve
a wait-free linked-list that performs comparably to the lock-free
linked list. We have implemented this algorithm and measured its
performance. It turns out that our implementation achieves performance
that is competitive with that of Harris, while still guaranteeing
non-starvation via wait-freedom.