В многопоточном программировании много сложностей, основными из которых являются работа c разделяемым состоянием и эффективное использование предоставляемых ядер. Об использовании ядер пойдет речь в следующей статье.
С разделяемым состоянием в многопоточной среде существуют два момента, из-за которых возникают все сложности: состояние гонки и видимость изменений. В состоянии гонки, потоки одновременно изменяют состояние, что ведет к недетерменированному поведению. А проблема с видимостью заключаются в том, что результат изменения данных в одном потоке, может быть невидим другому. В статье будут рассказаны шесть способов как бороться с данными проблемами.
Все примеры приведены на Java, но содержат комментарии и я надеюсь будут понятны программистам не знакомым c Java. Данная статья носит обзорный характер и не претендует на полноту. В то же время она наполнена ссылками, которые дают более подробное объяснение терминам и утверждениям.
Shared State
Работу с разделяемым состоянием я покажу на примере вычисления чисел фибоначчи.
Формула для вычисления выглядит так:
f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2) , n >= 2
В первую очередь определим интерфейс:
public interface FibonacciGenerator<T> {
/**
* Следующее сгенерированное значение
*/
T next();
/**
* Текущее значение в генераторе
*/
public T val();
}
Наши классы будут реализовывать интерфейс FibonacciGenerator<BigInteger>. Из формулы видно, что для предоставления следующего числа, надо хранить два предыдущих — это и будет разделяемое состояние, за которое будет проходить конкуренция. Наша реализация должна быть потоко-безопасной. То есть независимо от одновременного количества потребителей, она будет сохранять свои инварианты и придерживаться контракта. И так, приступим.
Locking
Первый способ сделать класс корректно работающим в многопоточной среде — это использовать блокировки) и объявить все методы synchronized. Примером может служить класс Vector.
public class IntrinsicLock implements FibonacciGenerator<BigInteger> {
private BigInteger curr = BigInteger.ONE;
private BigInteger next = BigInteger.ONE;
@Override
public synchronized BigInteger next() {
BigInteger result = curr;
curr = next;
next = result.add(next);
return result;
}
@Override
public synchronized BigInteger val() {
return curr;
}
}
Мы получили класс, который корректно работает в многопоточной среде, затратив при этом минимум усилий. В первую очередь, мы жертвуем производительностью. Производительность класса такая же, как если бы он запускался в однопоточной среде. К тому же, использование локов приносит проблемы, такие как: deadlock, livelock и т.п.
Fine-Grained locking
Следующий способ — разбить наши структуры на части и оградить локами только те секции, в которых происходит работа с разделяемым состоянием. Примером такого подхода является СoncurrentHashMap. В нем все данные разбиваются на несколько частей. При доступе блокируется только та часть, изменение которой происходит в текущий момент. Также есть вариант использовать более функциональные локи, такие как: StampedLock, ReadWriteLock. При корректных алгоритме и реализации мы получаем более высокий уровень параллелизма. Пример с использованием ReadWriteLock:
public class FineGrainedLock implements FibonacciGenerator<BigInteger> {
private final ReadWriteLock lock = new ReentrantReadWriteLock();
private BigInteger curr = BigInteger.ONE;
private BigInteger next = BigInteger.ONE;
@Override
public BigInteger next() {
BigInteger result;
lock.writeLock().lock();
try {
// Вход другим потокам запрещен
result = curr;
curr = next;
next = result.add(next);
return result;
} finally {
lock.writeLock().unlock();
}
}
@Override
public BigInteger val() {
lock.readLock().lock();
try {
// При отпущенном write lock
// Допуст`им вход множества потоков
return curr;
} finally {
lock.readLock().unlock();
}
}
}
Мы усовершенствовали класс и добились более высокой пропускной способности на чтение. У такой реализации есть все минусы локов. К тому же, из минусов добавилось то, что алгоритм усложнился (добавилось шума, не связанного с логикой работы) и вероятность некорректной реализации возросла.
Lock-free algorithms
Использование локов влечет массу проблем с производительностью и корректностью. Существует альтернатива в виде неблокирующих алгоритмов. Такие алгоритмы построены на атомарных операциях, предоставляемых процессорами. Примером служит метод get в ConcurrentHashMap. Чтобы писать неблокирующие алгоритмы, имеет смысл воспользоваться существующими неблокирующими классами: ConcurrentLinkedQueue, ConcurrentHashMap и т.п. Напишем неблокирующую реализацию нашего класса.
public class LockFree implements FibonacciGenerator<BigInteger> {
// Инкапсулируем состояние генератора в класс
private static class State {
final BigInteger next;
final BigInteger curr;
public State(BigInteger curr, BigInteger next) {
this.next = next;
this.curr = curr;
}
}
// Сделаем состояние класса атомарным
private final AtomicReference<State> atomicState = new AtomicReference<>(
new State(BigInteger.ONE, BigInteger.ONE));
public BigInteger next() {
BigInteger value = null;
while (true) {
// сохраняем состояние класса
State state = atomicState.get();
// то что возвращаем если удалось изменить состояние класса
value = state.curr;
// конструируем новое состояние
State newState = new State(state.next, state.curr.add(state.next));
// если за время пока мы конструировали новое состояние
// оно осталось прежним, то заменяем состояние на новое,
// иначе пробуем сконструировать еще раз
if (atomicState.compareAndSet(state, newState)) {break;}
}
return value;
}
@Override
public BigInteger val() {
return atomicState.get().curr;
}
}
Из плюсов такого подхода следует отметить увеличение производительности, по сравнению с блокирующими алгоритмами. А также, что не менее важно, избавление от недостатков локов. Минус в том, что неблокирующий алгоритм придумать гораздо сложнее.
Software Transactional Memory
Альтернативой неблокирующим алгоритмам является применение программной транзакционной памяти. Её использование похоже на использование транзакций при работе с базами данных. Концепция довольно таки новая (1995) и среди популярных языков, нативная поддержка есть только в Clojure. Поддержка STM на уровне библиотек есть во многих языках, в том числе и Java. Я буду использовать STM, реализованный в рамках проекта Akka.
public class STM implements FibonacciGenerator<BigInteger> {
// Оборачиваем переменные в транзакционные ссылки
// система будет отслеживать изменения этих переменных внутри транзакции
private final Ref<BigInteger> curr = new Ref<>(BigInteger.ONE);
private final Ref<BigInteger> next = new Ref<>(BigInteger.ONE);
@Override
public BigInteger next() {
// Создаем транзакцию
return new Atomic<BigInteger>() {
// Изменения внутри метода
// будут обладают АСI (https://en.wikipedia.org/wiki/ACID)
@Override
public BigInteger atomically() {
// Все значения отслеживаемых переменных согласованы
BigInteger result = curr.get();
// Изменения не видны другим потокам
curr.set(next.get());
next.set(result.add(next.get()));
// Проверяется были ли изменения над отслеживаемыми
// переменными. Если да, то нас опередили, но мы
// оптимистичны и повторяем транзакцию еще раз.
// Если мы первые, то атомарно записываем новые значения.
return result;
}
// и выполняем ее
}.execute();
}
@Override
public BigInteger val() {
// Транзакция создается неявно
return curr.get();
}
}
Код легко понимается и нет шума, создаваемого неблокирующими алгоритмами и использованием локов. Но за это мы платим более низкой производительностью и ограниченной применимостью, поскольку STM хорошо себя показывает когда читателей гораздо больше, чем писателей.
Immutability
Проблемы с общим доступом к состоянию от того, что оно изменяемое. То есть спроектировав класс неизменяемым, можно без ограничений работать с ним в многопоточной среде, так как он также будет потоко-безопасным. Но неизменяемые структуры данных зачастую требуют функциональных подходов и специальных структур данных, так как расходы на память могут быть очень велики.
public class Immutable {
private final BigInteger next;
// Текущее значение
public final BigInteger val;
private Immutable(BigInteger next, BigInteger val) {
this.next = next;
this.val = val;
}
public Immutable next() {
return new Immutable(val.add(next), next);
}
public static Immutable first() {
return new Immutable(BigInteger.ONE, BigInteger.ONE);
}
}
Как вы заметили, интерфейс класса изменился и это потребует других способов работы с ним.
Isolated mutability
Идея изолированной изменяемости объектов состоит в том, что доступ к ним ограничен всегда одним потоком. Следовательно у нас не возникнет проблем, характерных для многопоточных программ. Такой подход использует модель акторов. Акторы — это сущности похожие на объекты, у которых есть изменяемое состояние и поведение. Взаимодействие акторов происходит через асинхронную передачу сообщений. Сообщения неизменяемы и актор обрабатывает одно сообщение за раз. Результатом обработки сообщения является изменение поведения, состояния и выполнение других действий. Пример использования акторов будет приведен в следующей статье.
Итог
У каждого подхода есть свои минусы и плюсы и нельзя дать универсального совета.
Комбинация fine-grained локов и неблокирующих алгоритмов, наиболее часто используемый подход в Java. В Clojure же напротив — транзакционная память и неизменяемые структуры данных. Транзакционная память, на мой взгляд, многообещающий инструмент (предлагаю читателю самостоятельно провести аналогию со сборкой мусора). Надеюсь, что при следующем проектировании системы, модуля или класса, вы вспомните подходы, описанные в данной статье, и выберите подходящий именно вам.
Спасибо за внимание. Жду ваших замечаний и предложений.
Автор: f0y
