Готовый перевод Linux Device Drivers 3 / Драйверы устройств Линукс (третье издание): 5.7. Alternatives to Locking

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

5.7.1 Свободные от блокировки алгоритмы

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

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

Тщательно реализованный круговой буфер не требует блокирования в отсутствие нескольких поставщиков или потребителей. Поставщик является единственным потоком, которому разрешено изменять индекс записи и массив в том месте, куда он указывает. Пока писатель заносит новое значение в буфер до обновления индекса записи, читатель будет всегда видеть согласованные данные. Читатель, в свою очередь, является единственным потоком, который может получить доступ к индексу чтения и значению, которое он указывает. Немного позаботясь, чтобы эти два указателя не вышли за границы друг друга, поставщик и потребитель могут получать доступ к буферу одновременно без состояний гонок.

Рисунок 5-1 показывает круговой буфер в нескольких состояниях заполненности. Этот буфер был определён так, что пустое состояние обозначается одинаковыми указателями чтения и записи, а состояние заполненности - когда указатель записи имеет значение непосредственно за указателем чтения (будьте внимательны с учётом переноса по достижении границ буфера!). После тщательного программирования этот буфер может быть использован без блокировок.

Рисунок 5-1. Круговой буфер

Круговые буферы появляются в драйверах устройств разумно часто. Сетевые адаптеры, в частности, часто используют круговые буферы для обмена данными (пакетами) с процессором. Отметим, что в ядре версии 2.6.10 есть общая реализация кругового буфера, смотрите <linux></linux>kfifo.h> для получения информации о том, как его использовать.

5.7.2. Атомарные переменные

Иногда общий ресурс представляет собой простую целую величину. Предположим, что драйвер поддерживает общую переменную n_op, которая сообщает, сколько операций устройства в настоящее время ожидает исполнения. Обычно, даже такие простые операции, как:

n_op++;

потребуют блокировки. Некоторые процессоры могут выполнять такого рода увеличение атомарным образом, но вы не можете на это рассчитывать. Но режим полной блокировки выглядит перегруженным для простых целочисленных значений. В случаях, подобных этому, ядро обеспечивает атомарный целочисленный тип, названный atomic_t и определённый в <asm></asm>atomic.h>.

atomic_t на всех поддерживаемых архитектурах содержит значение int. Однако, из-за особенностей работы этого типа на некоторых процессорах, полный диапазон целого числа может быть не доступен; таким образом, вы не должны рассчитывать, что atomic_t содержит более чем 24 бита. Для этого типа определены следующие операции и они гарантированно будут атомарными в отношении всех процессоров SMP компьютера. Операции очень быстрые, потому что когда это возможно, они компилируются в одну машинную команду.

void atomic_set(atomic_t *v, int i);

atomic_t v = ATOMIC_INIT(0);

Задать атомарной переменной v целое значение i. Вы также можете инициализировать атомарные значения во время компиляции с помощью макроса ATOMIC_INIT.

void atomic_add(int i, atomic_t *v);

Добавляет i к атомарной переменной, указываемой v. Возвращаемое значение является неопределённым, потому что существуют дополнительные расходы для возвращения нового значения и в большинстве случаев знать его нет необходимости.

void atomic_add(int i, atomic_t *v);

Добавляет i к атомарной переменной, указываемой v. Возвращаемое значение является неопределённым, потому что существуют дополнительные расходы для возвращения нового значения и в большинстве случаев знать его нет необходимости.

void atomic_inc(atomic_t *v);

void atomic_dec(atomic_t *v);

Увеличение или уменьшение атомарной переменной.

int atomic_inc_and_test(atomic_t *v);

int atomic_dec_and_test(atomic_t *v);

int atomic_sub_and_test(int i, atomic_t *v);

Выполнить указанные операции и проверить результат; если после операции атомарное значение равно 0, то возвращаемое значение является истинным (true); в противном случае, оно является ложным (false). Обратите внимание, что нет atomic_add_and_test.

int atomic_add_return(int i, atomic_t *v);

int atomic_sub_return(int i, atomic_t *v);

int atomic_inc_return(atomic_t *v);

int atomic_dec_return(atomic_t *v);

Ведут себя так же, как atomic_add и друзья, с тем исключением, что они возвращают новое значение атомарной переменной вызывающему.

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

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

atomic_sub(amount, &first_atomic);

atomic_add(amount, &second_atomic);

