I have a question about the wait-free multi-producer queue in boost atomic example. I think the 'push' is only lock-free rather than wait-free, because there is a 'compare_exchange_weak loop', then there may be a particular thread in the loop for unpredictable time by some kind of thread scheduling. Besides I think 'pop' is wait-free

Are there mistakes in my understanding?


template<typename T>
class waitfree_queue {
  struct node {
    T data;
    node * next;
  void push(const T &data)
    node * n = new node;
    n->data = data;
    node * stale_head = head_.load(boost::memory_order_relaxed);
    do {
      n->next = stale_head;
    } while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));

  node * pop_all(void)
    T * last = pop_all_reverse(), * first = 0;
    while(last) {
      T * tmp = last;
      last = last->next;
      tmp->next = first;
      first = tmp;
    return first;

  waitfree_queue() : head_(0) {}

  // alternative interface if ordering is of no importance
  node * pop_all_reverse(void)
    return head_.exchange(0, boost::memory_order_consume);
  boost::atomic<node *> head_;
  • I found a same question stackoverflow.com/questions/40756575/…, but no one answer it ..... :( – Derek Zhang Apr 11 at 14:30
  • I posted an answer there; this should be closed as a duplicate. (That's fine, interesting question. Reposting like this is basically the only option for old unanswered questions that are actually good and just got overlooked when originally posted.) – Peter Cordes Apr 12 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.