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

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

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

Рассмотрим двусвязный список, в котором каждый узел содержит указатели на следующий и предыдущий узел. Один из инвариантов формулируется так: если «указатель на следующий» в узле А указывает на узел В, то «указатель на предыдущий» в узле В указывает на узел А. Чтобы удалить узел из списка, необходимо обновить узлы по обе стороны от него, так чтобы они указывали друг на друга. После обновления одного узла инвариант оказывается нарушен и остается таковым, пока не будет обновлен узел по другую сторону. После того как обновление завершено, инвариант снова выполняется.

Шаги удаления узла из списка показаны на рис. 3.1:

1. Найти подлежащий удалению узел (N).

2. Изменить «указатель на следующий» в узле, предшествующем N, так чтобы он указывал на узел, следующий за N.

3. Изменить «указатель на предыдущий» в узле, следующем за N, так чтобы он указывал на узел, предшествующий N.

4. Удалить узел N.

Рис. 3.1. Удаление узла из двусвязного списка

Как видите, между шагами b и с указатели в одном направлении не согласуются с указателями в другом направлении, и инвариант нарушается.

Простейшая проблема, которая может возникнуть при модификации данных, разделяемых несколькими потоками, — нарушение инварианта. Если не предпринимать никаких мер, то в случае, когда один поток читает двусвязный список, а другой в это же время удаляет из списка узел, вполне может случиться, что читающий поток увидит список, из которого узел удален лишь частично (потому что изменен только один указатель, как на шаге b на рис. 3.1), так что инвариант нарушен. Последствия могут быть разными — если поток читает список слева направо, то он просто пропустит удаляемый узел. Но если другой поток пытается удалить самый правый узел, показанный на рисунке, то он может навсегда повредить структуру данных, и в конце концов это приведет к аварийному завершению программы. Как бы то ни было, этот пример иллюстрирует одну из наиболее распространенных причин ошибок в параллельном коде: состояние гонки (race condition).

3.1.1. Гонки

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

В параллельном программировании под состоянием гонки понимается любая ситуация, исход которой зависит от относительного порядка выполнения операций в двух или более потоках — потоки конкурируют за право выполнить операции первыми. Как правило, ничего плохого в этом нет, потому что все исходы приемлемы, даже если их взаимный порядок может меняться. Например, если два потока добавляют элементы в очередь для обработки, то вообще говоря неважно, какой элемент будет добавлен первым, лишь бы не нарушались инварианты системы. Проблема возникает, когда гонка приводит к нарушению инвариантов, как в приведенном выше примере удаления из двусвязного списка. В контексте параллельного программирования состоянием гонки обычно называют именно такую проблематичную гонку — безобидные гонки не так интересны и к ошибкам не приводят. В стандарте С++ определен также термин гонка за данными (data race), означающий ситуацию, когда гонка возникает из-за одновременной модификации одного объекта (детали см. в разделе 5.1.2); гонки за данными приводят к внушающему ужас неопределенному поведению.

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

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

3.1.2. Устранение проблематичных состояний гонки

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

Другой вариант — изменить дизайн структуры данных и ее инварианты, так чтобы модификация представляла собой последовательность неделимых изменений, каждое из которых сохраняет инварианты. Этот подход обычно называют программированием без блокировок (lock-free programming) и реализовать его правильно очень трудно; если вы работаете на этом уровне, то приходится учитывать нюансы модели памяти и разбираться, какие потоки потенциально могут увидеть те или иные наборы значений. Модель памяти обсуждается в главе 5, а программирование без блокировок — в главе 7.

Еще один способ справиться с гонками — рассматривать изменения структуры данных как транзакцию, то есть так, как обрабатываются обновления базы данных внутри транзакции. Требуемая последовательность изменений и чтений данных сохраняется в журнале транзакций, а затем атомарно фиксируется. Если фиксация невозможна, потому что структуру данных в это время модифицирует другой поток, то транзакция перезапускается. Это решение называется программной транзакционной памятью (Software Transactional Memory — STM), в настоящее время в этой области ведутся активные исследования. Мы не будем рассматривать STM в этой книге, потому что в С++ для нее нет поддержки. Однако к самой идее о том, чтобы выполнить какую-то последовательность действий и за один шаг зафиксировать результаты, я еще вернусь.

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

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

