Что такое "неблокирующий" concurrency и как он отличается от обычного concurrency?

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

Пример для 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();

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

Ответ 1

Что такое блокировка Concurrency и как оно отличается.

Формальный:

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

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

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

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

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

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

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

Ответ 2

Что такое Non-blocking Concurrency и как он отличается от Normal Concurrency с помощью Threads.

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

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

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

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

Ну, накладные расходы для любого типа обмена информацией между потоками, вплоть до того, как структурируется процессор, особенно когда вы получаете то, что мы называем "конкуренцией", то есть синхронизируем более одного потока, который пытается написать в одно и то же место памяти одновременно. Но в целом неблокирование происходит быстрее, чем блокирование (lock-based) Concurrency во многих случаях, особенно во всех случаях, когда есть хорошо известная, простая, незакрепленная реализация данного алгоритма/структуры данных. Именно эти хорошие решения предоставляются 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. Это может дать вам лучшую производительность в некоторых сценариях.

Общая записка

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

Ответ 3

1) Что такое Non-blocking Concurrency и как оно отличается.

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

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

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

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

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

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

Ответ 4

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

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

Ответ 5

1] Что такое неблокирование Concurrency и как он отличается.

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

Что означает "concurrency", так это то, что одновременно выполняются несколько вычислений (одновременно).

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

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

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

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

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

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

Если используемый список был синхронизированнымList, и этот цикл был выполнен в двух разных потоках, то мы можем получить {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 вы можете вставить без явного использования синхронизированный блок.
Синхронизированный список может дать вам ложное чувство безопасности, поскольку вы могут наивно полагать, что последовательные операции на одном потоке атомный, когда только отдельные операции являются атомными
Использование блока syncrhonized (list) должно выполняться с осторожностью, потому что мы в состоянии создать тупик (подробнее см. ниже).

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

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

Тема 1 получает блокировку для userList
Тема 2 получает блокировку в movieList
Тема 1 пытается получить блокировку в movieList, ждет, когда Thread 2 выпустит
Thread 2 пытается получить блокировку для userList, ждет от Thread 1 для выпуска

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

Ответ 6

Википедия - отличный ресурс для любого студента-программиста. Вот статья о неблокирующей синхронизации - http://en.wikipedia.org/wiki/Non-blocking_synchronization
Неблокирующая синхронизация доступна на любом языке, так как программист определяет их многопоточное приложение.
Вы должны использовать только блокировку (т.е. синхронизированную (список)), когда это необходимо из-за времени, необходимого для получения блокировки. В Java вектор представляет собой потокобезопасную структуру данных, которая очень похожа на Java ArrayList.

Ответ 7

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация, которую я сделал для этого, использует операции 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*/

Ответ 8

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

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

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

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

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

В 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