Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Если без захвата нескольких мьютексов никак не обойтись и захватить их в одной операции типа std::lockне получается, то следует прибегнуть к другому способу — захватывать их во всех потоках в одном и том же порядке. Мы уже говорили об этом в разделе 3.2.4, как о способе избежать взаимоблокировки при захвате двух мьютексов; идея в том, чтобы четко определить порядок захвата и соблюдать его во всех потоках. Иногда это сравнительно просто. Например, в случае стека из раздела 3.2.3 мьютекс хранится в каждом экземпляре стека, но для операций над хранящимися в стеке элементами необходимо вызывать пользовательский код. Однако можно добавить ограничение: никакая операция над хранящимися в стеке данными не должна производить какие-либо действия с самим стеком. Это возлагает определенную ответственность на пользователя стека, но на практике редко бывает, чтобы хранящимся в контейнере данным нужно было обращаться к самому контейнеру, а если такое и случается, то сразу видно. Поэтому бремя ответственности не слишком тяжело.

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

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

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

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

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

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

hierarchical_mutex high_level_mutex(10000); ← (1)

hierarchical_mutex low_level_mutex(5000); ← (2)

int do_low_level_stuff();

int low_level_func() {

std::lock_guard lk(low_level_mutex); ← (3)

return do_low_level_stuff();

}

void high_level_stuff(int some_param);

void high_level_func() {

std::lock_guard lk(high_level_mutex); ← (4)

high_level_stuff(low_level_func()); ← (5)

}

void thread_a() { ← (6)

high_level_func();

}

hierarchical_mutex other_mutex(100); ← (7)

void do_other_stuff();

void other_stuff() {

high_level_func(); ← (8)

do_other_stuff();

}

void thread_b() { ← (9)

std::lock_guard lk(other_mutex); ← (10)

other_stuff();

}

Поток thread_a() (6)соблюдает правила и выполняется беспрепятственно. Напротив, поток thread_b() (9)нарушает правила, поэтому во время выполнения столкнется с трудностями. Функция thread_a()вызывает high_level_func(), которая захватывает мьютекс high_level_mutex (4)(со значением уровня иерархии 10000 (1)), а затем вызывает low_level_func() (5)(мьютекс в этот момент уже захвачен), чтобы получить параметр, необходимый функции high_level_stuff(). Далее функция low_level_func()захватывает мьютекс low_level_mutex (3), и в этом нет ничего плохого, так как уровень иерархии для него равен 5000 (2), то есть меньше, чем для high_level_mutex.

С другой стороны, функция thread_b()некорректна. Первым делом она захватывает мьютекс other_mutex (10), для которого уровень иерархии равен всего 100 (7). Это означает, что мьютекс призван защищать только данные очень низкого уровня. Следовательно, когда функция other_stuff()вызывает high_level_func() (8), она нарушает иерархию — high_level_func()пытается захватить мьютекс high_level_mutex, уровень иерархии которого (10000) намного больше текущего уровня иерархии 100. Поэтому hierarchical_mutexсообщит об ошибке, возбудив исключение или аварийно завершив программу. Таким образом, взаимоблокировки между иерархическими мьютексами невозможны, так как они сами следят за порядком захвата. Это означает, что программа не может удерживать одновременно два мьютекса, находящихся на одном уровне иерархии, поэтому в схемах «передачи из рук в руки» требуется, чтобы каждый мьютекс в цепочке имел меньшее значение уровня иерархии, чем предыдущий, — на практике удовлетворить такому требованию не всегда возможно.