CSC/ECE 506 Spring 2011/ch5 LL - Revision history

Admin: /* Allow elements to be returned to the list */

2011-03-27T01:04:37Z

Allow elements to be returned to the list

← Older revision		Revision as of 01:04, 27 March 2011
Line 88:		Line 88:
	==Allow elements to be returned to the list==		==Allow elements to be returned to the list==
	Allowing elements to be returned to the list can cause list corruption in a subtle manner. This is generally referred to as the [http://en.wikipedia.org/wiki/ABA_problem ABA problem], where the head of the list transitions from A to B and back to A.		Allowing elements to be returned to the list can cause list corruption in a subtle manner. This is generally referred to as the [http://en.wikipedia.org/wiki/ABA_problem ABA problem], where the head of the list transitions from A to B and back to A.
	We consider the case, where a node can be returned to the list and both the insert and the remove happen at the head of the list. Let's assume that we have two threads that are trying to update the list, one that is trying to remove the head node and the other thread executes both removes and insert operations.		We consider the case where a node can be returned to the list and both the insert and the remove happen at the head of the list. Let's assume that we have two threads that are trying to update the list, one that is trying to remove the head node and the other thread executes both removes and insert operations.

	The state of the list according to thread-1 is: <code>head-> A->B->C</code>. It then gets preempted by the scheduler before it executes the CAS instruction but after it has read A's next pointer that points to B. In the meanwhile, Thread-2 does multiple updates of the list and transitions it to: <code>head->A->C->D</code>. Thus, it removes A from the list and inserts it back onto the list. Thread-1 now gets to execute its CAS instruction that updates the head pointer to A's next pointer, which is node B according to thread-1. This CAS succeeds since the head still points to A. The list now looks like: <code>head->A->B</code>. We have inadvertently removed nodes C and D from the list and corrupted it. This issue is referred to as the ''ABA'' issue, indicating the transition states of the ''head'' pointer.		The state of the list according to thread-1 is: <code>head-> A->B->C</code>. It then gets preempted by the scheduler before it executes the CAS instruction but after it has read A's next pointer that points to B. In the meanwhile, Thread-2 does multiple updates of the list and transitions it to: <code>head->A->C->D</code>. Thus, it removes A from the list and inserts it back onto the list. Thread-1 now gets to execute its CAS instruction that updates the head pointer to A's next pointer, which is node B according to thread-1. This CAS succeeds since the head still points to A. The list now looks like: <code>head->A->B</code>. We have inadvertently removed nodes C and D from the list and corrupted it. This issue is referred to as the ''ABA'' issue, indicating the transition states of the ''head'' pointer.

Admin: /* Allow elements to be returned to the list */

2011-03-27T01:04:13Z

Allow elements to be returned to the list

← Older revision		Revision as of 01:04, 27 March 2011
Line 87:		Line 87:

	==Allow elements to be returned to the list==		==Allow elements to be returned to the list==
	Allowing elements to be returned to the list can cause list corruption in a subtle manner. This is generally referred to as the [http://en.wikipedia.org/wiki/ABA_problem ABA problem], where the head of the list, transitions from A to B and back to A.		Allowing elements to be returned to the list can cause list corruption in a subtle manner. This is generally referred to as the [http://en.wikipedia.org/wiki/ABA_problem ABA problem], where the head of the list transitions from A to B and back to A.
	We consider the case, where a node can be returned to the list and both the insert and the remove happen at the head of the list. Let's assume that we have two threads that are trying to update the list, one that is trying to remove the head node and the other thread executes both removes and insert operations.		We consider the case, where a node can be returned to the list and both the insert and the remove happen at the head of the list. Let's assume that we have two threads that are trying to update the list, one that is trying to remove the head node and the other thread executes both removes and insert operations.

Admin: /* Motivation */

2011-03-27T00:59:28Z

Motivation

← Older revision		Revision as of 00:59, 27 March 2011
Line 13:		Line 13:
	* Locks can cause other issues such as [http://en.wikipedia.org/wiki/Thundering_herd_problem the thundering-herd problem]		* Locks can cause other issues such as [http://en.wikipedia.org/wiki/Thundering_herd_problem the thundering-herd problem]

	[http://en.wikipedia.org/wiki/Non-blocking_synchronization Non-blocking algorithms] permit truly concurrent thread-safe access to shared data structures where threads don't block on access. A thread might however have to retry to achieve ~~it's~~ objective. In the modern computing era, [http://en.wikipedia.org/wiki/Nehalem_(microarchitecture) multi-core architecture] is ubiquitous. In these architectures non-blocking algorithms can make use of the available compute rather than the blocking approach where the extra cores would generally be wasted. Thus non-blocking algorithms have significant throughput benefits on current architectures.		[http://en.wikipedia.org/wiki/Non-blocking_synchronization Non-blocking algorithms] permit truly concurrent thread-safe access to shared data structures where threads don't block on access. A thread might however have to retry to achieve its objective. In the modern computing era, [http://en.wikipedia.org/wiki/Nehalem_(microarchitecture) multi-core architecture] is ubiquitous. In these architectures non-blocking algorithms can make use of the available compute rather than the blocking approach where the extra cores would generally be wasted. Thus non-blocking algorithms have significant throughput benefits on current architectures.

	==Categories==		==Categories==

Briyenga: /* Building blocks */

2011-03-26T19:34:26Z

Building blocks

← Older revision		Revision as of 19:34, 26 March 2011
Line 46:		Line 46:

	* [http://en.wikipedia.org/wiki/Load-Link/Store-Conditional Load Linked/Store Conditional / LL-SC ]:		* [http://en.wikipedia.org/wiki/Load-Link/Store-Conditional Load Linked/Store Conditional / LL-SC ]:
	These are a pair of instructions that together implement a lock-free atomic read-modify-write operation. Load-link returns the current value of a memory location. A subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link.		These are a pair of instructions that together implement a lock-free atomic read-modify-write operation. Load-link returns the current value of a memory location. A subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link. Section 9.1.5 of [[#References \| Solihin (2009)]] discusses the semantics of the LL-SC instructions and a lock implementation based on the LL-SC instructions.

	Most modern architectures provide the CAS instruction. The Power PC architecture provides a LL-SC implementation. Most compiler/tool chains provide convenient wrappers around these instructions, e.g., [http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html#Atomic-Builtins GCC atomic builtins].		Most modern architectures provide the CAS instruction. The Power PC architecture provides a LL-SC implementation. Most compiler/tool chains provide convenient wrappers around these instructions, e.g., [http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html#Atomic-Builtins GCC atomic builtins].

Briyenga: /* Allow elements to be returned to the list */

2011-03-26T19:28:19Z

Allow elements to be returned to the list

← Older revision		Revision as of 19:28, 26 March 2011
Line 87:		Line 87:

	==Allow elements to be returned to the list==		==Allow elements to be returned to the list==
	Allowing elements to be returned to the list can cause list corruption in a subtle manner. This is generally referred to as the [http://en.wikipedia.org/wiki/ABA_problem ABA problem]		Allowing elements to be returned to the list can cause list corruption in a subtle manner. This is generally referred to as the [http://en.wikipedia.org/wiki/ABA_problem ABA problem], where the head of the list, transitions from A to B and back to A.
	We consider the case, where a node can be returned to the list and both the insert and the remove happen at the head of the list. Let's assume that we have two threads that are trying to update the list, one that is trying to remove the head node and the other thread executes both removes and insert operations.		We consider the case, where a node can be returned to the list and both the insert and the remove happen at the head of the list. Let's assume that we have two threads that are trying to update the list, one that is trying to remove the head node and the other thread executes both removes and insert operations.

Briyenga: /* DCAS based solutions */

2011-03-26T19:06:21Z

DCAS based solutions

← Older revision		Revision as of 19:06, 26 March 2011
Line 109:		Line 109:

	===DCAS based solutions===		===DCAS based solutions===
	A [http://en.wikipedia.org/wiki/Double_compare-and-swap The double compare-and-swap instruction] allows atomic update of a double word in memory. This could be used to use implement a much larger tag and further decrease the probability of the tag wrapping around.		[http://en.wikipedia.org/wiki/Double_compare-and-swap The double compare-and-swap instruction] allows atomic update of a double word in memory. This could be used to use implement a much larger tag and further decrease the probability of the tag wrapping around.

	===Other approaches===		===Other approaches===

Briyenga: /* DCAS based solutions */

2011-03-26T19:06:09Z

DCAS based solutions

← Older revision		Revision as of 19:06, 26 March 2011
Line 109:		Line 109:

	===DCAS based solutions===		===DCAS based solutions===
	A [http://en.wikipedia.org/wiki/Double_compare-and-swap The ~~Double~~ compare-and-swap instruction] allows atomic update of a double word in memory. This could be used to use implement a much larger tag and further decrease the probability of the tag wrapping around.		A [http://en.wikipedia.org/wiki/Double_compare-and-swap The double compare-and-swap instruction] allows atomic update of a double word in memory. This could be used to use implement a much larger tag and further decrease the probability of the tag wrapping around.

	===Other approaches===		===Other approaches===

Briyenga: /* DCAS based solutions */

2011-03-26T19:05:57Z

DCAS based solutions

← Older revision		Revision as of 19:05, 26 March 2011
Line 109:		Line 109:

	===DCAS based solutions===		===DCAS based solutions===
	A [http://en.wikipedia.org/wiki/Double_compare-and-swap ~~DCAS~~ instruction] allows atomic update of a double word in memory. This could be used to use implement a much larger tag and further decrease the probability of the tag wrapping around.		A [http://en.wikipedia.org/wiki/Double_compare-and-swap The Double compare-and-swap instruction] allows atomic update of a double word in memory. This could be used to use implement a much larger tag and further decrease the probability of the tag wrapping around.

	===Other approaches===		===Other approaches===

Briyenga: /* Building blocks */

2011-03-26T19:04:56Z

Building blocks

← Older revision		Revision as of 19:04, 26 March 2011
Line 48:		Line 48:
	These are a pair of instructions that together implement a lock-free atomic read-modify-write operation. Load-link returns the current value of a memory location. A subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link.		These are a pair of instructions that together implement a lock-free atomic read-modify-write operation. Load-link returns the current value of a memory location. A subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link.

	Most modern architectures provide the CAS instruction. The ~~power-pc~~ architecture provides a LL-SC implementation. Most compiler/tool chains provide convenient wrappers around these instructions, e.g., [http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html#Atomic-Builtins GCC atomic builtins].		Most modern architectures provide the CAS instruction. The Power PC architecture provides a LL-SC implementation. Most compiler/tool chains provide convenient wrappers around these instructions, e.g., [http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html#Atomic-Builtins GCC atomic builtins].
	It is important to note that the atomic primitives like other memory instructions operate at the granularity of a single memory word. 64 bit machines have 64 bit memory words, while 32 bit machines operate on 32 bit memory words. Algorithms that use these atomic primitives, frequently rely on being able to atomically update two distinct fields of a data structure. This is generally achieved by concatenating the two fields to be part of a single memory word.		It is important to note that the atomic primitives like other memory instructions operate at the granularity of a single memory word. 64 bit machines have 64 bit memory words, while 32 bit machines operate on 32 bit memory words. Algorithms that use these atomic primitives, frequently rely on being able to atomically update two distinct fields of a data structure. This is generally achieved by concatenating the two fields to be part of a single memory word.

Briyenga: /* Barrier instructions */

2011-03-26T19:04:18Z

Barrier instructions

← Older revision		Revision as of 19:04, 26 March 2011
Line 137:		Line 137:

	==Barrier instructions==		==Barrier instructions==
	Most architectures provide [http://en.wikipedia.org/wiki/Memory_barrier barrier instructions] also referred to as fence instructions that enable software to force an order on memory operations. For e.g. in the X86 architecture, loads can moved above stores as long as they are to different locations, however this can be restricted by inserting a fence instruction between the store and the load.		Most architectures provide [http://en.wikipedia.org/wiki/Memory_barrier barrier instructions] also referred to as fence instructions that enable software to force an order on memory operations. For, e.g., in the X86 architecture, loads can moved above stores as long as they are to different locations, however this can be restricted by inserting a fence instruction between the store and the load.

	The barrier instructions in the [http://siyobik.info/index.php?module=x86 X86 architecture] are:		The barrier instructions in the [http://siyobik.info/index.php?module=x86 X86 architecture] are: