DocumentCode :
2860846
Title :
A wait-free queue for multiple enqueuers and multiple dequeuers using local preferences and pragmatic extensions
Author :
Stellwag, Philippe ; Ditter, Alexander ; Schröder-Preikschat, Wolfgang
Author_Institution :
Comput. Sci. 4, Friedrich-Alexander Univ. Erlangen-Nuremberg, Erlangen, Germany
fYear :
2009
fDate :
8-10 July 2009
Firstpage :
237
Lastpage :
248
Abstract :
Queues are one of the most commonly used data structures in applications and operating systems. Up-and-coming 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 to achieve this. Wait-freedom 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 dasialocal preferencespsila 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 concurrent 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 multiple readers.
Keywords :
alarm systems; concurrency control; control engineering computing; data structures; embedded systems; mobile robots; multi-threading; multiprocessing systems; operating system kernels; path planning; storage allocation; arbitrary concurrent thread operation; average response time; contention minimization; data structure; embedded real-time system parallelization; local preferences; motion control program; multicore processor; multiple dequeue operation; multiple enqueue operation; multiple read operation; operating system kernel; pragmatic extension; robotic control kernel; software development; statically-linked queue allocation; unsorted thread-safe alarm queue; wait-free queue; worst case execution time reduction; Application software; Control systems; Data structures; Delay; Multicore processing; Operating systems; Parallel robots; Real time systems; Robot control; Yarn;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Industrial Embedded Systems, 2009. SIES '09. IEEE International Symposium on
Conference_Location :
Lausanne
Print_ISBN :
978-1-4244-4109-9
Electronic_ISBN :
978-1-4244-4110-5
Type :
conf
DOI :
10.1109/SIES.2009.5196220
Filename :
5196220
Link To Document :
بازگشت