Обнаружение удаленных узлов в заблокированном буфере fifo

Question

Я работаю над заблокированным буфером C++ 11 fifo. И я почти понял это. Однако одна маленькая деталь стала лучше меня. Буфер голова указывает:

std::shared_ptr<node<T>> m_head; 

Из типа:

struct node 
    { 
     node(const T data) 
      : 
      data(new T(data)), 
      next(nullptr) 
     {} 
     std::shared_ptr<T> data; 
     std::shared_ptr<node<T>> next; 
    }; 

И тогда есть продукция:

void produce(const T &&data) 
    { 
     //bool indicating whether a notification should be sent after adding 
     bool l_notifyUponAdding; 

     //the new node to be added at the end of the array 
     std::shared_ptr<node<T>> l_newNode(new node<T>(std::forward<const T&&>(data))); 
     //pointer to the last node 
     std::shared_ptr<node<T>> l_lastNode(std::atomic_load(&m_head)); 
     //value to compare the next of the last node with 
     std::shared_ptr<node<T>> l_expectedNullPointer; 
     //notify if this isn't the only node 
     l_notifyUponAdding = !l_lastNode; 

     if (!l_lastNode)//if there are no nodes, add this as the only node 
     if (std::atomic_compare_exchange_strong(&m_head, &l_expectedNullPointer, l_newNode)) 
      return; 

     do 
     { 
      l_expectedNullPointer.reset(); 
      while (l_lastNode->next) 
      { 
       l_lastNode = std::atomic_load(&l_lastNode)->next; 
      } 
     } while (!std::atomic_compare_exchange_weak(&l_lastNode->next, &l_expectedNullPointer, l_newNode)); 

     //adding failed since another thread already did this. 
     l_lastNode = l_expectedNullPointer; 


     if (l_notifyUponAdding) 
      m_newDataWaiter.notify_one(); 
     }  

И потребляют:

 std::shared_ptr<T> consume(bool blockingCall = false) 
     { 
      //Check if the head is null if it is: 
      if (!std::atomic_load(&m_head)) 
      { 
       if (blockingCall)//And this is a blocking call, 
       { 
        do 
        { 
         m_newDataWaiter.wait(m_newDataWaiterLock, [this]{return std::atomic_load(&(this->m_head)) == nullptr; });//we block until 
        } while (!std::atomic_load(&m_head));// the load yields a head that is not null(to avoid unnecessary calls on spurious wake ups) 
       } 
       else//And this is not a blocking call we 
       { 
        return nullptr; 
       } 
      } 

     //If we've found a valid head we will now try to make the node pointed to by head the new head. 
     std::shared_ptr<node<T>> l_poppee = atomic_load(&m_head); 
     std::shared_ptr<node<T>> l_newHead = atomic_load(&m_head); 

     //note that l_poppee gets updated if the compare exchange fails 
     while (l_poppee && !std::atomic_compare_exchange_weak(&m_head, &l_poppee, l_poppee->next)) 
     { 

     } 

     if (l_poppee) 
      return l_poppee->data; 
     else 
      return std::shared_ptr<T>(); 
    } 

Функции.

Все, кажется, хорошо работает. Однако я считаю, что есть один недостаток. Если все узлы потребляются во время выполнения produce. Данные будут добавлены к последнему элементу. Хотя элемент уже удален.

Чтобы быть более точным, если эта линия была выполнена:

if (std::atomic_compare_exchange_strong(&m_head, &l_expectedNullPointer, l_newNode)) 

И загруженный узел не был нулевым. Следующий элемент последнего узла будет изменен. Независимо от того, удаляются ли узлы в это время или нет. Узлы не будут физически удаляться, если функция продукта вызывается из-за общих указателей.

Однако основной указатель будет установлен в NULL. И поэтому новый узел будет удален, как только будет выведена функция продукта.

Неужели кто-нибудь знает решение этой проблемы :)?

Answer 1

Этот случай всегда разрешен в списках без блокировки, сохраняя в списке фиктивный узел. Голова всегда указывает на фиктивный узел, который является первым узлом в списке .

Когда очередь становится пустой, обе головы и хвоста указывают на фиктивный узел.

Более подробную информацию вы можете найти на странице http://www.research.ibm.com/people/m/michael/podc-1996.pdf, так что я не искажаю концепцию как ее легко выбрать из статьи.