заблокировать свободную очередь очереди, если она не пуста

Question

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

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

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

Так в принципе, как бы я написал атомарную операцию enqueue_if_not_empty?

Answer 1

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

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

Answer 2

РЕДАКТИРОВАТЬ: Как было отмечено, я написал функцию с совершенно противоположной семантикой - в очередь только в пустую очередь. Я исправил название, чтобы отразить это, и решил оставить его на всякий случай, если кому-то будет интересно. Таким образом, это не правильный ответ на вопрос, но не отрицайте, пожалуйста, если вы не найдете другую причину:)

---

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

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;
}