Разработка ядра Linux - Роберт Лав

Код, который безопасно выполнять параллельно с обработчиком прерывания, называется безопасным при прерываниях (interrupt-safe). Код, который содержит защиту от конкурентного доступа к ресурсам при симметричной многопроцессорной обработке, называется безопасным при SMP-обработке (SMP-safe). Код, который имеет защиту от конкурентного доступа к ресурсам при вытеснении кода ядра, называется безопасным при вытеснения[45] (preempt-safe). Механизмы, которые во всех этих случаях используются для обеспечения синхронизации и защиты от состояний конкуренции, будут рассмотрены в следующей главе.

Что требует защиты

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

Что же тогда требует применения блокировок? Это — большинство глобальных структур данных ядра. Есть хорошее эмпирическое правило: если, кроме одного, еще и другой поток может обращаться к данным, то эти данные требуют применения какого-либо типа блокировок. Если что-то видно кому-то еще — блокируйте его. Помните, что блокировать необходимо данные, а не код.

Так как ядро операционной системы Linux может быть сконфигурировано на этапе компиляции, имеет смысл "подогнать" ядро под данный тип машины. Важной функцией ядра является поддержка симметричной многопроцессорной обработки (SMP), которая включается с помощью параметра конфигурации ядра CONFIG_SMP. На однопроцессорной (uniprocessor, UP) машине исчезают многие проблемы, связанные с блокировками, и, следовательно, если параметр CONFIG_SMP не установлен, то код, в котором нет необходимости, не компилируется в исполняемый образ ядра. Например, это позволяет на однопроцессорной машине отказаться от накладных расходов, связанных со спин-блокировками. Аналогичный прием используется для параметра CONFIG_PREEMPT (параметр ядра, который указывает, будет ли ядро вытесняемым). Такое решение является отличным проектным решение, поскольку позволяет использовать общий четкий исходный код, а различные механизмы блокировок используются при необходимости. Различные комбинации параметров CONFIG_SMP и CONFIG_PREEMPT на различных аппаратных платформах позволяют компилировать в ядро различные механизмы блокировок.

При написании кода необходимо обеспечить все возможные варианты защиты для всех возможных случаев жизни и всех возможных сценариев, которые будут рассмотрены.

При написании кода ядра следует задать себе следующие вопросы.

• Являются ли данные глобальными? Может ли другой поток выполнения, кроме текущего, обращаться к этим данным?

• Являются ли данные совместно используемыми из контекста процесса и из контекста прерывания? Используют ли их совместно два обработчика прерываний?

• Если процесс во время доступа к данным будет вытеснен, может ли новый процесс, который запланирован на выполнение, обращаться к этим же данным?

• Может ли текущий процесс перейти в состояние ожидания (заблокироваться) на какой-либо операции? Если да, то в каком состоянии он оставляет все совместно используемые данные?

• Что запрещает освободить память, в которой находятся данные?

• Что произойдет, если эта же функция будет вызвана на другом процессоре?

• Как все это учесть?

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

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

Взаимоблокировка (тупиковая ситуация, 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