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

Выглядит просто и элегантно, но реализовать на практике очень трудно. Сразу приходит в голову мысль, что для такой задачи подошло бы что-то вроде std::shared_ptr<> — ведь это и есть указатель с подсчетом ссылок. Увы, хотя некоторые операции над std::shared_ptr<> атомарны, не гарантируется, что они свободны от блокировок. Сам по себе класс std::shared_ptr<> ничем не хуже прочих с точки зрения операций над атомарными типами, но он рассчитан на применение в самых разных контекстах, и попытка сделать атомарные операции над ним свободными от блокировок, скорее всего, привела бы к увеличению накладных расходов при любом его использовании. Если на вашей платформе функция std::atomic_is_lock_free(&some_shared_ptr) возвращает true, то проблему освобождения памяти можно считать полностью решенной. Достаточно хранить в списке объекты std::shared_ptr, как показано в следующем листинге.

Листинг 7.9. Свободный от блокировок стек на основе свободной от блокировок реализации std::shared_ptr<>

template

class lock_free_stack {

private:

 struct node {

  std::shared_ptr data;

  std::shared_ptr next;

  node(T const& data_) :

   data(std::make_shared(data_)) {}

 };

 std::shared_ptr head;

public:

 void push(T const& data) {

  std::shared_ptr const new_node =

   std::make_shared(data);

  new_node->next = head.load();

  while (!std::atomic_compare_exchange_weak(

   &head, &new_node->next, new_node));

 }

 std::shared_ptr pop() {

  std::shared_ptr old_head = std::atomic_load(&head);

  while(old_head && !std::atomic_compare_exchange_weak(

   &head, &old_head, old_head->next));

  return old_head ? old_head->data : std::shared_ptr();

 }

};

В том весьма вероятном случае, когда реализация std::shared_ptr<> не свободна от блокировок, управлять подсчетом ссылок придется самостоятельно.

В одном из возможных способов используется не один, а два счетчика ссылок — внутренний и внешний. Их сумма равна общему количеству ссылок на узел. Внешний счетчик хранится вместе с указателем на узел и увеличивается при каждом чтении этого указателя. Когда читатель закапчивает работу с узлом, он уменьшает его внутренний счетчик. Таким образом, по завершении простой операции чтения указателя внешний счетчик увеличится на единицу, а внутренний уменьшится на единицу.

Когда необходимость в связи между внешним счетчиком и указателем отпадает (то есть узел невозможно получить из области памяти, доступной другим потокам), внутренний счетчик увеличивается на величину внешнего минус 1, а внешний отбрасывается. Если внутренний счетчик обратился в нуль, значит, никаких ссылок на узел извне не осталось и его можно удалять. Для обновления разделяемых данных по-прежнему необходимо применять атомарные операции. Теперь рассмотрим реализацию свободного от блокировок стека, в которой эта техника используется для гарантии того, что узлы освобождаются, только когда это безопасно.

В листинге ниже показала внутренняя структура данных и реализация функции push() — простая и элегантная.

Листинг 7.10. Помещение узла в свободный от блокировок стек с разделённым счётчиком ссылок

template

class lock_free_stack {

private:

 struct node;

 struct counted_node_ptr {←(1)

  int external_count;

  node* ptr;

 };

 struct node {

  std::shared_ptr data;←(2)

  std::atomic internal_count;

  counted_node_ptr next;  ←(3)

  node(T const& data_) :

   data(std::make_shared(data_)), internal_count(0) {}

 };

 std::atomic head;←(4)

public:

 ~lock_free_stack() {

  while(pop());

 }

 void push(T const& data) {←(5)

  counted_node_ptr new_node;

  new_node.ptr = new node(data);

  new_node.external_count = 1;

  new_node.ptr->next = head.load();

  while(

   !head.compare_exchange_weak(new_node.ptr->next, new_node));

 }

};