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

Блокировки

Теперь давайте рассмотрим более сложный пример конкуренции за ресурсы, который требует более сложного решения. Допустим, что у нас есть очередь запросов, которые должны быть обработаны. Как реализована очередь — не существенно, но мы будем считать, что это — связанный список, в котором каждый узел соответствует одному запросу. Очередью управляют две функции: одна— добавляет новый запрос в конец очереди, а другая — извлекает запрос из головы очереди и делает с ним нечто полезное. Различные части ядра вызывают обе эти функции, поэтому запросы могут постоянно поступать, удаляться и обрабатываться. Все манипуляции очередью запросов, конечно, требуют нескольких инструкций. Если один из потоков пытается считывать данные из очереди, а другой поток находится в средине процесса манипуляции очередью, то считывающий поток обнаружит, что очередь находится в несогласованном состоянии. Легко понять, что при конкурентном обращении к очереди может произойти разрушение структуры данных. Часто ресурс общего доступа — это сложная структура данных, и в результате состояния конкуренции возникает разрушение этой структуры.

Вначале кажется, что описанная ситуация не имеет простого решения. Как можно предотвратить чтение очереди на одном процессоре в тот момент, когда другой процессор обновляет ее? Вполне логично аппаратно реализовать простые инструкции, такие как атомарные арифметические операции или операции сравнения, тем не менее было бы смешно аппаратно реализовывать критические участки неопределенного размера, как в приведенном примере. Все что нужно — это предоставить метод, который позволяет отметить начало и конец; критического участка, и предотвратить или заблокировать (lock) доступ к этому участку, пока другой поток выполняет его.

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

В приведенном выше примере очереди запросов для защиты очереди может использоваться одна блокировка. Как только необходимо добавить запрос в очередь, поток должен вначале захватить блокировку. Затем он может безопасно добавить запрос в очередь и после этого освободить блокировку. Если потоку необходимо извлечь запрос из очереди, он тоже должен захватить блокировку. После этого он может прочитать запрос и удалить его из очереди. В конце поток освобождает блокировку. Любому другому потоку для доступа к очереди также необходимо аналогичным образом захватывать блокировку. Так как захваченная блокировка может удерживаться только одним потоком в любой момент времени, то только один поток может производить манипуляции с очередью в любой момент времени. Блокировка позволяет предотвратить конкуренцию и защитить очередь от состояния конкуренции за ресурс.

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

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

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

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

Блокировки бывают различных "форм" и "размеров". В операционной системе Linux реализовано несколько различных механизмов блокировок. Наиболее существенная разница между ними — это поведение кода в условиях, когда блокировка захватывается (конфликт при захвате блокировки, contended lock). Для некоторых типов блокировок, задания просто ожидают освобождения блокировки, постоянно выполняя проверку освобождения в замкнутом цикле (busy wait[44]), в то время как другие тины блокировок переводят задание в состояние ожидания до тех пор, пока блокировка не освободится.

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

Проницательный читатель в этом месте должен воскликнуть: "Блокировки не решают проблемы, они просто сужают набор всех возможных критических участков до кода захвата и освобождения блокировок. Тем не менее, здесь потенциально может возникать состояние конкуренции за ресурсы, хотя и с меньшими последствиями!" К счастью, блокировки реализованы на основе атомарных операций, которые гарантируют, что состояние конкуренции за ресурсы не возникнет. С помощью одной машинной инструкции выполняется проверка захвачен ли ключ, и, если нет, то этот ключ захватывается. То, как это делается, очень сильно зависит от аппаратной платформы, но почти для всех процессоров определяется машинная инструкция test-and-set (проверить и установить), которая позволяет проверить значение целочисленной переменной и присвоить этой переменной указанное число, если се значение равно нулю. Значение нуль соответствует незахваченной блокировке.

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