Библиотека сайта rus-linux.net
| Цилюрик О.И. Модули ядра Linux | ||
| Назад | Внутренние механизмы ядра | Вперед |
Блокировки
Различные виды блокировок используются для того, чтобы оградить критический участок кода от одновременного исполнения. В этом смысле блокировки гораздо ближе к защите участков кода, чем к защите областей данных, хотя семафоры, например, (не бинарные) используются, главным образом, именно для ограничения доступа к данным: классические задачи производители-потребители.
До появления и широкого распространения SMP, когда параллелизмы были квази-параллелизмами, блокировки использовались в своём классическом варианте (Э. Дейкстра), они защищали критические области от последовательного доступа несколькими вытесненными процессами. Такие механизмы работают на вытеснении запрашивающих процессов в блокированное состояние до времени освобождения критических ресурсов. Эти блокировки мы будем называть пассивными блокировками. При таких блокировках процессор прекращает (в точке блокирования) выполнение текущего процесса и переключается на выполнение другого процесса (возможно idle).
Принципиально другой вид блокировок — активные блокировки — появляются только в SMP системах, когда процессор в ожидании недоступного пока ресурса не переводится в блокированное состояние, а «накручивает» в ожидании освобождения ресурса «пустые» циклы. В этом случае, процессор не освобождается на выполнение другого ожидающего процесса в системе, а продолжает активное выполнение («пустых» циклов) в контексте текущего процесса.
Эти два рода блокировок (каждый из которых включает несколько подвидов) принципиально отличаются:
- возможностью использования: пассивно заблокировать (переключить контекст) можно только последовательность выполнения, которая имеет свой собственный контекст (запись задачи), куда позже можно вернуться (активировать процесс) — в обработчиках прерываний или тасклетах это не так;
- эффективностью: активные блокировки не всегда проигрывают пассивным в производительности, переключение контекста в системе это очень трудоёмкий процесс, поэтому для ожидания короткого интервала времени активные блокировки могут оказаться даже эффективнее, чем пассивные;
Семафоры (мьютексы)
Семафоры ядра определены в <linux/semaphore>. Так как задачи, которые конфликтуют при захвате блокировки, переводятся в состояние ожидания и в этом состоянии ждут, пока блокировка не будет освобождена, семафоры хорошо подходят для блокировок, которые могут удерживаться в течение длительного времени. С другой стороны, семафоры не оптимальны для блокировок, которые удерживаются в течение очень короткого периода времени, так как накладные затраты на перевод процессов в состояние ожидания могут превысить время, в течение которого удерживается блокировка. Существует очевидное ограничение на использование семафоров в ядре: их невозможно использовать в том коде, который не должен перейти в блокированное состояние, например, при обработке верхней половины прерываний.
В то время как спин-блокировки позволяют удерживать блокировку только одной задаче в любой момент времени, количество задач (count), которым разрешено одновременно удерживать семафор (владеть семафором), может быть задано при декларации семафора:
struct semaphore {
spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};
Если значение count больше 1, то семафор называется счетным семафором, и он допускает количество потоков, которые одновременно удерживают блокировку, не большее чем значение счетчика использования (count). Часто встречается ситуация, когда разрешенное количество потоков, которые одновременно могут удерживать семафор, равно 1 (как и для спин-блокировок), в этом семафоры называются бинарными семафорами, или взаимоисключающими блокировками (mutex, мьютекс, потому что он гарантирует взаимоисключающий доступ — mutual exclusion). Бинарные семафоры (мьютексы) используются для обеспечения взаимоисключающего доступа к фрагментам кода, называемым критической секцией, и в таком качестве и состоит их наиболее частое использование.
Примечание: Независимо от того, определёно ли поле владельца захватившего мютекс (в различных POSIX ОС, и в мютексах пространства ядра и пространства пользователя), принципиальными особенностями мютекса, вытекающими из его логики, в отличии от счётного семафора будет то, что: а). у захваченного мютекса всегда будет и единственный владелец, его захвативший, и б). освободить блокированные на мютексе потоки (освободить мютекс) может только один владеющий мютексом поток; в случае счётного семафора освободить блокированные на семафоре потоки может любой из потоков, владеющий семафором.
Статическое определение и инициализация семафоров выполняется макросом:
static DECLARE_SEMAPHORE_GENERIC( name, count );
Для создания взаимоисключающей блокировки (mutex), что используется наиболее часто, есть более короткая запись:
static DECLARE_MUTEX( name );
- где в обоих случаях name — это имя переменной типа семафор.
Но чаще семафоры создаются динамически, как часть больших структур данных. В таком случае для инициализации счётного семафора используется функция:
void sema_init( struct semaphore *sem, int val );
А вот такая же инициализация для бинарных семафоров (мютексов) — макросы:
init_MUTEX( struct semaphore *sem ); init_MUTEX_LOCKED( struct semaphore *sem );
В операционной системе Linux для захвата семафора (мютекса используется операция down(), она уменьшает его счетчик на единицу. Если значение счетчика больше или равно нулю, то блокировка захватывается успешно (задача может входить в критический участок). Если значение счетчика (после декремента) меньше нуля, то задание помещается в очередь ожидания и процессор переходит к выполнению других задач. Метод up() используется для того, чтобы освободить семафор (после завершения выполнения критического участка), его выполнение увеличивает счётчик семафора на единицу.
Операции над семафорами:
void down( struct semaphore *sem ); int down_interruptible( struct semaphore *sem ); int down_killable( struct semaphore *sem ); int down_trylock( struct semaphore *sem ); int down_timeout( struct semaphore *sem, long jiffies ); void up( struct semaphore *sem );
down_interruptible() - выполняет попытку захватить семафор. Если эта попытка неудачна, то задача переводится в блокированное состояние с флагом TASK_INTERRUPTIBLE (в структуре задачи). Такое состояние процесса означает, что задание может быть возвращено к выполнению с помощью сигнала, а такая возможность обычно очень ценная. Если сигнал приходит в то время, когда задача блокирована на семафоре, то задача возвращается к выполнению, а функция down_interruptible() возвращает значение -EINTR.
down() - переводит задачу в блокированное состояние ожидания с флагом TASK_UNINTERRUPTIBLE. В большинстве случаев это нежелательно, так как процесс, который ожидает на освобождение семафора, не будет отвечать на сигналы.
down_trylock() - используется для неблокирующего захвата семафора. Если семафор уже захвачен, то функция немедленно возвращает ненулевое значение. В случае успешного захвата семафора возвращается нулевое значение и захватывается блокировка.
down_timeout() - используется для попытки захвата семафора на протяжении интервала времени jiffies системных тиков.
up() - инкрементирует счётчик семафора, если есть блокированные на семафоре потоки, то один из них может захватить блокировку (принципиальным является то, что какой конкретно поток из числа заблокированных - непредсказуемо).
Спин-блокировки
Блокирующая попытка входа в критическую секцию при использовании семафоров означает потенциальный перевод задачи в блокированное состояние и переключение контекста, что является дорогостоящей операцией. Для синхронизации в случае, когда: а). контекст выполнения не позволяет переходить в блокированное состояние (контекст прерывания), или б). требуется кратковременная блокировка без переключение контекста - используются спин-блокировки (spinlock_t), представляющие собой активное ожидание освобождения в пустом цикле. Если необходимость синхронизации связана только с наличием в системе нескольких процессоров, то для небольших критических секций следует использовать спин-блокировку, основанную на простом ожидании в цикле. Спин-блокировка может быть только бинарной. По spinlock_t достаточно много определений разбросано по нескольким заголовочным файлам:
$ ls spinlock*
spinlock_api_smp.h spinlock_api_up.h spinlock.h spinlock_types.h spinlock_types_up.h spinlock_up.h
typedef struct {
raw_spinlock_t raw_lock;
...
} spinlock_t;
Для инициализации spinlock_t (и родственного типа rwlock_t, о котором детально ниже) раньше (и в литературе) использовались макросы:
spinlock_t lock = SPIN_LOCK_UNLOCKED; rwlock_t lock = RW_LOCK_UNLOCKED;
Но сейчас мы можем читать в комментариях:
// SPIN_LOCK_UNLOCKED and RW_LOCK_UNLOCKED defeat lockdep state tracking and are hence deprecated.
Для определения и инициализации используем макросы (эквивалентные по смыслу записанным выше) вида:
DEFINE_SPINLOCK( lock ); DEFINE_RWLOCK( lock );
Основной интерфейс spinlock_t:
spin_lock ( spinlock_t *sl ); spin_unlock( spinlock_t *sl );
Примечание: Если при компиляции ядра не установлено SMP и не конфигурировано вытеснение кода в ядре (наличие 2-х этих условий), то spinlock_t вообще не компилируются (на их месте остаются пустые места) за счёт препроцессорных директив условной трансляции.
Примечание: В отличие от реализаций в некоторых других операционных системах, спин-блокировки в операционной системе Linux не рекурсивны. Это означает, что код:
DEFINE_SPINLOCK( lock ); spin_lock( &lock ); spin_lock( &lock );
- обречён на дэдлок (скорее всего, вместе с процессором его выполняющим, то есть происходит деградация системы — число доступных системе процессоров уменьшается)...
Вот такой рекурсивный захват спин-блокировки может неявно происходить в обработчике прерываний, поэтому перед захватом такой блокировки нужно запретить прерывания на локальном процессоре. Это общий случай, поэтому для него предоставляется специальный интерфейс:
DEFINE_SPINLOCK( lock ); unsigned long flags; spin_lock_irqsave( &lock, flags ); /* критический участок ... */ spin_unlock_irqre_store( &lock, flags );
Для спин-блокировки определены ещё такие интерфейсы,
void spin_lock_init( spinlock_t *sl ); - динамическая инициализация спин-блокировки
int spin_try_lock( spinlock_t *sl ); - попытка захвата без блокирования, если блокировка уже захвачена, функция возвратит ненулевое значение
int spin_is_locked( spinlock_t *sl ); - возвращает ненулевое значение, если блокировка в данный момент захвачена
Блокировки чтения-записи
Особым, но часто встречающимся, случаем синхронизации являются случай «читателей» и «писателей». Читатели только читают состояние некоторого ресурса, и поэтому могу осуществлять к нему параллельный доступ. Писатели изменяют состояние ресурса, и в силу этого писатель должен иметь к ресурсу монопольный доступ (только один писатель), причем чтение ресурса (для всех читателей) в этот момент времени так же должно быть заблокировано. Для реализации блокировок чтения-записи в ядре Linux существуют отдельные версии для семафоров и спин-блокировок. Мьютексы реального времени не имеют реализации для случая читателей и писателей.
В случае семафоров, вместо структуры struct semaphore вводится struct rw_semaphore, а набор интерфейсных функций захвата освобождения (down()/up()) расширяется до:
down_read( &mr_rwsem ); - попытка захватить семафор для чтения
up_read( &rar_rwsem ); - освобождение семафора для чтения
down_write(&mr_rwsem); - попытка захватить семафор для записи
up write(&mr rwsem); - освобождение семафора для записи
Семантика этих операций следующая:
- если семафор ещё не захвачен, то любой захват (down_read(), down_write()) будет успешным (без блокирования);
- если семафор захвачен уже для чтения, то последующие сколь угодно много попыток захвата семафора для чтения (down_read()) будут завершаться успешно (без блокирования), но запрос на захват такого семафора для записи (down_write()) закончится блокированием;
- если семафор захвачен уже для записи, то любая последующая попытка захвата семафора (независимо, down_read() это или down_write()) закончится блокированием;
Статически определенный семафор чтения-записи создаётся макросом:
static DECLARE_RWSEM( name );
Семафоры чтения-записи, которые создаются динамически, должны быть инициализированы с помощью функции:
void init_rwsem( struct rw_semaphore *sem );
Примечание: Из описаний инициализаторов видно, что семафоры чтения-записи являются исключительно бинарными (не счётными), то-есть фактически не семафорами, а мютексами.
Пример того, как могут быть использованы семафоры чтения-записи:
struct data {
int value;
struct list_head list;
};
static struct list_head list;
static struct rw_semaphore rw_sem;
int add_value( int value ) {
struct data *item;
item = kmalloc( sizeof(*item), GFP_ATOMIC );
if ( !item ) goto out;
item->value = value;
down_write( &rw_sem ); /* захватить для записи */
list_add( &(item->list), &list );
up_write( &rw_sem ); /* освободить по записи */
return 0;
out:
return -ENOMEM;
}
int is_value( int value ) {
int result = 0;
struct data *item;
struct list_head *iter;
down_read( &rw_sem ); /* захватить для чтения */
list_for_each( iter, &list ) {
item = list_entry( iter, struct data, list );
if( item->value == value ) {
result = 1; goto out;
}
}
out:
up_read( &rw_sem ); /* освободить по чтению */
return result;
}
void init_list( void ) {
init_rwsem( &rw_sem );
INIT_LIST_HEAD( &list );
}
Точно так же, как для семафоров, вводится и блокировка чтения-записи для спин-блокировки:
typedef struct {
raw_rwlock_t raw_lock;
...
} rwlock_t;
С набором операций:
read_lock( rwlock_t *rwlock );
read_unlock( rwlock_t *rwlock );
write_lock( rwlock_t *rwlock );
write_unlock ( rwlock_t *rwlock );
Примечание: Если при компиляции ядра не установлено SMP и не конфигурировано вытеснение кода в ядре, то spinlock_t вообще не компилируются (на их месте остаются пустые места), а, значит, соответственно и rwlock_t.
Примечание: Блокировку, захваченную для чтения, уже нельзя далее «повышать» до блокировки, захваченной для записи; последовательность операторов:
read_lock( &rwlock ); write_lock( &rwlock );
- гарантирует нам дэдлок, так как при захвате блокировки на запись будет выполняться периодическая проверка, пока все потоки, которые захватили блокировку для чтения, ее освободили, это касается и текущего потока, который не сделает этого никогда... Но несколько потоков чтения безопасно могут захватывать одну и ту же блокировку чтения-записи, поэтому один поток также может безопасно рекурсивно захватывать одну и ту же блокировку для чтения несколько раз, например в обработчике прерываний без запрета прерываний.
Сериальные (последовательные) блокировки
Это пример одного только из нескольких механизмов синхронизации, которые и блокировками по существу не являются... Это подвид блокировок чтения-записи. Такой механизм добавлен для получения эффективных по времени реализаций. Описаны в <linux/seqlock.h>, для их представления вводится тип seqlock_t.
typedef struct {
unsigned sequence;
spinlock_t lock;
} seqlock_t;
Такой элемент блокировки создаётся и инициализируется статически :
seqlock_t lock = SEQLOCK_UNLOCKED;
Или динамически:
seqlock_t lock; seqlock_init( &lock );
Доступ на чтение работает получая беззнаковое целочисленное значение последовательности на входе в защищаемую критическую секцию. На выходе из этой секции это значение должно сравниваться с текущим таким значением; если есть несоответствие, то значит секция (за это время!) обрабатывалась операциями записи, и проделанное чтение должно быть повторено. В результате, код читателя имеет вид подобный:
seqlock_t lock = SEQLOCK_UNLOCKED;
unsigned int seq;
do {
seq = read_seqbegin( &lock );
/* ... */
} while read_seqretry( &lock, seq );
Блокировка по записи реализована через спин-блокировку. Писатели должны получить эксклюзивную блокировку, чтобы войти в критическую секцию, защищаемую последовательной блокировкой. Чтобы это сделать, код писателя делает вызов функции:
void write_seqlock( seqlock_t *lock );
Снятие блокировки записи:
void write_sequnlock( seqlock_t *lock );
Существует также вариант write_tryseqlock(), которая возвращает ненулевое значение, если она не смогла получить блокировку.
Если механизмы последовательной блокировки должны быть использованы в обработчике прерываний, то должны использоваться специальные (безопасные) версии API всех показанных выше вызовов (макросы):
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_irqsave( seqlock_t *lock, unsigned long flags ); void write_seqlock_irq( seqlock_t *lock ); void write_sequnlock_irqrestore( seqlock_t *lock, unsigned long flags ); void write_sequnlock_irq( seqlock_t *lock );
- где flags — просто заранее зарезервированная область сохранения IRQ флагов.
Мьютексы реального времени
Кроме обычных мьютексов (как бинарного подвида семафоров), в ядре создан новый интерфейс для мьютексов реального времени (rt_mutex). Это механизм достаточно позднего времени, его рассмотрение будем проводить на ядре:
$ uname -r
2.6.37.3
Структура мьютекса реального времени (<linux/rtmutex.h>), если исключить из рассмотрения её отладочную часть:
// RT Mutexes: blocking mutual exclusion locks with PI support
struct rt_mutex { // The rt_mutex structure
raw_spinlock_t wait_lock; // spinlock to protect the structure
struct plist_head wait_list; // head to enqueue waiters in priority order
struct task_struct *owner; // the mutex owner
...
};
Характерным является присутствие поля owner, что характерно для любых вообще мьютексов POSIX (и отличает их от семафоров), это уже обсуждалось ранее. Там же определяется весь API для работы с этим примитивом, который не предлагает ничего необычного:
#define DEFINE_RT_MUTEX( mutexname ) void __rt_mutex_init( struct rt_mutex *lock, const char *name ); // name используется в отладочной части void rt_mutex_destroy( struct rt_mutex *lock ); void rt_mutex_lock( struct rt_mutex *lock ); int rt_mutex_trylock( struct rt_mutex *lock ); void rt_mutex_unlock( struct rt_mutex *lock );
Очень любопытно определяется признак захваченности мьютекса:
inline int rt_mutex_is_locked( struct rt_mutex *lock ) {
return lock->owner != NULL;
}
Инверсия и наследование приоритетов
Мьютексы реального времени доступны только тогда, когда ядро собрано с параметром CONFIG_RT_MUTEXES, что проверяем так:
# cat /boot/config-2.6.32.9-70.fc12.i686.PAE | grep RT_MUTEX CONFIG_RT_MUTEXES=y # CONFIG_DEBUG_RT_MUTEXES is not set # CONFIG_RT_MUTEX_TESTER is not set
В отличие от регулярных мьютексов, мьютексы реального времени обеспечивают наследование приоритетов (priority inheritance, PI), что является одним из нескольких (немногих) известных способов, препятствующих возникновению инверсии приоритетов (priority inversion). Если RT мьютекс захвачен процессом A, и его пытается захватить процесс B (более высокого приоритета), то:
- процесс B блокируется и помещается в очередь ожидающих освобождения процессов wait_list (в описании структуры rt_mutex);
- при необходимости, этот список ожидающих процессов переупорядочивается в порядке приоритетов ожидающих процессов;
- приоритет владельца мьютекса (текущего выполняющегося процесса) B повышается до приоритета ожидающего процесса A (максимального приоритета из ожидающих в очереди процессов);
- это и обеспечивает избежание потенциальной инверсии приоритетов.
Примечание: Эти действия затрагивают глубины управления процессами, для этого в <linux/sched.h> определяется специальный вызов :
void rt_mutex_setprio( struct task_struct *p, int prio );
И парный ему:
static inline int rt_mutex_getprio( struct task_struct *p ) {
return p->normal_prio;
}
Из этой inline реализации хорошо видно, что в основной структуре описания процесса:
struct task_struct {
...
int prio, static_prio, normal_prio;
...
}
- необходимо теперь иметь несколько полей приоритета, из которых поле prio является динамическим приоритетом, согласно которому и происходит диспетчеризация процессов в системе, а поле приоритета normal_prio остаётся неизменным, по значению которого происходит восстановление приоритета после освобождения мьютекса реального времени.
| Предыдущий раздел: | Оглавление | Следующий раздел: |
| Локальные переменные процессора | Множественное блокирование |