Что ж, это вовсе не сказка — именно такое поведение вы получаете при использовании примитива синхронизации, который называется мьютекс (слово mutex происходит от mutual exclusion — взаимное исключение). Перед тем как обратиться к структуре данных, программа захватывает (lock) мьютекс, а по завершении операций с ней освобождает (unlock) его. Библиотека Thread Library гарантирует, что если один поток захватил некоторый мьютекс, то все остальные потоки, пытающиеся захватить тот же мьютекс, будут вынуждены ждать, пока удачливый конкурент не освободит его. В результате все потоки видят согласованное представление разделяемых данных, без нарушенных инвариантов.

Мьютексы — наиболее общий механизм защиты данных в С++, но панацеей они не являются; важно структурировать код так, чтобы защитить нужные данные (см. раздел 3.2.2), и избегать состояний гонки, внутренне присущих интерфейсам (см раздел 3.2.3). С мьютексами связаны и собственные проблемы, а именно: взаимоблокировки (deadlock) (см. раздел 3.2.4), а также защита слишком большого или слишком малого количества данных (см. раздел 3.2.8). Но начнем с простого.

3.2.1. Использование мьютексов в С++

В С++ для создания мьютекса следует сконструировать объект типа

std::mutex

lock()

unlock()

unlock()

std::lock_guard

std::mutex

std::lock_guard

Листинг 3.1. Защита списка с помощью мьютекса

#include 

#include 

#include 

std::list some_list; ←

std::mutex some_mutex;   ←

void add_to_list(int new_value) {

 std::lock_guard guard(some_mutex); ←

 some_list.push_back(new_value);

}

bool list_contains(int value_to_find) {

 std::lock_guard guard(some_mutex); ←

 return

  std::find(some_list.begin(), some_list.end(), value_to_find) !=

  some_list.end();

}

В листинге 3.1 есть глобальный список (1), который защищен глобальным же объектом

std::mutex

std::lock_guard

add_to_list()

list_contains()

list_contains()

add_to_list()

Хотя иногда такое использование глобальных переменных уместно, в большинстве случаев мьютекс и защищаемые им данные помещают в один класс, а не в глобальные переменные. Это не что иное, как стандартное применение правил объектно-ориентированного проектирования; помещая обе сущности в класс, вы четко даете понять, что они взаимосвязаны, а, кроме того, обеспечиваете инкапсулирование функциональности и ограничение доступа. В данном случае функции

add_to_list

list_contains

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

3.2.2. Структурирование кода для защиты разделяемых данных

Как мы только что видели, для защиты данных с помощью мьютекса недостаточно просто «воткнуть» объект

std::lock_guard

Листинг 3.2. Непреднамеренная передача наружу ссылки на защищённые данные

class some_data {

 int а;

 std::string b; 

public:

 void do_something();

};

class data_wrapper {

private:

 some_data data;

 std::mutex m;

public :

 template

 void process_data(Function func) 

 {                 │

  std::lock_guard l(m);│

  func(data);           ←┘

 }                  

};

some_data* unprotected;

void malicious_function(some_data& protected_data) {

 unprotected = &protected_data;

}

data_wrapper x;

void foo               

{                   │

 x.process_data(malicious_function); ←┘

 unprotected->do_something(); ←

}                 

В этом примере функция-член

process_data

std::lock_guard

func

foo

malicious_function

do_something()

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

foo()

unprotected->do_something()

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

3.2.3. Выявление состояний гонки, внутренне присущих интерфейсам

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

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

std::stack

swap()

push()

pop()

top()

empty()

size()

top()

Листинг 3.3. Интерфейс адаптера контейнера

std::stack

template >

class stack {

public:

 explicit stack(const Container&);

 explicit stack(Container&& = Container());

 template  explicit stack(const Alloc&);

 template  stack(const Container&, const Alloc&);

 template  stack(Container&&, const Alloc&);

 template  stack(stack&&, const Alloc&);

 bool empty() const;

 size_t size() const;

 T& top();

 T const& top() const;

 void push(T const&);

 void push(T&&);

 void pop();

 void swap(stack&&);

};

Проблема в том, что на результаты, возвращенные функциями

