мой вопрос касается синхронизации и предотвращения взаимоблокировок при использовании потоков. В этом примере объект просто содержит целочисленную переменную, и несколько потоков вызывают swapValue для этих объектов.
public class Data {
private long value;
public Data(long value) {
this.value = value;
}
public synchronized long getValue() {
return value;
}
public synchronized void setValue(long value) {
this.value = value;
}
public void swapValue(Data other) {
long temp = getValue();
long newValue = other.getValue();
setValue(newValue);
other.setValue(temp);
}
}
Метод swapValue должен быть потокобезопасным и не должен пропускать замену значений, если ресурсы недоступны. Простое использование ключевого слова synchronized в сигнатуре метода приведет к взаимоблокировке. Я придумал это (очевидно) рабочее решение, которое основано только на вероятности того, что один поток разблокирует свой ресурс, а другой попытается заявить права на него, пока ресурс все еще разблокирован.
private Lock lock = new ReentrantLock();
...
public void swapValue(Data other) {
lock.lock();
while(!other.lock.tryLock())
{
lock.unlock();
lock.lock();
}
long temp = getValue();
long newValue = other.getValue();
setValue(newValue);
other.setValue(temp);
other.lock.unlock();
lock.unlock();
}
Для меня это выглядит как взлом. Это обычное решение для таких проблем? Существуют ли решения, которые являются «более детерминированными» по своему поведению и также применимы на практике?
В вашем случае просто используйте AtomicInteger или AtomicLong вместо того, чтобы снова изобретать колесо. Что касается синхронизации и взаимоблокировок, часть вашего вопроса в целом - DO NOT RELY ON PROBABILITY
- это слишком сложно и слишком легко ошибиться, если вы не опытный математик, точно знающий, что вы делаете, - но даже в этом случае это рискованно. Одним из примеров использования вероятности является UUID, но если компьютеры станут достаточно быстрыми, то код, который не должен разумно ломаться до конца вселенной, может сломаться за миллисекунды или быстрее, лучше писать код, который не полагается на вероятность, особенно параллельный код.
@Neran По крайней мере, в наиболее очевидной реализации атомы на самом деле не работают для этой проблемы. Вы можете атомарно заменить локальный на атомарный, но вы не можете атомарно поменять местами локальный на атомарный (см. это). После некоторых набросков я нашел по крайней мере один шаблон доступа, который начинается с данных 1, 2, 3 и заканчивается данными 2, 3, 2 после двух свопов (с использованием атомарного доступа) (поскольку для каждого обмена требуется несколько атомарных). Krzysztof - у вас есть конкретный алгоритм без блокировки, который вы предлагаете?
Если у нас есть данные A, B, C, загрузить B -> tempvar 1, загрузить B -> tempvar 2, поменять местами tempvar 1 и A, поменять местами tempvar 2 на C, сохранить tempvar 1 в B, сохранить tempvar 2 в B, в итоге получится две копии B и одна C, при этом копия A потеряна.
Здесь есть две проблемы:
Data.lock
со встроенным замком, используемым ключевым словом synchronized
.Даже без synchronized
, a.swapValue(b)
и b.swapValue(a)
могут зайти в тупик, если вы не используете свой подход, чтобы попытаться вращаться при блокировке и разблокировке, что неэффективно.
Один из подходов, который вы могли бы использовать, — это добавить поле с каким-то final
уникальным идентификатором к каждому Data
объекту — при обмене данными двух объектов блокируйте один с более низким идентификатором перед тем, который имеет более высокий идентификатор, независимо от того, какой из них this
и что такое other
. Обратите внимание, что System.identityHashCode, к сожалению, не уникален, поэтому его нельзя легко использовать здесь.
Порядок разблокировки здесь не критичен, но разблокировка в порядке, обратном блокировке, обычно является хорошей практикой, которой следует следовать, где это возможно.
Я отредактировал утверждение (добавленное в предлагаемом редактировании), что неправильный порядок разблокировки может привести к тупиковой ситуации. Снятие блокировок само по себе не должно блокироваться, поэтому разблокирующийся поток должен иметь возможность продвигаться вперед и освобождать следующий поток.
Я слишком много предполагал. Пожалуйста, примите мои извинения за это. Но я по-прежнему считаю, что «хорошая практика», на которую вы ссылаетесь, на самом деле является необходимой частью заказа блокировки.
@Queeg Я согласен с тем, что порядок разблокировки становится важным, когда у вас есть повторное приобретение, когда вы находитесь под подмножеством замков. Я не могу придумать последовательность блокировки, которая блокирует этот алгоритм, когда выпуски выходят из строя.
У @Nanofarad есть правильная идея: дать каждому экземпляру Data
уникальный постоянный числовой идентификатор, а затем использовать эти идентификаторы, чтобы решить, какой объект заблокировать первым. Вот как это может выглядеть на практике:
private static void lockBoth(Data a, Data b) {
Lock first = a.lock;
Lock second = b.lock;
if (a.getID() < b.getID()) {
first = b.lock;
second = a.lock;
}
first.lock();
second.lock();
}
private static void unlockBoth(Data a, Data b) {
a.lock.unlock();
b.lock.unlock();
// Note: @Queeg suggests in comments below that in the general case,
// it would be good practice to make this routine always unlock the
// two locks in the order opposite to which `lockBoth()` locked them.
// See https://stackoverflow.com/a/8949355/801894 for an explanation.
}
public void swapValue(Data other) {
lockBoth(this, other);
...swap 'em...
unlockBoth(this, other);
}
Пока ресурсы для блокировки сортируются, убедитесь, что разблокировка происходит в обратном порядке.
@Queeg, почему? Какая разница, какой замок откроется первым? Вызовы разблокировки не будут ни блокироваться, ни сбоить.
@Queeg Меня тоже удивляет то же самое - снятие блокировки не блокирует и не зависит от получения других блокировок. Можете ли вы объяснить свое обоснование этого утверждения? (что должно было быть комментарием, а не правкой, поскольку мой ответ не является целью моего ответа). Я могу себе представить, что так лучше сделать, но я изо всех сил пытаюсь определить шаблон блокировки, который блокируется, когда порядок получения правильный.
Я наткнулся на похожий пост здесь, на SO, который предлагает очень похожее решение, взятое из книги о параллелизме "Java concurrency in Practice". он из 2006 года, такой довольно "старый". Являются ли решения проблем параллелизма в этой книге все еще очень распространенными/актуальными на данный момент?
@Neran, книги стареют. Алгоритмы этого не делают. Прошли годы с тех пор, как я взломал Java Concurrency in Practice, но я думаю, что на обсуждение того, как решать определенные проблемы в Java, может быть потрачено больше слов, чем на описание самих проблем. С тех пор Java сильно выросла, но основные идеи остались прежними. Вы хотите безопасно заблокировать несколько объектов? Эта проблема и это решение существовали еще до того, как о Java даже мечтали. Я не знаю, есть ли лучшая архитектура для решения вашей проблемы, но это решение будет работать для той архитектуры, которая у вас есть сейчас.
Кажется, мы согласны с тем, что блокировка по порядку хороша для предотвращения взаимоблокировок. Объяснение на stackoverflow.com/questions/1951275/… показывает, что если вы снимаете блокировки не по порядку, нарушения порядка блокировки могут быть скрыты в коде. Но нарушение порядка блокировки будет означать, что предотвращение взаимоблокировок, вызванное порядком блокировки, не действует.
@Queeg, хорошо, так что в этом конкретном случае нет «нарушения порядка блокировки ... скрытого в коде», но я вижу, как в целом было бы хорошей гигиеной всегда открывать блокировки в обратном порядке. к которому они были заперты.
Я также подумал об атомарных типах данных. Когда нельзя использовать атомарные типы?