Что такое «неблокирующий» параллелизм и чем он отличается от обычного параллелизма?

Question

1. Что такое «неблокирующий» параллелизм и чем он отличается от обычного параллелизма с использованием потоков? Почему мы не используем неблокирующий параллелизм во всех сценариях, где требуется параллелизм? Есть ли накладные расходы на использование неблокирующего параллелизма?
2. Я слышал, что неблокирующий параллелизм доступен в Java. Существуют ли какие-либо конкретные сценарии, в которых мы должны использовать эту функцию?
3. Есть ли разница или преимущество использования одного из этих методов с коллекцией? Каковы компромиссы?

Пример для Q3:

class List   
{  
    private final ArrayList<String> list = new ArrayList<String>();

    void add(String newValue) 
    {
        synchronized (list)
        {
            list.add(newValue);
        }
    }
}  

против

private final ArrayList<String> list = Collections.synchronizedList(); 

Вопросы больше относятся к изучению / пониманию. Спасибо за внимание.

Answer 1

Что такое неблокирующий параллелизм и как это отличается.

Формально:

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

Неофициальный. Одна из наиболее выгодных особенностей неблокирования по сравнению с блокировкой заключается в том, что потоки не должны быть приостановлены / пробуждены операционной системой. Такие издержки могут составлять от 1 мс до нескольких 10 мс, поэтому их устранение может привести к значительному увеличению производительности. В Java это также означает, что вы можете использовать несправедливую блокировку, которая может иметь гораздо большую пропускную способность системы, чем справедливая блокировка.

Я слышал, что это доступно на Яве. Есть ли какие-то конкретные сценарии, мы должны использовать эту функцию

Да, с Java5. На самом деле, в Java вы должны стараться максимально удовлетворить ваши потребности с помощью java.util.concurrent (что часто использует неблокируемый параллелизм, но в большинстве случаев вам не нужно явно беспокоиться). Только если у вас нет другого выбора, вы должны использовать синхронизированные оболочки (.synchronizedList () и т. Д.) Или ключевое слово synchronize, заданное вручную. Таким образом, в большинстве случаев вы получаете более удобные и эффективные приложения.

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

Есть ли разница / преимущество используя один из этих методов для коллекция. Каковы компромиссы

Оба имеют одинаковое поведение (байт-код должен быть одинаковым). Но я предлагаю использовать Collections.synchronized, потому что он короче = меньше места, чтобы облажаться!

Answer 2

Что такое неблокирующий параллелизм и чем он отличается от обычного параллелизма с использованием потоков.

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

Почему мы не используем «неблокирующий» параллелизм во всех сценариях, где требуется параллелизм.

Мы делаем. Я покажу вам немного. Но это правда, что не всегда эффективные неблокирующие алгоритмы для каждой проблемы параллелизма.

есть ли накладные расходы для "неблокирования"

Что ж, есть издержки для любого типа обмена информацией между потоками, вплоть до того, как структурируется процессор, особенно когда вы получаете то, что мы называем «конфликтом», то есть синхронизируем более одного потока, который пытается записать в ту же ячейку памяти в то же время. Но в целом неблокирование выполняется быстрее, чем блокирующий (основанный на блокировке) параллелизм во многих случаях, особенно во всех случаях, когда существует хорошо известная простая реализация без блокировок данного алгоритма / структуры данных. Именно эти хорошие решения предоставляются с Java.

Я слышал, что это доступно на Java.

Абсолютно. Для начала, все классы в java.util.concurrent.atomic обеспечивают беспрепятственное обслуживание общих переменных. Кроме того, все классы в java.util.concurrent, чьи имена начинаются с ConcurrentLinked или ConcurrentSkipList, обеспечивают реализацию списков, карт и наборов без блокировок.

Существуют ли конкретные сценарии, в которых мы должны использовать эту функцию.

