lock free queue enqueue if not empty

Question

Я реализовал бесплатную очередь блокировки на C, используя команду сравнения и свопинга на основе http://www.boyet.com/articles/LockfreeQueue.html.

Его работа замечательная, но я пытаюсь интегрировать эту очередь в незагруженный skip-список, который я реализовал. Я использую skip-list в качестве очереди приоритетов и хотел бы использовать свободную от блокировки очередь внутри каждого узла для хранения нескольких значений при столкновении с приоритетом. однако из-за того, как управляются узлы в списке пропуска, когда я обнаруживаю столкновение с приоритетом, мне нужно иметь возможность добавлять элемент в очередь только в том случае, если очередь не пуста.

из-за незащищенного характера очереди, не уверен, как выполнить эту операцию.

Так как же я могу написать атомную операцию enqueue_if_not_empty?

Answer 1

EDIT: Как было замечено, я написал эту функцию с совершенно противоположной семантикой - enqueuing только в пустую очередь. Я исправил это имя, чтобы отразить это, и решил оставить его, как на всякий случай, кому-то будет интересно. Таким образом, это не правильный ответ на этот вопрос, но не downvote пожалуйста, если вы не найдете другую причину :)

---

Ниже является попыткой добавить EnqueueIfEmpty() к реализации очереди в указанной статье. Я не проверял, что он работает или даже компилируется. Основная идея заключается в том, что вы вставляете новый узел сразу после головки (а не в хвост), при условии, что следующая следующая голова является нулевой (что является необходимым условием для пустой очереди). Я оставил дополнительные проверки, чтобы голова была равна хвосту, который, возможно, можно удалить.

public bool EnqueueIfEmpty(T item) { 
    // Return immediately if the queue is not empty. 
    // Possibly the first condition is redundant. 
    if (head!=tail || head.Next!=null) 
     return false; 

    SingleLinkNode<T> oldHead = null; 

    // create and initialize the new node 
    SingleLinkNode<T> node = new SingleLinkNode<T>(); 
    node.Item = item; 

    // loop until we have managed to update the tail's Next link 
    // to point to our new node 
    bool Succeeded = false; 
    while (head==tail && !Succeeded) { 

    // save the current value of the head 
    oldHead = head;   

    // providing that the tail still equals to head... 
    if (tail == oldHead) { 

     // ...and its Next field is null... 
     if (oldhead.Next == null) { 

     // ...try inserting new node right after the head. 
     // Do not insert at the tail, because that might succeed 
     // with a non-empty queue as well. 
     Succeeded = SyncMethods.CAS<SingleLinkNode<T>>(ref head.Next, null, node); 
     } 

     // if the head's Next field was non-null, another thread is 
     // in the middle of enqueuing a new node, so the queue becomes non-empty 
     else { 
     return false; 
     } 
    } 
    } 

    if (Succeeded) { 
    // try and update the tail field to point to our node; don't 
    // worry if we can't, another thread will update it for us on 
    // the next call to Enqueue() 
    SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldHead, node); 
    } 
    return Succeeded; 
} 

Answer 2

Ну, Enqueue-If-Not-Empty представляется относительно простой, но с ограничением: другие потоки могут одновременно удалить все предыдущие элементы из очереди, так что после вставки в хвосте будет сделана, новый элемент может оказаться первым в очереди. Поскольку операции атомного сравнения и свопинга выполняются с разными полями (в результате внесения изменений tail.Next при удалении аванса head), более сильные гарантии потребуют дополнительной сложности не только в этой функции, но и по крайней мере в Dequeue().

следующие изменения к нормальному Enqueue() метода являются достаточными:
1) в начале функции, проверьте head.Next будучи нулевым, и если да, то возвращают сразу же, как очередь пуста.
2) добавить head.Next!=null в условие цикла в случае, если попытки захвата должны быть остановлены, если изначально непустая очередь становится пустой до того, как вставка завершится успешно. Это не мешает описанной выше ситуации (потому что есть время между проверкой пустоты и вставкой узла), но уменьшает вероятность ее возникновения.
3) в конце функции попробуйте только продвигать хвост, если новый узел был успешно установлен в очередь (например, я сделал в ответе Enqueue-If-Empty).