⬆️ ⬇️

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:

')





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:



empty queue



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:



writing



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:



image



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:

Source: https://habr.com/ru/post/102542/



All Articles