Вы хотели бы использовать очередь без блокировки и deque во всех случаях, когда в противном случае (до JDK 1.5) использовали Collections.synchronizedlist, поскольку они обеспечивают лучшую производительность в большинстве условий. то есть вы должны использовать их всякий раз, когда несколько потоков одновременно изменяют коллекцию, или когда один поток изменяет коллекцию, а другие потоки пытаются ее прочитать. Обратите внимание, что очень популярный ConcurrentHashMap действительно использует блокировки внутри, но он более популярен, чем ConcurrentSkipListMap, потому что я думаю, что он обеспечивает лучшую производительность в большинстве сценариев. Однако я думаю, что Java 8 будет включать реализацию ConcurrentHashMap без блокировок.

Есть ли разница / преимущество использования одного из этих методов для коллекции. Каковы компромиссы

Ну, в этом коротком примере они точно такие же. Тем не менее, обратите внимание, что когда у вас есть одновременные программы чтения и записи, вы должны синхронизировать чтение и запись, и это делает Collections.synchronizedList (). Вы можете попробовать использовать ConcurrentLinkedQueue без блокировки в качестве альтернативы. Это может дать вам лучшую производительность в некоторых сценариях.

Общее примечание

Хотя параллелизм - очень важная тема для изучения, имейте в виду, что это также очень сложная тема, в которой часто ошибаются даже очень опытные разработчики. Что еще хуже, вы можете обнаружить ошибки параллелизма только тогда, когда ваша система находится под большой нагрузкой. Поэтому я всегда рекомендую использовать как можно больше готовых параллельных классов и библиотек, а не развертывать свои собственные.

Answer 3

1) Что такое неблокирующий параллелизм и чем он отличается.

Задача (поток) не блокируется, если она не заставляет другие задачи (потоки) ждать, пока задача не будет завершена.

2) Я слышал, что это доступно на Java. Существуют ли какие-либо конкретные сценарии, в которых мы должны использовать эту функцию

Java поддерживает собственную многопоточность. Вы можете воспользоваться этим для одновременного запуска нескольких задач. Если это хорошо написано и реализовано, это может ускорить выполнение программы при работе на компьютере с несколькими логическими процессорами. Для начала существуют java.lang.Runnable и java.lang.Thread в качестве реализаций параллелизма низкого уровня. Затем существует высокий уровень параллелизма в интерфейсе API java.util.concurrent.

3) Есть ли разница / преимущество использования одного из этих методов для коллекции. Каковы компромиссы

Я бы использовал Collections#synchronizedList(), не только потому, что это более надежно и удобно, но и потому, что Map не List. Там нет необходимости пытаться доморощить один, когда API уже предлагает объект.

---

Тем не менее, есть Sun руководство по параллелизму . Я рекомендую вам пройти через это.

Answer 4

1] Что такое неблокирующий параллелизм и как это отличается.

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

Что подразумевается под «параллелизмом», так это то, что несколько вычислений происходят одновременно (одновременно).

2] Я слышал, что это доступно на Яве. Есть ли какие-то конкретные сценарии, мы должны использовать эту функцию

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

3] Есть ли разница / преимущество используя один из этих методов для коллекция. Какие компромиссы

.

Использование блока synchronized (list) гарантирует, что все действия, выполняемые в блоке, будут рассматриваться как атомарные. То есть, пока мы получаем доступ к списку только из синхронизированных (списочных) блоков, все обновления в списке будут выглядеть так, как если бы они происходили в одно и то же время внутри блока.

Объект synchronizedList (или synchronizedMap) гарантирует, что отдельные операции являются поточно-ориентированными. Это означает, что две вставки не будут происходить одновременно. Рассмотрим следующий цикл:

for(int i=0; i < 4; i++){
    list.add(Integer.toString(i));
}

Если используемый список представлял собой synchronizedList и этот цикл был выполнен в двух разных потоках, то в нашем списке может оказаться {0,0,1,2,1,3,2,3}, или некоторые другая перестановка.

Почему? Что ж, нам гарантировано, что поток 1 добавит 0-3 в этом порядке, и мы гарантируем то же самое, что и поток 2, однако у нас нет гарантии того, как они будут чередоваться.

Если, однако, мы завернули этот список в синхронизированный блок (список):

