A Wait-Free Queue for Multiple Enqueuers and Multiple Dequeuers Using Local Preferences and Pragmatic Extensions

Stellwag P, Schröder-Preikschat W (2009)

Publication Type: Conference contribution

Publication year: 2009

Publisher: IEEE Computer Society Press

Edited Volumes: Proceedings - 2009 IEEE International Symposium on Industrial Embedded Systems, SIES 2009

City/Town: Lausanne

Pages Range: 237-248

Conference Proceedings Title: Industrial Embedded Systems (SIES 2009)

Event location: Lausanne, Switzerland CH

ISBN: 978-1-4244-4110-5

URI: http://www4.informatik.uni-erlangen.de/Publications/2009/stellwag_sies09_ah.pdf

DOI: 10.1109/SIES.2009.5196220

Abstract

Queues are one of the most commonly used data structures in applications and operating systems [1].Up-andcoming multi-core processors force software developers to consider data structures in order to make them thread-safe.But, in real-time systems, e.g., robotic controls, parallelization is even more complicated as such systems must guarantee to meet their mostly hard deadlines.A considerable amount of research has been carried out on wait-free objects [2] to achieve this.Waitfreedom can guarantee that each potentially concurrent thread completes its operation within a bounded number of steps.But applicable wait-free queues, which supports multiple enqueue, dequeue and read operations, do not exist yet.Therefore, we present a statically allocated and statically linked queue, which supports arbitrary concurrent operations.Our approach is also applicable in other scenarios, where unsorted queues with statically allocated elements are used.Moreover, we introduce 'local preferences' to minimize contention.But, as the response times of our enqueue operation directly depends on the fill level, the response times of a nearly filled queue still remain an issue.Moreover, our approach is jitter-prone with a varying fill level.In this paper, we also address all of these issues with an approach using a helping queue.The results show that we can decrease the worst case execution time by approximately factor twenty.Additionally, we reduce the average response times of potentially oncurrent enqueue operations in our queue.To the best of our knowledge, our wait-free queue is the best known and practical solution for an unsorted thread-safe queue for multiple enqueuers, multiple dequeuers and mulitple readers.© 2009 IEEE.

Authors with CRIS profile

Philippe Stellwag Graduiertenzentrum der FAU Wolfgang Schröder-Preikschat Lehrstuhl für Informatik 4 (Verteilte Systeme und Betriebssysteme)

How to cite

APA:

Stellwag, P., & Schröder-Preikschat, W. (2009). A Wait-Free Queue for Multiple Enqueuers and Multiple Dequeuers Using Local Preferences and Pragmatic Extensions. In Industrial Embedded Systems (SIES 2009) (pp. 237-248). Lausanne, Switzerland, CH: Lausanne: IEEE Computer Society Press.

MLA:

Stellwag, Philippe, and Wolfgang Schröder-Preikschat. "A Wait-Free Queue for Multiple Enqueuers and Multiple Dequeuers Using Local Preferences and Pragmatic Extensions." Proceedings of the IEEE Symposium on Industrial Embedded Systems 2009, Lausanne, Switzerland Lausanne: IEEE Computer Society Press, 2009. 237-248.

BibTeX: Download