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