An optimistic approach to lock-free FIFO queues

First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java T...

Full description

Saved in:
Bibliographic Details
Published in:Distributed computing 2008-02, Vol.20 (5), p.323-341
Main Authors: Ladan-Mozes, Edya, Shavit, Nir
Format: Article
Language:English
Subjects:
Computer Communication Networks
Computer Hardware
Computer Science
Computer Systems Organization and Communication Networks
Software Engineering/Programming and Operating Systems
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java TM Concurrency Package . This work presents a new dynamic-memory concurrent lock-free FIFO queue algorithm that in a variety of circumstances performs better than the Michael and Scott queue. The key idea behind our new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an “optimistic” doubly - linked list whose pointers are updated using a simple store, yet can be “fixed” if a bad ordering of events causes them to be inconsistent. We believe it is the first example of such an “optimistic” approach being applied to a real world data structure.
ISSN:0178-2770
1432-0452
DOI:10.1007/s00446-007-0050-0