synchronized(list){
    for(int i=0; i < 4; i++){
        list.add(Integer.toString(i));
    }
}

Мы гарантируем, что вставки из потока 1 и потока 2 не будут чередоваться, но они будут происходить одновременно. Наш список будет содержать {0,1,2,3,0,1,2,3}. Другой поток будет блокироваться, ожидая списка, пока не завершится первый поток. У нас нет гарантии, какая нить будет первой, но мы гарантируем, что она закончится до начала другой.

Итак, некоторые компромиссы:

• С помощью syncrhonizedList вы можете вставить без явного использования синхронизированный блок.
• SyncrhonizedList может дать вам ложное чувство безопасности, так как вы может наивно полагать последовательным операции на одном потоке должны быть атомный, когда только индивидуальный операции атомарные
• Использование синхронизированного блока (списка) должно выполняться с осторожностью, потому что мы можем создать тупик (подробнее ниже).

Мы можем создать взаимоблокировку, когда каждый из двух (или более) потоков ожидает подмножество ресурсов, удерживаемых другим. Если, например, у вас было два списка: userList и movieList.

Если поток 1 сначала получает блокировку для userList, затем movieList, но поток два выполняет эти шаги в обратном порядке (получает блокировку для movieList до userList), то мы открыли себя для взаимоблокировки. Рассмотрим следующий ход событий:

1. Тема 1 получает блокировку для userList
2. Тема 2 получает блокировку для списка фильмов
3. Поток 1 пытается получить блокировку для movieList, ожидает в потоке 2, чтобы освободить
4. Поток 2 пытается получить блокировку для userList, ожидает в потоке 1, чтобы освободить

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

Answer 5

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

2) Подробнее о неблокирующей синхронизации алгоритмы в Java.

Answer 6

1: Что такое «неблокирующий» параллелизм и чем он отличается от обычного параллелизма с использованием потоков? Почему мы не используем неблокирующий параллелизм во всех сценариях, где требуется параллелизм? Есть ли накладные расходы на использование неблокирующего параллелизма?

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

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

Наконец, по мере развития JDK / JRE разработчики ядра улучшают реализацию на внутреннем языке, пытаясь включить наиболее эффективные средства достижения этих целей в конструкции ядра. По мере удаления от базовых конструкций вы теряете автоматическую реализацию этих улучшений, поскольку вы используете менее стандартные реализации (например, jaxb / jibx; jaxb раньше сильно уступал jibx, но теперь равен, если не быстрее, в большинстве случаев, что я проверено на Java 7), когда вы подняли свою версию Java.

если вы посмотрите на пример кода ниже, вы можете увидеть «накладные» места. Это на самом деле не накладные расходы, но код должен быть чрезвычайно эффективным, чтобы работать без блокировки, и на самом деле работать лучше, чем стандартная синхронизированная версия из-за зацикливания. Даже небольшие изменения могут привести к тому, что код будет работать в несколько раз лучше, чем стандарт, в код, который в несколько раз хуже (например, экземпляры объектов, которые не нужны, или даже быстрые условные проверки; вы говорите о сохранении циклов). здесь, поэтому разница между успехом и провалом очень мала).

2: я слышал, что неблокирующий параллелизм доступен в Java. Есть ли какие-либо конкретные сценарии, в которых мы должны использовать эту функцию?

По моему мнению, вы должны использовать это только в том случае, если у вас: A) есть доказанная проблема производительности в вашей работающей системе на производстве, на ее производственном оборудовании; и B) если вы можете доказать, что единственная неэффективность, оставшаяся в критической секции, связана с блокировкой; C) Вы твердо согласны с заинтересованными сторонами, что они готовы иметь нестандартный, менее обслуживаемый код в обмен на повышение производительности, которое вы должны D) численно доказать на своем производственном оборудовании, чтобы быть уверенным, что оно вообще поможет.

3: Есть ли разница или преимущество в использовании одного из этих методов с коллекцией? Каковы компромиссы?

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

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

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

Обсуждение / Код

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

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

