Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Собственно обновление указателя tailвынесено в отдельную функцию set_new_tail() (1). В ней мы используем цикл по compare_exchange_weak() (2), потому что если другие потоки пытаются поместить в очередь новый узел с помощью push(), то значение external_countможет измениться, а нам не хотелось бы его потерять. Однако нужно позаботиться и о том, чтобы не затереть значение, которое другой поток уже успешно изменил, в противном случае в очереди могут возникнуть циклы, а это уже совершенно лишнее. Следовательно, нужно гарантировать, что часть ptrзагруженного значения осталась той же самой, если сравнение с обменом не прошло. Если ptrне изменился после выхода из цикла (3), то мы успешно установили tail, поэтому старый внешний счетчик нужно освободить (4). Если значение ptrизменилось, то счетчик уже освобождён другим потоком, поэтому нам нужно только освободить ссылку, которую удерживает наш поток (5).

Если поток, вызвавший push(), не сумел установить указатель dataна этой итерации цикла, то он может помочь более удачливому потоку завершить обновление. Сначала мы пытаемся записать в next указатель на новый узел, выделенный в этом потоке (11). Если это получилось, то выделенный нами узел будет использоваться как новый узел tail (12), а нам следует выделить еще один узел, поскольку поместить свои данные в очередь еще только предстоит (13). После этого мы можем попытаться установить узел tail, вызвав set_new_tailдо перехода к очередной итерации (14).

Вероятно, вы обратили внимание на чрезмерно большое для такого крохотного фрагмента количество newи delete. Вызвало это тем, что новые узлы создаются в push(), а уничтожаются в pop(). Поэтому быстродействие этого кода существенно зависит от того, насколько эффективно работает распределитель памяти; плохой распределитель может полностью свести на нет свойства масштабируемости, присущие свободному от блокировок контейнеру. Вопрос о выборе и реализации подобных распределителей выходит за рамки данной книги, но имейте в виду, что единственный способ узнать, какой распределитель лучше, — испытывать и замерять производительность. К числу стандартных приемов оптимизации выделения памяти можно отнести создание отдельного распределителя в каждом потоке и использование списка свободных узлов — освободившиеся узлы помещаются в этот список, а не возвращаются распределителю.

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

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

Порядок доступа к памяти std::memory_order_seq_cstгораздо проще для понимания и анализа, чем любой другой, потому что операции с такой семантикой полностью упорядочены. Во всех примерах из этой главы мы начинали с упорядочения std::memory_order_seq_cstи только потом ослабляли ограничения. В этом смысле использование других способов упорядочения можно считать оптимизацией , которой не следует заниматься преждевременно. В общем случае, для того чтоб определить, какие операции можно ослабить, нужно иметь перед глазами полный код, правильно работающий со структурой данных. Любая попытка пойти другим путем только осложнит вам жизнь. Проблема еще и в том, что тестирование кода может не выявить ошибок, но это еще не гарантирует их отсутствия. Если нет верификатора алгоритма, способного систематически тестировать все возможные сочетания видимости в разных потоках, которые совместимы с гарантиями, предоставляемыми заданными режимами упорядочения доступа к памяти (а такие программы существуют), то одного лишь прогона кода недостаточно.