Параллелизм и блокировка

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

Параллелизм может встречаться на однопроцессорных рабочих станциях, где несколько потоков используют один и тот же процессор, вытесняя друг друга и создавая ситуацию гонки. Вытеснением называется прозрачное совместное использование процессора путем временной приостановки одного потока для обеспечения возможности выполнения другого. Ситуация гонки - это ситуация, когда два или более потока управляют одними и теми же данными и результат зависит от порядка выполнения. Параллелизм также существует на многопроцессорных машинах, где одновременно выполняемые потоки разных процессоров используют одни и те же данные. Обратите внимание, что в случае многопроцессорных систем имеет место истинный параллелизм, поскольку потоки выполняются одновременно. В случае однопроцессорной системы параллелизм создаётся механизмом вытеснения. В обоих режимах параллелизма имеются свои сложности.

Ядро Linux поддерживает параллелизм в обоих вариантах. Ядро само по себе динамично, и ситуации гонки могут возникать в различных случаях. Ядро Linux также поддерживает многопроцессорный режим, известный как симметричная многопроцессорность (SMP). Подробнее узнать об SMP можно из литературы, ссылки на которую имеются в разделе Ресурсы .

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

Однако с критическими секциями связана проблема тупиковой взаимной блокировки. Рассмотрим две отдельные критические секции, каждая из которых защищает свой ресурс. Каждый ресурс имеет свою блокировку; назовем их A и B. Рассмотрим два потока, которым необходим доступ к нашим ресурсам. Поток X захватывает блокировку A, а поток Y - блокировку B. Пока эти блокировки удерживаются, каждый из потоков пытается захватить блокировку, удерживаемую другим потоком (поток X пытается захватить блокировку B, а поток Y – блокировку A). Теперь потоки находятся в тупиковой ситуации, поскольку каждый из них блокирует нужный другому ресурс. Простое решение состоит в том, чтобы всегда захватывать блокировки в одном и том же порядке, что позволяет завершить работу потока. Другое решение состоит в обнаружении таких ситуаций. В таблице 1 определены наиболее важные обсуждаемые здесь понятия из области параллелизма.

Теперь, когда мы немного ознакомились с теорией и поняли, какую проблему предстоит решать, давайте рассмотрим различные способы реализации параллельного исполнения и взаимных исключений в Linux. Раньше обработка взаимных исключений выполнялась путем отключения прерываний, но такая блокировка неэффективна (хотя её следы еще можно найти в ядре). Кроме того, этот метод не очень хорошо масштабируется и не гарантирует взаимное исключение на других процессорах.

В приведенном ниже обзоре механизмов блокировки мы сначала рассмотрим атомарные операции, которые обеспечивают защиту простых переменных (счетчиков и битовых масок). После этого рассматриваются простые взаимные блокировки (спинлоки) и взаимные блокировки чтения и записи в качестве эффективного механизма активного ожидания блокировок для архитектур SMP. И, наконец, мы рассмотрим взаимные исключения (мьютексы) ядра, которые построены на атомарном API.

Простейшим средством синхронизации ядра Linux являются атомарные операции. Атомарность означает, что критическая секция содержится внутри функции API. Необходимость в блокировке отсутствует, поскольку она подразумевается в вызове. Учитывая, что язык C не может гарантировать атомарности операций, Linux использует для этого архитектуру более низкого уровня. Поскольку архитектуры могут различаться в значительной степени, существуют различные реализации атомарных функций. Некоторые из них выполнены почти полностью на ассемблере, тогда как другие прибегают к помощи C и отключению прерываний с помощью local_irq_save и local_irq_restore.

Старые методы блокировки Плохим способом реализации блокировки в ядре является отключение аппаратных прерываний локального процессора. Такие функции существуют и используются (иногда атомарными операторами), но не рекомендуются. Процедура local_irq_save отключает прерывания, а local_irq_restore восстанавливает ранее отключенные прерывания. Эти процедуры являются реентерабельными , то есть они могут вызываться в контексте друг друга.

Атомарные операторы идеальны для ситуаций, в которых защищаемые данные просты, например, как счетчик. При всей своей простоте атомарный API предоставляет целый ряд операторов для различных ситуаций. Рассмотрим пример использования этого API.

Чтобы объявить атомарную переменную, мы просто объявляем переменную типа atomic_t. В этой структуре содержится один элемент int. После этого надо проследить за тем, чтобы наша атомарная переменная инициализировалась с помощью символьной константы ATOMIC_INIT. В случае, показанном в листинге 1, атомарному счетчику присваивается значение ноль. Кроме того, можно инициализировать атомарную переменную в процессе работы с помощью atomic_set function.

 
atomic_t my_counter ATOMIC_INIT(0);

... или ...

 atomic_set( &my_counter, 0 );
 