Существует определенный период времени, когда amount был вычтен из первой атомарной величины, но ещё не добавлен ко второй. Если такое состояние может создать проблемы для кода, который может выполняться между двумя операциями, должны быть использованы какие-либо формы блокировки.

2.7.3. Битовые операции

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

Атомарные битовые операции очень быстрые, так как они выполняют операции с использованием одной машинной инструкции без запрета прерываний всегда, когда нижележащая платформа может это сделать. Функции зависят от архитектуры и объявлены в <asm></asm>bitops.h>. Они гарантированно атомарные даже на компьютерах с SMP и полезны для сохранения согласованности между процессорами.

К сожалению, типы данных в этих функциях зависят от архитектуры. Аргумент nr (описывающий биты для манипулирования) обычно определяется как int, но для нескольких архитектур является unsigned long. Адрес изменяемого, как правило, указатель на unsigned long, но на нескольких архитектурах вместо этого используется void *.

Доступными битовыми операциями являются:

void set_bit(nr, void *addr);

Установить бит номер nr в объекте данных, на который указывает addr.

void clear_bit(nr, void *addr);

Очищает указанный бит в данных типа unsigned long, которые находятся по addr. Иначе говоря, его семантика такая же, как у set_bit.

void change_bit(nr, void *addr);

Переключает бит.

test_bit(nr, void *addr);

Эта функция является единственной битовой операцией, которой не требуется быть атомарной; она просто возвращает текущее значение бита.

int test_and_set_bit(nr, void *addr);

int test_and_clear_bit(nr, void *addr);

int test_and_change_bit(nr, void *addr);

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

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

Сегмент кода, которому необходимо получить доступ к объекту с общими данными, пытается получить блокировку атомарно используя либо test_and_set_bit, либо test_and_clear_bit. Здесь показана обычная реализация; она предполагает, что блокировка находится в бите nr по адресу addr. Предполагается также, что бит равен 0, когда блокировка свободна или ненулевой, когда блокировка занята.

/* пробуем установить блокировку */

while (test_and_set_bit(nr, addr) != 0)

wait_for_a_while( );



/* выполняем работу */



/* освобождаем блокировку и проверяем... */

if (test_and_clear_bit(nr, addr) == 0)

something_went_wrong( ); /* уже свободна: ошибка */

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

5.7.4. Последовательные блокировки

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

Последовательные блокировки (seqlock-и) определены в <linux></linux>seqlock.h>. Есть два обычных метода для инициализации такого примитива (который имеет тип seqlock_t):

seqlock_t lock1 = SEQLOCK_UNLOCKED;



seqlock_t lock2;

seqlock_init(&lock2);

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

unsigned int seq;



do {

seq = read_seqbegin(&the_lock);

/* Do what you need to do */

} while read_seqretry(&the_lock, seq);

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

Если ваш примитив последовательной блокировки должен быть доступен из обработчика прерываний, вы должны вместо этого использовать IRQ-безопасные версии:

unsigned int read_seqbegin_irqsave(seqlock_t *lock,

unsigned long flags);

int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq,

unsigned long flags);

Писатели должны получить эксклюзивную блокировку, чтобы войти в критическую секцию, защищаемую примитивом последовательной блокировки. Чтобы это сделать, вызовите:

void write_seqlock(seqlock_t *lock);

для снятия блокировки. Так как для контроля записи используются спин-блокировки, имеются все обычные варианты:

void write_sequnlock(seqlock_t *lock);

для снятия блокировки. Так как для контроля записи используются спин-блокировки, имеются все обычные варианты:

void write_seqlock_irqsave(seqlock_t *lock, unsigned long flags);

void write_seqlock_irq(seqlock_t *lock);

void write_seqlock_bh(seqlock_t *lock);



void write_sequnlock_irqrestore(seqlock_t *lock, unsigned long flags);

void write_sequnlock_irq(seqlock_t *lock);

void write_sequnlock_bh(seqlock_t *lock);

Существует также write_tryseqlock, которая возвращает ненулевое значение, если она смогла получить блокировку.

Код, использующий RCU должен включать <linux></linux>rcupdate.h>

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

абзац 20
int atomic_add_negative(int i, atomic_t *v);

Добавить целую переменную i к *v. Возвращаемое значение является истиной (true), если результат отрицательный, ложным (false), в противном случае.

Внимание! Этот перевод, возможно, ещё не готов.
Его статус: идёт перевод

Переведено на Нотабеноиде
http://notabenoid.org/book/11832/38293

Переводчики: hardorsoft, victor8632