Queues are among the most ubiquitous data structures in the field of computer science. With the advent of multiprocessor programming, concurrent queues are at the core of many concurrent and distributed algorithms.
This work is an experimental study covering a number of concurrent queueing algorithms, with the aim of comparing their performance and replicating the results of other researchers. The production of a benchmarking framework for concurrent queues also forms part of this study’s contributions. Particular focus has been placed on evaluating the ‘Baskets Queue’ of Hoffman et al. [1], Valois’ queue [2], together with Michael and Scott’s lock-free and double-locked concurrent queue [3].
With the exception of Michael and Scott’s double-locked concurrent queue, each queue possesses the non-blocking progress condition, meaning that one thread is guaranteed to make progress in a bounded number of steps. This progress condition makes queues more resistant to random delays, unlike its blocking counterpart, where a delay in one thread could cause delays elsewhere.
Two benchmarks were used in the evaluation phase. Firstly, the pairwise enqueue-dequeue benchmark was applied, which consists of a number of enqueue-dequeue pairs, evenly split across each process. Secondly, the 50% enqueue benchmark was used, where each process would have a 50% chance of executing an enqueue, The execution of operations was decided by a uniformly distributed random-number generator. This randomness would offer a more varied interleaving of
operations, exercising a wider combination of code paths.
The number of processes concurrently interacting with the queue and the length of the artificial delay between each operation were used as control variables. Using readings from the initial stages of this study, the two provided plots were generated, showing that although blocking queues could compete with non-blocking queues with less threads, the blocking queues were several magnitudes slower than their non-blocking counterparts.
References/Bibliography:
[1] Hoffman, M., Shalev, O., Shavit, N. (2007). The Baskets Queue. In: Tovar, E., Tsigas, P., Fouchal, H. (eds) Principles of Distributed Systems. OPODIS 2007. Lecture Notes in Computer Science, vol 4878. Springer, Berlin.
[2] John D. Valois ( 1995). Lock-Free Data Structures. PhD thesis, Rochester Institute of Technology.
[3] Maged M. Michael and Michael L. Scott (May 1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Proceedings of the 15th ACM Symposium on Principles of Distributed Computing. pp. 267–275.
Student: Luca Muscat
Course: B.Sc. (Hons.) Computing Science
Supervisor: Prof. Kevin Vella