Параллельное программирование на С++ в действии полностью

  }                          │данные из узла

  try_reclaim(old_head);←┐Освободить удаленные

  return res;           (4) узлы, если получится

 }

};

Атомарная переменная threads_in_pop (1) нужна для подсчета потоков, которые в данный момент пытаются извлечь элемент из стека. Она увеличивается на единицу в начале pop() (2) и уменьшается на единицу внутри функции try_reclaim(), которая вызывается после изъятия узла из списка (4). Поскольку мы откладываем удаление самого узла, то можно с помощью swap() переместить из него данные (3), а не просто скопировать указатель; тогда данные будут автоматически удалены, когда в них отпадает необходимость, вместо того, чтобы занимать память только потому, что на них ссылается еще не удаленный узел. В следующем листинге показан код функции try_reclaim().

Листинг 7.5. Механизм освобождения памяти на основе подсчёта ссылок

template

class lock_free_stack {

private:

 std::atomic to_be_deleted;

 static void delete_nodes(node* nodes) {

  while (nodes) {

   node* next = nodes->next;

   delete nodes;

   nodes = next;

  }

 }

 void try_reclaim(node* old_head) {

  if (threads_in_pop == 1) ←(1)

  {         Заявляем права на список подлежащих удалению узлов (2)

   node* nodes_to_delete = to_be_deleted.exchange(nullptr);←┘

   if (!--threads_in_pop)←┐Я — единственный

   {                      (3) поток в pop()?

    delete_nodes(nodes_to_delete);       ←(4)

   } else if(nodes_to_delete) {          ←(5)

    chain_pending_nodes(nodes_to_delete);←(6)

   }

   delete old_head; ←(7)

  } else {

   chain_pending_node(old_head); ←(8)

   --threads_in_pop;

  }

 }

 void chain_pending_nodes(node* nodes) {

  node* last = nodes;

  while (node* const next =

         last->next) {←┐  По указателям

                       ├(9) next доходим до

   last = next;        │  конца списка

  }

  chain_pending_nodes(nodes, last);

 }

 void chain_pending_nodes(node* first, node* last) {

  last->next = to_be_deleted;←(10)

  while (

   !to_be_deleted.compare_exchange_weak(←┐   цикл гарантиру-

   last->next, first));                  ├(11)ет, что last->next

  }                                      │   корректно

 void chain_pending_node(node* n) {

  chain_pending_nodes(n, n);←(12)

 }

};

Если при попытке освободить занятую узлом (1) память счетчик threads_in_pop оказывается равен 1, то данный поток — единственный в pop(), и, значит, можно безопасно удалять только что исключенный из списка узел (7) и, быть может, также узлы, ожидающие удаления. Если счетчик не равен 1, то никакие узлы удалять нельзя, поэтому мы просто добавляем узел в список ожидающих (8).

Предположим, что threads_in_pop равно 1. Тогда нам нужно освободить ожидающие узлы, потому что если этого не сделать, то они так и будут ожидать удаления до момента уничтожения стека. Для этого мы запрашиваем монопольные права на список с помощью атомарной операции exchange (2), после чего уменьшаем на единицу счетчик threads_in_pop (3). Если в результате счетчик оказался равным нулю, значит, больше ни один поток не работает со списком ожидающих удаления узлов. По ходу дела могли появиться новые ожидающие узлы, но сейчас — когда можно безопасно очистить список — нам это безразлично. Мы просто вызываем функцию delete_nodes, которая обходит список и удаляет узлы (4).