Книга: Разработка ядра Linux

Взаимоблокировки

Взаимоблокировки

Взаимоблокировка (тупиковая ситуация, deadlock) — это состояние, при котором каждый поток ожидает на освобождение одного из ресурсов, а все ресурсы при этом захвачены. Потоки будут ожидать друг друга, и они никогда не смогут освободить захваченные ресурсы. Поэтому ни один из потоков не сможет продолжать выполнение, что означает наличие взаимоблокировки.

Хорошая аналогия — это перекресток, на котором стоят четыре машины, которые подъехали с четырех разных сторон. Каждая машина ожидает, пока не уедут остальные машины, и ни одна из машин не сможет уехать; в результате получается тупиковая ситуация.

Самый простой пример взаимоблокировки— это самоблокировка[46] (self-deadlock). Если поток выполнения пытается захватить ту блокировку, которую он уже удерживает, то ему необходимо дождаться, пока блокировка не будет освобождена. Но поток никогда не освободит блокировку, потому что он ожидает на ее захват, и это приводит к тупиковой ситуации.

захватить блокировку
захватить блокировку еще раз
ждать, пока блокировка не будет освобождена
...

Аналогично рассмотрим n потоков и n блокировок. Если каждый поток удерживает блокировку, на которую ожидает другой поток, то все потоки будут заблокированы до тех пор, пока не освободятся те блокировки, на освобождение которых ожидают потоки. Наиболее часто встречающийся пример — это два потока и две блокировки, что часто называется взаимоблокировка типа ABBA (ABBA deadlock).

Поток 1                                                                Поток 2

захватить блокировку А             захватить блокировку В
попытка захватить блокировку В     попытка захватить блокировку А
ожидание освобождения блокировки В ожидание освобождения блокировки А

Оба потока будут ожидать друг друга, и ни один из потоков никогда не освободит первоначально захваченной блокировки, поэтому ни одна из блокировок не будет освобождена. Такая тупиковая ситуация еще называется deadly embrace (буквально. смертельные объятия).

Важно не допустить появление взаимоблокировок. Хотя сложно проверить готовый код на наличие взаимоблокировок, можно написать код, который не содержит взаимоблокировок. Такую возможность дает соблюдение нескольких простых правил.

• Жизненно важным является порядок захвата блокировок. Вложенные блокировки всегда должны захватываться в одном и том же порядке. Это предотвращает взаимоблокировку нескольких потоков (deadly embrace). Порядок захвата блокировок необходимо документировать, чтобы другие тоже могли его соблюдать.

• Необходимо предотвращать зависания. Следует спросить себя: "Всегда ли этот код сможет завершиться?". Если не выполнится какое-либо условие, то не будет ли что-то ожидать вечно?

• Не захватывать одну и ту же блокировку дважды.

• Сложность в схеме блокировок — верный путь к тупиковым ситуациям, поэтому при разработке необходимо стремиться к простоте.

Первый пункт важный и наименее сложный для выполнения. Если две или более блокировок захватываются в одном месте, то они всегда должны захватываться в строго определенном порядке. Допустим, у нас есть три блокировки cat, dog и fox, которые используются для защиты данных с такими же именами. И еще допустим, что у нас есть функция, которая должна работать с этими тремя структурами данных одновременно— например, может копировать данные между ними. В любом случае, для того чтобы гарантировать безопасность доступа, эти структуры данных необходимо защищать блокировками. Если одна функция захватывает эти блокировки в следующем порядке: cat, dog и в конце fox, то любая другая функция должна захватывать эти блокировки (или только некоторые из них) в том же порядке. Например, если захватывать сначала блокировку fox, а потом блокировку dog, то это потенциальная возможность взаимоблокировки (а значит, ошибки в работе), потому что блокировка dog всегда должна захватываться перед блокировкой fox. И еще раз рассмотрим пример, как может возникнуть взаимоблокировка.

Поток 1                                                                   Поток 2

захватить блокировку cat             захватить блокировку fox
захватить блокировку dog             попытка захватить блокировку dog
попытка захватить блокировку fox     ожидание освобождения блокировки dog
ожидание освобождения блокировки fox —
Поток 1 ожидает освобождения блокировки fox, которую удерживает поток 2, а поток 2 в это время ожидает освобождения блокировки dog, которую удерживает поток 1. Ни один из потоков никогда не освободит своих блокировок, и, соответственно, оба потока будут ждать вечно — возникает тупиковая ситуация. Если оба потока всегда захватывают блокировки в одном и том же порядке, то подобной тупиковой ситуации возникнуть не может.

Если несколько процедур захвата блокировок вложены друг в друга, то должен быть принят определенный порядок захвата. Хорошая практика — всегда использовать комментарий сразу перед объявлением блокировки, который указывает на порядок захвата. Использовать что-нибудь вроде следующего будет хорошей идеей.

/*
* cat_lock - всегда захватывать перед блокировкой dog
* (и всегда захватывать блокировку dog перед блокировкой fox)
*/

Следует заметить, что порядок освобождения блокировок не влияет на возможность появления взаимоблокировок, хотя освобождать блокировки в обратном порядке по отношению к их захвату — это хорошая привычка.

Очень важно предотвращать взаимоблокировки. В ядре Linux есть некоторые отладочные возможности, которые позволяют обнаруживать взаимоблокировки при выполнении кода ядра. Эти возможности будут рассмотрены в следующем разделе.

Оглавление книги