empty()

size()

empty()

size()

Если экземпляр

stack

empty()

top()

stack s;

if (!s.empty())       ←

{

 int const value = s.top(); ←

 s.pop();          ←

 do_something(value);

}

Такой подход в однопоточном коде не только безопасен, но и единственно возможен: вызов

top()

stack

empty()

top()

pop()

И что же делать? Поскольку проблема коренится в дизайне интерфейса, то и решать ее надо путем изменения интерфейса. Но возникает вопроса — как его изменить? В простейшем случае мы могли бы просто декларировать, что

top()

empty()

false

empty()

Внимательно присмотревшись к показанному выше фрагменту, мы обнаружим еще одну потенциальную гонку, на этот раз между вызовами

top()

pop()

s

stack

stack

empty()

top()

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

do_something()

Поток А

-           -

if (!s.empty())

               if (!s.empty())

 int const value = s.top();

               int const value = s.top();

s.pop();

do_something(value);    s.pop();

               do_something(value);

Как видите, если работают только эти два потока, то между двумя обращениями к

top()

pop()

top()

empty()

top()

do_something()

Для решения проблемы необходимо более радикальное изменение интерфейса — выполнение обеих операций

top()

pop()

Для тех, кто незнаком с историей вопроса, рассмотрим класс

stack>

std::bad_alloc

pop()

std::stack

top()

pop()

Увы, это как раз то разбиение, которого мы пытались избежать в попытке уйти от гонки! К счастью, альтернативы имеются, но они не бесплатны.

Первый вариант решения — передавать функции

pop()

std::vector result;

some_stack.pop(result);

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

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

Это решение, пусть и безопасное, не идеально. Хотя на этапе компиляции можно узнать, существует ли копирующий или перемещающий конструктор, который не возбуждает исключений, — с помощью концепций

std::is_nothrow_copy_constructible

std::is_nothrow_move_constructible

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

std::shared_ptr

new

delete

new

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

Пример определения потокобезопасного стека

В листинге 3.4 приведено определение класса стека со свободным от гонок интерфейсом. В нем реализованы приведенные выше варианты 1 и 3: имеется два перегруженных варианта функции-члена

pop()

std::shared_ptr<>

push()

pop()

Листинг 3.4. Определение класса потокобезопасного стека

#include 

struct empty_stack: std::exception {

 const char* what() const throw();

};

template

class threadsafe_stack {

public:

 threadsafe_stack();

 threadsafe_stack(const threadsafe_stack&);

 threadsafe_stack& operator=(const threadsafe_stack&)

 = delete;←

 void push(T new_value);

 std::shared_ptr pop();

 void pop(T& value);

 bool empty() const;

};

Упростив интерфейс, мы добились максимальной безопасности — даже операции со стеком в целом ограничены: стек нельзя присваивать, так как оператор присваивания удален (1) (см. приложение А, раздел А.2) и функция

swap()

pop()

empty_stack

empty()

std::shared_ptr

new

delete

push()

pop()

empty()

empty()

std::stack<>

Листинг 3.5. Определение класса потокобезопасного стека

#include 

#include 

#include 

#include 

struct empty_stack: std::exception {

 const char* what() const throw();

};

template

class threadsafe_stack {

private:

 std::stack data;

 mutable std::mutex m;

public:

 threadsafe_stack(){}

 threadsafe_stack(const threadsafe_stack& other) {

 std::lock_guard lock(other.m);

 data = other.data; ←┐

 }           │

 threadsafe_stack& operator=(const threadsafe_stack&) = delete;

 void push(T new_value) {

  std::lock_guard lock(m);

  data.push(new_value);

 }

 std::shared_ptr pop()│

 {            ←┘

  std::lock_guard lock(m);

  if (data.empty()) throw empty_stack();

  std::shared_ptr const res(std::make_shared(data.top()));

  data.pop(); ←┐

  return res;  │

 }       │

 void pop(T& value) {

  std::lock_guard lock(m);

  if (data.empty()) throw empty_stack();

  value = data.top();

  data.pop();

 }

 bool empty() const {

  std::lock_guard lock(m);

  return data.empty();

 }

};

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

Обсуждение функций

top()

pop()

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

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

