Разработка ядра Linux
Шрифт:
Список стандартных атомарных битовых операций приведен в табл. 9.2.
Таблица 9.2. Список стандартных атомарных битовых операций
| Атомарная битовая операция | Описание |
|---|---|
void set_bit(int nr, void *addr) | Атомарно установить nr –
addr |
void clear_bit(int nr, void *addr) | Атомарно очистить nr – й бит в области памяти, которая начинается с адреса addr |
void change_bit(int nr, void *addr) | Атомарно изменить значение nr – го бита в области памяти, которая начинается с адреса addr , на инвертированное |
int test_and_set_bit(int nr, void *addr) | Атомарно установить значение nr – го бита в области памяти, которая начинается с адреса addr , и возвратить предыдущее значение этого бита |
int test_and_clear_bit(int nr, void *addr) | Атомарно очистить значение nr – го бита в области памяти, которая начинается с адреса addr , и возвратить предыдущее значение этого бита |
int test_and_change_bit(int nr, void *addr) | Атомарно изменить значение nr – го бита в области памяти, которая начинается с адреса addr , на инвертированное и возвратить предыдущее значение этого бита |
int test_bit(int nr, void *addr) | Атомарно возвратить значение nr – го бита в области памяти, которая начинается с адреса addr |
Для удобства работы также предоставляются неатомарные версии всех битовых операций. Эти операции работают так же, как и их атомарные аналоги, но они не гарантируют атомарности выполнения операций, и имена этих функций начинаются с двух символов подчеркивания. Например, неатомарная форма функции
На первый взгляд, такое понятие, как неатомарная битовая операция, вообще не имеет смысла. Задействован только один бит, и здесь не может быть никакого нарушения целостности. Одна из операций всегда завершится успешно, что еще нужно? Да, порядок выполнения может быть важным, но атомарность– то тут при чем? В конце концов, если значение бита равно тому, которое устанавливается хотя бы одной из операций, то все хорошо, не так ли?
Давайте вспомним, что такое атомарность? Атомарность означает, что операция или завершается полностью, не прерываясь, или не выполняется вообще. Следовательно, если выполняется две атомарные битовые операции, то предполагается, что они обе должны выполниться. Понятно, что значение бита должно быть правильным (и равным тому значению, которое устанавливается с помощью последней операции, как рассказано в конце предыдущего параграфа). Более того, если другие битовые операции тоже выполняются успешно, то в некоторые моменты времени значение бита должно соответствовать тому, которое устанавливается этими промежуточными операциями.
Допустим, выполняются две атомарные битовые операции: первоначальная установка бита, а затем очистка бита. Без атомарности этот бит может быть очищен, но никогда не установлен. Операция установки может начаться одновременно с операцией очистки и не выполниться совсем. Операция очистки бита может завершиться успешно, и бит будет очищен, как и предполагалось. В случае атомарных операций, установка бита выполнится на самом деле. Будет существовать момент времени, в который операция считывания покажет, что бит установлен, после этого выполнится операция очистки и значение бита станет равным нулю.
Иногда может требоваться именно такое поведение, особенно если критичен порядок выполнения.
Ядро также предоставляет функции, которые позволяют найти номер первого установленного (или не установленного) бита, в области памяти, которая начинается с адреса
Обе функции в качестве первого аргумента принимают указатель на область памяти и в качестве второго аргумента — количество битов, по которым будет
В отличие от атомарных операций с целыми числами, при написании кода обычно нет возможности выбора, использовать или не использовать рассмотренные битовые операции, они являются единственными переносимыми средствами, которые позволяют установить или очистить определенный бит. Вопрос лишь в том, какие разновидности этих операций использовать — атомарные или неатомарные. Если код по своей сути является защищенным от состояний конкуренции за ресурсы, то можно использовать неатомарные операции, которые могут выполняться быстрее для определенных аппаратных платформ.
Спин-блокировки
Было бы очень хорошо, если бы все критические участки были такие же простые, как инкремент или декремент переменной, однако в жизни все более серьезно. В реальной жизни критические участки могут включать в себя несколько вызовов функций. Например, очень часто данные необходимо извлечь из одной структуры, затем отформатировать, произвести анализ этих данных и добавить результат в другую структуру. Весь этот набор операций должен выполняться атомарно. Никакой другой код не должен иметь возможности читать ни одну из структур данных до того, как данные этих структур будут полностью обновлены. Так как ясно, что простые атомарные операции не могут обеспечить необходимую защиту, то используется более сложный метод защиты — блокировки (lock).
Наиболее часто используемый тип блокировки в ядре Linux — это спин-блокировки (spin lock). Спин-блокировка — это блокировка, которую может удерживать не более чем один поток выполнения. Если поток выполнения пытается захватить блокировку, которая находится в состоянии конфликта (contended), т.е. уже захвачена, поток начинает выполнять постоянную циклическую проверку (busy loop) — "вращаться" (spin), ожидая на освобождение блокировки. Если блокировка не находится в состоянии конфликта при захвате, то поток может сразу же захватить блокировку и продолжить выполнение. Циклическая проверка предотвращает ситуацию, в которой более одного потока одновременно может находиться в критическом участке. Следует заметить, что одна и та же блокировка может использоваться в нескольких разных местах кода, и при этом всегда будет гарантирована защита и синхронизация при доступе, например, к какой-нибудь структуре данных.
Тот факт, что спин-блокировка, которая находится в состоянии конфликта, заставляет потоки, ожидающие на освобождение этой блокировки, выполнять замкнутый цикл (и, соответственно, тратить процессорное время), является важным. Неразумно удерживать спин-блокировку в течение длительного времени. По своей сути спин-блокировка — это быстрая блокировка, которая должна захватываться на короткое время одним потоком. Альтернативным является поведение, когда при попытке захватить блокировку, которая находится в состоянии конфликта, поток переводится в состояние ожидания и возвращается к выполнению, когда блокировка освобождается. В этом случае процессор может начать выполнение другого кода. Такое поведение вносит некоторые накладные затраты, основные из которых — это два переключения контекста. Вначале переключение на новый поток, а затем обратное переключение на заблокированный поток. Поэтому разумным будет использовать спин-блокировку, когда время удержания этой блокировки меньше длительности двух переключений контекста. Так как у большинства людей есть более интересные занятия, чем измерение времени переключения контекста, то необходимо стараться удерживать блокировки по возможности в течение максимально короткого периода времени [47] . В следующем разделе будут описаны семафоры (semaphore) — механизм блокировок, который позволяет переводить потоки, ожидающие на освобождение блокировки, в состояние ожидания, вместо того чтобы периодически проверять, не освободилась ли блокировка, находящаяся в состоянии конфликта.
47
Сейчас это требование становится еще более важным, так как ядро является преемптивным. Время, в течение которого удерживаются блокировки, эквивалентно времени задержки (латентности) системного планировщика.
Спин-блокировки являются зависимыми от аппаратной платформы и реализованы на языке ассемблера. Зависимый от аппаратной платформы код определен в заголовочном файле