Deadlock - Revision history

JaroslavTulach at 16:21, 6 June 2025

JaroslavTulach — Fri, 06 Jun 2025 16:21:17 GMT

←Older revision		Revision as of 16:21, 6 June 2025
Line 69:		Line 69:
	This is the correct code which removes the [[deadlock]] danger and still keeps consistency. A kind of manually written [[TransactionalMemory]]. First of all atomically read the values needed for the computation. Then release the lock and call the unknown code. Then obtain the lock again, make sure nobody else modified the internal state and if so, modify the state of the object. If the state of the object has been modified meanwhile, repeat the computation with new values.		This is the correct code which removes the [[deadlock]] danger and still keeps consistency. A kind of manually written [[TransactionalMemory]]. First of all atomically read the values needed for the computation. Then release the lock and call the unknown code. Then obtain the lock again, make sure nobody else modified the internal state and if so, modify the state of the object. If the state of the object has been modified meanwhile, repeat the computation with new values.

-	~~The code can be made even cleaner, if the internal data are kept in a special immutable object:~~	+	=== Cleaner Code ===

-		+	{{:TransactionDataStructureExample}}
-	~~<source lang="java">~~	+
-		+
-		+
-	~~import java.util.concurrent.atomic.AtomicReference;~~	+
-		+
-	~~public abstract class Helper~~ {	+
-		+
-	~~private static final class Data~~ {	+
-		+
-	~~final int value1;~~	+
-	~~final int value2;~~	+
-	~~final int value3;~~	+
-		+
-	~~Data(int value1, int value2, int value3) {~~	+
-	~~this.value1 = value1;~~	+
-	~~this.value2 = value2;~~	+
-	~~this.value3 = value3;~~	+
-	}	+
-	}	+
-		+
-	~~private AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0));~~	+
-		+
-	~~protected abstract int combine(int x, int y);~~	+
-		+
-	~~public final void update() {~~	+
-	~~Data current;~~	+
-	~~while (true) {~~	+
-	~~current = data.get();~~	+
-		+
-	~~int r1 = combine(current.value1, current.value2);~~	+
-	~~int r2 = combine(current.value2, current.value3);~~	+
-	~~int r3 = combine(current.value3, current.value1);~~	+
-		+
-	~~if (data.compareAndSet(current, new Data(r1, r2, r3))) {~~	+
-	~~return;~~	+
-	}	+
-	}	+
-	}	+
-	}	+
-	~~</source>~~	+
-		+
-	Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK\|java/util/concurrent/atomic\|AtomicReference}} ~~''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value.~~	+

	Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no clash and the update succeeds.		Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no clash and the update succeeds.

JaroslavTulach at 07:09, 2 August 2018

JaroslavTulach — Thu, 02 Aug 2018 07:09:20 GMT

←Older revision		Revision as of 07:09, 2 August 2018
Line 116:		Line 116:

	Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no clash and the update succeeds.		Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no clash and the update succeeds.
		+
		+
		+	[[Category:APIDesignPatterns]]

JaroslavTulach at 16:27, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 16:27:27 GMT

←Older revision		Revision as of 16:27, 1 August 2018
Line 115:		Line 115:
	Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK\|java/util/concurrent/atomic\|AtomicReference}} ''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value.		Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK\|java/util/concurrent/atomic\|AtomicReference}} ''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value.

-	Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no ~~class~~ and the update succeeds.	+	Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no clash and the update succeeds.

JaroslavTulach at 16:24, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 16:24:25 GMT

←Older revision		Revision as of 16:24, 1 August 2018
Line 1:		Line 1:
-	[[wikipedia::Deadlock\|Deadlock]] can only happen when all four [[deadlock conditions]] are satisfied. One would expect satisfying all of them isn't that common, but that would be wrong assumption. [[Deadlock]]s happen. While it is fine to avoid them by eliminating just one of the [[deadlock conditions]] in a regular code, the situation in [[APIDesign]] is a bit different. As a [[paradox]] of [[APIDesign]] there is just a single [[good]] solution to avoid [[deadlock]]s when designing an [[API]]:	+	[[wikipedia::Deadlock\|Deadlock]] can only happen when all four [[deadlock conditions]] are satisfied. One would expect satisfying all of them isn't that common, but that would be wrong assumption. [[Deadlock]]s happen. Fighting with them is [[ImpossibleThreading\|close to impossible]]. While it is fine to avoid them by eliminating just one of the [[deadlock conditions]] in a regular code, the situation in [[APIDesign]] is a bit different. As a [[paradox]] of [[APIDesign]] there is just a single [[good]] solution to avoid [[deadlock]]s when designing an [[API]]:

	'''Never hold a lock when calling a foreign code!'''		'''Never hold a lock when calling a foreign code!'''

