A Scalable Multi-Producer Multi-Consumer Wait-Free Ring Buffer

Keywords

Concurrent; Non-blocking; Parallel; Queue; Ring buffer; Wait-free

Abstract

A ring buffer or cyclical queue is a First In, First Out (FIFO) queue that stores elements on a fixed-length array. This allows for efficient O(1) operations, cache-aware optimizations, and low memory overhead. Because ring buffers are limited to only the array and two counters they are desirable for systems with limited memory. Many applications (e.g. cloud-based services) depend on ring buffers to pass work from one thread to another. The rise in many-core architecture has resulted in increased performance from shared data structures such as ring buffers. Existing research has forgone the use of locks and permitted greater scalability and core utilization for such designs. Such non-blocking designs are categorized by the level of progress they guarantee with wait-freedom being the most desirable categorization. Such a guarantee provides freedom from deadlock, livelock, and thread starvation. Lock-free and obstruction-free designs are not safe from all of these pitfalls [5].

Publication Date

4-13-2015

Publication Title

Proceedings of the ACM Symposium on Applied Computing

Volume

13-17-April-2015

Number of Pages

1321-1328

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/2695664.2695924

Socpus ID

84955477481 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84955477481

This document is currently not available here.

Share

COinS