Атомарные операции в Cortex-M3


Часто возникает ситуация, когда одна и та-же переменная используется и изменяется из разных потоков или из островного потока и прерываний. В этом случае модификацию такой разделяемой переменной необходимо осуществлять атомарно. Простейший способ обеспечения атомарности — это запрет прерываний на время операции, но это не наш метод — в ядре ARM Cortex-M3 есть более интересные средства для этого.
В большинстве 8/16 битных микроконтроллеров, таких как AVR, PIC или MSP430 запрещение прерываний — единственный способ обеспечения атомарности операций чтение-модификация-запись:

	сохранить текущее состояние прерываний;
	запретить все прерывания;
	прочитать текущее значение;
	вычислить новое значение;
	записать новое значение;
	восстановить состояние прерываний;

В большинстве случаев такой подход вполне приемлем, если вычисление нового значения занимает не много времени и нет прерываний чувствительных к дополнительной задержке. Если-же такие прерывания есть (например, в прерывании по таймеру формируется какой-нибудь протокол обмена, чувствительный к таймингам/джиттеру), то остаётся только выборочно запрещать прерывания, которые могут изменить интересующую нас переменную. Но этот подход не универсален.
В случае применения RTOS всё становится ещё интереснее, помимо прерываний есть ещё и потоки и в большинстве случаев применяются средства синхронизации предоставляемые операционной системой. Стоимость этой самой синхронизации становится при этом еще больше.

В ядре Cortex-M3 есть встроенные средства синхронизации, позволяющие осуществлять операции чтение-модификация-запись без блокирования прерываний и других потоков. Это набор инструкций LDREX и STREX, осуществляющие эксклюзивные загрузку и сохранение ячеек памяти.
Команда LDREX загружает значение по указанному адресу в регистр и взводит специальный флаг процессора, сигнализирующий об эксклюзивном доступе к памяти.
STREX — проверяет не был-ли нарушен эксклюзивный доступ к памяти, если нет, то записывает значение из входного регистра по указанному адресу и сбрасывает флаг эксклюзивного доступа. При этом в выходном регистре будет записан ноль. Если между LDREX и STREX произошло прерывание и оно что-то записало в память (а оно обязательно хоть регистры, да сохранит в стек), то STREX ничего не запишет в память и в выходной регистре будет записана 1. Это значит, что значение в памяти могло изменится (а могло и нет) и нам надо снова перечитать его из памяти модифицировать и снова попытаться его сохранить. Естественно, чем меньше кода между LDREX и STREX, тем меньше вероятность, что там произойдёт прерывание и больше шансов обновить значение с первого раза.
У этих команд существуют модификации, загружающие/сохраняющие байт, полуслово(16 бит) и слово(32 бит) соответственно: LDREXB/STREXB, LDREXH/STREXH, LDREXW/STREXW.
Есть еще команда CLREX, которая не имеет параметров и просто очищает флаг эксклюзивного доступа.
Синтаксис этих команд можно посмотреть в Cortex-M3 programming manual.

В заголовке «core_cm3.h», поставляемым ARM Limited, есть определения для этих и многих других команд для разных компиляторов, ими и воспользуемся:
uint32_t AtomicFetchAndAdd(uint32_t * ptr, uint32_t value)
{
	uint32_t oldValue, newValue;
	do
	{
		oldValue = __LDREXW(ptr);
		newValue = oldValue + value;
	}while(__STREXW(newValue, ptr));
	return oldValue;
}

uint32_t AtomicAddAndFetch(uint32_t * ptr, uint32_t value)
{
	uint32_t oldValue, newValue;
	do
	{
		oldValue = __LDREXW(ptr);
		newValue = oldValue + value;
	}while(__STREXW(newValue, ptr));
	return newValue;
}

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

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

UPDATE.
Если «атомарно» должен выполнятся достаточно длинный кусок кода и велика вероятность, что он будет слишком часто прерываться, то применение этого подхода напрямую будет не очень эффективно. Тут нам поможет распространённая в многопоточном программировании стратегия «сделай-запиши-(попытайся снова)». Для этого нам понадобится функция CompareExchange (типа InterlockedCompareExchange в Windows API), которая атомарно сравнивает значение по указанному адресу с одним параметром, и заменяет его значением другого параметра в зависимости от результата сравнения:

bool CompareExchange(uint32_t * ptr, uint32_t oldValue, uint32_t newValue)
{
// эксклюзивно читаем значение переменной и сравниваем со старым значением 
	if(__LDREXW(ptr) == oldValue)
// пытаемся эксклюзивно записать в переменную новое значение
		return __STREXW(newValue, ptr) == 0;
// кто-то изменил ячейку до нас 
	__CLREX();
	return false;
}

Эта функция возвращает true если значение в переменной совпадает с тем, что мы ожидаем и никто нас не прервал, пока мы его сравнивали и обновляли.
Здесь между LDREX и STRE всего одно сравнение и переход и вероятность прерывания в этом месте очень мала.
Теперь «длинная атомарная» операция может быть реализована так:

// переменная, которую нужно атомарно модифицировать
volatile uint32_t value;
...
uint32_t oldValue;
uint32_t newValue;
do
{
// запоминаем старое значение
	oldValue = value;
// производим длинное вычисление
	newValue = SomeLongOperation(oldValue);
// пытаемся атомарно заменить исходное значение
// если его кто-то изменил без нас - перечитываем и вычисляем снова
}while(!CompareExchange((uint32_t *)&value, oldValue, newValue));

Теперь перечитывать и заново вычислять придётся только если изменится значение только одной переменной «value».

Кстати, в GCC начиная с версии 4.6 были реализованы Atomic-Builtins для ARM (до того они были только для x86), построенные по описываемому принципу:
http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html

  • +8
  • 23 мая 2011, 17:12
  • neiver

Комментарии (33)

RSS свернуть / развернуть
Хм. Она проверяет всю память? Или ту самую ячейку?

А то в высоконагруженной системе же получится полный ад:

Например:

Диспетчер пихает в очередь байт (предварительно найдя ее конец и подготовив место), естественно проверяет нет ли туда записи. Если флаг оказался сброшен, то ему надо заново найти конец очереди, опять подготовить байт и опять попытаться записать. Если нагрузка большая и постоянно что то вызывается и пишется в память, то процесс залочится.
0
Флаг ставится, если верить мануалу, для всей SRAM. И любая запись в память нарушает эксклюзивный доступ. Поэтому между LDREX и STREX должно быть как можно меньше всего. А если нужно атомарно сделать длинную операцию… сейчас лучше допишу апдейт к статье…
0
Хм. Тогда получается запрет прерываний наоборот. Т.е. задача запрещающая прерывания повышает свой приоритет над системой.

