Разработка ядра Linux

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

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

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

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

Откуда берется параллелизм

При работе в пространстве пользователя необходимость синхронизации возникает из того факта, что программы выполняются преемптивно, т.е. могут быть вытеснены другой программой по воле планировщика. Поскольку процесс может быть вытеснен в любой момент и другой процесс может быть запущен планировщиком для выполнения на этом же процессоре, появляется возможность того, что процесс может быть вытеснен независящим от него образом во время выполнения критического участка. Если новый, запланированный на выполнение процесс входит в тот же критический участок (скажем, если оба процесса — потоки одной программы, которые могут обращаться к общей памяти), то может возникнуть состояние конкуренции за ресурс. Аналогичная проблема может возникнуть даже в однопоточной программе при использовании сигналов, так как сигналы приходят асинхронно. Такой тип параллелизма, когда два события происходят не одновременно, а накладываются друг на друга, так вроде они происходят в один момент времени, называется псевдопараллелизмом (pseudo-concurrency).

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

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

• Отложенные прерывания и тасклеты. Ядро может выполнять обработчики softirq и тасклеты практически в любой момент времени и прерывать код, который выполняется в данный момент времени.

• Преемптивность ядра. Так как ядро является вытесняемым, то одно задание, которое работает в режиме ядра, может вытеснить другое задание, тоже работающее в пространстве ядра.

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

• Симметричная многопроцессорность. Два или больше процессоров могут выполнять код в один и тот же момент времени.