© Георгиевский Анатолий, 21.08.2010

Атомарные операции

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

Возникает задача синхронизации и обмена данными между процессами с общей памятью. Процессы могут выполняться на одном процессоре (прерывая друг-друга) или одновременно на нескольких ядрах. При одновременном доступе к переменой в памяти может возникнуть ситуация, когда процесс-1 прочитал переменную, потом произошло переключение задач, процесс-2 изменил значение переменной в памяти, и только после этого процесс-1 сохранил свое значение. В этом случае 1+1 не равно 2. Возникает ошибка. Чтобы избежать подобных ошибок следует использовать атомарные операции, действие которых не прерывается. Типичные примеры использования атомарных операций: счетчик числа ссылок на объект, синхронизация работы двух процессов через флаги состояний.

RISC load-store architecture

Аппаратная поддержка атомарных операций встречается на процессорах DEC Alpha AXP, во всех моделях (с 1992 г) и на процессорах MIPS с архитектурой MIPS32/MIPS64, начиная с 1990 г. Обе архитектуры относятся к RISC процессорам. Архитектура Alpha изначально ориентирована на рабочие станции и сервера с симметричной многопроцессорной архитектурой (SMP). Один из принципов построения архитектуры RISC -- не должно быть инструкций, которые читают-модифицируют-и-сохраняют данные в одну инструкцию. Разделение операций чтения, записи и исполнения позволяет реализовать ассинхронный доступ к памяти, эффективно грузить конвейер(ы), реализовать многопоточность, многопроцессорность с общей памятью.

Архитектура Alpha создавалась на многие годы вперед и ещё в конце 80-х начале 90-х разработчики прогнозировали развитие в сторону многоядерных архитектур. Каждое ядро должно иметь возможность исполнять код независимо и предоставлять возможности исполнения многопотоковых программ с общим сегментом памяти данных. Для синхронизации процессов, для обмена данными между конвейерами и между ядрами с общим кешем, вопреки принципу разделения операций чтения и записи, необходимо обеспечивать неприкосновенность некоторых переменных в течение цикла между чтением переменной из памяти и сохранением обратно в память. Был предложен неблокирующий метод контроля неприкосновенности выделнной ячейки памяти.

Неблокирующий эксклюзивный доступ к памяти

Неблокирующий метод реализуется с использованием пары процессорных инструкций эксклюзивного доступа (Load-link/Store-Conditional):

  • (LL) load-linked -- загрузить данные в регистр с пометкой
  • (SC) store-conditional -- сохранить условно

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

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

Помимо архитектуры Alpha, механизм неблокирующих операций LL/SC поддержан на платформах: ARM, PowerPC и MIPS.

Приведем пример составления атомарных операций с использованием инструкций эксклюзивного доступа LL/SC. В нашем примере функция SС возвращает TRUE если значение переменной по указанному адресу не изменилось с момента последней операции LL.

int atomic_inc(volatile int *counter)
{
	int ret, value;
	do {
		value = LL(counter);
		ret = SC(counter, value+1);
	} while (!ret);
	return value;
}

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

Блокирующие атомарные операции

Система команд Intel IA-32/64 пердусматривает возможность составления блокирующих команд чтение-изменение-сохранение, с использованием префикса LOCK. В этом случае гарантируется эксклюзивный доступ к памяти между операциями чтения и сохранения.

Атомарная инструкция сравнения и замены, compare-and-swap (CAS)

Атомарная операция CAS поддержана в архитектуре SPARC и реализуется в Intel IA-32/64 c использованием префикса блокировки доступа (LOCK + CMPXCHG), когда замена производится между регистром и ячейкой памяти при условии сравнения.

Приведем пример составления атомарных операций с использованием атомарной инструкции CAS. В нашем примере функция CAS возвращает TRUE если значение аргумента-2 равно значению в памяти.

int atomic_inc(volatile int *counter)
{
	int ret, value;
	do {
		value = *counter;
		ret = CAS(counter, value, value+1);
	} while (!ret);
	return value;
}

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

Атомарная операция CAS может быть реализована с использованием неблокируеющего метода LL/SC. В современных многоядерных процессорах использование механизма блокировок доступа вызывает простой конвейера и синхронизацию ядер, поэтому неблокирующие методы основанные на методе LL/SC считаются более предпочтительными.

Инструкции эксклюзивного доступа и компилятор

