CSC/ECE 506 Spring 2012/ch9a cm - Revision history

Mkotyad: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-14T23:37:23Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 23:37, 14 April 2012
Line 181:		Line 181:

	Without Biased Locking:		Without Biased Locking:



	[[File:biasedlocking1.jpg]]		[[File:biasedlocking1.jpg]]

	With Biased Locking:		With Biased Locking:




	[[File:biasedlocking.jpg]]		[[File:biasedlocking.jpg]]

Mkotyad: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-14T23:36:03Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 23:36, 14 April 2012
Line 179:		Line 179:

	QRL locks are optimized for a single-process repeated-acquisition data access pattern; however, rebiasable QRLs<ref name=BiasedLocks></ref> that can be used with migratory data access patterns, also provide major performance enhancements.		QRL locks are optimized for a single-process repeated-acquisition data access pattern; however, rebiasable QRLs<ref name=BiasedLocks></ref> that can be used with migratory data access patterns, also provide major performance enhancements.

			Without Biased Locking:
			[[File:biasedlocking1.jpg]]

			With Biased Locking:
			[[File:biasedlocking.jpg]]

	== Conclusion ==		== Conclusion ==

Capsang: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-06T08:03:28Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 08:03, 6 April 2012
Line 178:		Line 178:
	Because they can be generalized to use any mutual exclusion algorithm with a standard interface, as well as many algorithms that do not use a standard interface, QRL locks can obtain the benefits of any properties of such locks for the uncontended case at the expense of a mere handful of non-atomic instructions in their critical path.		Because they can be generalized to use any mutual exclusion algorithm with a standard interface, as well as many algorithms that do not use a standard interface, QRL locks can obtain the benefits of any properties of such locks for the uncontended case at the expense of a mere handful of non-atomic instructions in their critical path.

	QRL locks are optimized for a single-process repeated-acquisition data access pattern; however, rebiasable QRLs<ref name=~~BiasLock~~></ref> that can be used with migratory data access patterns, also provide major performance enhancements.		QRL locks are optimized for a single-process repeated-acquisition data access pattern; however, rebiasable QRLs<ref name=BiasedLocks></ref> that can be used with migratory data access patterns, also provide major performance enhancements.

	== Conclusion ==		== Conclusion ==

Capsang: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-06T08:02:44Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 08:02, 6 April 2012
Line 175:		Line 175:

	Now, because the data read in step 2 includes the data that was written in step 1, the read must be ordered after the write. This approach provides portability to any memory model in which apparent program order is guaranteed for instructions executed on the same processor.		Now, because the data read in step 2 includes the data that was written in step 1, the read must be ordered after the write. This approach provides portability to any memory model in which apparent program order is guaranteed for instructions executed on the same processor.

			Because they can be generalized to use any mutual exclusion algorithm with a standard interface, as well as many algorithms that do not use a standard interface, QRL locks can obtain the benefits of any properties of such locks for the uncontended case at the expense of a mere handful of non-atomic instructions in their critical path.

			QRL locks are optimized for a single-process repeated-acquisition data access pattern; however, rebiasable QRLs<ref name=BiasLock></ref> that can be used with migratory data access patterns, also provide major performance enhancements.

	== Conclusion ==		== Conclusion ==

Capsang: /* Java Synchronizationhttp://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf */

2012-04-06T07:51:54Z

Java Synchronizationhttp://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf

