Nie tak dawno popełniłem tekst nt. rozszerzonego mechanizmu synchronizacji. Przygotowując się do wystąpienia na tegorocznym Devoxxie, przypomniałem sobie o jeszcze jednym pomyśle, który do pewnego stopnia rozwiązuje problem synchronizacji wielu obiektów.

Problemat bankowy

Czyli taki klasyczny przykład, za pomocą którego ilustrujemy różnej maści wyścigi i deadlocki. Mamy dwa konta Alice i Bob pomiędzy którymi następuje seria przelewów. Przelewy są realizowane w kilku, zazwyczaj dwóch, wątkach A i B. Z konta Alice w wątku A przelewamy N razy kwotę M. Tak samo z konta Bob w wątku B przelewamy N ramy kwotę M. Oczekiwany stan na koniec programu, to kwota identyczna z początkową na obu kontach. Mówiąc językiem kodu, chcemy osiągnąć coś mniej więcej takiego:

Listing 1. Klasa BankProblem – PoC

public class BankProblem {

	public static final int RUNS = 10000;
	private final BankService bankService;

	public BankProblem(BankService bankService) {
		this.bankService = bankService;
	}

	public static void main(String[] args) throws InterruptedException {
		new BankProblem(new MethodSync()).example();
	}

	public void example() throws InterruptedException {
		var bob = new Account("Bob");
		var alice = new Account("Alice");

		bob.deposit(RUNS);
		alice.deposit(RUNS);

		Thread a = new Thread(new Operation(bankService, alice, bob, 1), "A");
		Thread b = new Thread(new Operation(bankService, bob, alice, 1), "B");

		a.start();
		b.start();

		a.join();
		b.join();

		System.out.println("alice = " + alice);
		System.out.println("bob = " + bob);
	}
}

class Operation implements Runnable {

	private final BankService service;
	private final Account from;
	private final Account to;
	private final int value;

	public Operation(BankService service, Account from, Account to, int value) {
		this.service = service;
		this.from = from;
		this.to = to;
		this.value = value;
	}

	@Override
	public void run() {
		for (int i = 0; i < BankProblem.RUNS; i++) {
			service.checkout(from, to, value);
		}
	}
}

interface BankService {
	void checkout(Account from, Account to, int value);
}

I teraz w zależności od tego jak zaimplementujemy BankService otrzymamy różne wyniki.

Implementacja naiwna

Pierwsze podejście jest bardzo intuicyjne. Synchronizujmy metodę checkout i będzie git:

Listing 2. Naiwna implementacja MethodSync

class MethodSync implements BankService {

	public synchronized void checkout(Account from, Account to, int value) {
		from.withdraw(value);
		to.deposit(value);
	}
}

I jak to wszystko uruchomimy, to wynik będzie ok:

Listing 3. Wynik implementacji naiwnej

$ java pl.koziolekweb.orderedlock.BankProblem
alice = Account{uuid=888ed710-a216-4b30-ad88-c690441cb814, owner='Alice', balance=10000}
bob = Account{uuid=f347cfe8-f39a-48ae-8d42-95b1624e2ea7, owner='Bob', balance=10000}

Process finished with exit code 0

Tyle tylko, że nie do końca… Jeżeli chcielibyśmy dołożyć wątków, kont i operacji, to cały system dość szybko się zatnie. Przyczyna leży w sposobie synchronizacji. Muteksem w tym przypadku jest obiekt bankService. Oznacza to, że na raz możemy wykonać tylko jedną operację checkout niezależnie od tego ile wątków mamy. W efekcie każdy wątek, który nie załapie się na wykonanie, będzie czekać w kolejce, aż nastąpi zwolnienie blokady. Wtedy, o ile będzie miał szczęście, podejmie pracę, wchodząc do sekcji krytycznej. Użycie słowa kluczowego synchronized na zwykłej metodzie jest równoznaczne z:

Listing 4. synchronized na metodzie

synchronized void method() {
	//…
}

// to samo, ale inaczej

void method() {
	synchrnized(this) {
		//…
	}
}