Атомарный API поддерживает множество функций, охватывающих много вариантов применения. Мы можем прочесть содержимое атомарной переменной с помощью atomic_read и добавить к ней определенное значение с помощью atomic_add. Наиболее распространенная операция - простое приращение переменной, реализуемое посредством atomic_inc. Также имеются операторы вычитания, предоставляющие операции, обратные сложению и приращению. В листинге 2 продемонстрировано использование этих функций.

 
val = atomic_read( &my_counter );

 atomic_add( 1, &my_counter );

 atomic_inc( &my_counter );

 atomic_sub( 1, &my_counter );

 atomic_dec( &my_counter );
 

API-интерфейс также поддерживает ряд других распространенных сценариев использования, в том числе функции выполнения и проверки. Они позволяют управлять атомарной переменной и после этого проверять её значение (всё это выполняется в рамках одной атомарной операции). Специальная функция atomic_add_negative выполняет приращение атомарной переменной и возвращает истину, если возвращаемое значение отрицательно. Она используется некоторыми архитектурно-зависимыми функциями семафоров ядра.

Хотя многие из этих функций не имеют возвращаемых значений, две из них выполняют операцию и возвращают получившееся значение (atomic_add_return и atomic_sub_return), как показано в листинге 3.

 
if (atomic_sub_and_test( 1, &my_counter )) {
 // my_counter равен нулю
}

if (atomic_dec_and_test( &my_counter )) {
 // my_counter равен нулю
}

if (atomic_inc_and_test( &my_counter )) {
 // my_counter равен нулю
}

if (atomic_add_negative( 1, &my_counter )) {
 // my_counter меньше нуля
}

val = atomic_add_return( 1, &my_counter ));

val = atomic_sub_return( 1, &my_counter ));
 

Если архитектура поддерживает 64-разрядные типы long (BITS_PER_LONG равно 64), становятся доступны операции long_t atomic. Перечень реализованных операций типа long можно найти в linux/include/asm-generic/atomic.h.

Атомарный API также поддерживает операции битовых масок. Помимо арифметических операций (которые обсуждались выше) имеются операции установки (set) и очистки (clear). Атомарные операции используются многими драйверами, в частности, драйверами SCSI. Использование атомарных операций битовых масок слегка отличается от арифметических операций, поскольку здесь доступны только две операции (установить или очистить маску). Входными параметрами являются числовое значение и битовая маска, с которой будет выполняться операция, как показано в листинге 4.

 
unsigned long my_bitmask;

 atomic_clear_mask( 0, &my_bitmask );

 atomic_set_mask( (1<<24), &my_bitmask );

 

Прототипы атомарных API Реализация атомарных операций зависит от архитектуры, поэтому она находится в ./linux/include/asm-<arch>/atomic.h.

Взаимные блокировки

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

На самом деле взаимные блокировки полезны только в системах с SMP, но поскольку ваш код однажды будет запускаться и на SMP-системах, разумно вводить их и в однопроцессорные системы.

Взаимные блокировки бывают двух видов: полные блокировки и блокировки на запись и чтение. Рассмотрим сначала полные блокировки.

Для начала создадим новую взаимную блокировку посредством простого объявления. Ее можно инициализировать сразу же или с помощью вызова spin_lock_init. Все варианты, представленные в листинге 5, приводят к одинаковому результату.

 
spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

... или ...

 DEFINE_SPINLOCK( my_spinlock );

... или ...

 spin_lock_init( &my_spinlock );
 

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

Первый вариант, spin_lock и spin_unlock, показан в листинге 6. Это самый простой вариант; он не использует отключение прерываний, но устанавливает полные барьеры памяти. Этот вариант не предполагает взаимодействия обработчиков прерываний и блокировки.

 
 spin_lock( &my_spinlock );

// критическая секция

 spin_unlock( &my_spinlock );
 

Следующая пара, irqsave и irqrestore, показана в листинге 7. Функция spin_lock_irqsave захватывает взаимную блокировку и отключает прерывания локального процессора (в случае SMP). Функция spin_unlock_irqrestore захватывает взаимную блокировку и восстанавливает прерывания (через аргумент flags).

 
 spin_lock_irqsave( &my_spinlock, flags );

// критическая секция

 spin_unlock_irqrestore( &my_spinlock, flags );
 

Менее безопасный вариант spin_lock_irqsave/spin_unlock_irqrestore - это spin_lock_irq/spin_unlock_irq. Я рекомендую избегать этого варианта, поскольку он опирается на предположения о состоянии прерываний.

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

 
 spin_lock_bh( &my_spinlock );

// критическая секция

 spin_unlock_bh( &my_spinlock );
 