← Older revision		Revision as of 07:51, 6 April 2012
Line 3:		Line 3:

	== Java Synchronization<ref name=kawachiya>http://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf</ref> ==		== Java Synchronization<ref name=kawachiya>http://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf</ref> ==
	Java is an explicitly multi-threaded language, hence each of the classes ~~are~~ designed with synchronization ~~in mind~~. Java provides a mutual exclusion mechanism based on the concept of [http://en.wikipedia.org/wiki/Monitor_%28synchronization%29 Monitors]. At most only one thread can enter an object’s monitor simultaneously. When another thread is in the monitor, a thread trying to enter is forced to wait by the JVM until the first thread exits from the monitor~~. In Java, a thread is permitted to enter a monitor recursively. In this case, a waiting thread can enter the monitor only when it has been exited the same number of times as it was entered~~.		Java is an explicitly multi-threaded language, hence each of the classes that it provides has been designed with implicit synchronization. Java provides a mutual exclusion mechanism based on the concept of [http://en.wikipedia.org/wiki/Monitor_%28synchronization%29 Monitors]. At most only one thread can enter an object’s monitor simultaneously. When another thread is in the monitor, a thread trying to enter is forced to wait by the JVM until the first thread exits from the monitor.

	In Java, the monitor operations are specified by declaring a method or a block as ''synchronized'' (refer to the code below). If the specified method is an instance method, its receiver object, ''this'', is used as the owner of the lock. To realize this Monitor behavior, the JVM uses a lock mechanism, "Java lock", associated with each object. The lock is acquired by a thread when it enters the object’s monitor, held while the thread is in the monitor and executing the synchronized method, and released when the thread exits from the monitor. If a thread attempts to acquire a lock held by another thread, the second thread is blocked until the first thread releases the lock.		In Java, the monitor operations are specified by declaring a method or a block as ''synchronized'' (refer to the code below). If the specified method is an instance method, its receiver object, ''this'', is used as the owner of the lock. To realize this Monitor behavior, the JVM uses a lock mechanism, "Java lock", associated with each object. The lock is acquired by a thread when it enters the object’s monitor, held while the thread is in the monitor and executing the synchronized method, and released when the thread exits from the monitor. If a thread attempts to acquire a lock held by another thread, the second thread is blocked until the first thread releases the lock.
Line 17:		Line 17:
	</pre>		</pre>

	A very simple implementation of ~~Monitors~~ could be to embed the OS provided monitor object in each of the Objects that is created. Access to each object is synchronized using this Monitor object. Following code illustrates this idea:		A very simple but naive implementation of this could be to embed the OS provided monitor object in each of the Objects that is created. Access to each object is synchronized using this Monitor object. Following code illustrates this idea:

	<pre>		<pre>

Capsang: /* Introduction */

2012-04-06T07:49:07Z

Introduction

← Older revision		Revision as of 07:49, 6 April 2012
Line 1:		Line 1:
	== Introduction ==		== Introduction ==
	Various schemes have been explored in the past to provide synchronization in a multiprocessor system. These solutions have been known to be associated with either software or hardware overhead or both. Software overhead is because of system calls and other book keeping the Operating system has to do. Hardware overhead is due to the bus transactions and the [http://en.wikipedia.org/wiki/Cache_coherence ~~cache~~ coherence protocols]. This article discusses the overheads associated with traditional locking mechanisms, taking Java Virtual Machine as an example. It also discusses some novel approaches to counter these overheads and provide efficient synchronization mechanisms.		Various schemes have been explored in the past to provide synchronization in a multiprocessor system. These solutions have been known to be associated with either software overhead or hardware overhead or both. Software overhead is because of system calls and other book keeping the Operating system has to perform. Hardware overhead is due to the bus transactions and the [http://en.wikipedia.org/wiki/Cache_coherence Cache coherence protocols]. This article discusses the overheads associated with traditional locking mechanisms, taking Java Virtual Machine<ref name=JVM>http://en.wikipedia.org/wiki/Java_virtual_machine</ref> as an example. It also discusses some novel approaches to counter these overheads and provide efficient synchronization mechanisms.

	== Java Synchronization<ref name=kawachiya>http://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf</ref> ==		== Java Synchronization<ref name=kawachiya>http://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf</ref> ==

Capsang: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-06T07:45:57Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 07:45, 6 April 2012
Line 167:		Line 167:

	In a system that assures [http://en.wikipedia.org/wiki/Sequential_consistency Sequential consistency], it is easy to design a technique in which a bias holder reacquires the lock by first writing its quicklock bit and then verifying that the lock has not been revoked; and revoking processes first indicate revocation and then check whether the bias holder has acquired		In a system that assures [http://en.wikipedia.org/wiki/Sequential_consistency Sequential consistency], it is easy to design a technique in which a bias holder reacquires the lock by first writing its quicklock bit and then verifying that the lock has not been revoked; and revoking processes first indicate revocation and then check whether the bias holder has acquired
	the Quicklock. However, for weaker consistency models, we may be required to use barriers/fences to ensure correctness. But, in this case, it is sufficient to preclude a single read (of the lock status) from being reordered before a single write (of the Quicklock). Hence, if we can introduce an artificial dependency between the write and read instructions mentioned above, we can ensure that they are not adversely reordered.		the Quicklock. However, for [http://en.wikipedia.org/wiki/Weak_consistency weaker consistency models], we may be required to use barriers/fences to ensure correctness. But, in this case, it is sufficient to preclude a single read (of the lock status) from being reordered before a single write (of the Quicklock). Hence, if we can introduce an artificial dependency between the write and read instructions mentioned above, we can ensure that they are not adversely reordered.

	One way of introducing this dependency is to '''collocate''' the status field and the quicklock field into the two halves of a 32-bit word. Then, perform the following steps in order to reacquire the lock on the ultra fast path:		One way of introducing this dependency is to '''collocate''' the status field and the quicklock field into the two halves of a 32-bit word. Then, perform the following steps in order to reacquire the lock on the ultra fast path:

Capsang: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-06T07:44:33Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 07:44, 6 April 2012
Line 166:		Line 166:
	Switching a lock from NEUTRAL to being biased to a particular process can be done for the one-time cost of a single CAS operation. The main difficulty in constructing an atomic-free QRL lies in coordinating the revocation of a lock between a revoking process and the bias holder process. Race conditions that must typically be addressed include a revocation that occurs simultaneous to a biased acquire as well as a revocation that occurs simultaneous to a biased release.		Switching a lock from NEUTRAL to being biased to a particular process can be done for the one-time cost of a single CAS operation. The main difficulty in constructing an atomic-free QRL lies in coordinating the revocation of a lock between a revoking process and the bias holder process. Race conditions that must typically be addressed include a revocation that occurs simultaneous to a biased acquire as well as a revocation that occurs simultaneous to a biased release.

	In a system that assures Sequential consistency, it is easy to design a technique in which a bias holder reacquires the lock by first writing its quicklock bit and then verifying that the lock has not been revoked; and revoking processes first indicate revocation and then check whether the bias holder has acquired		In a system that assures [http://en.wikipedia.org/wiki/Sequential_consistency Sequential consistency], it is easy to design a technique in which a bias holder reacquires the lock by first writing its quicklock bit and then verifying that the lock has not been revoked; and revoking processes first indicate revocation and then check whether the bias holder has acquired
	the Quicklock. However, for weaker consistency models, we may be required to use barriers/fences to ensure correctness. But, in this case, it is sufficient to preclude a single read (of the lock status) from being reordered before a single write (of the Quicklock). Hence, if we can introduce an artificial dependency between the write and read instructions mentioned above, we can ensure that they are not adversely reordered.		the Quicklock. However, for weaker consistency models, we may be required to use barriers/fences to ensure correctness. But, in this case, it is sufficient to preclude a single read (of the lock status) from being reordered before a single write (of the Quicklock). Hence, if we can introduce an artificial dependency between the write and read instructions mentioned above, we can ensure that they are not adversely reordered.

	One way of introducing this dependency ~~(link)~~ is to '''collocate''' the status field and the quicklock field into the two halves of a 32-bit word. Then, perform the following steps in order to reacquire the lock on the ultra fast path:		One way of introducing this dependency is to '''collocate''' the status field and the quicklock field into the two halves of a 32-bit word. Then, perform the following steps in order to reacquire the lock on the ultra fast path:
	* perform a half-word store on the quicklock field		* perform a half-word store on the quicklock field
	* load the entire 32 bit word		* load the entire 32 bit word

Capsang: /* Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf */

2012-04-06T07:43:00Z

Biased locks http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf

← Older revision		Revision as of 07:43, 6 April 2012
Line 151:		Line 151:
	=== Biased locks <ref name=BiasedLocks> http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf</ref> ===		=== Biased locks <ref name=BiasedLocks> http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLocking.pdf</ref> ===
	By using the thin lock, the cost of lock acquisition has been reduced to one compare and swap operation. However, such an atomic operation is usually very costly compared to simple memory access operations. If we can acquire a lock without any atomic operations for common cases, the cost of locks is further reduced.		By using the thin lock, the cost of lock acquisition has been reduced to one compare and swap operation. However, such an atomic operation is usually very costly compared to simple memory access operations. If we can acquire a lock without any atomic operations for common cases, the cost of locks is further reduced.
	In addition, the thin lock implementation uses a busy-wait loop for inflating an object’s lock. It should also be checked that this will not cause performance degradation. When we explore the area of non-contended lock ~~aquisition~~, we arrive at an alternative that exploits these characteristics - Biased locks.		In addition, the thin lock implementation uses a busy-wait loop for inflating an object’s lock. It should also be checked that this will not cause performance degradation. When we explore the area of non-contended lock acquisition, we arrive at an alternative that exploits these characteristics - Biased locks.

	Java Virtual Machines is the case wherein a single process repeatedly acquires and releases a lock, but other processes rarely if ever access this lock (First characteristic above). The locks that can be optimized for this case may be referred to as Quickly Re-acquirable Locks (QRLs). We shall also refer to the optimized code path in which a process reacquires and subsequently releases a lock that it has previously held, and that no other process has ever held, as an ''ultra fast path''. The idea is to try to reduce the use of atomic instructions (e.g CAS,Barriers,etc) in the ultra fast path, because these instructions are typically much more expensive than other instructions.		Java Virtual Machines is the case wherein a single process repeatedly acquires and releases a lock, but other processes rarely if ever access this lock (First characteristic above). The locks that can be optimized for this case may be referred to as Quickly Re-acquirable Locks (QRLs)<ref name=BiasedLocks></ref>. We shall also refer to the optimized code path in which a process reacquires and subsequently releases a lock that it has previously held, and that no other process has ever held, as an ''ultra fast path''. The idea is to try to reduce the use of atomic instructions (e.g CAS,Barriers,etc) in the ultra fast path, because these instructions are typically much more expensive than other instructions.
	For QRLs, our target is to avoid all such instructions in both the acquire and release portions of the ultra fast code path.		For QRLs, our target is to avoid all such instructions in both the acquire and release portions of the ultra fast code path.

Capsang: /* Java Synchronizationhttp://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf */

2012-04-06T07:41:36Z

Java Synchronizationhttp://www.research.ibm.com/trl/people/kawatiya/Kawachiya05phd.pdf

← Older revision		Revision as of 07:41, 6 April 2012
Line 41:		Line 41:
	When these classes are used in single threaded programs, there's a huge performance overhead, even in the absence of true concurrency. Also, it incurs space overhead due to the presence of monitor code in each of the objects, even if it may not need any synchronization. Currently in JDK design the concurrency primitives are kept outside of the objects to avoid space cost and looked up through a ''Monitor Cache''<ref name=kawachiya> </ref>. Unfortunately this does not scale well since monitor cache itself needs to be locked when making the look-ups.		When these classes are used in single threaded programs, there's a huge performance overhead, even in the absence of true concurrency. Also, it incurs space overhead due to the presence of monitor code in each of the objects, even if it may not need any synchronization. Currently in JDK design the concurrency primitives are kept outside of the objects to avoid space cost and looked up through a ''Monitor Cache''<ref name=kawachiya> </ref>. Unfortunately this does not scale well since monitor cache itself needs to be locked when making the look-ups.

	Additionally, monitors make use of [http://en.wikipedia.org/wiki/Linearizability atomic operations] to provide mutual exclusion. On typical SMP systems, reads are very efficient, since all the requesting processors can have the cache line replicated in their caches.But if even one processor is writing to a shared cache line, those writes will generate considerable cache coherence traffic. Assuming a write-invalidate cache coherence policy, the readers will continually re-load the cache line just to have it subsequently invalidated by the writer. Coherency bandwidth is a limited and global resource, so in addition to local latency, excessive sharing traffic will impact overall scalability and impede the progress of threads running on other processors. A so-called coherency miss, assuming [http://en.wikipedia.org/wiki/MESI_protocol MESI protocol] -- for example a load on processor P1 where processor P2 has the cache line in M-state -- is typically much slower than a normal miss. So if you have threads on processors P1 and P2 iterating trying to acquire the same lock, then lock acquisition itself will generate coherency traffic and result in the cache "sloshing" of the line(s) holding the metadata.		Additionally, monitors make use of [http://en.wikipedia.org/wiki/Linearizability atomic operations] to provide mutual exclusion. On typical SMP systems, reads are very efficient, since all the requesting processors can have the cache line replicated in their caches.But if even one processor is writing to a shared cache line, those writes will generate considerable cache coherence traffic. Assuming a write-invalidate cache coherence policy, the readers will continually re-load the cache line just to have it subsequently invalidated by the writer. Coherency bandwidth is a limited and global resource, so in addition to local latency, excessive sharing traffic will impact overall scalability and impede the progress of threads running on other processors. A so-called coherency miss, assuming [http://en.wikipedia.org/wiki/MESI_protocol MESI protocol] -- for example a load on processor P1 where processor P2 has the cache line in M-state -- is typically much slower than a normal miss. So if you have threads on processors P1 and P2 iterating trying to acquire the same lock, then lock acquisition itself will generate coherency traffic and result in the cache "sloshing" of the line(s) holding the metadata <ref name=BiasedLockBlog> https://blogs.oracle.com/dave/entry/biased_locking_in_hotspot </ref>.

	== Solutions for Reducing the Overhead ==		== Solutions for Reducing the Overhead ==