А задача работающая с **REX наоборот понижает свой приоритет, позволяя системе ее перебивать. Удобно.
0
Я читал здесь: www.doulos.com/knowhow/arm/Hints_and_Tips/Implementing_Semaphores/
Пишут, что флаг только для одной ячейки.
With this mechanism, bus masters won't be locked out from memory access altogether, but only if they access the same location.
0
да, совершенно верно, только непонятно, что произойдет если две инструкции LDREX по разным адресам сработают. Будет ли сохраняться значения для каждой ячейки или же последний вход перешибет таки первый, и первому придется идти на цикл…
0
Если две инструкции LDREX по разным адресам сработают, то STREX для первой из них отвалится и пойдёт на второй круг, для второй сработает.
0
спасибо, весьма полезно)
0
как ни искал не смог найти ф-цию uint32_t AtomicAddAndFetch(uint32_t * ptr, uint32_t value) в хидере core_cm3.h и в его сишном файле.
В какой версии CMSIS его можно найти?
0
Так ее и нет там. В core_cm3.h есть функции __LDREXW и __STREXW. А AtomicFetchAndAdd — это уже моё творчество. Ее описание в статье есть.
0
В IAR есть прикольная директива процессора _monitor вроде как она обеспечивает атомарность доступа
0
А в KEIL подобное _monitor есть?
0
в KEIL есть реализация инструкции процессора ATOMIC. Смысл таков, что инструкция ATOMIC блокирует прерывания от одного до 4 циклов процессора. Сразу после этой инструкции можно написать коротенький код, который поместился бы в 4 такта. Ядро гарантирует, что в этом промежутке прерывание не возникнет.
Подробнее здесь и здесь
0
Если нужен большой кусок — то стандартно: Сохранение флага прерываний, запрет прерываний, действие, восстановление флага прерываний.
0
А как быть случае, если надо одновременно «защитить» несколько переменных? Например, имеется буфер типа стека, в который я в произвольный момент ложу пакеты, состоящие из адреса и данных (и меняю указатель буфера). В прерывании извлекается один пакет и данные отправляются по нужному адресу. В таком случае мне надо защитить 3 операции: запись адреса, запись данных, чтение-изменение-запись указателя в буфере. Только запрет-восстановление ОСОБОГО прерывания? И кстати как это просто сделать для ARM Cortex-M3?
0
Для этого используются lock-free алгоритмы/структуры данных, AFAIK. Подробнее — вики и гугль.
0
Пожалуй, полезно будет покопаться тут www.cl.cam.ac.uk/research/srg/netos/lock-free/
0
А еще лучше — тут.
0
Vga, evsi — спасибо за подсказки, буду изучать. Но тут дело не столько в специальных структурах данных, а в самой идее — атомарное выполнение непрерывного блока команд программы. Раз уж статья называется «Атомарные операции в Cortex-M3» то логично эти методы здесь описать, а не один вариант операции «чтение-модификация-запись» с одной переменной.
0
Согласен. Проблема больше в том, что lock-free операции/алгоритмы не достаточно хорошо известны большинству программеров. Даже сам факт их существования.
0
Да правда. И я не знал — теперь изучаю. Спасибо за подсказку ))
0
Как я понимаю, статье посвящена не атомарному выполнению вообще (это как раз то, что делается проще всего — disable_irq(); действия; restore_irq();), а существованию в ARM элементарных атомарных операций. Сомневаюсь, что в нем есть аналогичное для более крупных структур — для этого обычно как раз и используются lock-free алгоритмы. А примитивы — в первую очередь для того, чтобы эти самые алгоритмы можно было реализовать (они обычно как раз на таких примитивах и строятся), плюс для реализации средств синхронизации в ОС.
0
Посидел, подумал над использованием команд LDREX и STREX и до меня доперло, что их можно использовать для включения-выключения флага захвата (блокировки) ресурса (а наверно как-то так реализуются механизмы мьютексов в ОС). Попытался изменить функцию из статьи:
// Захватить (заблокировать) ресурс
void Lock(uint8_t *ptr)
{
        do {
                while (__LDREXB(ptr));        // ждем освобождение ресурса
        } while (__STREXB(1, ptr));           // пытаемся захватить (заблокировать) ресурс
}

// Освободить (разблокировать) ресурс
void Unlock(uint8_t *ptr)
{
        *ptr = 0;        // освобождаем ресурс
}
а между вызовами Lock() и Unlock() защищенный блок управления ресурсом получится.
Ну вот как-то так…
0
Как концепция — ага.
На практике — Unlock может позвать по ошибке не тот поток, который заблокировал ресурс. Отловить такую ошибку будет очень сложно.
После *ptr = 0; нужно поставить барьер __DSB();. Чтоб гарантировать, что эта запись завершится прежде, чем будит выполнятся другие операции. Иначе можно словить очень коварные глюки при наличии нескольких зависимых блокировок в нескольких потоках.
0
Угу. Такой вариант, обычно, называют спинлоком (spinlock).
0
сюда же в эту статью следовало бы добавить bit banding. Тоже вполне себе атомарный доступ побитово предоставляет. http://we.easyelectronics.ru/STM32/stm32---bit-banding.html
0
(а оно обязательно хоть регистры, да сохранит в стек)
думаю, это выражение необходимо подправить с учетом того, что пара LDREX-STREX контролирует только одну или 2 или 4 ячейки памяти в зависимости от разрядности переменной.
0

   145:                                 oldValue = __LDREXH(ptr); 