В большинстве случаев доступ к данным характеризуется большим числом читающих процессов и меньшим числом пишущих (доступ к данным для чтения более распространен, чем доступ для записи). Для поддержки такой модели были созданы взаимные блокировки чтения/записи. В этой модели интересно то, что одновременно разрешается доступ к данным нескольким операциям считывания и только одной операции записи. Если блокировка установлена пишущим процессом, чтение в критической секции не допускается. Если блокировка установлена читающим процессом, в критической секции допускается несколько операций чтения. Эта модель показана в листинге 9.

 
rwlock_t my_rwlock;

 rwlock_init( &my_rwlock );

 write_lock( &my_rwlock );

// критическая секция -- разрешено чтение и запись

 write_unlock( &my_rwlock );


 read_lock( &my_rwlock );

// критическая секция -- разрешено только чтение

 read_unlock( &my_rwlock );
 

Для различных ситуаций, в которых может потребоваться блокировка, существуют варианты взаимных блокировок чтения и записи для сохранения запросов прерываний (IRQ) и нижних половин. Очевидно, если необходимая вам блокировка по своей природе связана с чтением и записью, следует использовать такую взаимную блокировку вместо стандартной, которая не делает различия между операциями чтения и записи.

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

Мьютексы создаются и инициализируются в одной операции с помощью макроса DEFINE_MUTEX. Он создаёт новый мьютекс и инициализирует его структуру. Эту реализацию можно найти в ./linux/include/linux/mutex.h.

 DEFINE_MUTEX( my_mutex );
 

В API-интерфейсе мьютексов реализовано пять функций: три используются для блокировки, одна для снятия блокировки и ещё одна для проверки мьютекса. Рассмотрим сначала функции блокировки. Первая функция, mutex_trylock, используется в случаях, когда блокировка вам нужна немедленно или вы хотите получить контроль обратно, если мьютекс недоступен. Эта функция показана в листинге 10.

ret = mutex_trylock( &my_mutex );
if (ret != 0) {
 // Блокировка получена!
} else {
 // Блокировка не получена
}
 

Если же вы готовы ждать освобождения мьютекса, вы можете вызвать mutex_lock. Выход из этого вызова происходит при доступности мьютекса, в противном случае вызов переводится в режим ожидания освобождения мьютекса. В любом случае, когда управление возвращается, вызывающая программа держит мьютекс. И, наконец, mutex_lock_interruptible используется в случаях, когда вызывающая программа может быть переведена в режим ожидания. В этом случае функция может вернуть -EINTR. Оба эти вызова показаны в листинге 11.

 
 mutex_lock( &my_mutex );

// Блокировка удерживается вызывающей процедурой.

if (mutex_lock_interruptible( &my_mutex ) != 0) {

 // Прервано сигналом, взаимное исключение не получено

}
 

После того, как мьютекс заблокирован, его необходимо разблокировать. Это делается функцией mutex_unlock. Эта функция не может быть вызвана из контекста прерывания. И, наконец, можно проверить состояние мьютекса вызовом mutex_is_locked. Фактически этот вызов компилируется в подставляемую функцию. Если мьютекс удерживается (заблокирован), будет возвращена единица, в противном случае - ноль. Использование этих функций продемонстрировано в листинге 12.

 mutex_unlock( &my_mutex );

if (mutex_is_locked( &my_mutex ) == 0) {

 // Взаимное исключение снято

}
 

Хотя у API мьютексов есть свои ограничения, поскольку он построен на базе атомарного API, он эффективен, и если он подходит к вашим потребностям, его применение целесообразно.

И, наконец, остаётся большая блокировка ядра (BKL). Её применение в ядре сокращается, но оставшиеся случаи применения устранить сложнее всего. BKL сделала возможной многопроцессорность Linux, но со временем BKL заменили более детальные блокировки. BKL выполняется с помощью функций lock_kernel и unlock_kernel. Более подробную информацию можно найти в ./linux/lib/kernel_lock.c.

В том, что касается возможностей выбора, Linux напоминает швейцарский армейский нож, и методы блокировки здесь не являются исключением. Атомарные блокировки предоставляют не только механизм блокировки, но и арифметические и битовые операции. Взаимные блокировки реализуют механизм блокировки, ориентированный большей частью на SMP-системы; существуют также взаимные блокировки чтения и записи, которые допускают получение блокировки несколькими операциями чтения и только одной операцией записи. И, наконец, мьютексы - это относительно новый механизм блокировки, который предоставляет простой API, построенный на базе атомарных операций. В Linux найдется схема блокировки для защиты ваших данных на любой случай.

Об авторе

		M. Тим Джонс (M. Tim Jones) является архитектором встраиваимого программного обеспечения и автором работ: Программирование Приложений под GNU/Linux, Программирование AI-приложений и Использование BSD-сокетов в различных языках программирования. Он имеет опыт разработки процессоров для геостационарных космических летательных аппаратов, а также разработки архитектуры встраиваемых систем и сетевых протоколов. Сейчас Тим работает инженером-консультантом в корпорации Эмулекс (Emulex Corp.) в г.Лонгмонт, Колорадо.