Действительно ли алгоритмы блокировки действительно работают лучше, чем их блокирующие полные копии?

Ответ 1

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

Однако они, как правило, значительно улучшают общую пропускную способность алгоритма в целом перед лицом конкуренции. Задержка переключения потоков и контекстные переключатели, которые быстро, по многим потоки замедляют пропускную способность вашего приложения. Блокирующие алгоритмы эффективно реализуют свои собственные "блокировки", но они делают это таким образом, что предотвращают или уменьшают количество переключателей контекста, поэтому они склонны выполнять свои блокирующие копии.

Говоря это, большая часть этого зависит от алгоритма (и реализации), о котором идет речь. Например, у меня есть некоторые подпрограммы, которые мне удалось переключить на новые сборники .NET 4, вместо использования предыдущих механизмов блокировки, и измерили улучшения почти на 30% в моей общей скорости алгоритма. Это, как говорится, есть много тестов, которые вы можете найти, которые показывают снижение производительности, используя некоторые из этих же коллекций по сравнению с базовой блокировкой. Как и во всех оптимизациях производительности - вы действительно не знаете, пока не заметите.

Ответ 2

Помимо простых случаев функций InterlockedXxx, похоже преобладающая картина со всеми этими фактами заключается в том, что они реализуют свои собственные блокировки.

Ни один из ответов здесь, по-видимому, не попадает в суть разницы между замкнутым контуром CAS и мьютексом или спин-блокировки.

Важное различие заключается в том, что алгоритмы без блокировки гарантируют самостоятельный прогресс - без помощи других потоков. С блокировкой или блокировкой вращения любой бедный нить, которая не может получить замок, полностью зависит от нити, которой принадлежит замок. Бедный поток, который не может получить блокировку, ничего не может сделать, кроме ожидания (либо через ожидание ожидания, либо со спящим с ОС).

Благодаря алгоритмам без блокировки, которые работают на CAS, каждый поток гарантированно продвигается независимо от того, что делают другие конкурирующие потоки. Каждая нить, по сути, контролирует свою судьбу. Да, ему все равно придется перебирать много раз, но количество циклов цикла ограничено количеством конкурирующих потоков. По большей части он не может бесконечно зацикливаться. (На практике возможно, что блокировка в реальном времени происходит из-за, например, цикла

Ответ 3

Lock-free не обязательно быстрее, но он может исключить возможность тупика или livelock, поэтому вы можете гарантировать, что ваша программа всегда будет продвигаться к завершению. С замками трудно сделать любую такую ​​гарантию - слишком легко пропустить некоторую возможную последовательность выполнения, которая приводит к тупиковой ситуации.

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

Ответ 4

В Windows на x64 простой (без объединения массива перед freelist) свободный от фриланса на порядок больше, чем фрилайст на основе мьютекса.

На моем ноутбуке (Core i5) для одного потока, без блокировки, я получаю около 31 миллиона лишних операций в секунду, а для мьютекса - около 2,3 миллиона операций в секунду.

Для двух потоков (на отдельных физических ядрах), без блокировки, я получаю около 12,4 миллиона лишних операций на поток. С помощью мьютекса я получаю около 80 операций ТЫСЯЧИ в секунду.

Ответ 5

Алгоритмы без блокировки могут быть абсолютно быстрее, чем их блокирующие копии. Но, конечно, верно и обратное. Предполагая, что реализация выполняется лучше, чем часть счетчика блокировки, единственным ограничивающим фактором является утверждение.

Возьмите два класса Java, ConcurrentLinkedQueue и LinkedBlockingQueue. В условиях умеренного реального мира CLQ превосходит LBQ на хорошую сумму. С тяжелым утверждением использование подвесных нитей позволит LBQ работать лучше.

Я не согласен с user237815. синхронизированное ключевое слово не требует столько накладных расходов, сколько когда-то, но по сравнению с алгоритмом без блокировки у него есть достаточное количество накладных расходов, связанных с ним, по сравнению с одним CAS.

Ответ 6

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

(*) Я видел некоторые попытки в "незаблокированных" многопроцессорных очередях, когда производитель, который получил недействительное время, не позволял потребителям видеть какие-либо новые предметы, пока не завершит свою работу); такие структуры данных на самом деле не следует называть "заблокированными". Один производитель, который блокируется, не будет препятствовать прогрессу других производителей, но может произвольно блокировать потребителей.

Ответ 7

В Java, по крайней мере, блокировка сама по себе может быть очень быстрой. Синхронизированное ключевое слово не добавляет много накладных расходов. Вы можете сравнить его самостоятельно, просто вызвав синхронизированный метод в цикле.

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

Ответ 8

Недавно на JavaOne Russia Сотрудник Oracle (специализирующийся на производительности и тестах Java) показал некоторые измерения операций в секунду в параллельном доступе к простым int counter, используя CAS (блокировка, высокий уровень спин-блокировки на самом деле) и классические блокировки (java.util.concurrent.locks.ReentrantLock)

http://dl.dropbox.com/u/19116634/pics/lock-free-vs-locks.png//извините, я не могу вставить изображения

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

Ответ 9

Блокировка также имеет то преимущество, что она не спит. Есть места в ядрах, где вам не разрешено спать - в ядре Windows есть куча - и это больно ограничивает вашу способность использовать структуры данных.

Ответ 10

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