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

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

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

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

Пользуйтесь иерархией блокировок

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

Листинг 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.