3.2.4. Взаимоблокировка: проблема и решение

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

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

Общая рекомендация, как избежать взаимоблокировок, заключается в том, чтобы всегда захватывать мьютексы в одном и том же порядке, — если мьютекс А всегда захватывается раньше мьютекса В, то взаимоблокировка не возникнет. Иногда это просто, потому что мьютексы служат разным целям, а иногда совсем не просто, например, если каждый мьютекс защищает отдельный объект одного и того же класса. Рассмотрим, к примеру, операцию сравнения двух объектов одного класса. Чтобы сравнению не мешала одновременная модификация, необходимо захватить мьютексы для обоих объектов. Однако, если выбрать какой-то определенный порядок (например, сначала захватывается мьютекс для объекта, переданного в первом параметре, а потом — для объекта, переданного во втором параметре), то легко можно получить результат, обратный желаемому: стоит двум потокам вызвать функцию сравнения, передав ей одни и те же объекты в разном порядке, как мы получим взаимоблокировку!

К счастью, в стандартной библиотеке есть на этот случай лекарство в виде функции

std::lock

Листинг 3.6. Применение

std::lock

std::lock_guard

class some_big_object;

void swap(some_big_object& lhs, some_big_object& rhs);

class X {

private:

 some_big_object some_detail;

 std::mutex m;

public:

 X(some_big_object const& sd) : some_detail(sd) {}

 friend void swap(X& lhs, X& rhs) {

  if (&lhs == &rhs)

  return;

  std::lock(lhs.m, rhs.m); ←

  std::lock_guard lock_a(lhs.m, std::adopt_lock);←

  std::lock_guard lock_b(rhs.m, std::adopt_lock);←

  swap(lhs.some_detail,rhs.some_detail);

 }

};

Сначала проверяется, что в аргументах переданы разные экземпляры, постольку попытка захватить

std::mutex

std::recursive_mutex

std::lock()

std::lock_guard

std::adopt_lock

std::lock_guard

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

lhs.m

rhs.m

std::lock

std::lock

std::lock

std::lock

Хотя

std::lock

3.2.5. Дополнительные рекомендации, как избежать взаимоблокировок

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

jоin()

std::thread

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

std::lock

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

Если без захвата нескольких мьютексов никак не обойтись и захватить их в одной операции типа

std::lock

Но не всегда всё так просто, и пример мы видели при рассмотрении оператора сравнения в разделе 3.2.4. В этом конкретном случае есть возможность захватить мьютексы одновременно, но так бывает не всегда. Пример связанного списка из раздела 3.1 дает еще один способ защитить список — хранить мьютекс в каждом узле. Тогда, чтобы получить доступ к списку, поток должен будет захватить мьютекс для каждого интересующего его узла. Так, чтобы удалить элемент, надо будет захватить мьютексы трех узлов — удаляемого, предшествующего и последующего, — постольку все они так или иначе модифицируются. Аналогично для обхода списка поток должен удерживать мьютекс текущего узла, пока не захватит мьютекс следующего за ним; это гарантирует, что никто не может изменить указатель на следующий узел. Захватив мьютекс следующего узла, можно освободить мьютекс текущего, так как больше он не понадобится.

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

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

Предотвратить в этом случае взаимоблокировку можно, определив порядок обхода, так что поток всегда должен захватывать мьютекс А раньше мьютекса В, а мьютекс В раньше мьютекса С. Это устранило бы возможность взаимоблокировки, но ценой запрета обхода в обратном направлении. Подобные соглашения можно принять и для других структур данных.

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

Листинг 3.7. Использование иерархии блокировок для предотвращения взаимоблокировки

hierarchical_mutex high_level_mutex(10000); ←

hierarchical_mutex low_level_mutex(5000);  ←

int do_low_level_stuff();

int low_level_func() {

 std::lock_guard lk(low_level_mutex); ←

 return do_low_level_stuff();

}

void high_level_stuff(int some_param);

void high_level_func() {

 std::lock_guard lk(high_level_mutex); ←

 high_level_stuff(low_level_func());            ←

}

void thread_a() { ←

 high_level_func();

}

hierarchical_mutex other_mutex(100); ←

void do_other_stuff();

void other_stuff() {

 high_level_func(); ←

 do_other_stuff();

}

