Глава 1. Обзор методов и средств многопоточного взаимодействия
Работа с изменяемыми типами и структурами подразумевает выполнение таких операций, как чтение и модификация данных соответствующих объектов. Если используется только операция чтения, то есть, если типы и структуры, с которыми производится работа, имеют постоянные значения, никаких проблем с параллельным доступом к ним не возникает. Доступ к таким данным может производиться из множества потоков без всякой их синхронизации. Однако, другое дело, если работа производится с данными, которые могут изменяться: с момента начала операции модификации и вплоть до ее окончания, структура может находиться в несогласованном состоянии. Если теперь в этом промежутке времени будет произведена операция чтения, то она вернет неверное значение. Существует два решения проблемы: блокирующая и неблокирующая синхронизация.
1.1. Блокирующая синхронизация
Традиционные алгоритмы синхронизации в многопоточной среде, как известно, основаны на механизме блокировок. В момент времени до начала операции доступ к структуре для потоков, отличных от потока, получившего монопольный доступ, блокируется, далее – производится необходимое изменение, и, наконец, доступ для других потоков вновь разрешается. Таким образом, гарантируется целостность структуры данных. В простом виде блокирующий алгоритм можно представить в виде блок-схемы, показанной на рис. 1.1.
Рис. 1.1. Блок-схема простого алгоритма с блокировкой
Блокировки являются мощным средством синхронизации действий в многопоточной среде, которое может обеспечить синхронизацию любых сложных структур. Но, как и все мощное, эта это средство таит в себе множество недостатков, например:
они являются довольно медленными операциями и требуют много ресурсов;
они являются узким местом программы, поскольку с ресурсом, на котором установлена блокировка, может работать только заблокировавший его процесс, и в связи с этим процесс с низким приоритетом может заблокировать на неопределенное время другой процесс, с более высоким приоритетом;
они подвержены проблеме взаимных блокировок, отладка же взаимных блокировок бывает чрезвычайно сложна, поскольку возникает при определенных специфических условиях;
использование блокирующих механизмов синхронизации подразумевает применение особой техники программирования, и внедрять и отлаживать механизмы синхронизации нужно с самого начала работы над проектом, так как внедрить эти механизмы в уже готовый проект гораздо сложнее.
1.2. Неблокирующая синхронизация
1.2.1. Общие сведения
Алгоритмы и структуры данных для неблокирующей синхронизации (в дальнейшем неблокирующие алгоритмы и структуры) частично лишены недостатков блокирующих алгоритмов и структур, однако они не являются универсальными. Самое замечательное свойство подобных алгоритмов и структур состоит в том, что они часто не требуют вообще никаких дополнительных техник параллельного программирования, то есть последовательный алгоритм, реализованный с их помощью, во многих случаях превращается в параллельный алгоритм без дополнительных усилий.
В основе лежит взаимодействие с ресурсами при помощи указателей. Учитывая эту особенно, можно создать копию ресурса по указателю, которая заведомо не будет использоваться другими потоками, изменить данные в копии и, подменив указатель, получить изменённый ресурс, а старый освободить. Однако для реализации данного алгоритма необходимо учитывать некоторые особенности, к примеру, если какой-то поток использует ресурс, то мы не можем уничтожить оригинал, а если его используют несколько потоков, то этот ресурс необходимо уничтожить только после того, как все потоки закончат с ним работать.
Эти особенности учитываются в следующих принципах:
узлы неизменяемого типа;
подмена указателей;
атомарные операции;
специальные методы управления памятью.
В простом виде неблокирующий алгоритм можно представить в виде блок-схемы, показанной на рис. 1.2.
Рис. 1.2. Блок-схема простого неблокирующего алгоритма