Компилятор языка Си не должен использовать процессорные инструкции эксклюзивного доступа LL/SC. Это означает, что на языке Си можно реализовать атомарные операции с использованием ассемблерных вставок или встроенных функций __builtin_*, см. документацию на GCC (Built-in functions for atomic memory access).

Библиотека атомарных операций

Попробуем сформулировать библиотеку атомарных операций, см. например, [Glib]. Атомарные операции используются в ядре Linux для задач синхронизации, для распределения ресурсов, для назначения идентификаторов и пр.

Атомарные операции определяются над неделимыми типами данных: над целыми числами и над указателями. Операции чтения и записи являются атомарными для простых типов, однако если данные не выровнены в памяти или располагаются в двух линиях кеш или пересекают границу страницы памяти, в таком случае операция чтения и записи не является атомарной, может возникнуть прерывание между операциями загрузки/сохранения данных.

Можно определить следующие типы операций: Атомарное сложение/вычитание: INC, DEC, ADD, SUB; Битовые атомарные операции: AND, OR, XOR; атомарная операция замены со сравнением CMPXCHG.

Декларация переменных для атомарных операций
typedef struct { volatile int counter; } atomic_t;

Инициализация статических переменных атомарного типа выполняется с помощью макроса

#define ATOMIC_INIT(v) {(v)}
static atomic_t v = ATOMIC_INIT(1);

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

#define atomic_set(v, i)	((v)->counter = (i))
#define atomic_get(v)		((v)->counter)

Операци чтения и записи являются атомарными, неделимыми на микрооперации.

Минимальный набор команд для реализации счетчиков и флагов:

int atomic_add(int d, atomic_t *v);
int atomic_sub(int d, atomic_t *v);

int atomic_inc(atomic_t *v);
int atomic_dec(atomic_t *v);

int atomic_set_bit(unsigned long nr, volatile unsigned long *addr);
int atomic_clear_bit(unsigned long nr, volatile unsigned long *addr);
int atomic_change_bit(unsigned long nr, volatile unsigned long *addr);

int atomic_cmpxchg(atomic_t *v, int old, int new);

Синхронизация процессоров

Сохранение переменной в память происходит не сразу. Сначала переменная записиывается из регистра в кеш-память, затем линия кеш при необходимости копируется в физическую память. Копирование в память происходит сравнительно медлено, потому при копировании используется дополнительная буферизация. Чтобы один процессор прочитал то, что было записано в переменную другим процессором, надо дождаться, когда переменная из кеш будет скопирована в физическую память. Для этого используются т.н. барьеры памяти и инструкции синхронизации кеш-памяти. Инструкция "memory barrier" или SYNC вызывает сброс результатов всех операций записи в память. Более того, для процессоров с нарушением порядка исполнения инструкций команда SYNC ожидает звершения всех инструкций запущенных на исполнение до команды SYNC, до момента завершения синхронизации ни одна инструкция не запускается на исполнение.

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

В зависимости от архитектуры процессора, синхронизация процессоров при выполнении операций CAS и LL/SC может выполняться неявно или требовать явного использования инструкций синхронизации (барьеров памяти). Даже для моделей процессоров с одинаковой системой команд но разным количеством процессоров в системе или количеством процессорных ядер условия синхронизации процессоров могут быть разные.

Реализация атомарных битовых операций

Далее, мы будем считать, что все необходимые "барьеры памяти" уже включены в базовые атомарные операции.

void atomic_bit_set (atomic_t * v, unsigned int mask)
{
	unsigned int old, val;
	do {
		old = atomic_get(v);
		val = old | mask;
	} while (!atomic_cmpxchg(v, old, val));
}

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

Заключение

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

Ссылки


Semantics and Behavior of Atomic and Bitmask Operations, David S. Miller
LINUX KERNEL MEMORY BARRIERS
[]Intel® 64 and IA-32 Architectures Software Developer’s Manual Vol.2A,Vol.2B
[ARM DDI 0100I] ARM Architecture Reference Manual
[ARM DDI 0337I] Cortex-M3 Revision r2p1 Technical Reference Manual
[ARM DDI 0344K]Cortex™-A8 Revision: r3p2 Technical Reference Manual
[] The SPARC Architecture Manual, Version 9
[] MIPS64® Architecture For Programmers Volume I: Introduction to the MIPS64® Architecture
[]Alpha Architecture Handbook Version 3
[Glib]Библиотека Glib-2.+

()