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

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

21.1 Атомарные операции и 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 семантика предотвращает переупорядочивание чтения и записи через барьер после барьера (запрет ↑), но не предотвращает переупорядочивание до него.

Управление переупорядочиванием в MS VC.

В MS VC для предотвращения переупорядочивания инструкций со стороны компилятора предлагает использовать ReadBarrier(), _WriteBarrier(), _ReadWriteBarrier(). Эти функции не предотвращают переупорядочивание на уровне процессора, они являются лишь инструментом более тонкого контроля над оптимизациями со стороны компилятора. Для предотвращения переупорядочивания инструкций со стороны процессора предлагает макрос MemoryBarrier(), который является полным барьером и предотвращает переупорядочивание как чтения, так и записи. Исходный код этого макроса можно увидеть в MSDN. 

Неявные барьеры:

• В случае MS VC 2005 и выше ключевое слово volatile приобретает значение, выходящее за рамки С++ стандарта.

• Запись в volatile переменную всегда реализует write release семантику.

• Чтение из volatile переменной всегда реализует read acquire семантику.

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

Пример решения проблемы переупорядочивания.

На x86 архитектуре в нашем случае не надо бояться переупорядочивания, поэтому единственным и достаточным в коде будет барьер для компилятора _WriteBarrier(). При использовании MS VC 2005 и выше, объявление переменной flag как volatile позволит отказаться от явного использования барьера.

Производительность lockless приложений.

• MemoryBarrier занимает 20-90 циклов.

• InterlockedIncrement занимает 36-90 циклов.

• Вхождение или освобождение критической секции может занимать 40-100 циклов.

• Захват или освобождение мьютекса может занимать 750-2500 циклов.