Такой способ «передачи из рук в руки» позволяет нескольким потокам одновременно обходить список при условии, что разные потоки обращаются к разным узлам. Но чтобы предотвратить взаимоблокировку, узлы следует обходить в одном и том же порядке; если один поток обходит список в одном направлении, а другой в противоположном, то при передаче мьютексов «из рук в руки» в середине списка может произойти взаимоблокировка. Если узлы А и В соседние, то поток, который обходит список в прямом направлении, попытается захватить мьютекс В, удерживая мьютекс А. В то же время поток, который обходит список в обратном направлении, попытается захватить мьютекс А, удерживая мьютекс В. Вот мы и получили классическую взаимоблокировку.
Рассмотрим еще ситуацию удаления узла В, расположенного между А и С. Если поток захватывает мьютекс В раньше, чем мьютексы А и С, то возможна взаимоблокировка с потоком, который обходит список. Такой поток попытается сначала захватить мьютекс А или С (в зависимости от направления обхода), но потом обнаружит, что не может захватить мьютекс В, потому что поток, выполняющий удаление, удерживает этот мьютекс, пытаясь в то же время захватить мьютексы А и С.
Предотвратить в этом случае взаимоблокировку можно, определив порядок обхода, так что поток всегда должен захватывать мьютекс А раньше мьютекса В, а мьютекс В раньше мьютекса С. Это устранило бы возможность взаимоблокировки, но ценой запрета обхода в обратном направлении. Подобные соглашения можно принять и для других структур данных.
Являясь частным случаем фиксированного порядка захвата мьютексов, иерархия блокировок в то же время позволяет проверить соблюдение данного соглашения во время выполнения. Идея в том, чтобы разбить приложение на отдельные слои и выявить все мьютексы, которые могут быть захвачены в каждом слое. Программе будет отказано в попытке захватить мьютекс, если она уже удерживает какой-то мьютекс из нижележащего слоя. Чтобы проверить это во время выполнения, следует приписать каждому мьютексу номер слоя и вести учет мьютексам, захваченным каждым потоком. В следующем листинге приведен пример двух потоков, пользующихся иерархическим мьютексом.
Листинг 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(3)
return do_low_level_stuff();
}
void high_level_stuff(int some_param);
void high_level_func() {
std::lock_guard(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(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.
