Необходимость синхронизации возникает, когда несколько сущностей работают с одними и теми же данными, или, по-другому, когда может возникнуть состояние гонки(race condition), чтобы гонку предотвратить и сделать поведение программы предсказуемым.
Самый простой способ синхронизации — отсутствие необходимости в синхронизации. В ядре к примеру такое достигается “Процессорными переменными”. У каждого процессора свой собственный экземпляр таких переменных, для оптимальности массивы процессорных переменных выровнены по строчкам аппаратного кэша. Таким образом удаётся избежать конфликтов кэш-промахов и гонки за ресурсы между различными процессорами. Однако, это не спасает в ситуациях с вытеснением и прерываниями на 1 процессоре, тут нужны дополнительные примитивы синхронизации.
Примитивы для работы с “Процессорными переменными” описаны в include/linux/ percpu.h и arch/x86/include/asm/percpu.h.
#define alloc_percpu(type)
void free_percpu(void __percpu *__pdata);и т.д.
Скажем так, классическое определение: Атомарные операции — выполняются, как неделимые, либо полностью, либо не выполняются вообще. Однако, что это значит в контексте исполнения процесса? Могут ли нас прервать во время исполнения, могут ли нас переключить на исполнение другого процесса? В классическом понимании прерывать исполнение нельзя, но в ядре стараются не запрещать прерывание, хотя такая возможность и поддерживается (/include/linux/irqflags.h). Процедура local_irq_save отключает прерывания, а local_irq_restore восстанавливает ранее отключенные прерывания, атомарные операции их иногда используют, но это не рекомендовано.
С переключением немного посложнее. В операциях с префиксом atomic_* скорее всего вас не переключат, пока операция не выполнится, так как там, очень часто, по одной ассемблерной инструкции, однако в более сложных(крупных) операциях нас могут и переключить, другое дело, что увидеть изменения данных, пока мы не завершим, никто не должен.
Таким образом атомарная операция — операция результат которой становится видим только полностью, после её завершения, половинчатый результат никто увидеть не сможет. Или она не исполняется, потому что ресурс занят, к примеру.
В ядре под атомарными операциями подразумевается именно операции с префиксом atomic_*, они платформозависимые. Для x86 их можно найти в /arch/x86/include/asm/atomic.h. В атомарных операциях используется тип данных atomic_t (/include/linux/types.h) или atomic64_t:
typedef struct {
int counter;
} atomic_t;
#ifdef CONFIG_64BIT
typedef struct {
long counter;
} atomic64_t;
#endifКак можно заметить класс atomic_* операций применяется в основном для простых объектов, таких как счётчики. Но как обеспечить атомарность работы с ними? В x86 есть несколько путей выполнения данной задачи:
- Использовать lock префикс для ассемблерной операции. Lock префикс гарантирует уникальное(mandatory) владение ресурсом даже в многопроцессорной системе.
- Специальные операции, такие как CMPXCHG, XCHG. В atomic операциях линукс используется lock префикс, что связано с тем, что она быстрее, чем CMPXCHG, так как он раскрывается примерно в следующую последовательность команд:
CMPXCHG ——> lock
read
cmp
jne
write
unloc
static __always_inline void atomic_dec(atomic_t *v)
{
asm volatile(LOCK_PREFIX "decl %0"
: "+m" (v->counter));
}Реализуем теперь сами функцию atomic_dec_and_test, она должна уменьшить значение счётчика на единицу и вернуть 1, если counter == 0, или 0 в противном случае.
atomic_dec_and_test( &counter )
{
lock decl %counter //выполнится атомарно
jnz exit
xor eax, eax
ret
exit:
mov eax, 1
ret
}Как видим, после lock dcl %counter, дальше работаем с локальными регистрами, потому относительно других процессов всё происходит атомарно.
У современных компиляторов очень агрессивные алгоритмы оптимизации, они могут менять инструкции местами, чтобы оптимизировать обращение к регистрам, ускорить выполнение программы и т.д. Чтобы ассемблерные команды одной СИ-функции не перемешались с командами другой есть барьеры оптимизации в Linux. (/include/linux/compiler-gcc.h)
#define barrier() __asm__ __volatile__("": : :"memory")Такая пустая “ассмеблерная” инструкция говорит компилятору, что он не может свободно применять оптимизации здесь, так как функции полностью изменяют память.
Однако, кроме компилятора современные процессоры так же оптимизируют исполнение инструкция — Out Of Order Execution (OOO). Для того, чтобы процессор выполнил ассемблерные инструкции в нужном порядке, есть барьеры памяти.(!TODO: дописать с примером).
Если ресурс свободен, то процесс берёт на него блокировку и работает с ним, если же обнаруживается, что ресурс уже кем-то заблокирован, процесс крутится в цикле, пока блокировка не будет снята.
Это так называемое “Активное” ожидание. С одной стороны оно может показаться не очень эффективной, но в ядре многие ресурсы оказываются заблокированными на сравнительно небольшое время. А перевод процесса в состояние ожидания и обратно занимает приличное количество времени. В критической секции, защищённой спин блокировкой, отключается вытеснение. Spin lock описывается структурой spinlock_t (/include/linux/spinlock_types.h). Однако для понимания рассмотрим пример попроще.
struct spinlock_t {
int v;
}spin_lock_init — инициализирует спин блокировку. После этого она будет в разблокированном состоянии = 1.
#define __ARCH_SPIN_LOCK_UNLOCKED { 1 }
spin_unlock() — разблокировать спинлок.
Для нашего примера будет выглядеть так:
void spin_unlock(struct spinlock_t *sp) {
sp->v = 1;
}spin_lock() — выполнять цикл, пока спинлок не станет равен 1, после сделать его 0. Напишем свой void spin_lock, чуть-чуть попроще, при спинлок = 1 спинлок свободен и мы берём его, при <= 0 занят и мы крутимся в цикле:
void spin_lock(struct spinlock_t *sp) {
TRY:
lock decl (%sp)
jz SUCCESS
SPIN:
cmp (%sp), 1
je TRY
jmp SPIN
SUCCESS:
ret
}Оригинальные функции можно начать разбирать с файла — /include/linux/ spinlock.h.
У такой спин блокировки есть несколько проблем:
- Порядок попытки захвата спинлока не гарантирует порядок его взятия. Иными словами, такая блокировка не честна по отношению к процессам, которые её ожидают. Эту проблему могут решить Ticket spinlocks, но они не помогут во втором случае.
- Можно взять только в исключительное пользование, а значит, что нельзя параллельно читать одни и те же структуры.
Для улучшения параллелизма есть read/write lock.
Практика показывает, что операции чтения более распространены, чем операции записи. При rwlock одновременно разрешено либо 1 операция записи, либо множество операций чтения. Описывается она структурой — rwlock_t (/include/linux/rwlock_types.h) rwlock_init() инициализирует rwlock = 0x01000000
read_lock() идейно выглядит так:
int read_lock(rwlock_t *lock)
{
atomic_t *count = (atomic_t *)lock->lock;
atomic_dec(count);
if (atomic_read(count) >= 0)
return 1;
atomic_inc(count);
return 0;
}Каждая read блокировка уменьшает значение счётчика на 1 и так до нуля. Состояние lock == 0x0 означает, что блокировка уже взята на запись. Разблокировка — просто увеличить значение счётчика на 1.
void read_unlock(rwlock_t *lock)
{
lock incl (%lock)
}Взятие и освобождение блокировки для записи:
int write_lock(rwlock_t *lock)
{
atomic_t *count = (atomic_t *)lock->lock;
if (atomic_sub_and_test(0x01000000, count))
return 1;
atomic_add(0x01000000, count);
return 0;
}
void write_unlock(rwlock_t *lock)
{
lock; addl $0x01000000,rwlp
}Минус r/wlock в том, что приоритет запросов блокировки на чтение и запись одинакова => при последовательности запросов read -> write -> read нет определённости в том, что произойдёт. Запросто может оказаться, что 2-ое будут читать, а wirte запрос будет ждать, хотя он и пришёл раньше второго read.
С этой проблемой борется другой примитив синхронизации — seqlock (/include/linux/seqlock.h). Основное отличие в том, что приоритет записи намного выше приоритета операции чтения. Описывается данная блокировка структурой с двумя полями:
typedef struct {
struct seqcount seqcount; // При обычной компиляции тут unsigned sequence;
spinlock_t lock;
} seqlock_t;Каждый читающий должен прочитать счётчик sequence дважды: до и после чтения. Если они совпадают, то он прочитал консистентные данные, которые никто не изменил, если отличаются, то считанные данные устарели, так как активизировался пишущий тракт. Пишущие увеличивают значение счётчика на 1 до записи и после.
Этот механизм очень похож на работу со счётчиком jiffies_64 (/include/linux/jiffies.h). Это 64 битный счётчик на 32 битных машинах его нельзя атомарно прочитать или изменить. Потому на них применяется алгоритм похожий надписанный выше: int seqcount = 0;
u64 get_jiffies_64()
{
int seq = 0;
u64 j = 0;
do {
seq = seqcount;
j = jiffies_64;
} while (seq == seqcount && seqcount%2 == 0)
return j;
}
void inc_jiffies_64()
{
++seqcount;
++jiffies_64;
++seqcount;
}RCU — обновление копии для чтения. (/include/linux/rcupdate.h) Это эволюция идей работы с ресурсами, которые обычно читаются чаще, чем изменяются. Эта технология позволяет работать в одними ресурсами одновременного нескольким писателям и читателям. Она lock-less и не требует постаянных попыток прочить данные. В ней нет совместно используемых структур данных, что существенно для скорости работы из-за конкуренции за них в кэше.
- Можно защищать только динамические данные, доступные по ссылке.
- Нельзя спать внутри RCU. Когда тракту в ядре надо прочитать данные он вызывает — rcu_read_lock(), что эквивалентно preempt_disable(). Затем читатель разыменовывает указатель и приступает к чтению. После окончания работы с данными нужно вызвать rcu_read_unlock()(preempt_enable).
{
rcu_read_lock();
obj-> …;
…
rcu_read_unlock();
}Как видим читаль почти что ничего не делает, значит всё делает писатель. Когда он хочет изменить структуру, о сначала разыменовывает указатель, делает себе её копию, после обновляет копию. Закончив обновление, пишущий тракт заменяет указатель, чтобы он указывал на новую копию, подмена указателя происходит атомарно, а значит любой читающий и пишущий тракт видит консистентную либо старую, либо новую копию объекта. После всего остаётся только один вопрос — когда освобождать старый объект? Потенциально каждый читающий может читать старую копию, потому каждый из них должен сначала вызвать rcu_read_unlock(), а только потом старую копию можно освободить.