Dodajmy zatem więcej serwisów… yyy… nie. Jeżeli zmienimy kod z listing 1 na taki:

Listing 5. Zmiana w PoC

Thread a = new Thread(new Operation(new MethodSync(), alice, bob, 1));
Thread b = new Thread(new Operation(new MethodSync(), bob, alice, 1));

I uruchomimy nasz kod, to:

Listing 6. Wynik implementacji naiwnej z wieloma instancjami serwisu

$ java pl.koziolekweb.orderedlock.BankProblem
alice = Account{uuid=f6ef15a4-9024-4852-835e-3f04dcef8974, owner='Alice', balance=9897}
bob = Account{uuid=9f8c9a67-83c8-4917-8f83-3c4717226808, owner='Bob', balance=10002}

Process finished with exit code 0

Balanse na koncie sie rozjechały. W dodatku są niższe niż oczekiwana suma.

I nie jest to nic dziwnego. W pierwotnej wersji modyfikacja wartości kont jest chroniona w ten sposób, że jest tylko jeden punkt, który może modyfikować wartości. Dostęp do tego punktu jest synchronizowany, więc tylko jeden wątek może dokonać modyfikacji. Jeżeli zwiększymy liczbę takich punktów, to każdego z nich dostęp ma tylko jeden wątek, ale każdy „grzebie” we wspólnych danych. Możliwa jest węc współbieżna modyfikacja danych.

Implementacja szkolna

Problem bankowy ma też swoją szkolna implementację:

Listing 7. Implementacja „szkolna”

class ArgumentSync implements BankService {

	public void checkout(Account from, Account to, int value) {
		synchronized (from) {
			synchronized (to) {
				from.withdraw(value);
				to.deposit(value);
			}
		}
	}
}

Jeżeli ją uruchomimy, to… program się zawiesi. Zrzut wątków pozwoli nam na odkrycie problemu:

Listing 8. Zrzut wątków.

"A" #32 [367397] prio=5 os_prio=0 cpu=0,32ms elapsed=1,97s tid=0x00007fe6b8244530 nid=367397 waiting for monitor entry  [0x00007fe616efd000]
   java.lang.Thread.State: BLOCKED (on object monitor)
	at pl.koziolekweb.orderedlock.ArgumentSync.checkout(BankProblem.java:83)
	- waiting to lock <0x000000011d1dcb70> (a pl.koziolekweb.orderedlock.Account)
	- locked <0x000000011d9de040> (a pl.koziolekweb.orderedlock.Account)
	at pl.koziolekweb.orderedlock.Operation.run(BankProblem.java:65)
	at java.lang.Thread.runWith(java.base@21.0.2/Thread.java:1596)
	at java.lang.Thread.run(java.base@21.0.2/Thread.java:1583)


"B" #33 [367398] prio=5 os_prio=0 cpu=0,23ms elapsed=1,97s tid=0x00007fe6b8245680 nid=367398 waiting for monitor entry  [0x00007fe616dfc000]
   java.lang.Thread.State: BLOCKED (on object monitor)
	at pl.koziolekweb.orderedlock.ArgumentSync.checkout(BankProblem.java:83)
	- waiting to lock <0x000000011d9de040> (a pl.koziolekweb.orderedlock.Account)
	- locked <0x000000011d1dcb70> (a pl.koziolekweb.orderedlock.Account)
	at pl.koziolekweb.orderedlock.Operation.run(BankProblem.java:65)
	at java.lang.Thread.runWith(java.base@21.0.2/Thread.java:1596)
	at java.lang.Thread.run(java.base@21.0.2/Thread.java:1583)

Wątek A czeka na dostęp do sekcji blokowanej przez wątek B i vice versa. Lub inaczej. Wątek ‘B’ założył monitor na Bobie w tym samym czasie gdy wątek A założył go na Alice. Próba złożenia kolejnego monitora nie jest możliwa, bo drugi wątek już to zrobił. Klasycznie mamy deadlock.

Idea

Trzeba zakładać blokadę zawsze w tej samej kolejności.

Tylko jak wyznaczyć kolejność?