void thread_b() { ←

 std::lock_guard lk(other_mutex); ←

 other_stuff();

}

Поток

thread_a()

thread_b()

thread_a()

high_level_func()

high_level_mutex

low_level_func()

high_level_stuff()

low_level_func()

low_level_mutex

high_level_mutex

С другой стороны, функция

thread_b()

other_mutex

other_stuff()

high_level_func()

high_level_func()

high_level_mutex

hierarchical_mutex

На этом примере демонстрируется еще один момент — использование шаблона

std::lock_guard<>

hierarchical_mutex

std::lock_guard<>

lock()

unlock()

try_lock()

ry_lock()

false

std::lock()

Листинг 3.8. Простая реализация иерархического мьютекса

class hierarchical_mutex {

 std::mutex internal_mutex;

 unsigned long const hierarchy_value;

 unsigned previous_hierarchy_value;

 static thread_local

 unsigned long this_thread_hierarchy_value;←

 void check_for_hierarchy_violation() {

  if (this_thread_hierarchy_value <= hierarchy_value) ←

  {

  throw std::logic_error("mutex hierarchy violated");

  }

 }

 void update_hierarchy_value() {

  previous_hierarchy_value = this_thread_hierarchy_value; ←

  this_thread_hierarchy_value = hierarchy_value;

 }

public:

 explicit hierarchical_mutex(unsigned long value):

  hierarchy_value(value),

  previous_hierarchy_value(0) {}

 void lock() {

  check_for_hierarchy_violation();

  internal_mutex.lock();   ←

  update_hierarchy_value(); ←

 }

 void unlock() {

  this_thread_hierarchy_value = previous_hierarchy_value; ←

  internal_mutex.unlock();

 }

 bool try_lock() {

  check_for_hierarchy_violation();

  if (!internal_mutex.try_lock()) ←

  return false;

  update_hierarchy_value();

  return true;

 }

};

thread_local unsigned long

hierarchical_mutex::this_thread_hierarchy_value(ULONG_MAX);←

Главное здесь — использование значения типа

thread_local

this_thread_hierarchy_value

thread_local

thread_local

Итак, при первом захвате потоком объекта

hierarchical_mutex

this_thread_hierarchy_value

ULONG_MAX

check_for_hierarchy_violation()

lock()

Если теперь попытаться захватить другой объект

hierarchical_mutex

this_thread_hierarchy_value

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

unlock()

internal_mutex

hierarchical_mutex

Функция

try_lock()

lock()

try_lock()

internal_mutex

true

false

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

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

Функция

std::lock()

std::lock_guard

std::unique_lock

std::lock_guard

std::lock_guard

3.2.6. Гибкая блокировка с помощью

std::unique_lock

Шаблон

std::unique_lock

std::lock_guard

std::unique_lock

std::adopt_lock

std::defer_lock

lock()

std::unique_lock

std::lock()

std::unique_lock

std::unique_lock

std::defer_lock()

std::lock_guard

std::adopt_lock

std::unique_lock

std::lock_guard

std::unique_lock

Листинг 3.9. Применение

std::lock()

std::unique_guard

class some_big_object;

void swap(some_big_object& lhs,some_big_object& rhs);

class X {

private:

 some_big_object some_detail;

 std::mutex m;

public:

 X(some_big_object const& sd): some_detail(sd) {}

 friend void swap(X& lhs, X& rhs) {

  if (&lhs == &rhs)          

  return;               

                std::unique_lock lock_a(lhs.m, std::defer_lock);←┤
            

                std::unique_lock lock_b(rhs.m, std::defer_lock);←┘
            

                std::lock(lock_a, lock_b); ←
            

  swap(lhs.some_detail, rhs.some_detail);

 }

};

В листинге 3.9 объекты

std::unique_lock

std::lock()

std::unique_lock

lock()

try_lock()

unlock()

std::unique_lock

unlock()

unlock()

owns_lock()

Естественно, этот флаг необходимо где-то хранить. Поэтому размер объекта

std::unique_lock

std::lock_guard

std::unique_lock

std::lock_guard

std::lock_guard

std::unique_lock

3.2.7. Передача владения мьютексом между контекстами

Поскольку экземпляры

