CSC/ECE 506 Spring 2011/ch10a dc - Revision history

Dmcarmon: /* References */

2011-04-14T18:25:18Z

References

← Older revision		Revision as of 18:25, 14 April 2011
Line 145:		Line 145:
	# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]		# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]
	# Wikipedia, [http://en.wikipedia.org/wiki/Transitive_relation Transitive Relation]		# Wikipedia, [http://en.wikipedia.org/wiki/Transitive_relation Transitive Relation]
	# Wikipedia, [[http://en.wikipedia.org/wiki/Volatile_variable#In_Java Volatile] Volatile Variables]		# Wikipedia, [http://en.wikipedia.org/wiki/Volatile_variable#In_Java Volatile Volatile Variables]
	# Wikipedia, [http://en.wikipedia.org/wiki/Final_(Java) Final (Java)]		# Wikipedia, [http://en.wikipedia.org/wiki/Final_(Java) Final (Java)]

Dmcarmon: rewrote for clarity and added more examples and references

2011-04-14T18:24:23Z

rewrote for clarity and added more examples and references

← Older revision		Revision as of 18:24, 14 April 2011
Line 37:		Line 37:
	</pre>		</pre>

	In this example it is important that the statement x = 1 is completed before xIsWritten = 1, and that this order is seen by both threads. In other words, x = 1 and xIsWritten need to have a happens-before relationship.		In this example it is important that the statement <tt>x = 1</tt> is completed before <tt>xIsWritten = 1</tt>, and that this order is seen by both threads. In other words, <tt>x = 1</tt> and <tt>xIsWritten</tt> need to have a happens-before relationship.

	==Happens-before Rules==		==Happens-before Rules==
	Brian Goetz in [http://www2.lib.ncsu.edu/catalog/record/NCSU2282669 Java Concurrency in Practice] explains that happens-before relationships require the following rules:		Brian Goetz in [http://www2.lib.ncsu.edu/catalog/record/NCSU2282669 Java Concurrency in Practice] explains that happens-before relationships require the following rules:

	* Program order rule		* Program order rule - the order that statements are written in should be the order that every processor sees them executed in.

	* Monitor lock rule		* Monitor lock rule - only one thread at a time is allowed to work on a synchronized method or block of code (synchronized means that it is protected by a monitor). Whenever a thread wants to enter a synchronized block of code it must acquire a lock (the monitor). The monitor lock rule insures that ever lock and unlock on the monitor is done in order. A monitor is like a key that a thread must get before it can access a synchronized method or block of code, and only one thread can have the key at any one time. Example code:

	* ~~Volatile variable rule~~		<pre>
			// synchronized method
			public synchronized insertLinkedList(int * element)
			{ // each thread must acquire the monitor associated with the method
			// here before executing the rest of the code

			// ... code to insert element into linked list
			}

			// synchronized block
			String myObj;
			synchronized(myObj)
			{ // each thread must acquire the monitor associated with the object
			// before executing the rest of the code.

			// ... critical code here
			}
			</pre>

			<b>Note:</b> any java object regardless of type has a monitor associated with it which can be used to synchronize a block of code via <tt>synchronized(myObj)</tt>.

	* ~~Thread start~~ rule		* Volatile variable rule - volatile variable rule says that a volatile variable is synchronized like a synchronized block of code or method is. In other words, only one thread at a time can write or read a volatile variable.

	* Thread ~~termination~~ rule		* Thread start rule - this ensures that insures that a thread can't start executing code before it has been properly set up (i.e. the call to Thread.start() has finished).

	* ~~Interruption~~ rule		* Thread termination rule - this ensures that before a thread is terminated every other thread sees the result of the terminating thread's instructions.

	* ~~Finalizer~~ rule		* Interruption rule - one thread must complete the process of calling an interrupt on the other thread before the other thread starts servicing the interrupt.

	* ~~Transitivity~~		* Finalizer rule - this ensures that the constructor finishes constructing the thread before the finalizer starts.

	~~Let's unpack this list. First of all, program order simply means that order that statements are written in should be the order that every processor sees them executed as, if they have a happens~~-~~after relationship. Secondly, with a monitor lock, the monitor is a "key"~~ that ~~a thread must get before it can access a synchronized block of code, and only one thread can have the "key" at any one time~~. ~~This means that only one thread at a time is working the block of code~~. The monitor lock rule insures that ever lock and unlock is done in order. The volatile variable rule says that a volatile variable is like a monitor locked variable. The two thread rules insures that the thread doesn't start executing before the call to Thread.start() has finished, and before it is terminated every thread sees the result of its instructions. ~~Similar to the thread start rule~~, the interruption rule says that a thread must complete calling an interrupt before the interrupt is started in the other thread. Also similar, the finalizer rule means that the constructor is completed before the finalizer starts. Lastly, transitivity means that if A->B and B->C~~, then~~ A~~->C~~.		* Transitivity - ensures that [http://en.wikipedia.org/wiki/Transitive_relation transitive relationships] are kept. For example, if A follows B and C follows B then C must follow A.

	These rules are the main framework for the Java programming model.		These rules are the main framework for the Java programming model.
			==Volatile and Final Variables==

			[http://en.wikipedia.org/wiki/Volatile_variable#In_Java Volatile] and [http://en.wikipedia.org/wiki/Final_(Java) final] variables are also important to the JMM. As mentioned above in the happens-before rules, volatile variables may only be written or read by one thread at a time. Reads and writes to them have a global order. This is critical for global variables that may be written by more than one thread. On the other hand, a final variable can only be written once. This means that they are written once in the constructor of a object. Note that this does not imply that the variables are immutable (see reference for more information).

	=Secondary Aspects=		=Secondary Aspects=
Line 122:		Line 144:
	# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]		# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]
	# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]		# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]
			# Wikipedia, [http://en.wikipedia.org/wiki/Transitive_relation Transitive Relation]
			# Wikipedia, [[http://en.wikipedia.org/wiki/Volatile_variable#In_Java Volatile] Volatile Variables]
			# Wikipedia, [http://en.wikipedia.org/wiki/Final_(Java) Final (Java)]

Dmcarmon: /* References */

2011-04-05T03:48:19Z

References

← Older revision		Revision as of 03:48, 5 April 2011
Line 119:		Line 119:
	# Wikipedia, [http://en.wikipedia.org/wiki/Data_race Data Race]		# Wikipedia, [http://en.wikipedia.org/wiki/Data_race Data Race]
	# Wikipedia, [http://en.wikipedia.org/wiki/Happened-before "Happened-before."]		# Wikipedia, [http://en.wikipedia.org/wiki/Happened-before "Happened-before."]
			# Wikipeida, [http://en.wikipedia.org/wiki/Initialization_on_demand_holder_idiom Initialization on Demand Holder Idiom]
	# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]		# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]
	# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]		# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]

Dmcarmon: /* Double-checked Locking */

2011-04-05T03:47:58Z

Double-checked Locking

← Older revision		Revision as of 03:47, 5 April 2011
Line 71:		Line 71:

	<pre>		<pre>
	// From Manson and Goetz (2004)		// From Manson and Goetz (2004) JSR 133 (Java Memory Model) FAQ
	// double-checked-locking - don't do this!		// double-checked-locking - don't do this!

Line 88:		Line 88:

	The problem with this code is that the reads may be reordered by the compiler (they are not happens-after statements). This means the code produces indeterminate results which could lead you to attempt to read from a null pointer while thinking that it had been initialized to new Something(). This can be avoided in the new version of the JMM by declaring the instance volatile due to the volatile rule.		The problem with this code is that the reads may be reordered by the compiler (they are not happens-after statements). This means the code produces indeterminate results which could lead you to attempt to read from a null pointer while thinking that it had been initialized to new Something(). This can be avoided in the new version of the JMM by declaring the instance volatile due to the volatile rule.

			A better alternative to this code is the [http://en.wikipedia.org/wiki/Initialization_on_demand_holder_idiom Initialization on Demand Holder Idiom]:

			<pre>
			// From Manson and Goetz (2004) JSR 133 (Java Memory Model) FAQ
			private static class LazySomethingHolder {
			public static Something something = new Something();
			}

			public static Something getInstance() {
			return LazySomethingHolder.something;
			}


			</pre>

	=Summary=		=Summary=

Dmcarmon: /* Motivation */

2011-04-05T03:41:28Z

Motivation

← Older revision		Revision as of 03:41, 5 April 2011
Line 13:		Line 13:
	* [http://en.wikipedia.org/wiki/Data_race data races] (that is, when two threads try to access the data at the same time when it is being altered by another thread)		* [http://en.wikipedia.org/wiki/Data_race data races] (that is, when two threads try to access the data at the same time when it is being altered by another thread)

	* [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization] directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see pages 290-313 in chapter 10 of Solihin's textbook, Fundamentals of Parallel Computer Architecture)		* [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization] directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see pages 290-313 in chapter 10 of Solihin's textbook, "Fundamentals of Parallel Computer Architecture)"

	* compiler reordering of instructions (part of [http://en.wikipedia.org/wiki/Compiler_optimization compiler optimization])		* compiler reordering of instructions (part of [http://en.wikipedia.org/wiki/Compiler_optimization compiler optimization])

Dmcarmon: references

2011-04-05T03:40:44Z

references

← Older revision		Revision as of 03:40, 5 April 2011
Line 100:		Line 100:
	# Manson, Pugh and Adve, [http://rsim.cs.illinois.edu/Pubs/popl05.pdf The Java Memory Model]		# Manson, Pugh and Adve, [http://rsim.cs.illinois.edu/Pubs/popl05.pdf The Java Memory Model]
	# Solihin, Yan, Fundamentals of Parallel Computer Architencture		# Solihin, Yan, Fundamentals of Parallel Computer Architencture
	~~# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]~~
	# Wikipedia, [http://en.wikipedia.org/wiki/Cache_consistency Cache Consistancy]		# Wikipedia, [http://en.wikipedia.org/wiki/Cache_consistency Cache Consistancy]
			# Wikipedia, [http://en.wikipedia.org/wiki/Compiler_optimization Compiler Optimization]
	# Wikipedia, [http://en.wikipedia.org/wiki/Data_race Data Race]		# Wikipedia, [http://en.wikipedia.org/wiki/Data_race Data Race]
			# Wikipedia, [http://en.wikipedia.org/wiki/Happened-before "Happened-before."]
			# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]
	# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]		# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]
	~~# Wikipedia, [http://en.wikipedia.org/wiki/Happened-before "Happened-before."]~~

Dmcarmon: /* Motivation */

2011-04-05T03:38:28Z

Motivation

← Older revision		Revision as of 03:38, 5 April 2011
Line 15:		Line 15:
	* [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization] directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see pages 290-313 in chapter 10 of Solihin's textbook, Fundamentals of Parallel Computer Architecture)		* [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization] directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see pages 290-313 in chapter 10 of Solihin's textbook, Fundamentals of Parallel Computer Architecture)

	* compiler reordering of instructions		* compiler reordering of instructions (part of [http://en.wikipedia.org/wiki/Compiler_optimization compiler optimization])

	Programmers need to know how these issues effect program execution so that they can write good software for parallel systems. For example, C/C++ has the [https://computing.llnl.gov/tutorials/pthreads/ pthreads] add-on to handle parallel programing. However, Java supports parallel programing by default. The JMM describes what is legal behavior for variables and memory accesses in programs with multiple threads.		Programmers need to know how these issues effect program execution so that they can write good software for parallel systems. For example, C/C++ has the [https://computing.llnl.gov/tutorials/pthreads/ pthreads] add-on to handle parallel programing. However, Java supports parallel programing by default. The JMM describes what is legal behavior for variables and memory accesses in programs with multiple threads.

Dmcarmon: Second Draft

2011-04-05T03:36:52Z

Second Draft

← Older revision		Revision as of 03:36, 5 April 2011
Line 1:		Line 1:
	Chapter 10a Supplement Java Memory Model		Chapter 10a Supplement - Java Memory Model

	=Introduction=		=Introduction=

	This chapter supplement discusses the Java Memory Model (JMM). First of all, we will cover the motivation for a memory model for Java. Secondly, the main aspects of JMM including happens-before relationships and final and volatile variables. And lastly, we'll mention double-checking.		This chapter supplement discusses the [http://rsim.cs.illinois.edu/Pubs/popl05.pdf Java Memory Model] (JMM). First of all, we will cover the motivation for a memory model for Java. Secondly, the main aspects of JMM including happens-before relationships and final and volatile variables. And lastly, we'll mention double-checking.

	=Motivation=		=Motivation=
Line 11:		Line 11:
	* multiple layers of cache across different processors (this introduces problems with [http://en.wikipedia.org/wiki/Cache_consistency cache consistancy])		* multiple layers of cache across different processors (this introduces problems with [http://en.wikipedia.org/wiki/Cache_consistency cache consistancy])

	* data races (that is, when two threads try to access the data at the same time when it is being altered by another thread)		* [http://en.wikipedia.org/wiki/Data_race data races] (that is, when two threads try to access the data at the same time when it is being altered by another thread)

	* synchronization directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see chapter ?? of ~~the~~ Solihin ~~___~~ textbook)		* [http://en.wikipedia.org/wiki/Synchronization_(computer_science) synchronization] directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see pages 290-313 in chapter 10 of Solihin's textbook, Fundamentals of Parallel Computer Architecture)

	* compiler reordering of instructions		* compiler reordering of instructions
Line 26:		Line 26:
	For example:		For example:

	// Thread 1:		<pre>
			// Thread 1
	int xIsWritten = 0;		int xIsWritten = 0;
	x = 1;		x = 1;
	xIsWritten = 1;		xIsWritten = 1;

			// Thread 2
	// Thread 2:		while(xIsWritten) {
	while(xIsWritten) {};		};
			</pre>

	In this example it is important that the statement x = 1 is completed before xIsWritten = 1, and that this order is seen by both threads. In other words, x = 1 and xIsWritten need to have a happens-before relationship.		In this example it is important that the statement x = 1 is completed before xIsWritten = 1, and that this order is seen by both threads. In other words, x = 1 and xIsWritten need to have a happens-before relationship.
Line 68:		Line 70:
	One of the controversial issues that came up with parallel computing and the JMM was double-checked locking. People wanted to avoid time consuming synchronization so they implemented double-checked locking. Here is an example of double-checked locking from [http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html Jeremy Manson and Brien Goetz (2004)]		One of the controversial issues that came up with parallel computing and the JMM was double-checked locking. People wanted to avoid time consuming synchronization so they implemented double-checked locking. Here is an example of double-checked locking from [http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html Jeremy Manson and Brien Goetz (2004)]

			<pre>
	// From Manson and Goetz (2004)		// From Manson and Goetz (2004)
	// double-checked-locking - don't do this!		// double-checked-locking - don't do this!
Line 82:		Line 85:
	return instance;		return instance;
	}		}
			</pre>

	The problem with this code is that the reads may be reordered by the compiler (they are not happens-after statements). This means the code produces indeterminate results which could lead you to attempt to read from a null pointer while thinking that it had been initialized to new Something(). This can be avoided in the new version of the JMM by declaring the instance volatile due to the volatile rule.		The problem with this code is that the reads may be reordered by the compiler (they are not happens-after statements). This means the code produces indeterminate results which could lead you to attempt to read from a null pointer while thinking that it had been initialized to new Something(). This can be avoided in the new version of the JMM by declaring the instance volatile due to the volatile rule.

	=Summary=		=Summary=

			In summary the JMM is a useful and necessary tool. It's useful for programmers trying to deal with multiple threads; because, it lets them know what (and what not) to expect. The happens-after relationship allows the programmers to restrict certain instructions that must be done in order. And, the JMM is necessary because without the tools it provides for synchronization programs may have indeterminate results.

			=References=

			# Barney, Blaise [https://computing.llnl.gov/tutorials/pthreads/ POSIX Threads Programming]
			# Goetz, Brian, [http://www2.lib.ncsu.edu/catalog/record/NCSU2282669 Java Concurrency in Practice]
			# Manson and Goetz, [http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html JSR 133 (Java Memory Model) FAQ]
			# Manson, Pugh and Adve, [http://rsim.cs.illinois.edu/Pubs/popl05.pdf The Java Memory Model]
			# Solihin, Yan, Fundamentals of Parallel Computer Architencture
			# Wikipedia, [http://en.wikipedia.org/wiki/Parallel_computing Parallel Computing]
			# Wikipedia, [http://en.wikipedia.org/wiki/Cache_consistency Cache Consistancy]
			# Wikipedia, [http://en.wikipedia.org/wiki/Data_race Data Race]
			# Wikipedia, [http://en.wikipedia.org/wiki/Synchronization_(computer_science) Synchronization (computer science)]
			# Wikipedia, [http://en.wikipedia.org/wiki/Happened-before "Happened-before."]

Dmcarmon: First Draft

2011-04-05T03:02:58Z

First Draft

New page

Chapter 10a Supplement Java Memory Model

=Introduction=

This chapter supplement discusses the Java Memory Model (JMM). First of all, we will cover the motivation for a memory model for Java. Secondly, the main aspects of JMM including happens-before relationships and final and volatile variables. And lastly, we'll mention double-checking.

=Motivation=

With [http://en.wikipedia.org/wiki/Parallel_computing parallel computing] becoming more popular, programming languages face many challenges including:

* multiple layers of cache across different processors (this introduces problems with [http://en.wikipedia.org/wiki/Cache_consistency cache consistancy])

* data races (that is, when two threads try to access the data at the same time when it is being altered by another thread)

* synchronization directives. Note: these may be different depending on whether you have a "strong" or "weak" memory model (see chapter ?? of the Solihin ___ textbook)

* compiler reordering of instructions

Programmers need to know how these issues effect program execution so that they can write good software for parallel systems. For example, C/C++ has the [https://computing.llnl.gov/tutorials/pthreads/ pthreads] add-on to handle parallel programing. However, Java supports parallel programing by default. The JMM describes what is legal behavior for variables and memory accesses in programs with multiple threads.

=Main Aspects=

One of the most important parts of the Java Memory Model is the concept of [http://en.wikipedia.org/wiki/Happened-before "happens-before."] Two statements have a happens-before relationship if one must come before the other.

==Happens-before Illustration==
For example:

// Thread 1:
int xIsWritten = 0;
x = 1;
xIsWritten = 1;

// Thread 2:
while(xIsWritten) {};

In this example it is important that the statement x = 1 is completed before xIsWritten = 1, and that this order is seen by both threads. In other words, x = 1 and xIsWritten need to have a happens-before relationship.

==Happens-before Rules==
Brian Goetz in [http://www2.lib.ncsu.edu/catalog/record/NCSU2282669 Java Concurrency in Practice] explains that happens-before relationships require the following rules:

* Program order rule

* Monitor lock rule

* Volatile variable rule

* Thread start rule

* Thread termination rule

* Interruption rule

* Finalizer rule

* Transitivity

Let's unpack this list. First of all, program order simply means that order that statements are written in should be the order that every processor sees them executed as, if they have a happens-after relationship. Secondly, with a monitor lock, the monitor is a "key" that a thread must get before it can access a synchronized block of code, and only one thread can have the "key" at any one time. This means that only one thread at a time is working the block of code. The monitor lock rule insures that ever lock and unlock is done in order. The volatile variable rule says that a volatile variable is like a monitor locked variable. The two thread rules insures that the thread doesn't start executing before the call to Thread.start() has finished, and before it is terminated every thread sees the result of its instructions. Similar to the thread start rule, the interruption rule says that a thread must complete calling an interrupt before the interrupt is started in the other thread. Also similar, the finalizer rule means that the constructor is completed before the finalizer starts. Lastly, transitivity means that if A->B and B->C, then A->C.

These rules are the main framework for the Java programming model.

=Secondary Aspects=

Beyond the main principles of the Java Memory Model there are many details.

==Double-checked Locking==

One of the controversial issues that came up with parallel computing and the JMM was double-checked locking. People wanted to avoid time consuming synchronization so they implemented double-checked locking. Here is an example of double-checked locking from [http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html Jeremy Manson and Brien Goetz (2004)]

// From Manson and Goetz (2004)
// double-checked-locking - don't do this!

private static Something instance = null;

public Something getInstance() {
if (instance == null) {
synchronized (this) {
if (instance == null)
instance = new Something();
}
}
return instance;
}

The problem with this code is that the reads may be reordered by the compiler (they are not happens-after statements). This means the code produces indeterminate results which could lead you to attempt to read from a null pointer while thinking that it had been initialized to new Something(). This can be avoided in the new version of the JMM by declaring the instance volatile due to the volatile rule.

=Summary=