Thread-safe queue without locks

Task

During the development of an interactive application, I needed to transfer data from one stream to another while avoiding any delays in both the transmitting and receiving streams. Data must be transmitted one by one, i.e. in the form of a queue.


I found two existing solutions used to securely transfer data from one thread to another - the use of mutually exclusive objects (MUTually EXclusive objects) and the lock pattern: Read-Write Lock Pattern. However, these solutions were not suitable for solving my problem. MUTEX objects at a time can only be used by one stream, so if one stream uses a MUTEX object, another thread must wait. The second option has a similar disadvantage - if reading is in progress, then the stream producing the record must wait for the lock to be released, and vice versa - if there is a recording, then the stream producing the read waits for the end of the recording.

Since the existing solutions did not fit, we had to develop a solution that would help in this case. Based on the task, the solution requirements were as follows:
')

• The data structure used is a queue.
• The solution must support one stream that writes data and one stream that reads data.
• The solution should allow to write and read data simultaneously.

Decision

The decision was based on a queue built on the basis of a unidirectional linked list, to which another element was added, which is always present in it, i.e. the queue never became empty. The criterion that there are no elements in the queue was the fact that the pointers to the head and to the tail of the queue showed the same element, i.e. were equal:



When recording, a new element is first created and only then the pointer to the tail of the queue is transferred. Due to the fact that the pointer to the tail is transferred at the last moment, when the data in the queue already is avoided the possibility of a conflict of writing and reading:



When reading, the pointer to the head of the queue is first transferred, then the empty queue element is removed, and finally the data from the queue is read. At the same time, the read data is deleted, only the “package” remains, which becomes a new empty element:



As a result, reading and writing are completely isolated from each other, i.e. Two streams can read and write simultaneously, without interfering with each other. Conflicts can be avoided due to the constant presence of at least one element in the queue.

Implementation

The queue element was implemented as a template as follows:

template <class E>
class QueueItem
{
public:
E* data;
QueueItem* next;

QueueItem(E* data);
};

template <class E>
QueueItem<E>::QueueItem(E* data)
{
this->data = data;
next = NULL;
}


When creating a queue, an empty element is immediately created:

template <class T>
Queue<T>::Queue()
{
QueueItem<T>* stub = new QueueItem<T>(NULL);

head = stub;
tail = stub;
}


Checking for a void queue is done by simply comparing pointers to the head and tail of the queue:

template <class T>
bool Queue<T>::empty()
{
return head == tail;
}


When writing a new element, the element is first written to the list and only then the pointer to the tail of the queue is transferred:

template <class T>
void Queue<T>::enqueue(T* value)
{
QueueItem<T>* item = new QueueItem<T>(value);

item->data = value;
item->next = NULL;

tail->next = item;

tail = item;
}

Reading is made as standard:

template <class T>
T* Queue<T>::dequeue()
{
if (head == tail)
return NULL; // queue is empty

QueueItem<T>* tmp = head;
head = head->next;
delete tmp;

return head->data;
}


It is important to note that the responsibility for returning the memory used for data transfer lies with the consumer thread.

Total

This solution is an example of a thread-safe queue implementation that can be applied in some particular cases, namely when:

• The essence of the task involves the use of the queue.
• It is necessary to avoid delays in writing and reading from the queue (for example, in computer games or other interactive programs).
• There is only one stream transmitting data and only one stream receiving data. This restriction can be extended to the case of several transmitting and one receiving stream will create a separate queue for each transmitting stream.