Concurrent linked list
-
Hi, I'm working on implementing a concurrent queue (implemented as single linked list) and I've encountered a problem. The structure of my linked list node looks like this:
struct queue {
queue *head, *tail;
pthread_mutex_t head_mut, tail_mut;
}
struct node {
_Atomic(node*) next;
int item;
};I am currently implementing pop and push operations, both of them have their own separate mutex - tail_mut and head_mut respectively. The list always includes a dummy node at the beginning. I'm encountering an issue when there's only one element in the list (the dummy node plus this one element). I can't figure out how to handle the case where one thread is trying to push an element and another is trying to pop an element from the list. The problem arises when we perform a pop operation first and change the head to head->next. In this scenario, another thread can still push elements to the list by adding them to the end of the list (tail). However, the list has only one element (the one that is being popped = tail), so i must find a solution to somehow block this operation or to signal 'pushing' thread that it should push to the head not to tail. Acquiring the tail mutex would obviously solve the problem, but I'm looking for a potentially more efficient solution (so I would not block push operations by acquiring the tail mutex). Is there a more efficient way to handle this situation? Any suggestions would be greatly appreciated.
-
Hi, I'm working on implementing a concurrent queue (implemented as single linked list) and I've encountered a problem. The structure of my linked list node looks like this:
struct queue {
queue *head, *tail;
pthread_mutex_t head_mut, tail_mut;
}
struct node {
_Atomic(node*) next;
int item;
};I am currently implementing pop and push operations, both of them have their own separate mutex - tail_mut and head_mut respectively. The list always includes a dummy node at the beginning. I'm encountering an issue when there's only one element in the list (the dummy node plus this one element). I can't figure out how to handle the case where one thread is trying to push an element and another is trying to pop an element from the list. The problem arises when we perform a pop operation first and change the head to head->next. In this scenario, another thread can still push elements to the list by adding them to the end of the list (tail). However, the list has only one element (the one that is being popped = tail), so i must find a solution to somehow block this operation or to signal 'pushing' thread that it should push to the head not to tail. Acquiring the tail mutex would obviously solve the problem, but I'm looking for a potentially more efficient solution (so I would not block push operations by acquiring the tail mutex). Is there a more efficient way to handle this situation? Any suggestions would be greatly appreciated.
cod3Ninj4 wrote:
I can't figure out how to handle the case
Good thing because there is no way to handle that case. You can only do it with one of the following. 1. One and only one lock. 2. Two dummy nodes, one at each end.
cod3Ninj4 wrote:
Is there a more efficient way to handle this situation?
Probably but that answer depends on how it is used and not on how it is implemented.