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

В главе 7 мы узнаем, как можно, не отходя от сформулированных рекомендаций, вообще обойтись без блокировок, применяя для обеспечения необходимых ограничений на упорядочение низкоуровневые атомарные операции.

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

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

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

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

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

В главе 5 мы реализовали простой мьютекс-спинлок с помощью std::atomic_flag. Этот код воспроизведён в листинге ниже.

Листинг 7.1. Реализация мьютекса-спинлока с помощью std::atomic_flag

class spinlock_mutex {

 std::atomic_flag flag;

public:

 spinlock_mutex():

  flag(ATOMIC_FLAG_INIT) {}

 void lock() {

  while (flag.test_and_set(std::memory_order_acquire));

 }

 void unlock() {

  flag.clear(std::memory_order_release);

 }

};