W tym celu użyjemy implementacji interfejsu Comparator. Pozwoli nam to na posortowanie obiektów w odpowiedniej kolejności, tak by niezależnie do kolejności na liście parametrów wchodziły one do bloku synchronized w tej samej kolejności. Ważne jest, żeby sortowanie odbywało się w oparciu o niezmienniki. W naszym przypadku może być to identyfikator konta lub nazwa właściciela. Jeżeli będziemy sortować w oparciu o mutowalne wartości, to polegniemy. Zaimplementujmy więc nasz serwis:

Listing 9. Implementacja BankService z sortowaniem

class OrderedArgumentSync implements BankService {

	public void checkout(Account from, Account to, int value, Comparator<Account> comparator) {
		final int compare = comparator.compare(from, to);
		if (compare > 0) {
			synchronized (from) {
				synchronized (to) {
					from.withdraw(value);
					to.deposit(value);
				}
			}
		} else {
			synchronized (to) {
				synchronized (from) {
					from.withdraw(value);
					to.deposit(value);
				}
			}
		}
	}
}

Metoda checkout otrzymuje tutaj dodatkowy parametr. I tyle. Starczy. Po uruchomieniu otrzymamy:

Listing 10. Wynik implementacji z sortowaniem

$ java pl.koziolekweb.orderedlock.BankProblem
alice = Account{uuid=84b5b695-b0ad-44d9-93bf-07fdc937162b, owner='Alice', balance=10000}
bob = Account{uuid=73a58b61-8224-4c4a-b011-e80f51457b42, owner='Bob', balance=10000}

Process finished with exit code 0

Niby pięknie, ale jest kilka drobnych problemów, którym trzeba zaradzić.

Generalizacja

Interfejs Comparator nie jest idealny w tym miejscu. Potrafi on porównywać jedynie obiekty tego samego typu. Mówiąc inaczej nie możemy jako parametrów użyć przykładowo Account i Check. To powoduje, że w bardziej złożonych przypadkach np. wywołani dwóch metod, do których przekazujemy obiekty różnych typów w odwrotnej kolejności, będzie niemożliwe. Możemy temu zaradzić, tworząc generyczną implementację naszego rozwiązania:

Listing 11. Rozwiązanie generyczne

class GenericOrderedSync {

	public <S1, S2, R> R perform(S1 s1, S2 s2, BiFunction<S1, S2, R> todo, BiFunction<S1, S2, Integer> orderJudge) {
		final Integer order = orderJudge.apply(s1, s2);
		if (order > 0) {
			synchronized (s1) {
				synchronized (s2) {
					return todo.apply(s1, s2);
				}
			}
		} else {
			synchronized (s2) {
				synchronized (s1) {
					return todo.apply(s1, s2);
				}
			}
		}
	}
}

S1 i S2 reprezentują typy w kolejności, w jakiej trafiają do naszej docelowej funkcji todo. Kolejność określamy za pomocą orderJudge, który ma „mentalność” interfejsu Comparator. Uruchomienie tego kodu jest trochę bardziej upierdliwe:

Listing 12. Przykład uruchomienia

Thread a = new Thread(() -> o1.perform(alice, bob, (Account from, Account to) -> {
	from.withdraw(1);
	to.deposit(1);
	return null;
}, (Account l, Account r) -> l.getOwner().compareTo(r.getOwner())), "A");

Thread b = new Thread(() -> o1.perform(bob, alice, (Account from, Account to) -> {
	from.withdraw(1);
	to.deposit(1);
	return null;
}, (Account l, Account r) -> l.getOwner().compareTo(r.getOwner())), "B");

ale wynik jest ok:

Listing 13. Wynik implementacji generycznej

$ java pl.koziolekweb.orderedlock.BankProblem
alice = Account{uuid=dc48c7c9-e27c-4e38-8a2f-2d619b63434f, owner='Alice', balance=10000}
bob = Account{uuid=57b571c3-346c-4816-8831-6f7e458c713d, owner='Bob', balance=10000}

Process finished with exit code 0

Na zakończenie chcę tylko przypomnieć, że to jest PoC i raczej nie powinno to trafić na produkcję. Do czego gorąco zachęcam.