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

Я работаю над встроенной ОС для ARM. Однако есть несколько вещей, которые я не понимал в архитектуре даже после обращения к ARMARM и источнику Linux.

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

ARM ARM говорит, что инструкции Load и Store являются атомарными, и выполнение гарантировано завершено до выполнения обработчика прерываний. Проверено, посмотрев

arch/arm/include/asm/atomic.h :
    #define atomic_read(v)  (*(volatile int *)&(v)->counter)
    #define atomic_set(v,i) (((v)->counter) = (i))

Однако проблема возникает, когда я хочу управлять этим значением атомарно, используя инструкции cpu (atomic_inc, atomic_dec, atomic_cmpxchg и т.д.), которые используют LDREX и STREX для ARMv7 (моя цель).

ARMARM ничего не говорит о блокировке прерываний в этом разделе, поэтому я предполагаю, что прерывание может происходить между LDREX и STREX. Дело в том, что речь идет о блокировке шины памяти, которая, по моему мнению, полезна только для систем MP, где в то же время может быть больше процессоров, пытающихся получить доступ к одному и тому же местоположению. Но для UP (и, возможно, MP), если в этом маленьком окне LDREX и STREX срабатывает прерывание таймера (или IPI для SMP), обработчик Exception выполняет, возможно, изменения cpu-контекста и возвращается к новой задаче, однако теперь поразительная часть, он выполняет "CLREX" и, следовательно, удаляет любую исключительную блокировку, удерживаемую предыдущим потоком. Итак, насколько лучше использовать LDREX и STREX, чем LDR и STR для атомарности в системе UP?

Я прочитал что-то об эксклюзивном мониторе блокировки, поэтому у меня есть возможная теория о том, что когда поток возобновляется и запускается STREX, монитор os вызывает этот вызов, который может быть обнаружен, и цикл может быть повторно выполнен используя новое значение в процессе (ответьте на LDREX), Am я прямо здесь?

Ответ 1

Хорошо, получил ответ со своего веб-сайта .

Если контекстный переключатель планирует процесс после того, как процесс выполнил Load-Exclusive, но до того, как он выполнит Store-Exclusive, Store-Exclusive вернет ложный отрицательный результат, когда процесс возобновится, а память не будет обновлена. Это не влияет на функциональность программы, так как процесс может немедленно выполнить операцию.

Ответ 2

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

do
{
  new_value = __LDREXW(dest) + 1;
} while (__STREXW(new_value, dest));

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

do
{
  old_value = *dest;

  new_value = complicated_function(old_value);
} while (CompareAndStore(dest, new_value, old_value) != 0);

... Assuming CompareAndStore is something like:

uint32_t CompareAndStore(uint32_t *dest, uint32_t new_value, uint_32 old_value)
{
  do
  {
    if (__LDREXW(dest) != old_value) return 1; // Failure
  } while(__STREXW(new_value, dest);
  return 0;
}

Этот код должен будет повторно запустить свой основной цикл, если что-то изменит * dest при вычислении нового значения, но только небольшой цикл необходимо будет повторно запустить, если __STREXW не сработает по какой-либо другой причине [что, надеюсь, не слишком вероятно, учитывая, что между __LDREXW и __STREXW будет только две команды

Добавление Примером ситуации, когда "вычислять новое значение на основе старого" может быть сложно, будет тот, где "значения" являются фактически ссылками на сложную структуру данных. Код может извлекать старую ссылку, выводить новую структуру данных из старого и затем обновлять ссылку. Этот шаблон чаще всего встречается в сборках, собранных с помощью мусора, чем в "голом металле", но существует множество способов, которые он может придумать даже при программировании голого металла. Обычные распределители malloc/calloc обычно не являются потокобезопасными/прерывистыми, но часто используются распределители для структур фиксированного размера. Если у вас есть "пул" некоторого количества двух структур данных (скажем, 255), можно использовать что-то вроде:

#define FOO_POOL_SIZE_SHIFT 8
#define FOO_POOL_SIZE (1 << FOO_POOL_SIZE_SHIFT)
#define FOO_POOL_SIZE_MASK (FOO_POOL_SIZE-1)

void do_update(void)
{
  // The foo_pool_alloc() method should return a slot number in the lower bits and
  // some sort of counter value in the upper bits so that once some particular
  // uint32_t value is returned, that same value will not be returned again unless
  // there are at least (UINT_MAX)/(FOO_POOL_SIZE) intervening allocations (to avoid
  // the possibility that while one task is performing its update, a second task
  // changes the thing to a new one and releases the old one, and a third task gets
  // given the newly-freed item and changes the thing to that, such that from the
  // point of view of the first task, the thing never changed.)

  uint32_t new_thing = foo_pool_alloc();
  uint32_t old_thing;
  do
  {
    // Capture old reference
    old_thing = foo_current_thing;

    // Compute new thing based on old one
    update_thing(&foo_pool[new_thing & FOO_POOL_SIZE_MASK],
      &foo_pool[old_thing & FOO_POOL_SIZE_MASK);
  } while(CompareAndSwap(&foo_current_thing, new_thing, old_thing) != 0);
  foo_pool_free(old_thing);
}

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