std::unique_lock

std::move()

std::unique_lock

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

get_lock()

std::unique_lock get_lock() {

 extern std::mutex some_mutex;

 std::unique_lock lk(some_mutex);

 prepare_data();

 return lk; ←

}

void process_data() {

 std::unique_lock lk(get_lock()); ←

 do_something();

}

Поскольку

lk

std:move()

process_data()

std::unique_lock

do_something()

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

std::unique_lock

get_lock()

Класс

std::unique_lock

unlock()

std::unique_lock

std::lock

std::unique_lock

3.2.8. Выбор правильной гранулярности блокировки

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

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

Объект

std::unique_lock

unlock()

lock()

void get_and_process_data()

{              ←┘

 std::unique_lock my_lock(the_mutex);

 some_class data_to_process = get_next_data_chunk();

 my_lock.unlock();

 result_type result = process(data_to_process);

 my_lock.lock();            ←┐

 write_result(data_to_process, result);│

}                    

Удерживать мьютекс на время выполнения

process()

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

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

В листингах 3.6 и 3.9 мы захватывали два мьютекса для операции обмела, которая очевидно требует одновременного доступа к обоим объектам. Предположим, однако, что требуется произвести сравнение простых членов данных типа

int

Y

Листинг 3.10. Поочерёдный захват мьютексов в операторе сравнения

class Y {

private:

 int some_detail;

 mutable std::mutex m;

 int get_detail() const {

  std::lock_guard lock_a(m); ←

  return some_detail;

 }

public:

 Y(int sd): some_detail(sd) {}

 friend bool operator==(Y const& lhs, Y const& rhs) {

  if (&lhs == &rhs)

  return true;

  int const lhs_value = lhs.get_detail(); ←

  int const rhs_value = rhs.get_detail(); ←

  return lhs_value == rhs_value; ←

 }

};

В данном случае оператор сравнения сначала получает сравниваемые значения, вызывая функцию-член

get_detail()

true

lhs.some_detail

rhs.some_detail

true

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

std::mutex

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

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

3.3.1. Защита разделяемых данных во время инициализации

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

std::shared_ptr resource_ptr;

void foo() {

 if (!resource_ptr) {

  resource_ptr.reset(new some_resource); ←

 }

 resource_ptr->do_something();

}

Если сам разделяемый ресурс безопасен относительно одновременного доступа, то при переходе к многопоточной реализации единственная нуждающаяся в защите часть — инициализация (1), однако наивный подход, показанный в листинге ниже, может привести к ненужной сериализации использующих ресурс потоков. Дело в том, что каждый поток должен ждать освобождения мьютекса, чтобы проверить, был ли ресурс уже инициализирован.

Листинг 3.11. Потокобезопасная отложенная инициализация с помощью мьютекса

std::shared_ptr resource_ptr;

std::mutex resource_mutex; ←┐

               │

void foo() {

 std::unique_lock lk(resource_mutex);

 if (!resource_ptr) {

  resource_ptr.reset(new some_resource); ←┐

 }                     │

 lk.unlock();               │

 resource_ptr->do_something();

}

Этот код встречается настолько часто, а ненужная сериализация вызывает столько проблем, что многие предпринимали попытки найти более приемлемое решение, в том числе печально известный паттерн блокировка с двойной проверкой (Double-Checked Locking): сначала указатель читается без захвата мьютекса (1) (см. код ниже), а захват производится, только если оказалось, что указатель равен

NULL

void undefined_behaviour_with_double_checked_locking() {

 if (!resource_ptr)           ←

 {

  std::lock_guard lk(resource_mutex);

  if (!resource_ptr)           ←

  {

  resource_ptr.reset(new some_resource);←

  }

 }

 resource_ptr->do_something();      ←

}

«Печально известным» я назвал этот паттерн не без причины: он открывает возможность для крайне неприятного состояния гонки, потому что чтение без мьютекса (1) не синхронизировано с записью в другом потоке с уже захваченным мьютексом (3). Таким образом, возникает гонка, угрожающая не самому указателю, а объекту, на который он указывает; даже если один поток видит, что указатель инициализирован другим потоком, он может не увидеть вновь созданного объекта

some_resource

do_something()