Реализация, которую я сделал для этого, использует операции CAS и семейство переменных Atomic. Этот базовый код никогда не блокировался и не вызывал каких-либо ошибок для меня в этом случае использования (ввод и вывод случайной выборки для автономного тестирования из системы перевода с высокой пропускной способностью). В основном это работает так:

У вас есть некоторый объект, который совместно используется потоками, и он объявляется либо как AtomicXXX, либо как AtomicReference (для большинства нетривиальных случаев использования вы будете работать с версией AtomicReference).

когда на указанное значение / объект ссылаются, вы извлекаете его из оболочки Atomic, это дает вам локальную копию, для которой вы выполняете некоторую модификацию. Отсюда вы используете compareAndSwap в качестве условия цикла while, чтобы попытаться установить этот Atomic из вашего потока, если в случае неудачи он возвращает false, а не блокирует. Это будет повторяться до тех пор, пока не заработает (код в этом цикле должен быть очень эффективным и простым).

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

Если CompareAndSwap завершается неудачно, вы снова получаете свой объект из оболочки Atomic, снова выполняете любые изменения, а затем снова пытаетесь сравнить и поменять местами, пока он не заработает. Конкретной блокировки нет, вы просто пытаетесь вернуть объект обратно в память, и если он не работает, попробуйте еще раз, когда ваш поток снова получает контроль.

Код для этого ниже для простого случая со списком:

/* field declaration*/
//Note that I have an initialization block which ensures that the object in this
//reference is never null, this was required to remove null checks and ensure the CAS
//loop was efficient enough to improve performance in my use case
private AtomicReference<List<SampleRuleMessage>> specialSamplingRulesAtomic = new AtomicReference<List<SampleRuleMessage>>();


/*start of interesting code section*/

    List<SampleRuleMessage> list = specialSamplingRulesAtomic.get();
    list.add(message);
    while(!specialSamplingRulesAtomic.compareAndSet(specialSamplingRulesAtomic.get(), list)){
        list = specialSamplingRulesAtomic.get();
        list.add(message);
    };
 /* end of interesting code section*/

Answer 7

1. Википедия - отличный ресурс для любого студента по информатике. Вот статья о неблокирующей синхронизации - http://en.wikipedia.org/wiki/Non-blocking_synchronization

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

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

Answer 8

Неблокирующая синхронизация - это то же самое, что и блокирующая синхронизация, обе являются разновидностью синхронизации, единственное отличие состоит в том, что неблокирующая синхронизация быстрее в целом.

Для начала вы хотите использовать синхронизацию только тогда, когда несколько потоков обращаются к одному и тому же ресурсу в ОЗУ. Вы не можете использовать синхронизацию при попытке доступа к объектам на диске, или, точнее, вам нужно использовать блокировки на диске.

Тем не менее, как вы можете синхронизировать, если ни один поток не блокирует?

Ответ - оптимистическая блокировка. Эта идея существует не менее 20 лет. Может быть, больше.

Возможно, вы слышали о языке Lisp. Оказывается, функциональные языки никогда не изменяют свои параметры, а только возвращают новые значения, поэтому им не нужно синхронизироваться.

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

Идея оптимистической блокировки заключается в том, что все потоки добровольно изменяют разделяемое значение, но имеют локальную область для изменения значений и применяют изменение только в конце, с одной инструкцией, атомарно, с использованием CAS. Cas расшифровывается как Compare And Swap, он работает всего за один цикл ЦП и внедряется в ЦП не менее 20 лет.

Отличное объяснение того, что такое CAS: https://www.cs.umd.edu/class/fall2010/cmsc433/lectures/nonBlocking.pdf

Так что, если в модификации есть конфликт, он затронет только одного из авторов, остальное будет сделано с ним.

Более того, если нет никаких противоречий, неблокирующие алгоритмы работают намного быстрее, чем их блокирующие аналоги.

Учебник по неблокирующим алгоритмам в Java с примерами кода, которые вы можете использовать в реальной жизни: http://tutorials.jenkov.com/java-concurrency/non-blocking-algorithms.html