Queue Fusion: Unleashing Multithreading Magic with Ruby

Introduction

Motivation for this post is to let people know things about designing concurrent queue. A queue is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. It represents an ordered list of elements where the addition of new elements (enqueue) occurs at the rear, and removal of existing elements (dequeue) occurs at the front. A concurrent queue is an extension of the traditional queue data structure designed to handle simultaneous operations from multiple threads.

In concurrent programming, where multiple threads execute concurrently, a regular queue may face issues related to thread safety and data integrity, due to multiple threads enqueue and dequeue concurrently. Let’s see the various approaches in designing a concurrent queue to synchronise queue between the threads using Ruby.

Concurrency Problems with Arrays in building queue

Let’s design concurrent queue using Array. Consider the following code snippet that attempts to implement a basic queue using a simple array without any thread synchronisation:

Now, let’s simulate a scenario where multiple threads are concurrently enqueuing and dequeuing items in a queue:

In this example, the producer_thread_1 and producer_thread_2 threads are concurrently adding items to the queue, and the consumer_thread is concurrently removing items from the queue. However, without proper synchronisation mechanisms, below are the possible issues.

Possible issues:

Race Condition: Both enqueue threads may try to modify the array simultaneously, leading to unpredictable results.
Data Corruption: The dequeue thread may try to remove an element from the array while it is being modified by one of the enqueue threads, resulting in data corruption or unexpected behaviour.

To address these issues, proper thread synchronisation mechanisms should be used. Please also note that the above examples I provided gives consistent results with MRI Ruby due to GIL in place (Allows only one thread to execute at a time. All the operations provided in the code snippet internally considered atomic that doesn’t have possibility of context switching in the enqueue and dequeue statements). Use JRuby to understand the examples better.

Use Thread Synchronisation

To address the concurrency challenges associated with arrays in the above example, let’s use thread synchronisation mechanisms in accessing the queue.

In Ruby, the Mutex class can be utilised to create a mutual exclusion zone, ensuring that only one thread can access the critical section at a time.
The ConditionVariable class can be employed to coordinate between threads, allowing for efficient waiting and signalling (To design in such a way that dequeue thread waits until queue no longer empty).

Below is a basic example of a concurrent queue implementation by synchronisation mechanisms:

Only one thread can do enqeueue/dequeue operation in queue at any given time. ConditionVariable class helps dequeue thread to wait until queue is no longer empty. Great, now the above code snippet addresses concurrency issues. Let’s see one more approach.

Use of Inbuilt Queue in Ruby

Ruby provides a built-in Queue class that inherently handles concurrency challenges. The Queue class internally uses thread synchronisation mechanisms to ensure safe concurrent access, making it a reliable choice for implementing concurrent queues in Ruby. Here’s an example of using the built-in Queue class:

Conclusion

Designing a concurrent queue in Ruby involves understanding the potential concurrency issues associated with basic data structures like arrays and employing thread synchronisation mechanisms to ensure thread safety. While manual implementation with mutex and ConditionVariable is possible, Ruby’s inbuilt Queue class provides a convenient and efficient solution for concurrent queue management. By adopting proper design practices, developers can create robust and reliable concurrent queues in Ruby, facilitating efficient concurrent processing in their applications.