JaroslavTulach at 16:14, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 16:14:36 GMT

←Older revision		Revision as of 16:14, 1 August 2018
Line 31:		Line 31:

	How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain:		How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain:
		+
		+	<source lang="java">
		+	public abstract class Helper {
		+
		+	private int value1;
		+	private int value2;
		+	private int value3;
		+
		+	protected abstract int combine(int x, int y);
		+
		+	public final void update() {
		+	int v1;
		+	int v2;
		+	int v3;
		+	while (true) {
		+	synchronized (this) {
		+	v1 = value1;
		+	v2 = value2;
		+	v3 = value3;
		+	}
		+	int r1 = combine(v1, v2);
		+	int r2 = combine(v2, v3);
		+	int r3 = combine(v3, v1);
		+	synchronized (this) {
		+	if (v1 == value1 && v2 == value2 && v3 == value3) {
		+	value1 = r1;
		+	value2 = r2;
		+	value3 = r3;
		+	return;
		+	}
		+	}
		+	}
		+	}
		+	}
		+	</source>
		+
		+	This is the correct code which removes the [[deadlock]] danger and still keeps consistency. A kind of manually written [[TransactionalMemory]]. First of all atomically read the values needed for the computation. Then release the lock and call the unknown code. Then obtain the lock again, make sure nobody else modified the internal state and if so, modify the state of the object. If the state of the object has been modified meanwhile, repeat the computation with new values.
		+
		+	The code can be made even cleaner, if the internal data are kept in a special immutable object:

JaroslavTulach at 15:34, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 15:34:40 GMT

←Older revision		Revision as of 15:34, 1 August 2018
Line 30:		Line 30:
	Placing such class into an [[API]] is directly asking for troubles. First of all one synchronizes on a publicly reachable object - e.g. '''this''' - see [[Java_Monitor]] page for details. Yet, the biggest problem is the call to a unknown code while holding the lock. The unknown code is represented by abstract ''combine'' method - it can do anything wild. For example ask for another lock - and that is just a step away from causing a [[deadlock]].		Placing such class into an [[API]] is directly asking for troubles. First of all one synchronizes on a publicly reachable object - e.g. '''this''' - see [[Java_Monitor]] page for details. Yet, the biggest problem is the call to a unknown code while holding the lock. The unknown code is represented by abstract ''combine'' method - it can do anything wild. For example ask for another lock - and that is just a step away from causing a [[deadlock]].

-	How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that ~~shall be blamed and~~ shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain:	+	How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain:

JaroslavTulach at 15:32, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 15:32:46 GMT

←Older revision		Revision as of 15:32, 1 August 2018
Line 76:		Line 76:
	Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK\|java/util/concurrent/atomic\|AtomicReference}} ''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value.		Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK\|java/util/concurrent/atomic\|AtomicReference}} ''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value.

-	Avoiding [[deadlock]] this way sort of trades the [[deadlock]]s for live-locks. It is ~~not limited how many~~ times the cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no class and the update succeeds.	+	Avoiding [[deadlock]]s this way sort of trades the [[deadlock]]s for live-locks. There is no limit to the number of times the '''while''' cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org-openide-util-lookup\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no class and the update succeeds.

JaroslavTulach at 15:31, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 15:31:06 GMT

←Older revision		Revision as of 15:31, 1 August 2018
Line 3:		Line 3:
	'''Never hold a lock when calling a foreign code!'''		'''Never hold a lock when calling a foreign code!'''

-	What is a foreign code in this context? Anything written by users of your [[API]]. E.g. callbacks, listeners, etc. must not be called under any lock used in your [[API]]. The rule is that simple. Memorize the rule, stick to it and your [[API]]s will be [[deadlock]] free!	+	What is a foreign code in this context? Anything written by users of your [[API]]. E.g. callbacks, listeners, overriden methods, etc. must not be called under any lock used in your [[API]]. The rule is that simple. Memorize the rule, stick to it and your [[API]]s will be [[deadlock]] free!

	It is easy to follow the rule when dealing with listeners - they are just simple callbacks that notify a change - they don't return any value and as such they can be called asynchronously. which is exactly what [[UI]] frameworks like [[AWT]] or [[Swing]] do: they notify the callbacks ''later''. Of course, without holding any locks and thus avoiding [[deadlock]]s.		It is easy to follow the rule when dealing with listeners - they are just simple callbacks that notify a change - they don't return any value and as such they can be called asynchronously. which is exactly what [[UI]] frameworks like [[AWT]] or [[Swing]] do: they notify the callbacks ''later''. Of course, without holding any locks and thus avoiding [[deadlock]]s.

JaroslavTulach at 15:30, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 15:30:08 GMT

