Анатомия методов синхронизации Linux

Механизмы атомарности ядра, мьютексы и спинлоки

В рамках изучения Linux® вы, возможно, слышали о параллелизме, критических секциях и блокировках, но как использовать эти концепции в рамках ядра? В этой статье приводится обзор механизмов блокировок, реализованных в ядре 2.6, в том числе - атомарных операций, спинлоков, блокировок чтения и записи, а также семафоров ядра. В ней также рассказывается, когда следует применять каждый из этих механизмов для создания безопасного и эффективного кода ядра.

М. Тим Джонс, инженер-консультант, Emulex

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



25.12.2007

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

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

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

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

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

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

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

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

Методы синхронизации Linux

Теперь, когда мы немного ознакомились с теорией и поняли, какую проблему предстоит решать, давайте рассмотрим различные способы реализации параллельного исполнения и взаимных исключений в 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.

Листинг 1. Создание и инициализация атомарных переменных
atomic_t my_counter ATOMIC_INIT(0);

... или ...

				atomic_set( &my_counter, 0 );

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

Листинг 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.

Листинг 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.

Листинг 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, приводят к одинаковому результату.

Листинг 5. Создание и инициализация взаимных блокировок
spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

... или ...

				DEFINE_SPINLOCK( my_spinlock );

... или ...

				spin_lock_init( &my_spinlock );

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

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

Листинг 6. Функции установки и снятия взаимной блокировки
spin_lock( &my_spinlock );

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

				spin_unlock( &my_spinlock );

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

Листинг 7. Вариант взаимной блокировки с отключенными локальными прерываниями
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.

Листинг 8. Функции взаимной блокировки для взаимодействий с нижней половиной
spin_lock_bh( &my_spinlock );

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

				spin_unlock_bh( &my_spinlock );

Взаимные блокировки чтения и записи

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

Листинг 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.

Листинг 10. Попытка получить мьютекс с помощью mutex_trylock
ret = mutex_trylock( &my_mutex );
if (ret != 0) {
  // Блокировка получена!
} else {
  // Блокировка не получена
}

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

Листинг 11. Блокировка взаимного исключения с возможностью перевода в режим ожидания
mutex_lock( &my_mutex );

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

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

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

}

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

Листинг 12. Проверка мьютекса с помощью mutex_is_locked
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 найдется схема блокировки для защиты ваших данных на любой случай.

Ресурсы

Научиться

Получить продукты и технологии

  • Новейшие исходные коды Linux можно найти в Архивах ядра Linux. Сам по себе исходный код Linux является наиболее естественным источником информации о работе ядра. В директории Documentation также можно найти солидное количество документации (хотя часть её несколько устарела).
  • Используйте в своем следующем проекте разработки для Linux ознакомительные версии программного обеспечения IBM, которые можно скачать непосредственно с developerWorks. (EN)

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=279196
ArticleTitle=Анатомия методов синхронизации Linux
publish-date=12252007