Второе издание
 Скачать 3.09 Mb.
|
|
Таблица 9.1. Полный список всех атомарных операций с целыми числами Атомарная целочисленная операция Описание ATOMIC_INIT(int i) int atomic_ read(atomic_t *y) void atomic_set (atomic_t *v, int i) void atomic_add (int i, atomic_t *v) void atomic_sub(int i, atomic_t *v) void atomic_inc(atomic_t *v) void atomic_dec(atomic_t *v) int atomic_sub_and_test(int i, atomic_t *v) int atomic_add_negative(int i, atomic_t *v) int atomic_dec_and_test (atomic_t *v) int atomic_inc_and_test(atomic_t *v) Объявление и инициализация в значение i переменной типа a t o m i c _ t Атомарное считывание значения целочислен- ной переменной v Атомарно установить переменную v в значение i Атомарно прибавить значение i к переменной v Атомарно вычесть значение 1 из переменной v Атомарно прибавить единицу к переменной v Атомарно вычесть единицу из переменной v Атомарно вычесть значение i из переменной v и возвратить t r u e , если результат равен нулю, и f a l s e в противном случае Атомарно прибавить значение i к переменной v и возвратить t r u e , если результат операции меньше нуля, иначе возвратить f a l s e Атомарно вычесть единицу из переменной v и возвратить t r u e , если результат операции равен нулю, иначе возвратить f a l s e Атомарно прибавить единицу к переменной v и возвратить t r u e , если результат операции равен нулю, иначе возвратить f a l s e Атомарность и порядок выполнения От атомарных операций чтения перейдем к различиям между атомарностью и порядком выпол- нения. Как уже рассказывалось, операции чтения одного машинного слова всегда выполняют- ся атомарно. Эти операции никогда не перекрываются операциями записи того же машинного слова. Иными словами, операция чтения данных всегда возвращает машинное слово в конси- стентном состоянии: иногда возвращается значение, которое было до записи, а иногда— то, которое стало после записи, но никогда не возвращается значение, которое было во время за- писи. Например, если целочисленное значение вначале было равно 42, а потом стало 365, то операция чтения всегда вернет значение 42 или 365, но никогда не смешанное значение. Это называется атомарностью. Иногда бывает так, что вашему коду необходимо нечто большее, например операция чтения всегда выполняется перед ожидающей операцией записи. Это называется не атомарностью, а порядком выполнения (ordering). Атомарность гарантирует, что инструкции выполняются не прерываясь и что они либо выполняются полностью, либо не выполняются совсем. Порядок вы- полнения же гарантирует, что две или более инструкций, даже если они выполняются разными потоками или разными процессами, всегда выполняются в нужном порядке. Атомарные операции, которые обсуждаются в этом разделе, гарантируют только атомарность. Порядок выполнения гарантируется с помощью операций барьеров (barrier), которые будут рассмотрены дальше в текущей главе. 180 Глава 9 В любом коде использование атомарных операций, где это возможно, более пред- почтительно по сравнению со сложными механизмами блокировок. Для большин- ства аппаратных платформ одна или две атомарные операции приподят к меньшим накладным затратам и к более эффективному использованию процессорного кэша, чем в случае более сложных методов синхронизации. Как и в случае любого кода, ко- торый чувствителен к производительности, всегда разумным будет протестировать несколько вариантов. Битовые атомарные операции В дополнение к атомарным операциям с целыми числами, ядро также предостав- ляет семейство функций, которые позволяют работать на уровне отдельных битов. Не удивительно, что эти операции зависят от аппаратной платформы и определены в файле Тем не менее может вызвать удивление то, что функции, которые реализуют би- товые операции, работают с обычными адресами памяти. Аргументами функций яв- ляются указатель и номер бита. Бит 0 — это наименее значащий бит числа, которое находится по указанному адресу. На 32-разрядных машинах бит 31 — это наиболее значащий бит, а бит 0 — наименее значащий бит машинного слова. Нет ограничений на значение номера бита, которое передается в функцию, хотя большинство пользо- вателей работают с машинными словами и номерами битов от 0 до 31 (или до 63 для 64-битовых машин). Так как функции работают с обычными указателями, то в этом случае нет аналога типу atomic_t, который используется для операций с целыми числами. Вместо этого можно использовать указатель на любые данные. Рассмотрим следующий пример. unsigned long word = 0; set_bit(0,&word); /* атомарно устанавливается бит 0 */ set_bit(l, &word); /* атомарно устанавливается бит 1 */ printk("%ul\n", word); /* будет напечатано "З" */ clear_bit(1, &word); /* атомарно очищается бит 1 */ change_bit(0, &word); /* атомарно изменяется значение бита 1, теперь он очищен */ /* атомарно устанавливается бит нуль и возвращается предыдущее значение этого бита (нуль) */ if (test_and_set_bit(0, &word)) { /* условие никогда не выполнится ... */ } Список стандартных атомарных битовых операций приведен в табл. 9.2. Для удобства работы также предоставляются неатомарные версии всех битовых операций. Эти операции работают так же, как и их атомарные аналоги, но они не га- рантируют атомарности выполнения операций, и имена этих функций начинаются с двух символов подчеркивания. Например, неатомарная форма функции t e s t _ b i t () будет иметь имя _ _ t e s t _ b i t ( ) . Если нет необходимости в том, чтобы операции были атомарными, например, когда данные уже защищены с помощью блокировки, неатомарные операции могут выполняться быстрее. Средства синхронизации в ядре 181 void set_bit (int nr, void *addr) Атомарно установить n r -й бит в области памя- ти, которая начинается с адреса addr void clear_bit (int nr, void *addr) Атомарно очистить n r -й бит в области памяти, которая начинается с адреса addr void change_bit ( i n t nr, void *addr) Атомарно изменить значение n r -го бита в обла- сти памяти, которая начинается с адреса addr, на инвертированное i n t t e s t _ a n d _ s e t _ b i t ( i n t n r , void *addr) Атомарно установить значение n r - г о бита в обла- сти памяти, которая начинается с адреса 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) Атомарно возвратить значение n r -го бита в об- ласти памяти, которая начинается с адреса addr 182 Глава 9 Откуда берутся неатомарные битовые операции На первый взгляд, такое понятие, как неатомарная битовая операция, вообще не имеет смыс- ла. Задействован только один бит, и здесь не может быть никакого нарушения целостности. Одна из операций всегда завершится успешно, что еще нужно? Да, порядок выполнения может быть важным, но атомарность-то тут при чем? В конце концов, если значение бита равно тому, которое устанавливается хотя бы одной из операций, то все хорошо, не так ли? Давайте вспомним, что такое атомарность? Атомарность означает, что операция или заверша- ется полностью, не прерываясь, или не выполняется вообще. Следовательно, если выполня- ется две атомарные битовые операции, то предполагается, что они обе должны выполниться. Понятно, что значение бита должно быть правильным (и равным тому значению, которое уста- навливается с помощью последней операции, как рассказано в конце предыдущего параграфа). Более того, если другие битовые операции тоже выполняются успешно, то в некоторые мо- менты времени значение бита должно соответствовать тому, которое устанавливается этими промежуточными операциями. Допустим, выполняются две атомарные битовые операции: первоначальная установка бита, а затем очистка бита. Без атомарности этот бит может быть очищен, но никогда не установлен. Операция установки может начаться одновременно с операцией очистки и не выполниться со- всем. Операция очистки бита может завершиться успешно, и бит будет очищен, как и пред- полагалось. В случае атомарных операций, установка бита выполнится на самом деле. Будет существовать момент времени, в который операция считывания покажет, что бит установлен, после этого выполнится операция очистки и значение бита станет равным нулю. Иногда может требоваться именно такое поведение, особенно если критичен порядок вы- полнения. Таблица 9.2. Список стандартных атомарных битовых операций Атомарная битовая операция Описание Ядро также предоставляет функции, которые позволяют найти номер первого установленного (или не установленного) бита, в области памяти, которая начинает- ся с адреса addr: int find_first_bit(unsigned long *addr, unsigned int size) int find_first_zero_bit(unsigned long *addr, unsigned int size) Обе функции в качестве первого аргумента принимают указатель на область па- мяти и в качестве второго аргумента — количество битов, по которым будет произ- водиться поиск. Эти функции возвращают номер первого установленного или не установленного бита соответственно. Если код производит поиск в одном машинном слове, то оптимальным решением будет использовать функции __f f s() и _ffz(), которые в качестве единственного параметра принимают машинное слово, где будет производиться поиск. В отличие от атомарных операций с целыми числами, при написании кода обыч- но нет возможности выбора, использовать или не использовать рассмотренные би- товые операции, они являются единственными переносимыми средствами, которые позволяют установить или очистить определенный бит. Вопрос лишь в том, какие разновидности этих операций использовать — атомарные или неатомарные. Если код по своей сути является защищенным от состояний конкуренции за ресурсы, то можно использовать неатомарные операции, которые могут выполняться быстрее для определенных аппаратных платформ. Спин-блокировки Было бы очень хорошо, если бы все критические участки были такие же простые, как инкремент или декремент переменной, однако в жизни все более серьезно. В ре- альной жизни критические участки могут включать в себя несколько вызовов функ- ций. Например, очень часто данные необходимо извлечь из одной структуры, затем отформатировать, произвести анализ этих данных и добавить результат в другую структуру. Весь этот набор операций должен выполняться атомарно. Никакой другой код не должен иметь возможности читать ни одну из структур данных до того, как данные этих структур будут полностью обновлены. Так как ясно, что простые ато- марные операции не могут обеспечить необходимую защиту, то используется более сложный метод защиты — блокировки (lock). Наиболее часто используемый тип блокировки в ядре Linux - это спин-блокировки (spin lock). Спин-блокировка — это блокировка, которую может удерживать не более чем один поток выполнения. Если поток выполнения пытается захватить блокиров- ку, которая находится в состоянии конфликта (contended), т.е. уже захвачена, поток начинает выполнять постоянную циклическую проверку (busy loop) — "вращаться" (spin), ожидая на освобождение блокировки. Если блокировка не находится в со- стоянии конфликта при захвате, то поток может сразу же захватить блокировку и продолжить выполнение. Циклическая проверка предотвращает ситуацию, в кото- рой более одного потока одновременно может находиться в критическом участке. Следует заметить, что одна и та же блокировка может использоваться в нескольких разных местах кода, и при этом всегда будет гарантирована защита и синхронизация при доступе, например, к какой-нибудь структуре данных. Средства синхронизации в ядре 183 Тот факт, что спин-блокировка, которая находится в состоянии конфликта, за- ставляет потоки, ожидающие на освобождение этой блокировки, выполнять зам- кнутый цикл (и, соответственно, тратить процессорное время), является важным. Неразумно удерживать спин-блокировку в течение длительного времени. По своей сути спин-блокировка — это быстрая блокировка, которая должна захватываться на короткое время одним потоком. Альтернативным является поведение, когда при попытке захватить блокировку, которая находится в состоянии конфликта, поток переводится в состояние ожидания и возвращается к выполнению, когда блокиров- ка освобождается. В этом случае процессор может начать выполнение другого кода. Такое поведение вносит некоторые накладные затраты, основные из которых — это два переключения контекста. Вначале переключение на новый поток, а затем обрат- ное переключение на заблокированный поток. Поэтому разумным будет использо- вать спин-блокировку, когда время удержания этой блокировки меньше длительности двух переключений контекста. Так как у большинства людей есть более интересные занятия, чем измерение времени переключения контекста, то необходимо старать- ся удерживать блокировки по возможности в течение максимально короткого пери- ода времени 1 . В следующем разделе будут описаны семафоры (semaphore) — механизм блокировок, который позволяет переводить потоки, ожидающие на освобождение блокировки, в состояние ожидания, вместо того чтобы периодически проверять, не освободилась ли блокировка, находящаяся в состоянии конфликта. Спин-блокировки япляются зависимыми от аппаратной платформы и реализова- ны на языке ассемблера. Зависимый от аппаратной платформы код определен в за- головочном файле spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; spin_lock (&mr_lock); /* критический участок ... */ spin_unlock(&mr_lock); Б любой момент времени блокировка может удерживаться не более чем одним потоком выполнения. Следовательно, только одному потоку позволено войти в кри- тический участок в данный момент времени. Это позволяет организовать защиту от состояний конкуренции на многопроцессорной машине. Заметим, что на одно- процессорной машине блокировки не компилируются в исполняемый код, и, со- ответственно, их просто не существует. Блокиропки играют роль маркеров, чтобы запрещать и разрешать вытеснение кода (преемптивпость) в режиме ядра. Если пре- емптивность ядра отключена, то блокировки совсем не компилируются. 1 Сейчас это требование становится еще более важным, так как ядро является преемптивным. Время, в течение которого удерживаются блокировки, эквивалентно времени задержки (латент- пости) системного планировщика. 184 Глава 9 Внимание: спин-блокировки не рекурсивны! В отличие от реализаций в других операционных системах, спин-блокировки в операционной системе Linux не рекурсивны. Это означает, что если поток пытается захватить блокировку, которую он уже удерживает, то этот поток начнет периодическую проверку, ожидая, пока он сам не освободит блокировку. Но поскольку поток будет периодически проверять, не освободилась ли блокировка, он никогда не сможет ее освободить, и возникнет тупиковая ситуация (самобло- кировка). Нужно быть внимательными! Спин-блокировки могут использоваться в обработчиках прерываний (семафоры не могут использоваться, поскольку они переводят процесс в состояние ожидания). Если блокировка используется в обработчике прерывания, то перед тем, как захва- тить эту блокировку (в другом месте - не в обработчике прерывания), необходимо запретить все локальные прерывания (запросы на прерывания на данном процессо- ре). В противном случае может возникнуть такая ситуация, что обработчик прерыва- ния прерывает выполнение кода ядра, Который уже удерживает данную блокировку, и обработчик прерывания также пытается захватить эту же блокировку. Обработчик прерывания постоянно проверяет (spin), не освободилась ли блокировка. С другой стороны, код ядра, который удерживает блокировку, не будет выполняться, пока обработчик прерывания не закончит выполнение. Это пример взаимоблокировки (двойной захват), который обсуждался в предыдущей главе. Следует заметить, что прерывания необходимо запрещать только на текущем процессоре. Если прерывание возникает на другом процессоре (по отношению к коду ядра, захватившего блокиров- ку) и обработчик будет ожидать на освобождение блокировки, то это не приведет к тому, что код ядра, который захватил блокировку, не сможет никогда ее освободить. Ядро предоставляет интерфейс, который удобным способом позволяет запретить прерывания и захватить блокировку. Использовать его можно следующим образом. spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; unsigned long flags; spin_lock_irqsave(&mr_lock, flags); /* критический участок ... */ spin_unlock_irqre_store(&rnr_lock, flags); Подпрограмма spin_lock_irqsave () сохраняет текущее состояние системы прерываний, запрещает прерывания и захватывает указанную блокировку. Функция spin_unlock_irqrestore (), наоборот, освобождает указанную блокировку и вос- станавливает предыдущее состояние системы прерываний. Таким образом, если пре- рывания были запрещены, показанный код не разрешит их по ошибке. Заметим, что переменная flags передается по значению. Это потому, что указанные функции ча- стично выполнены в виде макросов. На однопроцессорной машине показанный пример только лишь запретит преры- вания, чтобы предотвратить доступ обработчика прерывания к совместно исполь- зуемым данным, а механизм блокировок скомпилирован не будет. Функции захвата и освобождения блокировки также соответственно запрещают и разрешают преем- птивность ядра. Средства синхронизации в ядре 185 Что необходимо блокировать Важно, чтобы каждая блокировка была четко связана с тем, что она блокирует. Еще более важ- но — это защищать данные, а не код. Несмотря на то что во всех примерах этой главы рас- сматриваются критические участки, в основе этих критических участков лежат данные, которые требуют защиты, а никак не код. Если блокировки просто блокируют участки кода, то такой код труднопонимаем и подвержен состояниям гонок. Необходимо ассоциировать данные с соот- ветствующими блокировками. Например, структура s t r u c t f o o блокируется с помощью блокировки f o o _ l o c k . С данной блокировкой также необходимо ассоциировать некоторые данные. Если к некоторым данным осуществляется доступ, то необходимо гарантировать, что этот доступ будет безопасным. Наиболее часто это означает, что перед тем, как осуществить манипуляции с данными, необходимо захватить соответствующую блокировку и освободить эту блокировку нужно после завершения манипуляций. Если точно известно, что прерывания разрешены, то нет необходимости восста- навливать предыдущее состояние системы прерываний. Можно просто разрешить прерывания при освобождении блокировки. В этом случае оптимальным будет ис- пользование функций spin_lock_irq() и spin_unlock_irq(). spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; spin_lock_irq(&mr_lock); /* критический участок ... */ spin_unlock_irq(&mr_lock); Для любого участка кода очень сложно гарантиропать, что прерывания всегда раз- решены. В связи с этим не рекомендуется использовать функцию s p i n l o c k _ i r q (). Если стоит вопрос об использовании этих функций, то лучьше быть точно уверен- ным, что прерывания запрещены, а не огорчаться, когда найдете, что прерывания разрешены не там, где нужно. |