←Older revision		Revision as of 15:30, 1 August 2018
Line 35:		Line 35:
	<source lang="java">		<source lang="java">

-	~~public abstract class Helper {~~
-
-	~~private int value1;~~
-	~~private int value2;~~
-	~~private int value3;~~
-
-	~~protected abstract int combine(int x, int y);~~
-
-	~~public final void update() {~~
-	~~int v1;~~
-	~~int v2;~~
-	~~int v3;~~
-	~~while (true) {~~
-	~~synchronized (this) {~~
-	~~v1 = value1;~~
-	~~v2 = value2;~~
-	~~v3 = value3;~~
-	}
-
-	~~int r1 = combine(v1, v2);~~
-	~~int r2 = combine(v2, v3);~~
-	~~int r3 = combine(v3, v1);~~
-
-	~~synchronized (this) {~~
-	~~if (v1 == value1 && v2 == value2 && v3 == value3) {~~
-	~~value1 = r1;~~
-	~~value2 = r2;~~
-	~~value3 = r3;~~
-	~~return;~~
-	}
-	}
-	}
-	}
-	}
-
-	~~</source>~~
-
-	This is the correct code which removes the [[deadlock]] danger and still keeps consistency. A kind of manually written [[TransactionalMemory]]. First of all atomically read the values needed for the computation. Then release the lock and call the unknown code. Then obtain the lock again, make sure nobody else modified the internal state and if so, modify the state of the object. If the state of the object has been modified meanwhile, repeat the computation with new values.
-
-	~~The code can be made even cleaner, if the internal data are kept in a special immutable object:~~

-	~~<source lang="~~java">	+	import java.util.concurrent.atomic.AtomicReference;

	public abstract class Helper {		public abstract class Helper {
Line 93:		Line 53:
	}		}

-	private Data data = new Data(0, 0, 0);	+	private AtomicReference<Data> data = new AtomicReference<>(new Data(0, 0, 0));

	protected abstract int combine(int x, int y);		protected abstract int combine(int x, int y);
Line 100:		Line 60:
	Data current;		Data current;
	while (true) {		while (true) {
-	~~synchronized (this) {~~	+	current = data.get();
-	current = ~~this.~~data;	+
-	}	+

	int r1 = combine(current.value1, current.value2);		int r1 = combine(current.value1, current.value2);
Line 108:		Line 66:
	int r3 = combine(current.value3, current.value1);		int r3 = combine(current.value3, current.value1);

-	~~synchronized (this) {~~	+	if (data.compareAndSet(current, new Data(r1, r2, r3))) {
-	if (~~current == this.~~data~~) {~~	+	return;
-	~~this~~.~~data =~~ new Data(r1, r2, r3);	+
-	return;	+
-	}	+
	}		}
	}		}
Line 118:		Line 73:
	}		}
	</source>		</source>
		+
		+	Neat usage of immutability. The data that are supposed to be consistent are '''final''' in a ''Data'' class. The mutability is handled all at once with {{JDK\|java/util/concurrent/atomic\|AtomicReference}} ''compareAndSet'' method. Either it fails and the computation runs again or it succeeds and atomically changes the data to newly created and consistent value.
		+
		+	Avoiding [[deadlock]] this way sort of trades the [[deadlock]]s for live-locks. It is not limited how many times the cycle is executed. Under some bad setup, it might even run indefinitely. It helps, if there is some invariant that gets stabilized with every change of the ''data'' field. For example {{NB\|org/openide/util/lookup\|AbstractLookup}} is using the same approach and with every update of the ''data'' field, the internal data structure moves towards optimum - as a result it is clear that after some number of loops, there will be no class and the update succeeds.

JaroslavTulach at 15:17, 1 August 2018

JaroslavTulach — Wed, 01 Aug 2018 15:17:02 GMT

←Older revision		Revision as of 15:17, 1 August 2018
Line 28:		Line 28:
	</source>		</source>

-	Placing such class into an [[API]] is directly asking for troubles. First of all one synchronizes on a publicly reachable object - e.g. '''this''' - see [[Java_Monitor]] page for details. Yet, the biggest problem is the call to a unknown code while holding the lock. The unknown code is represented by abstract ''combine'' method - it can do anything wild. For example ask for another lock - and that is just a step away ~~for creating~~ [[deadlock]].	+	Placing such class into an [[API]] is directly asking for troubles. First of all one synchronizes on a publicly reachable object - e.g. '''this''' - see [[Java_Monitor]] page for details. Yet, the biggest problem is the call to a unknown code while holding the lock. The unknown code is represented by abstract ''combine'' method - it can do anything wild. For example ask for another lock - and that is just a step away from causing a [[deadlock]].

	How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that shall be blamed and shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain:		How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that shall be blamed and shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain: