Барьеры памяти по сравнению со взаимно блокируемыми операциями
Я пытаюсь улучшить свое понимание барьеров памяти. Предположим, что у нас есть слабая модель памяти, и мы адаптируем алгоритм Dekker. Действительно ли возможно заставить его работать правильно под слабой моделью памяти путем добавления барьеров памяти?
Я думаю, что ответ является удивлением нет. Причина (если я корректен) состоит в том, что, хотя барьер памяти может использоваться, чтобы гарантировать, что чтение не перемещено мимо другого, оно не может гарантировать, что чтение не видит устаревшие данные (такие как это в кэше). Таким образом это видело некоторое время в прошлом, когда критический раздел был разблокирован (на кэш ЦП), но в текущее время другие процессоры могли бы видеть его, как заблокировано. Если мое понимание корректно, нужно использовать взаимно блокируемые операции, такие как те, которые обычно звонившийся тест-и-набор или сравнивать-и-подкачивать для обеспечения синхронизировал соглашение о значении в ячейке памяти среди нескольких процессоров.
Таким образом мы можем справедливо ожидать, что никакая слабая система модели памяти не обеспечила бы только барьеры памяти? Система должна предоставить операции как тест-и-набор или сравнивать-и-подкачивать, чтобы быть полезной.
Я понимаю, что популярные процессоры, включая x86, обеспечивают модели памяти, намного более сильные, чем слабая модель памяти. Сфокусируйте обсуждение слабых моделей памяти.
(Если алгоритм Dekker является плохим выбором, выберите другой алгоритм взаимного исключения, где барьеры памяти могут успешно достигнуть корректной синхронизации, если это возможно.)
3 ответа
Вы правы, что барьер памяти не может гарантировать, что чтение видит актуальные значения. Что он делает, так это обеспечивает порядок между операциями, как в одном потоке, так и между потоками.
Например, если поток A делает серию сохранений, а затем выполняет барьер освобождения перед окончательным сохранением во флаг, а поток B читает из флага, а затем выполняет барьер приобретения перед чтением других значений, то другие переменные будут иметь значения, сохраненные потоком A:
// initially x=y=z=flag=0
// thread A
x=1;
y=2;
z=3;
release_barrier();
flag=1;
// thread B
while(flag==0) ; // loop until flag is 1
acquire_barrier();
assert(x==1); // asserts will not fire
assert(y==2);
assert(z==3);
Конечно, вам нужно убедиться, что загрузка и сохранение в flag являются атомарными (что простые инструкции загрузки и сохранения являются таковыми на большинстве обычных процессоров, при условии, что переменные соответствующим образом выровнены). Без цикла while на потоке B, поток B вполне может считать несвежее значение (0) для flag, и, таким образом, вы не можете гарантировать ни одно из значений, считанных для других переменных.
Таким образом, ограждения могут быть использованы для обеспечения синхронизации в алгоритме Деккера.
Вот пример реализации на C++ (с использованием атомарных переменных C++0x):
std::atomic<bool> flag0(false),flag1(false);
std::atomic<int> turn(0);
void p0()
{
flag0.store(true,std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
while (flag1.load(std::memory_order_relaxed))
{
if (turn.load(std::memory_order_relaxed) != 0)
{
flag0.store(false,std::memory_order_relaxed);
while (turn.load(std::memory_order_relaxed) != 0)
{
}
flag0.store(true,std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
}
}
std::atomic_thread_fence(std::memory_order_acquire);
// critical section
turn.store(1,std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_release);
flag0.store(false,std::memory_order_relaxed);
}
void p1()
{
flag1.store(true,std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
while (flag0.load(std::memory_order_relaxed))
{
if (turn.load(std::memory_order_relaxed) != 1)
{
flag1.store(false,std::memory_order_relaxed);
while (turn.load(std::memory_order_relaxed) != 1)
{
}
flag1.store(true,std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
}
}
std::atomic_thread_fence(std::memory_order_acquire);
// critical section
turn.store(0,std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_release);
flag1.store(false,std::memory_order_relaxed);
}
Полный анализ см. в моем блоге на http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html
Некоторые препятствия (например, isync powerpc и нагрузка .acq на ia64) также влияют на последующие нагрузки. то есть: если загрузка была доступна до isync из-за предварительной выборки, ее необходимо отбросить. При правильном использовании, возможно, этого достаточно, чтобы алгоритм Деккера работал на слабой модели памяти.
У вас также есть логика аннулирования кеша, работающая на вас. Если вы знаете, что ваша нагрузка является текущей из-за чего-то вроде isync и что кешированная версия данных становится недействительной, если к ней прикасается другой ЦП, этого достаточно?
Помимо интересных вопросов, алгоритм Деккера для всех практических целей тупой. Вы захотите использовать атомарные аппаратные интерфейсы и барьеры памяти для любого реального приложения, поэтому сосредоточение внимания на том, как исправить Dekker's с помощью атомики, просто не кажется мне стоящим;)
Допустим, вы поставили барьер загрузки и хранения после каждого оператора, и, кроме того, убедились, что компилятор не переупорядочивает ваши хранилища. Разве это не обеспечит строгую согласованность на любой разумной архитектуре? Деккер работает над последовательно согласованными архитектурами. Последовательная согласованность - более слабое условие, чем строгая согласованность.
http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html
Даже на процессоре, который имеет слабую модель согласованности, вы все равно будете ожидать согласованности кэша. Я думаю, что в этом случае все идет под откос - это поведение буферов хранения и спекулятивных чтений, и какие операции доступны для промывки сохраненных записей и аннулирования спекулятивных чтений. Если нет заграждения загрузки, которое может аннулировать спекулятивные чтения, или нет заграждения записи, которое смывает буфер хранения, то помимо того, что вы не сможете реализовать Dekker's, вы не сможете реализовать мьютекс!
Итак, вот мое утверждение. Если у вас есть барьер записи и барьер чтения, и кэш когерентен между процессорами, то вы можете тривиально сделать весь код последовательно согласованным, смывая записи (store fence) после каждой инструкции, и смывая спекуляции (read fence) перед каждой инструкцией. Поэтому я утверждаю, что вам не нужны атомики для того, о чем вы говорите, и что вы можете сделать то, что вам нужно, только с помощью Деккера. Конечно, вы бы этого не хотели.
BTW, Corensic, компания, в которой я работаю, пишет классные инструменты для отладки проблем параллелизма. Посмотрите http://www.corensic.com.