} else { ←(10)
counted_node_ptr old_next = {0};
if (old_tail.ptr->next.compare_exchange_strong(←(11)
old_next, new_next)) {
old_next = new_next; ←(12)
new_next.ptr = new node;←(13)
}
set_new_tail(old_tail, old_next);←(14)
}
}
}
};
В целом похоже на исходную версию push() из листинга 7.15, но есть и несколько принципиальных отличий. Если указатель data else, в которой один поток оказывает помощь другому (10).
Установив указатель data в узле (6), новая версия push() изменяет указатель next, вызывая compare_exchange_strong() (7). Мы используем compare_exchange_strong(), чтобы избежать цикла. Если обмен завершился неудачно, значит, другой поток уже установил указатель next, поэтому нам ни к чему узел, выделенный в начале, и его можно удалить (8). Мы также хотим использовать значение next, установленное другим потоком, для обновления tail (9).
Собственно обновление указателя 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, остаются в силе, но этого мало. Из анализа примеров я извлек несколько полезных рекомендаций, к которым вы можете обращаться при проектировании структур данных, свободных от блокировок.
