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

  {                                              │него указате-

                                                 │лей опасности

   delete old_head; ←(5)

  }

  delete_nodes_with_no_hazards();←(6)

 }

 return res;

}

Начнём с того, что мы перенесли цикл, в котором устанавливается указатель опасности, во внешний цикл, где перечитывается old_head, если операция сравнения с обменом завершается неудачно (1). Здесь мы используем функцию compare_exchange_strong(), потому что фактическая работа делается внутри цикла while: ложный отказ в compare_exchange_weak() привел бы к ненужному сбросу указателя опасности. Таким образом, гарантируется, что указатель опасности установлен перед разыменованием old_head. Заявив свои права на узел, мы можем очистить указатель опасности (2). Получив узел в свое распоряжение, мы должны проверить, не ссылаются ли на него указатели опасности, принадлежащие другим потокам (3). Если это так, то удалять узел пока нельзя, а нужно поместить его в список ожидающих (4); в противном случае узел можно удалять немедленно (5). Наконец, мы добавили вызов функции, в которой проверяется, существуют ли узлы, для которых мы ранее вызывали reclaim_later(). Если не осталось указателей опасности, ссылающихся на эти узлы, то мы можем спокойно удалить их (6). Те же узлы, на которые еще ссылается хотя бы один указатель опасности, остаются в списке и будут проверены следующим потоком, вызвавшим pop().

Разумеется, в новых функциях — get_hazard_pointer_for_current_thread(), reclaim_later(), outstanding_hazard_pointers_for() и delete_nodes_with_no_hazards() — скрыта масса деталей, поэтому отдёрнем занавес и посмотрим, как они работают.

Как именно в функции get_hazard_pointer_for_current_thread() выделяется память для принадлежащих потокам указателей опасности, несущественно для логики программы (хотя, как будет показано ниже, может влиять на эффективность). Поэтому пока ограничимся простой структурой: массивом фиксированного размера, в котором хранятся пары (идентификатор потока, указатель). Функция get_hazard_pointer_for_current_thread() ищет в этом массиве первую свободную позицию и записывает в поле ID идентификатор текущего потока. Когда поток завершается, эта позиция освобождается — в поле ID заносится сконструированное по умолчанию значение std::thread::id(). Этот алгоритм показан в следующем листинге.

Листинг 7.7. Простая реализация функции get_hazard_pointer_for_current_thread

unsigned const max_hazard_pointers = 100;

struct hazard_pointer {

 std::atomic id;

 std::atomic pointer;

};

hazard_pointer hazard_pointers[max_hazard_pointers];

class hp_owner {

 hazard_pointer* hp;

public:

 hp_owner(hp_owner const&) = delete;

 hp_owner operator=(hp_owner const&) = delete;

 hp_owner() :

  hp(nullptr) {

  for (unsigned i = 0; i < max_hazard_pointers; ++i) {

   std::thread::id old_id;

   if (

    hazard_pointers[i].

    id.compare_exchange_strong(         ←┐

     old_id, std::this_thread::get_id()))│Пытаемся заявить

   {                                     │права на владе-

    hp = &hazard_pointers[i];            │ние указателем

    break;                               │опасности

   }

  }

  if (!hp) {←(1)

   throw std::runtime_error("No hazard pointers available");

  }

 }

 std::atomic& get_pointer() {

  return hp->pointer;

 }

 ~hp_owner() {←(2)

  hp->pointer.store(nullptr);

  hp->id.store(std::thread::id());

 }

};

std::atomic& get_hazard_pointer_for_current_thread()←(3)

{                                    (4) У каждого потока

 thread_local static hp_owner hazard;←┘свой указатель опасности

 return hazard.get_pointer();←(5)

}