Статьи

Основанные на блокировке против параллельных алгоритмов без блокировки


На прошлой неделе я присутствовал на обзорной сессии нового 
JSR166  
StampedLock, которую  вел 
Хайнц Кабуц,  на отличной 
конференции  JCrete. StampedLock — это попытка решить проблемы конкуренции, возникающие в системе, когда несколько читателей одновременно получают доступ к общему состоянию. StampedLock разработан, чтобы работать лучше, чем 
ReentrantReadWriteLock  , используя оптимистический подход к чтению.

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

Тестовый пример

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

public interface Spaceship
{
int readPosition(final int[] coordinates);
int move(final int xDelta, final int yDelta);
}

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

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

Каждая реализация подвергается 4 различным сценариям потоков, которые приводят к различным профилям конкуренции:

  • 1 читатель — 1 писатель
  • 2 читателя — 1 писатель
  • 3 читателя — 1 писатель
  • 2 читателя — 2 писателя

Все тесты выполняются с 64-битной Java 1.7.0_25, Linux 3.6.30 и четырехъядерным 2,2-ГГц Ivy Bridge i7-3632QM. Пропускная способность измеряется в течение 5 секундных периодов для каждой реализации, при этом тесты повторяются 5 раз, чтобы обеспечить достаточный прогрев. Ниже приведены результаты, усредненные в секунду за 5 прогонов. Для аппроксимации типичного развертывания Java не использовалась привязка потоков или изоляция ядра, что значительно уменьшило бы дисперсию.

Примечание.  Другие процессоры и операционные системы могут давать очень разные результаты.

Полученные результаты

Фигура 1.
Фигура 2.
Рисунок 3
Рисунок 4

Исходные данные для указанных выше диаграмм можно найти 
здесь .

Анализ

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

  1. StampedLock является существенным улучшением по сравнению с существующими реализациями блокировок, особенно с увеличением числа потоков чтения.
  2. StampedLock имеет сложный API. Очень легко ошибочно вызвать неправильный метод для блокировки действий.
  3. Synchronized — это хорошая реализация блокировки общего назначения, когда конкуренция происходит только из двух потоков.
  4. ReentrantLock является хорошей реализацией блокировки общего назначения, когда число потоков растет, как  было обнаружено ранее .
  5. Выбор использования ReentrantReadWriteLock должен быть основан на тщательном и соответствующем измерении. Как и во всех основных решениях, измерять и принимать решения на основе данных.
  6. Реализации без блокировок могут предложить значительные преимущества по сравнению с алгоритмами на основе блокировок.

Заключение

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

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