0x0800190C E8D10F5F  LDREXH        r0,[r1]0x0800190C E8D10F5F  LDREXH        r0,[r1]
   146:                                 newValue = (oldValue < CHECK_COUNTER)? CHECK_COUNTER : oldValue; 
0x08001910 2815      CMP           r0,#0x15
0x08001912 D200      BCS           0x08001916
0x08001914 2015      MOVS          r0,#0x15
   147:                                 (*ptr)++; 
0x08001916 880A      LDRH          r2,[r1,#0x00]
0x08001918 1C52      ADDS          r2,r2,#1
0x0800191A 800A      STRH          r2,[r1,#0x00]
   148:                         }while(__STREXH(newValue, ptr)); 
   149:                 } 
   150:         } 
   151:         else 
   152:                 NVIC_SystemReset(); 
0x0800191C E8C10F52  STREXH        r2,r0,[r1]
0x08001920 2A00      CMP           r2,#0x00
0x08001922 D1F3      BNE           0x0800190C
   153: } 
По идее этот цикл должен быть бесконечным. Но по факту — этого не происходит. Камушек: STM32F407VET6. Или я чего-то не понимаю? Стал разбираться по причине того, что связка LDREX STREX почему-то не работает. Добавил строчку
(*ptr)++;
пытаясь увидеть бесконечный цикл. Но не тут-то было.
Причем если добавить в цикл
__CLREX();
то зацикливание происходит. В чем фишка?
0
для удобоваримости код на си:
ptr = &Counters[channel];
do
{
	oldValue = __LDREXH(ptr);
	newValue = (oldValue < CHECK_COUNTER)? CHECK_COUNTER : oldValue;
	(*ptr)++;
}while(__STREXH(newValue, ptr));
0
а вот так код зацикливается:
ptr = &Counters[channel];
do
{
	oldValue = __LDREXH(ptr);
	newValue = (oldValue < CHECK_COUNTER)? CHECK_COUNTER : oldValue;
	__STREXH(__LDREXH(ptr) + 1, ptr);
}while(__STREXH(newValue, ptr));

Усложнили код:
ptr = &Counters[channel];
ptr2 = &Counters[(channel + 1)&0x07];
do
{
	oldValue = __LDREXH(ptr);
	newValue = (oldValue < CHECK_COUNTER)? CHECK_COUNTER : oldValue;
	__STREXH(__LDREXH(ptr2) + 1, ptr2);
}while(__STREXH(newValue, ptr));

Данный код тоже уходит в бесконечный цикл, хотя изменение информации происходит уже в другой ячейке.
ВЫВОД: ВАЖНОЕ ЗАМЕЧАНИЕ!
Система не позволяет выполниться инструкциям вида STREX два раза подряд без LDREX. ВСЁ! Больше никаких ограничений и слежки памяти! Ничего он в памяти не отслеживает. По крайней мере в том камне, что у меня сейчас на столе.
ВЫВОД 2:
Если ячейки памяти изменять не инструкциями LDREX и STREX — то система эти изменения не отслеживает! Проще говоря, если уж решил какую-то ячейку памяти отслеживать через пару LDREX STREX — то будь добр, используй везде такой принцип, даже в самом высокоприоритетном прерывании, а не только в основном цикле
0
правда в самом высокоприоритетном прерывании можно сделать и послабление:
(*ptr)++;
__CLREX();
0
Сспасибо за дополнения.
0
Хорошо бы обновить статью, и точнее описать механизм работы команд LDREX, STREX CLREX. Потому что мало кто до комментариев опускается. А неверное представление о работе камня вылилось мне в 2 рабочих дня поймать ошибку, осознать происходящее, протестировать и сделать вывод.
0
Кстати, по теме: Нашел классный документ, в котором описаны все способы синхронизации в одном месте. Аглицкий канешно. Если перевести — цены ему не будет.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.