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

  if (tail) {

   tail->next = std::move(p);←(4)

  } else {

   head = std::move(p);      ←(5)

  }

  tail = new_tail;           ←(6)

}

};

Прежде всего отметим, что в листинге 6.4 для управления узлами используется класс std::unique_ptr, потому что он гарантирует удаление потерявших актуальность узлов (и содержащихся в них данных) без явного использования delete. За передачу владения отвечает head, тогда как tail является простым указателем на последний узел.

В однопоточном контексте эта реализация прекрасно работает, но при попытке ввести мелкогранулярные блокировки в многопоточном контексте возникают две проблемы. Учитывая наличие двух элементов данных (head (1) и tail (2)), мы в принципе могли бы использовать два мьютекса — для защиты head и tail соответственно. Но не всё так просто.

Самая очевидная проблема заключается в том, что push() может изменять как head (5), так и tail (6), поэтому придётся захватывать оба мьютекса. Это не очень хорошо, но не трагедия, потому что захватить два мьютекса, конечно, можно. Настоящая проблема возникает из-за того, что и push(), и pop() обращаются к указателю next в узле: push() обновляет tail->next (4), a try_pop() читает head->next (3). Если в очереди всего один элемент, то head==tail, и, значит, head->next и tail->next — один и тот же объект, который, следовательно, нуждается в защите. Поскольку нельзя сказать, один это объект или нет, не прочитав и head, и tail, нам приходится захватывать один и тот же мьютекс в push() и в try_pop(), и получается, что мы ничего не выиграли по сравнению с предыдущей реализацией. Есть ли выход из этого тупика?

Решить проблему можно, заранее выделив фиктивный узел, не содержащий данных, и тем самым гарантировать, что в очереди всегда есть хотя бы один узел, отделяющий голову от хвоста. В случае пустой очереди head и tail теперь указывают на фиктивный узел, а не равны NULL. Это хорошо, потому что try_pop() не обращается к head->next, если очередь пуста. После добавления в очередь узла (в результате чего в ней находится один реальный узел) head и tail указывают на разные узлы, так что гонки за head->next и tail->next не возникает. Недостаток этого решения в том, что нам пришлось добавить лишний уровень косвенности для хранения указателя на данные, чтобы поддержать фиктивный узел. В следующем листинге показано, как теперь выглядит реализация.

Листинг 6.5. Простая очередь с фиктивным узлом

template

class queue {

private:

 struct node {

  std::shared_ptr data;←(1)

  std::unique_ptr next;

 };

 std::unique_ptr head;

 node* tail;

public:

 queue():

 head(new node), tail(head.get())←(2)

 {}

 queue(const queue& other) = delete;

 queue& operator=(const queue& other) = delete;

 std::shared_ptr try_pop() {

  if (head.get() ==tail) ←(3)

  {

   return std::shared_ptr();

  }

  std::shared_ptr const res(head->data);←(4)

  std::unique_ptr old_head = std::move(head);

  head = std::move(old_head->next); ←(5)

  return res; ←(6)

 }

 void push(T new_value) {

  std::shared_ptr new_data(

   std::make_shared(std::move(new_value)));←(7)

  std::unique_ptr p(new node); ←(8)

  tail->data = new_data; ←(9)

  node* const new_tail = p.get();

  tail->next = std::move(p);

  tail = new_tail;

 }

};