Комитет по стандартизации С++ счел этот случай достаточно важным, поэтому в стандартную библиотеку включен класс

std::once_flag

std::call_once

std::call_once

std::call_once

std::call_once

std::call_once

std::shared_ptr resource_ptr;

std::once_flag resource_flag;←

void init_resource() {

 resource_ptr.reset(new some_resource);

}

       │

void foo() { ←┘

 std::call_once(resource_flag, init_resource);

 resource_ptr->do_something();

}

Здесь переменная типа

std::once_flag

std::call_once()

Листинг 3.12. Потокобезопасная отложенная инициализация члена класса с помощью функции

std::call_once()

class X {

private:

 connection_infо connection_details;

 connection_handle connection;

 std::once_flag connection_init_flag;

 void open_connection() {

  connection = connection_manager.open(connection_details);

 }

public:

 X(connection_info const& connection_details_):

  connection_details(connection_details_) {}

 void send_data(data_packet const& data)←

 {

  std::call_once(

  connection_init_flag, &X::open_connection, this);←┐

  connection.send_data(data);            │

 }                          │

 data_packet receive_data() { ←

  std::call_once(                   │

  connection_init_flag, &X::open_connection, 2)  

  this);                      ←┘

  return connection.receive_data();

 }

};

В этом примере инициализация производится либо при первом обращении к

send_data()

receive_data()

open_connection()

this

std::thread

std::bind()

std::call_once()

Следует отметить, что, как и в случае

std:mutex

std::once_flag

Возможность гонки при инициализации возникает, в частности, при объявлении локальной переменной с классом памяти

static

std::call_once

class my_class;

 my_class& get_my_class_instance() {

 static my_class instance; ←┐

 return instance;     

}

Теперь несколько потоков могут вызывать функцию

get_my_class_instance()

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

3.3.2. Защита редко обновляемых структур данных

Рассмотрим таблицу, в которой хранится кэш записей DNS, необходимых для установления соответствия между доменными именами и IP-адресами. Как правило, записи DNS остаются неизменными в течение длительного времени — зачастую многих лет. Новые записи, конечно, добавляются — скажем, когда открывается новый сайт — но на протяжении всей своей жизни обычно не меняются. Периодически необходимо проверять достоверность данных в кэше, но и тогда обновление требуется, лишь если данные действительно изменились.

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

Использование

std::mutex

В новой стандартной библиотеке С++ такой мьютекс не предусмотрен, хотя комитету и было подано предложение[6]. Поэтому в этом разделе мы будем пользоваться реализацией из библиотеки Boost, которая основана на отвергнутом предложении. В главе 8 вы увидите, что использование такого мьютекса — не панацея, а его производительность зависит от количества участвующих процессоров и относительного распределения нагрузки между читателями и писателями. Поэтому важно профилировать работу программу в целевой системе и убедиться, что добавочная сложность действительно дает какой-то выигрыш.

Итак, вместо

std::mutex

boost::shared_mutex

std::lock_guard

std::unique_lock

boost::shared_mutex

std::mutex

boost::shared_lock

std::unique_lock

boost::shared_mutex

В листинге ниже приведена реализация простого DNS-кэша, в котором данные хранятся в контейнере

std::map

boost::shared_mutex

Листинг 3.13. Защита структуры данных с помощью

boost::shared_mutex

#include 

#include 

#include 

#include 

class dns_entry;

class dns_cache {

 std::map entries;

 mutable boost::shared_mutex entry_mutex;

public:

 dns_entry find_entry(std::string const& domain) const {

  boost::shared_lock lk(entry_mutex); ←

  std::map::const_iterator const it =

  entries.find(domain);

  return (it == entries.end()) ? dns_entry() : it->second;

 }

 void update_or_add_entry(std::string const& domain,

  dns_entry const& dns_details) {

  std::lock_guard lk(entry_mutex); ←

  entries[domain] = dns_details;

 }

};

В листинге 3.13 в функции

find_entry()

boost::shared_lock<>

update_or_add_entry()

std::lock_guard<>

update_or_add_entry()

find_entry()

3.3.3. Рекурсивная блокировка

Попытка захватить

std::mutex

std::recursive_mutex

std::mutex

lock()

std::lock_guard

std::unique_lock

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

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