Почему инструкция CompareAndSwap считается дорогой?

Question

Почему инструкция CompareAndSwap считается дорогой?

Я прочитал в книге:

«Барьеры памяти стоят дорого, примерно как дорого как атомарное сравнение AndSet () инструкция. "

Спасибо!

Answer 1

"CAS заметно не отличается от обычного хранилища. Некоторая дезинформация относительно CAS, вероятно, связана с оригинальной реализацией lock: cmpxchg (CAS) на процессорах Intel. Префикс lock: вызвал сигнал LOCK #быть утвержденным, получая эксклюзивный доступ к шине. Конечно, это не масштабировалось. Последующие реализации lock: cmpxchg используют протокол когерентности кэша - обычно основанный на snoop MESI - и не утверждают LOCK #. "- Дэвид Дайс, Смещенная блокировка в HotSpot

"Барьеры памяти стоят дорого, примерно так же дорого, как атомарная инструкция сравнения AndSet ()."

Это совершенно верно.
Например, на x86, правильный CAS в многопроцессорной системе имеет префикс блокировки.
Префикс блокировки приводит к полному барьеру памяти:

"...locked операции сериализуют все незавершенные операции загрузки и сохранения (то есть ждут их завершения). "... "Заблокированные операции являются атомарными по отношению ко всем остальным операциям с памятью и всем видимым извне событиям. Только выборка инструкций и доступ к таблице страниц могут передавать заблокированные инструкции. Заблокированные инструкции могут использоваться для синхронизации данных, записанных одним процессором и считанных другим процессором«.- Руководство разработчика программного обеспечения для архитектур Intel® 64 и IA-32 , глава 8.1.2.

Барьер памяти фактически реализован в виде фиктивной LOCK OR или LOCK ANDв .NET и JAVA JIT на x86 / x64.
На x86 CAS создает полный барьер памяти.

На КПП все по другому.Пара LL / SC - lwarx & stwcx - может использоваться для загрузки операнда памяти в регистр, а затем либо записать его обратно, если не было другого хранилища дляцелевое местоположение, или повторите весь цикл, если он был.LL / SC может быть прерван.
Это также не означает автоматического полного забора.
Рабочие характеристики и поведение могут сильно различаться на разных архитектурах.
Но опять же - слабый LL /SC не является CAS.

Answer 2

«дорогой» здесь очень относительный. Это абсолютно незначительно по сравнению, скажем, с доступом к жесткому диску. Но скорость шины ОЗУ не поспевает за скоростью современных ЦП, и по сравнению с арифметическими операциями внутри ЦП прямой доступ к ОЗУ (то есть без кэширования) довольно дорог. Для извлечения int из ОЗУ может потребоваться в 50 раз больше времени, чем для добавления двух регистров.

Итак, поскольку барьеры памяти в основном вынуждают прямой доступ к ОЗУ (возможно, для нескольких процессоров), они относительно дороги.

Answer 3

Это потому, что они вносят дополнительные издержки для того, чтобы сделать операцию атомарной. Базовая платформа должна будет подавлять оптимизации (например, кэширование) и приостанавливать выполнение потоков для облегчения барьера, а это требует много дополнительных усилий. Пока эта дополнительная активность выполняется, потоки не могут выполняться, поэтому вся программа подвергается временной задержке.

Answer 4

Я думаю, что нашел ответ в своей книге:

Каждый getAndSet () транслируется на шину. так как все потоки должны использовать шину для связи с памяти, эти вызовы getAndSet () задерживают все потоки (ядра), даже те, кто не ждет блокировки.

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

Answer 5

В общем, атомарные операции дороги, потому что они требуют межпроцессорной синхронизации. «Нормальная» операция позволяет работать с кэшированными данными, обеспечивая дополнительную скорость. Взять, к примеру, в системе с 2 процессорами:

Тема 1

while (1) x++;

Тема 2

while (1) x++;

Поскольку приращение не является атомарной операцией или защищено барьером памяти, результаты этого в значительной степени не определены. Вы не знаете, как будет увеличен x, или он может даже быть поврежден.

Тема 1

while (1) atomicIncrement(&x);

Тема 2

while (1) atomicIncrement(&x);

Теперь вы пытаетесь получить четко определенное поведение - независимо от порядка, x должен увеличиваться один за другим. Если два потока работают на разных процессорах, они должны либо уменьшить количество разрешенного кэширования, либо иным образом «сравнить заметки», чтобы убедиться, что что-то разумное происходит.

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