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

Здесь не вызываются никакие блокирующие функции; lock() просто «крутится» в цикле, пока test_and_set() не вернет false. Отсюда и название спинлок (spin lock) — слово spin означает «крутиться». Как бы то ни было, блокирующих вызовов нет, и, значит, любая программа, в которой для защиты разделяемых данных используется такой мьютекс, будет неблокирующей. Однако она не свободна от блокировок. Это по-прежнему мьютекс, который в каждый момент времени может захватить только один поток. Теперь сформулируем определение свободы от блокировок и посмотрим, какие структуры данных под него подпадают.

Чтобы структура данных считалась свободной от блокировок, она должна быть открыта для одновременного доступа со стороны сразу нескольких потоков. Не требуется, чтобы потоки могли выполнять одну и ту же операцию; свободная от блокировок очередь может позволять одного потоку помещать, а другому — извлекать данные, но запрещать одновременное добавление данных со стороны двух потоков. Более того, если один из потоков, обращающихся к структуре данных, будет приостановлен планировщиком в середине операции, то остальные должны иметь возможность завершить операцию, не дожидаясь возобновления приостановленного потока.

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

Свободные от блокировок алгоритмы с такими циклами могут приводить к застреванию (starvation) потоков, когда один поток, выполняющий операции с «неудачным» хронометражем, продвигается вперёд, а другой вынужден постоянно повторять одну и ту же операцию. Структуры данных, в которых такой проблемы не возникает, называются свободными от блокировок и ожидания.

Свободная от блокировок структура данных называется свободной от ожидания, если обладает дополнительным свойством: каждый обращающийся к ней поток может завершить свою работу за ограниченное количество шагов вне зависимости от поведения остальных потоков. Алгоритмы, в которых количество шагов может быть неограничено из-за конфликтов с другими потоками, не свободны от ожидания.

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

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

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