7.1.4. Плюсы и минусы структур данных, свободных от блокировок

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

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

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

Ввиду отсутствия блокировок невозможны и взаимоблокировки, однако вместо них появляется угроза активных блокировок. Активная блокировка (live lock) возникает, когда два потока одновременно пытаются изменить структуру данных, но каждый из них должен начинать свою операцию сначала из-за изменений, произведенных другим потоком. Таким образом, каждый поток беспрестанно повторяет попытки в цикле. Представьте себе двух людей, пытающихся разойтись в узком проходе. Войдя в него одновременно, они сталкиваются лбами, поэтому оба отступают назад и пробуют еще раз. И так будет повторяться до тех пор, пока кто-то не проскочит первым (по взаимному согласию, потому что оказался быстрее или просто благодаря удаче). Как и в этом простом примере, активные блокировки обычно существуют недолго, потому что зависят от случайных временных соотношений при планировании потоков. Поэтому они скорее «подъедают» производительность, чем вызывают долгосрочные проблемы, но остерегаться их все равно стоит. По определению программа, свободная от блокировок, не страдает от активных блокировок, потому что существует ограничение сверху на количество шагов, необходимых для выполнения операции. Зато и алгоритм, скорее всего, окажется сложнее альтернативного и может потребовать большего числа шагов даже в случае, когда никакой другой поток одновременно не обращается к структуре данных.

Это подводит нас к еще одному недостатку кода, свободного от блокировок и ожидания: хотя он позволяет лучше распараллелить операции над структурой данных и сократить время ожидания в каждом конкретном потоке, общая производительность программы вполне может упасть. Во-первых, атомарные операции, используемые в свободном от блокировок коде, часто выполняются гораздо медленнее, чем неатомарные, а в структуре данных без блокировок их, скорее всего, будет гораздо больше, чем в аналогичной структуре с блокировками на основе мьютексов. К тому же, оборудование должно как-то синхронизировать данные между потоками, которые обращаются к одним и тем же атомарным переменным. В главе 8 мы увидим, что эффект перебрасывания кэша, возникающий из-за того, что несколько потоков обращаются к одним и тем же атомарным переменным, может привести к существенному падению производительности. Как обычно, необходимо тщательно анализировать аспекты, связанные с производительностью (время ожидания в худшем случае, среднее время ожидания, полное время выполнения и т.д.), для обоих решений — с блокировками и без, — прежде чем остановиться на каком-то одном.

А теперь перейдём к примерам.