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

  std::lock_guard tail_lock(tail_mutex);

  tail->data = new_data;

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

  tail = new_tail;

 }

};

Давайте взглянем на этот код критически, памятуя о рекомендациях из раздела 6.1.1. Прежде чем искать, где нарушены инварианты, надо бы их точно сформулировать:

• tail->next == nullptr.

• tail->data == nullptr.

• head == tail означает, что список пуст.

• Для списка с одним элементом head->next==tail.

• Для каждого узла x списка, для которого x!=tail, x->data указывает на экземпляр T, a x->next — на следующий узел списка. Если x->next==tail, то x — последний узел списка.

• Если проследовать по указателям next, начиная с головы списка, то рано или поздно мы достигнем его хвоста.

Сама по себе, функция push() очень проста: все модификации данных защищены мьютексом tail_mutex, и инвариант при этом сохраняется, потому что новый хвостовой узел пуст и правильно установлены указатели data и next для старого хвостового узла, который теперь стал настоящим последним узлом списка.

Самое интересное происходит в функции try_pop(). Как выясняется, мьютекс tail_mutex нужен не только для защиты чтения самого указателя tail, но и чтобы предотвратить гонку при чтении данных из головного узла. Не будь этого мьютекса, могло бы получиться, что один поток вызывает try_pop(), а другой одновременно вызывает push(), и эти операции никак не упорядочиваются. Хотя каждая функция-член удерживает мьютекс, но это разные мьютексы, а функции могут обращаться к одним и тем же данным — ведь все данные появляются в очереди только благодаря push(). Раз потоки потенциально могут обращаться к одним и тем же данным без какого бы то ни было упорядочения, то возможна гонка за данными и, как следствие (см. главу 5), неопределенное поведение. К счастью, блокировка мьютекса tail_mutex в get_tail() решает все проблемы. Поскольку внутри get_tail() захватывается тот же мьютекс, что в push(), то оба вызова оказываются упорядоченными. Либо обращение к функции get_tail() происходит раньше обращения к push() — тогда get_tail() увидит старое значение tail — либо после обращения к push() — и тогда она увидит новое значение tail и новые данные, присоединенные к прежнему значению tail.

Важно также, что обращение к get_tail() производится под защитой захваченного мьютекса head_mutex. Если бы это было не так, то между вызовом get_tail() и захватом head_mutex мог бы вклиниться вызов pop_head(), потому что другой поток вызвал try_pop() (и, следовательно, pop_head()) и захватил мьютекс первым, не давая первому потоку продолжить исполнение:

                                  │Эта реализация

std: :unique_ptr pop_head()←┘некорректна

{                                   (1) Старое значение tail

                                    │получено не

 node* const old_tail = get_tail();←┘под защитой head_mutex

 std::lock_guard head_lock(head_mutex);

 if (head.get() == old_tail)      ←(2)

  return nullptr;

 }

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

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

 return old_head;

}

При такой — некорректной — реализации в случае, когда get_tail() (1) вызывается вне области действия блокировки, может оказаться, что и head, и tail изменились к моменту, когда первому потоку удалось захватить head_mutex, и теперь возвращенный хвост мало того что больше не является хвостом, но и вообще не принадлежит списку. Тогда сравнение head с old_tail (2) не прошло бы, хотя head в действительности является последним узлом. Следовательно, после обновления (3) узел head мог бы оказаться в списке дальше tail, то есть за концом списка, что полностью разрушило бы структуру данных. В корректной реализации, показанной в листинге 6.6, вызов get_tail() производится под защитой head_mutex. Это означает, что больше никакой поток не сможет изменить head, a tail будет только отодвигаться от начала списка (по мере добавления новых узлов с помощью push()) — это вполне безопасно. Указатель head никогда не сможет оказаться дальше значения, возвращенного get_tail(), так что инварианты соблюдаются.