Обмен переменных в многопоточной среде

Недавно меня задал вопрос, который меня насторожил.

public void swapEngine(Car a, Car b) {
  Engine temp = a.engine;
  a.engine = b.engine;
  b.engine = temp;
}

Это не потокобезопасный метод. Если Thread 1 вызывает swapEngine(car1, car2), а затем Thread 2 вызывает swapEngine(car1, car3), возможно, что car2 закончит работу с двигателем car3. Наиболее очевидным способом решения этой проблемы является метод synchronize.

Синхронизация метода приводит к потенциальной неэффективности. Что делать, если Thread 1 вызывает swapEngine(car1, car2) и Thread 2 вызывает swapEngine(car3, car4)? Ни в коем случае эти два потока не могут мешать друг другу. В этом случае идеальной ситуацией будет то, что два потока будут поочередно менять двигатели. Синхронизация метода исключает это из процесса.

Есть ли другой способ поменять местами эти двигатели поточно-безопасным способом, все еще используя parallelism?

Изменить: сделанный метод открыт.

Ответ 1

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

Итак, если у автомобилей есть уникальный идентификатор, вы можете просто отсортировать автомобили, а затем поменять местами:

void swapEngine(Car a, Car b) {
    Comparator<Car> byId = Comparator.comparing(Car::id);
    Car[] cars = new Car[] {a, b};
    Arrays.sort(cars, byId);
    doSwap(cars[0]), cars[1];
}

private void doSwap(Car a, Car b) { 
    synchronized(a) {
        synchronized(b) {
            Engine temp = a.engine;
            a.engine = b.engine;
            b.engine = temp;
        }
    }
}

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

Ответ 2

Если вы храните Car.engine в AtomicReference, вы можете поменять их с помощью операций CAS:

public <T> void atomicSwap(AtomicReference<T> a, AtomicReference<T> b) {
    for(;;) {
        T aa = a.getAndSet(null);
        if (aa != null) {
            T bb = b.getAndSet(null);  
            if (bb != null) {
                // this piece will be reached ONLY if BOTH `a` and `b` 
                // contained non-null (and now contain null)
                a.set(bb);
                b.set(aa);
                return;
            } else {
                // if `b` contained null, try to restore old value of `a`
                // to avoid deadlocking
                a.compareAndSet(null, aa);
            }
        } 
    }          
}

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

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

public <T> T getValue(AtomicReference<T> a) {
    for(;;) {
        T v = a.get();
        if (v != null)
            return v;
    }
}

public <T> T setValue(AtomicReference<T> a, T value) {
    for(;;) {
        T old = a.get();
        if (old != null && a.compareAndSet(old, value))
            return old; 
    }
}