Атомарные операции и lockless программирование. Реализация многопоточности с

Использованием технологии OpenMP, блокировки и синхронизация потоков в OpenMP .

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

Lockless программирование – разработка неблокирующих многопоточных приложений.

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

Виды атомарных операций:

· Все инструкции вида Операция Регистр-Регистр можно считать атомарными так как регистры за пределами вычислительного процессорного ядра не видны.

· Загрузка данных из памяти по выровненному адресу в регистр общего назначения.

· Сохранение данных из регистра общего назначения в память по выровненному адресу.

· Специальные операции для атомарной работы (например, cmpxchg).

· Многие команды вида Чтение-Модификация-Запись могут быть сделаны искусственно атомарными с помощью операции блокировки шины (префикс lock).

Реализация атомарных операций в Windows 2000-2003.

· Для увеличения значения целочисленных переменных –InterlockedIncrement, InterlockedIncrement64.

· Для уменьшения значения целочисленных переменных – InterlockedDecrement, InterlockedDecrement64.

· Для изменения значений целочисленных переменных – InterlockedExchange, InterlockedExchange64, InterlockedExchangeAdd, InterlockedExchangePointer.

· Для изменения значений целочисленных переменных со сравнением – InterlockedCompareExchange, InterlockedCompareExchangePointer.

Пример использования атомарной операции:

static DWORD array [100];

…

for (int i = 0; i < 100; i++)

InterlockedIncrement(array+i);

Эффект переупорядочивания.

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

Переупорядочивать операции могут компилятор, исполняемая среда и процессор. Говоря о переупорядочивании, мы приходим к термину модели памяти (memory consistency model или просто memory model). Модель памяти, в которой нет переупорядочивания, чтения и записи будет считаться сильной (strong), а модель памяти, где возможны любые переупорядочивания чтения и записи принято считать слабой (weak). При этом слабые модели обеспечивают наибольшую производительность за счет возможных оптимизаций, но и порождают большое количество проблем при программировании.

Барьеры памяти.

Для борьбы с переупорядочиванием применяются так называемые барьеры памяти (memory barrier или memory fence). В случае барьера для компилятора применяют еще и термин барьер оптимизации (optimization barrier).

Барьеры могут быть как явными, так и не явными (с точки зрения программиста). Кроме того барьеры могут быть полными, двухсторонними и односторонними.

· Полный барьер (full fence) предотвращает любые переупорядочивания операций чтения или записи через него. Таким образом, можно говорить о том, что все операции чтения и записи до барьера будут завершены, по отношению к операциям, расположенным после барьера. Данный барьер предлагает инструкцию mfence в x86/x64 архитектуре.

· Двусторонние барьеры (Store fenceиLoad fence) предотвращают переупорядочивание лишь одного вида операций.

· Барьер записи (store fence) не позволяет переупорядочивать через себя операции записи.

· Барьер чтения(load fence) не позволяет переупорядочивать через себя операции чтения соответственно.

На x86/x64 архитектурах данные барьеры реализованы в инструкциях lfence и sfence.

· Односторонние барьеры обычно реализуют одну из двух семантик – write release (store release) или read acquire (load acquire).

· Write release семантика предотвращает любое переупорядочивание чтения и записи через барьер до барьера (запрет ↓), но не предотвращает переупорядочивания после него.

· Read acquire семантика предотвращает переупорядочивание чтения и записи через барьер после барьера (запрет ↑), но не предотвращает переупорядочивание до него.