Идея проста — не захватывайте мьютекс, если уже захватили какой-то другой. Если строго придерживаться этой рекомендации, то взаимоблокировка, обусловленная одними лишь захватами мьютексов, никогда не возникнет, потому что каждый поток в любой момент времени владеет не более чем одним мьютексом. Конечно, можно получить взаимоблокировку по другим причинам (например, из-за взаимного ожидания потоков), но захват мьютексов — наиболее распространенная. Если требуется захватить сразу несколько мьютексов, делайте это атомарно с помощью std::lock, так вы сможете избежать взаимоблокировки.
По существу, это простое развитие предыдущей рекомендации. Поскольку код написан пользователем, вы не можете знать, что он делает. А делать он может все, что угодно, в том числе захватывать мьютекс. Если вы вызываете пользовательский код, не освободив предварительно мьютекс, а этот код захватывает какой-то мьютекс, то оказывается нарушена рекомендация избегать вложенных блокировок, и может возникнуть взаимоблокировка. Иногда избежать этого невозможно: если вы пишете обобщенный код, например класс стека из раздела 3.2.3, то каждая операция над типом или типами параметров — не что иное, как пользовательский код. В таком случае прислушайтесь к следующему совету.
Если без захвата нескольких мьютексов никак не обойтись и захватить их в одной операции типа std::lock не получается, то следует прибегнуть к другому способу — захватывать их во всех потоках в одном и том же порядке. Мы уже говорили об этом в разделе 3.2.4, как о способе избежать взаимоблокировки при захвате двух мьютексов; идея в том, чтобы четко определить порядок захвата и соблюдать его во всех потоках. Иногда это сравнительно просто. Например, в случае стека из раздела 3.2.3 мьютекс хранится в каждом экземпляре стека, но для операций над хранящимися в стеке элементами необходимо вызывать пользовательский код. Однако можно добавить ограничение: никакая операция над хранящимися в стеке данными не должна производить какие-либо действия с самим стеком. Это возлагает определенную ответственность на пользователя стека, но на практике редко бывает, чтобы хранящимся в контейнере данным нужно было обращаться к самому контейнеру, а если такое и случается, то сразу видно. Поэтому бремя ответственности не слишком тяжело.
Но не всегда всё так просто, и пример мы видели при рассмотрении оператора сравнения в разделе 3.2.4. В этом конкретном случае есть возможность захватить мьютексы одновременно, но так бывает не всегда. Пример связанного списка из раздела 3.1 дает еще один способ защитить список — хранить мьютекс в каждом узле. Тогда, чтобы получить доступ к списку, поток должен будет захватить мьютекс для каждого интересующего его узла. Так, чтобы удалить элемент, надо будет захватить мьютексы трех узлов — удаляемого, предшествующего и последующего, — постольку все они так или иначе модифицируются. Аналогично для обхода списка поток должен удерживать мьютекс текущего узла, пока не захватит мьютекс следующего за ним; это гарантирует, что никто не может изменить указатель на следующий узел. Захватив мьютекс следующего узла, можно освободить мьютекс текущего, так как больше он не понадобится.
Такой способ «передачи из рук в руки» позволяет нескольким потокам одновременно обходить список при условии, что разные потоки обращаются к разным узлам. Но чтобы предотвратить взаимоблокировку, узлы следует обходить в одном и том же порядке; если один поток обходит список в одном направлении, а другой в противоположном, то при передаче мьютексов «из рук в руки» в середине списка может произойти взаимоблокировка. Если узлы А и В соседние, то поток, который обходит список в прямом направлении, попытается захватить мьютекс В, удерживая мьютекс А. В то же время поток, который обходит список в обратном направлении, попытается захватить мьютекс А, удерживая мьютекс В. Вот мы и получили классическую взаимоблокировку.
Рассмотрим еще ситуацию удаления узла В, расположенного между А и С. Если поток захватывает мьютекс В раньше, чем мьютексы А и С, то возможна взаимоблокировка с потоком, который обходит список. Такой поток попытается сначала захватить мьютекс А или С (в зависимости от направления обхода), но потом обнаружит, что не может захватить мьютекс В, потому что поток, выполняющий удаление, удерживает этот мьютекс, пытаясь в то же время захватить мьютексы А и С.