CSC/ECE 506 Spring 2012/9a mm - Revision history

Pmfernan: /* Biased Locks */

2012-04-11T19:35:23Z

Biased Locks

Pmfernan: /* Thin Locks */

2012-04-11T19:27:55Z

Thin Locks

← Older revision		Revision as of 19:27, 11 April 2012
Line 46:		Line 46:
	Monitors are multi-word structures and include space for a thread pointer, a nested lock count and queues. Thin locks work by incorporating a special synchronization word into each object header and they require the availability of instructions that can be used to build atomic primitives such as a compare-and-swap or store-conditional. In the [http://en.wikipedia.org/wiki/Java_virtual_machine JVM] system that was used to develop thin locks each object was made of a three word header followed by data. The original implementation reserved 24 bits of the three word header for the synchronization word but was able to maintain the three word size of the header through compression techniques. The structure of the 24-bit lock field is key to facilitating the facile locking ability of the thin lock in common locking situations. The lock field represents either a thin lock or a reference to a ''fat lock'', or native heavyweight lock. The first bit, referred to as the ''monitor shape bit'' is 0 if the lock field refers to a thin lock and 1 if it is a reference to a fat lock. If the monitor shape bit is 1 the remaining 23 bits are an index of a fat lock. If the monitor shape bit is 0 the next 15 bits constitute a thread identifier and the last 8 bits serve as a measure of nesting depth- the number of times an already locked object is locked. When the thread identifier is 0 the object is unlocked, but if it is non-zero it is an index into a table which maps thread indices to thread pointers.		Monitors are multi-word structures and include space for a thread pointer, a nested lock count and queues. Thin locks work by incorporating a special synchronization word into each object header and they require the availability of instructions that can be used to build atomic primitives such as a compare-and-swap or store-conditional. In the [http://en.wikipedia.org/wiki/Java_virtual_machine JVM] system that was used to develop thin locks each object was made of a three word header followed by data. The original implementation reserved 24 bits of the three word header for the synchronization word but was able to maintain the three word size of the header through compression techniques. The structure of the 24-bit lock field is key to facilitating the facile locking ability of the thin lock in common locking situations. The lock field represents either a thin lock or a reference to a ''fat lock'', or native heavyweight lock. The first bit, referred to as the ''monitor shape bit'' is 0 if the lock field refers to a thin lock and 1 if it is a reference to a fat lock. If the monitor shape bit is 1 the remaining 23 bits are an index of a fat lock. If the monitor shape bit is 0 the next 15 bits constitute a thread identifier and the last 8 bits serve as a measure of nesting depth- the number of times an already locked object is locked. When the thread identifier is 0 the object is unlocked, but if it is non-zero it is an index into a table which maps thread indices to thread pointers.

	Situations that are applicable to thin lock usage include objects that do not have the cooperation commands of ''wait, notify, or notifyAll'' performed on them, are not subject to contention and are not locked to a nesting depth of greater than 257. These restrictions sound significant but in most applications the majority of objects meet these criteria. When an object transitions from thin state to fat it remains there for its duration. Key to the performance of a thin lock is the design element that while an object is owned by a particular thread it is never modified by another thread. This means that [[File:Locking_word.jpg\|300px\|thumb\|left\|Locking a thin lock. Taken from [[#References\|[1] ]]]once an object is locked all subsequent operations can be performed with loads and stores as opposed to using atomic primitives.		Situations that are applicable to thin lock usage include objects that do not have the cooperation commands of ''wait, notify, or notifyAll'' performed on them, are not subject to contention and are not locked to a nesting depth of greater than 257. These restrictions sound significant but in most applications the majority of objects meet these criteria. When an object transitions from thin state to fat it remains there for its duration. Key to the performance of a thin lock is the design element that while an object is owned by a particular thread it is never modified by another thread. This means that [[File:Locking_word.jpg\|300px\|thumb\|left\|Locking a thin lock. Taken from [[#References\|[1] ]]]]once an object is locked all subsequent operations can be performed with loads and stores as opposed to using atomic primitives.

	Assume initially that an object is unlocked and the entire lock field is 0 (figure left ''(a)''). If a thread A wants to lock the object, it first performs a compare-and-swap operation on the word containing the lock field. The old value given to the compare-and-swap is shown in the figure as the upper state, built by masking the high 24 bits. The new value corresponds to ''(b)'' in the figure and contains 0 for the monitor bit shape, a thread index which corresponds to thread A and a count of zero. The new value is generated by a bitwise '''or''' operation of the old value and the index and then shifting 16 bits left. The thread index can be accessed in a single load instruction from a separate data structure. If thread A owns the lock and attempts to lock again (nested locking) it first begins a CAS operation, which fails because the object is already locked. The routine then will check the monitor bit shape, thread index and count. If the bit shape is 0, the thread index matches that of thread A and if the count is under 255 then count is incremented with a simple store. This situation corresponds to ''(c)'' of the left figure.		Assume initially that an object is unlocked and the entire lock field is 0 (figure left ''(a)''). If a thread A wants to lock the object, it first performs a compare-and-swap operation on the word containing the lock field. The old value given to the compare-and-swap is shown in the figure as the upper state, built by masking the high 24 bits. The new value corresponds to ''(b)'' in the figure and contains 0 for the monitor bit shape, a thread index which corresponds to thread A and a count of zero. The new value is generated by a bitwise '''or''' operation of the old value and the index and then shifting 16 bits left. The thread index can be accessed in a single load instruction from a separate data structure. If thread A owns the lock and attempts to lock again (nested locking) it first begins a CAS operation, which fails because the object is already locked. The routine then will check the monitor bit shape, thread index and count. If the bit shape is 0, the thread index matches that of thread A and if the count is under 255 then count is incremented with a simple store. This situation corresponds to ''(c)'' of the left figure.

Pmfernan: /* Thin Locks */

2012-04-11T19:27:19Z

Thin Locks

← Older revision		Revision as of 19:27, 11 April 2012
Line 46:		Line 46:
	Monitors are multi-word structures and include space for a thread pointer, a nested lock count and queues. Thin locks work by incorporating a special synchronization word into each object header and they require the availability of instructions that can be used to build atomic primitives such as a compare-and-swap or store-conditional. In the [http://en.wikipedia.org/wiki/Java_virtual_machine JVM] system that was used to develop thin locks each object was made of a three word header followed by data. The original implementation reserved 24 bits of the three word header for the synchronization word but was able to maintain the three word size of the header through compression techniques. The structure of the 24-bit lock field is key to facilitating the facile locking ability of the thin lock in common locking situations. The lock field represents either a thin lock or a reference to a ''fat lock'', or native heavyweight lock. The first bit, referred to as the ''monitor shape bit'' is 0 if the lock field refers to a thin lock and 1 if it is a reference to a fat lock. If the monitor shape bit is 1 the remaining 23 bits are an index of a fat lock. If the monitor shape bit is 0 the next 15 bits constitute a thread identifier and the last 8 bits serve as a measure of nesting depth- the number of times an already locked object is locked. When the thread identifier is 0 the object is unlocked, but if it is non-zero it is an index into a table which maps thread indices to thread pointers.		Monitors are multi-word structures and include space for a thread pointer, a nested lock count and queues. Thin locks work by incorporating a special synchronization word into each object header and they require the availability of instructions that can be used to build atomic primitives such as a compare-and-swap or store-conditional. In the [http://en.wikipedia.org/wiki/Java_virtual_machine JVM] system that was used to develop thin locks each object was made of a three word header followed by data. The original implementation reserved 24 bits of the three word header for the synchronization word but was able to maintain the three word size of the header through compression techniques. The structure of the 24-bit lock field is key to facilitating the facile locking ability of the thin lock in common locking situations. The lock field represents either a thin lock or a reference to a ''fat lock'', or native heavyweight lock. The first bit, referred to as the ''monitor shape bit'' is 0 if the lock field refers to a thin lock and 1 if it is a reference to a fat lock. If the monitor shape bit is 1 the remaining 23 bits are an index of a fat lock. If the monitor shape bit is 0 the next 15 bits constitute a thread identifier and the last 8 bits serve as a measure of nesting depth- the number of times an already locked object is locked. When the thread identifier is 0 the object is unlocked, but if it is non-zero it is an index into a table which maps thread indices to thread pointers.

	Situations that are applicable to thin lock usage include objects that do not have the cooperation commands of ''wait, notify, or notifyAll'' performed on them, are not subject to contention and are not locked to a nesting depth of greater than 257. These restrictions sound significant but in most applications the majority of objects meet these criteria. When an object transitions from thin state to fat it remains there for its duration. Key to the performance of a thin lock is the design element that while an object is owned by a particular thread it is never modified by another thread. This means that [[File:Locking_word.jpg\|300px\|thumb\|left\|Locking a thin lock. Taken from [1]]]once an object is locked all subsequent operations can be performed with loads and stores as opposed to using atomic primitives.		Situations that are applicable to thin lock usage include objects that do not have the cooperation commands of ''wait, notify, or notifyAll'' performed on them, are not subject to contention and are not locked to a nesting depth of greater than 257. These restrictions sound significant but in most applications the majority of objects meet these criteria. When an object transitions from thin state to fat it remains there for its duration. Key to the performance of a thin lock is the design element that while an object is owned by a particular thread it is never modified by another thread. This means that [[File:Locking_word.jpg\|300px\|thumb\|left\|Locking a thin lock. Taken from [[#References\|[1] ]]]once an object is locked all subsequent operations can be performed with loads and stores as opposed to using atomic primitives.

	Assume initially that an object is unlocked and the entire lock field is 0 (figure left ''(a)''). If a thread A wants to lock the object, it first performs a compare-and-swap operation on the word containing the lock field. The old value given to the compare-and-swap is shown in the figure as the upper state, built by masking the high 24 bits. The new value corresponds to ''(b)'' in the figure and contains 0 for the monitor bit shape, a thread index which corresponds to thread A and a count of zero. The new value is generated by a bitwise '''or''' operation of the old value and the index and then shifting 16 bits left. The thread index can be accessed in a single load instruction from a separate data structure. If thread A owns the lock and attempts to lock again (nested locking) it first begins a CAS operation, which fails because the object is already locked. The routine then will check the monitor bit shape, thread index and count. If the bit shape is 0, the thread index matches that of thread A and if the count is under 255 then count is incremented with a simple store. This situation corresponds to ''(c)'' of the left figure.		Assume initially that an object is unlocked and the entire lock field is 0 (figure left ''(a)''). If a thread A wants to lock the object, it first performs a compare-and-swap operation on the word containing the lock field. The old value given to the compare-and-swap is shown in the figure as the upper state, built by masking the high 24 bits. The new value corresponds to ''(b)'' in the figure and contains 0 for the monitor bit shape, a thread index which corresponds to thread A and a count of zero. The new value is generated by a bitwise '''or''' operation of the old value and the index and then shifting 16 bits left. The thread index can be accessed in a single load instruction from a separate data structure. If thread A owns the lock and attempts to lock again (nested locking) it first begins a CAS operation, which fails because the object is already locked. The routine then will check the monitor bit shape, thread index and count. If the bit shape is 0, the thread index matches that of thread A and if the count is under 255 then count is incremented with a simple store. This situation corresponds to ''(c)'' of the left figure.

Pmfernan: /* Monitors in Java */

2012-04-11T19:26:32Z

Monitors in Java

← Older revision		Revision as of 19:26, 11 April 2012
Line 25:		Line 25:

	==Monitors in Java==		==Monitors in Java==
	Monitors in Java are conceptual spaces that can be occupied by only one thread at a time. Entering the monitor space is termed ''entering the monitor''. The monitor space has a conceptual inner region which when entering is called ''acquiring the monitor''. Occupying this inner region is called ''owning the monitor'' while leaving it is called ''releasing the monitor'' and exiting the monitor space all together is called ''exiting the monitor''. No more than one thread can own the monitor at any given time. This region of the monitor typically contains data and code that potentially support two types of synchronization available with Java, mutual exclusion and cooperation. Monitors can contain many code regions, related or not, which each when executed must do so with a [[File:Java_monitor.gif\|500px\|thumb\|rignt\|Java Monitor. Taken from [[#References\|[15]]]]]]guarantee of atomicity with respect to other executing threads. Each code region has its own ''entry set''. This means that each monitor has multiple points of entry, each of which is associated with a particular region of code that for correctness must be synchronized. When a thread, in its course of execution, comes upon a region controlled by the monitor it is placed in the entry set of that region. If the monitor is not occupied, the thread acquires and then occupies the monitor and continues with its execution of that region. If the monitor is occupied then the thread is forced to wait (along with other waiting threads) for the occupying thread to release the monitor. All waiting threads then compete for the opportunity to acquire the monitor.		Monitors in Java are conceptual spaces that can be occupied by only one thread at a time. Entering the monitor space is termed ''entering the monitor''. The monitor space has a conceptual inner region which when entering is called ''acquiring the monitor''. Occupying this inner region is called ''owning the monitor'' while leaving it is called ''releasing the monitor'' and exiting the monitor space all together is called ''exiting the monitor''. No more than one thread can own the monitor at any given time. This region of the monitor typically contains data and code that potentially support two types of synchronization available with Java, mutual exclusion and cooperation. Monitors can contain many code regions, related or not, which each when executed must do so with a [[File:Java_monitor.gif\|500px\|thumb\|rignt\|Java Monitor. Taken from [[#References\|[15] ]]]]guarantee of atomicity with respect to other executing threads. Each code region has its own ''entry set''. This means that each monitor has multiple points of entry, each of which is associated with a particular region of code that for correctness must be synchronized. When a thread, in its course of execution, comes upon a region controlled by the monitor it is placed in the entry set of that region. If the monitor is not occupied, the thread acquires and then occupies the monitor and continues with its execution of that region. If the monitor is occupied then the thread is forced to wait (along with other waiting threads) for the occupying thread to release the monitor. All waiting threads then compete for the opportunity to acquire the monitor.

	Mutual exclusion is guaranteed by the monitor because no more than one thread is allowed in any region of a particular monitor. Cooperation between threads can be orchestrated with a "Wait and Notify" (or "Signal and Continue") monitor. In this type of monitor a thread, while occupying the monitor, can execute a ''wait command''. Executing a wait causes a thread to release the monitor and enter a ''wait set''. The thread, now in the wait set, will stay in a suspended state until after it receives a ''notify command'' '''and''' it is able to occupy the monitor according to protocols already described. A thread which executes a ''notify command'' (the ''Signal'') continues to occupy the monitor in its normal course of execution until it releases the monitor or suspends as well via a wait command.		Mutual exclusion is guaranteed by the monitor because no more than one thread is allowed in any region of a particular monitor. Cooperation between threads can be orchestrated with a "Wait and Notify" (or "Signal and Continue") monitor. In this type of monitor a thread, while occupying the monitor, can execute a ''wait command''. Executing a wait causes a thread to release the monitor and enter a ''wait set''. The thread, now in the wait set, will stay in a suspended state until after it receives a ''notify command'' '''and''' it is able to occupy the monitor according to protocols already described. A thread which executes a ''notify command'' (the ''Signal'') continues to occupy the monitor in its normal course of execution until it releases the monitor or suspends as well via a wait command.

Pmfernan: /* Monitors in Java */

2012-04-11T19:24:24Z

Monitors in Java

← Older revision		Revision as of 19:24, 11 April 2012
Line 25:		Line 25:

	==Monitors in Java==		==Monitors in Java==
	Monitors in Java are conceptual spaces that can be occupied by only one thread at a time. Entering the monitor space is termed ''entering the monitor''. The monitor space has a conceptual inner region which when entering is called ''acquiring the monitor''. Occupying this inner region is called ''owning the monitor'' while leaving it is called ''releasing the monitor'' and exiting the monitor space all together is called ''exiting the monitor''. No more than one thread can own the monitor at any given time. This region of the monitor typically contains data and code that potentially support two types of synchronization available with Java, mutual exclusion and cooperation. Monitors can contain many code regions, related or not, which each when executed must do so with a [[File:Java_monitor.gif\|500px\|thumb\|rignt\|Java Monitor. Taken from [[#References\|[15]]]]]guarantee of atomicity with respect to other executing threads. Each code region has its own ''entry set''. This means that each monitor has multiple points of entry, each of which is associated with a particular region of code that for correctness must be synchronized. When a thread, in its course of execution, comes upon a region controlled by the monitor it is placed in the entry set of that region. If the monitor is not occupied, the thread acquires and then occupies the monitor and continues with its execution of that region. If the monitor is occupied then the thread is forced to wait (along with other waiting threads) for the occupying thread to release the monitor. All waiting threads then compete for the opportunity to acquire the monitor.		Monitors in Java are conceptual spaces that can be occupied by only one thread at a time. Entering the monitor space is termed ''entering the monitor''. The monitor space has a conceptual inner region which when entering is called ''acquiring the monitor''. Occupying this inner region is called ''owning the monitor'' while leaving it is called ''releasing the monitor'' and exiting the monitor space all together is called ''exiting the monitor''. No more than one thread can own the monitor at any given time. This region of the monitor typically contains data and code that potentially support two types of synchronization available with Java, mutual exclusion and cooperation. Monitors can contain many code regions, related or not, which each when executed must do so with a [[File:Java_monitor.gif\|500px\|thumb\|rignt\|Java Monitor. Taken from [[#References\|[15]]]]]]guarantee of atomicity with respect to other executing threads. Each code region has its own ''entry set''. This means that each monitor has multiple points of entry, each of which is associated with a particular region of code that for correctness must be synchronized. When a thread, in its course of execution, comes upon a region controlled by the monitor it is placed in the entry set of that region. If the monitor is not occupied, the thread acquires and then occupies the monitor and continues with its execution of that region. If the monitor is occupied then the thread is forced to wait (along with other waiting threads) for the occupying thread to release the monitor. All waiting threads then compete for the opportunity to acquire the monitor.

	Mutual exclusion is guaranteed by the monitor because no more than one thread is allowed in any region of a particular monitor. Cooperation between threads can be orchestrated with a "Wait and Notify" (or "Signal and Continue") monitor. In this type of monitor a thread, while occupying the monitor, can execute a ''wait command''. Executing a wait causes a thread to release the monitor and enter a ''wait set''. The thread, now in the wait set, will stay in a suspended state until after it receives a ''notify command'' '''and''' it is able to occupy the monitor according to protocols already described. A thread which executes a ''notify command'' (the ''Signal'') continues to occupy the monitor in its normal course of execution until it releases the monitor or suspends as well via a wait command.		Mutual exclusion is guaranteed by the monitor because no more than one thread is allowed in any region of a particular monitor. Cooperation between threads can be orchestrated with a "Wait and Notify" (or "Signal and Continue") monitor. In this type of monitor a thread, while occupying the monitor, can execute a ''wait command''. Executing a wait causes a thread to release the monitor and enter a ''wait set''. The thread, now in the wait set, will stay in a suspended state until after it receives a ''notify command'' '''and''' it is able to occupy the monitor according to protocols already described. A thread which executes a ''notify command'' (the ''Signal'') continues to occupy the monitor in its normal course of execution until it releases the monitor or suspends as well via a wait command.

Pmfernan: /* Monitors in Java */

2012-04-11T19:23:12Z

Monitors in Java

← Older revision		Revision as of 19:23, 11 April 2012
Line 25:		Line 25:

	==Monitors in Java==		==Monitors in Java==
	Monitors in Java are conceptual spaces that can be occupied by only one thread at a time. Entering the monitor space is termed ''entering the monitor''. The monitor space has a conceptual inner region which when entering is called ''acquiring the monitor''. Occupying this inner region is called ''owning the monitor'' while leaving it is called ''releasing the monitor'' and exiting the monitor space all together is called ''exiting the monitor''. No more than one thread can own the monitor at any given time. This region of the monitor typically contains data and code that potentially support two types of synchronization available with Java, mutual exclusion and cooperation. Monitors can contain many code regions, related or not, which each when executed must do so with a [[File:Java_monitor.gif\|500px\|thumb\|rignt\|Java Monitor. Taken from [15}]]guarantee of atomicity with respect to other executing threads. Each code region has its own ''entry set''. This means that each monitor has multiple points of entry, each of which is associated with a particular region of code that for correctness must be synchronized. When a thread, in its course of execution, comes upon a region controlled by the monitor it is placed in the entry set of that region. If the monitor is not occupied, the thread acquires and then occupies the monitor and continues with its execution of that region. If the monitor is occupied then the thread is forced to wait (along with other waiting threads) for the occupying thread to release the monitor. All waiting threads then compete for the opportunity to acquire the monitor.		Monitors in Java are conceptual spaces that can be occupied by only one thread at a time. Entering the monitor space is termed ''entering the monitor''. The monitor space has a conceptual inner region which when entering is called ''acquiring the monitor''. Occupying this inner region is called ''owning the monitor'' while leaving it is called ''releasing the monitor'' and exiting the monitor space all together is called ''exiting the monitor''. No more than one thread can own the monitor at any given time. This region of the monitor typically contains data and code that potentially support two types of synchronization available with Java, mutual exclusion and cooperation. Monitors can contain many code regions, related or not, which each when executed must do so with a [[File:Java_monitor.gif\|500px\|thumb\|rignt\|Java Monitor. Taken from [[#References\|[15]]]]]guarantee of atomicity with respect to other executing threads. Each code region has its own ''entry set''. This means that each monitor has multiple points of entry, each of which is associated with a particular region of code that for correctness must be synchronized. When a thread, in its course of execution, comes upon a region controlled by the monitor it is placed in the entry set of that region. If the monitor is not occupied, the thread acquires and then occupies the monitor and continues with its execution of that region. If the monitor is occupied then the thread is forced to wait (along with other waiting threads) for the occupying thread to release the monitor. All waiting threads then compete for the opportunity to acquire the monitor.

	Mutual exclusion is guaranteed by the monitor because no more than one thread is allowed in any region of a particular monitor. Cooperation between threads can be orchestrated with a "Wait and Notify" (or "Signal and Continue") monitor. In this type of monitor a thread, while occupying the monitor, can execute a ''wait command''. Executing a wait causes a thread to release the monitor and enter a ''wait set''. The thread, now in the wait set, will stay in a suspended state until after it receives a ''notify command'' '''and''' it is able to occupy the monitor according to protocols already described. A thread which executes a ''notify command'' (the ''Signal'') continues to occupy the monitor in its normal course of execution until it releases the monitor or suspends as well via a wait command.		Mutual exclusion is guaranteed by the monitor because no more than one thread is allowed in any region of a particular monitor. Cooperation between threads can be orchestrated with a "Wait and Notify" (or "Signal and Continue") monitor. In this type of monitor a thread, while occupying the monitor, can execute a ''wait command''. Executing a wait causes a thread to release the monitor and enter a ''wait set''. The thread, now in the wait set, will stay in a suspended state until after it receives a ''notify command'' '''and''' it is able to occupy the monitor according to protocols already described. A thread which executes a ''notify command'' (the ''Signal'') continues to occupy the monitor in its normal course of execution until it releases the monitor or suspends as well via a wait command.

Pmfernan: /* Biased Locks */

2012-04-11T16:23:17Z

Biased Locks

← Older revision		Revision as of 16:23, 11 April 2012
Line 114:		Line 114:
	'' }''		'' }''

	Often, the problem of using the Peterson's Algorithm is that it uses barriers and that can make the dominant and other processes to step back and spin. To solve this issue '''asymmetric locks''' [10] are used, where the non-dominant threads actually ask for permission to the dominant one to step in, making used of a flag.		Often, the problem of using the Peterson's Algorithm is that it uses barriers and that can make the dominant and other processes to step back and spin. To solve this issue '''asymmetric locks''' [10] are used, where the non-dominant threads actually ask for permission to the dominant one to step in, making used of a flag and a grant variable. The flag indicates that there is a request from a process from a lesser thread. When the dominant is about to end with its critical section, checks if the flag is set. If so, sets the grant variable and retires with a barrier until the lesser thread ends, moment at which the latter would reset the grant variable, so the dominant can come back in.
	==An example of biased locks: Rogers' lock==		==An example of biased locks: Rogers' lock==
	[http://www.cs.man.ac.uk/~irogers/index.php Dr. Ian Rogers] (Manchester University, Azul Systems, Google) has an extensive curriculum in computer science, going from network security to binary translators and was a program committee member for [http://pppj2011.imm.dtu.dk PPPJ2011]. He is also part of the Android mobile group at Google.		[http://www.cs.man.ac.uk/~irogers/index.php Dr. Ian Rogers] (Manchester University, Azul Systems, Google) has an extensive curriculum in computer science, going from network security to binary translators and was a program committee member for [http://pppj2011.imm.dtu.dk PPPJ2011]. He is also part of the Android mobile group at Google.

Pmfernan: /* Biased Locks */

2012-04-11T16:17:24Z

Biased Locks

← Older revision		Revision as of 16:17, 11 April 2012
Line 114:		Line 114:
	'' }''		'' }''

			Often, the problem of using the Peterson's Algorithm is that it uses barriers and that can make the dominant and other processes to step back and spin. To solve this issue '''asymmetric locks''' [10] are used, where the non-dominant threads actually ask for permission to the dominant one to step in, making used of a flag.
	==An example of biased locks: Rogers' lock==		==An example of biased locks: Rogers' lock==
	[http://www.cs.man.ac.uk/~irogers/index.php Dr. Ian Rogers] (Manchester University, Azul Systems, Google) has an extensive curriculum in computer science, going from network security to binary translators and was a program committee member for [http://pppj2011.imm.dtu.dk PPPJ2011]. He is also part of the Android mobile group at Google.		[http://www.cs.man.ac.uk/~irogers/index.php Dr. Ian Rogers] (Manchester University, Azul Systems, Google) has an extensive curriculum in computer science, going from network security to binary translators and was a program committee member for [http://pppj2011.imm.dtu.dk PPPJ2011]. He is also part of the Android mobile group at Google.

Pmfernan: /* Biased Locks */

2012-04-11T16:09:30Z

Biased Locks

← Older revision		Revision as of 16:09, 11 April 2012
Line 89:		Line 89:
	Regarding the question of how the main thread decides when to leave the lock. The important factor here is to do it efficiently and many proposals have been made. In Kawachiya's work [3], one of the pioneers in these techniques, the author proposes that when a new thread needs the lock, it would just stop the owner thread and enter it. This task is very expensive because implies the revocation of the owner thread. Onodera et al [12] and Vasudevan et al [10] propose hybrid methods that mix a 2 process algorithm with n-process mutual algorithms (for instance, CAS). Vasudevan's algorithm, for instance, is capable of passing the lock to the younger thread without having to suspend the owner and only uses an extra two assignments and two comparisons. Russell and Detlefs [9] also offers lock transfer, but their transfer algorithm is more expensive and it has been questioned because the difficulty to ascertain if the biased lock is actually in possession of a particular thread.		Regarding the question of how the main thread decides when to leave the lock. The important factor here is to do it efficiently and many proposals have been made. In Kawachiya's work [3], one of the pioneers in these techniques, the author proposes that when a new thread needs the lock, it would just stop the owner thread and enter it. This task is very expensive because implies the revocation of the owner thread. Onodera et al [12] and Vasudevan et al [10] propose hybrid methods that mix a 2 process algorithm with n-process mutual algorithms (for instance, CAS). Vasudevan's algorithm, for instance, is capable of passing the lock to the younger thread without having to suspend the owner and only uses an extra two assignments and two comparisons. Russell and Detlefs [9] also offers lock transfer, but their transfer algorithm is more expensive and it has been questioned because the difficulty to ascertain if the biased lock is actually in possession of a particular thread.

	Following, a biased lock snippet proposed by Vasudevan et al [10]. It first defines a structure with the id of the owner of thread and the two locks, the light weight and the heavier weight. In the biased locks we see that while the thread id is that of the owner, only the light weight lock is executed. When the thread is other than the owner, both locks are executed.		Following, a biased lock snippet proposed by Vasudevan et al [10]. It first defines a structure with the id of the owner of thread and the two locks, the light weight and the heavier weight. In the biased locks we see that while the thread id is that of the owner, only the light weight lock is executed. When the thread is other than the owner, both locks are executed.The heavy weight, or not dominant, lock could be a
			variant of the [http://en.wikipedia.org/wiki/Peterson%27s_algorithm Peterson's Algorithm] before and after the critical section.

	'' typedef struct {		'' typedef struct {

Pmfernan: /* References */

2012-04-11T16:04:10Z

References

← Older revision		Revision as of 16:04, 11 April 2012
Line 192:		Line 192:
	# [http://www.artima.com/insidejvm/blurb.html ''Inside the Java Virtual Machine 2''], Bill Venners, McGraw-Hill Companies; 2nd edition 2000		# [http://www.artima.com/insidejvm/blurb.html ''Inside the Java Virtual Machine 2''], Bill Venners, McGraw-Hill Companies; 2nd edition 2000
	# [http://www.research.ibm.com/people/d/dfb/talks/Bacon98ThinTalk.pdf ''Thin Locks: Featherweight Synchronization for Java'']. Paper presented at the ACM Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998.		# [http://www.research.ibm.com/people/d/dfb/talks/Bacon98ThinTalk.pdf ''Thin Locks: Featherweight Synchronization for Java'']. Paper presented at the ACM Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998.
	# {''Thread Synchronization'' :http://www.artima.com/insidejvm/ed2/threadsynch.html~~]: Artima, Inc, 2009~~		# ''Thread Synchronization'', Artima, Inc, 2009: http://www.artima.com/insidejvm/ed2/threadsynch.html

	=Quiz=		=Quiz=

← Older revision		Revision as of 19:35, 11 April 2012
Line 66:		Line 66:

	=Biased Locks=		=Biased Locks=
	One of the techniques, previously introduced, that are used to test and capture the locks is compare&swap, CAS. These atomic instructions are indeed very intensive, and consume many bus cycles (in a [http://en.wikipedia.org/wiki/Intel_Core Core Duo], a CAS operation can consume up to seven times longer than a increment [10]). They solely could be blamed on using a significant percentage of the computing time and resources of a processor. (It is interesting to state here that this effect depends on the processor architecture, as well as the VM implementation and, hence, [http://publib.boulder.ibm.com/infocenter/javasdk/v1r4m2/index.jsp?topic=%2Fcom.ibm.java.doc.diagnostics.142%2Fhtml%2Funderthejvm.html IBM Java VM] is less disposed to this effect than [http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html Oracle's]. Also, recent processors, like the Intel Core family, have been optimized to perform this task) Due to its architecture and way of use, Java is prone to use a considerable amount of locking, and that amount has a tremendous effect on the computing time of every program. Due to the idiosyncrasy of the spins, it is not uncommon [1] that, when we compare the times used in the execution of a program serially or using threads, the latter shows higher inefficiency and latencies grow exponentially with relation to the number of threads used. [[File:Comparison_biased.PNG\|400px\|thumb\|right\|Comparison biased-not biased for a Readers-Writers process (taken from [1])]]		One of the techniques, previously introduced, that are used to test and capture the locks is compare&swap, CAS. These atomic instructions are indeed very intensive, and consume many bus cycles (in a [http://en.wikipedia.org/wiki/Intel_Core Core Duo], a CAS operation can consume up to seven times longer than a increment [[#References\|[10]]]). They solely could be blamed on using a significant percentage of the computing time and resources of a processor. (It is interesting to state here that this effect depends on the processor architecture, as well as the VM implementation and, hence, [http://publib.boulder.ibm.com/infocenter/javasdk/v1r4m2/index.jsp?topic=%2Fcom.ibm.java.doc.diagnostics.142%2Fhtml%2Funderthejvm.html IBM Java VM] is less disposed to this effect than [http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html Oracle's]. Also, recent processors, like the Intel Core family, have been optimized to perform this task) Due to its architecture and way of use, Java is prone to use a considerable amount of locking, and that amount has a tremendous effect on the computing time of every program. Due to the idiosyncrasy of the spins, it is not uncommon [[#References\|[1]]] that, when we compare the times used in the execution of a program serially or using threads, the latter shows higher inefficiency and latencies grow exponentially with relation to the number of threads used. [[File:Comparison_biased.PNG\|400px\|thumb\|right\|Comparison biased-not biased for a Readers-Writers process (taken from [[#References\|[1]]] )]]
	One of the solutions proposed to mitigate this problem is based on taking advantage of some observations in the distribution of locks by the programs: in most cases, due to the way the programs are structured, there is one thread that consumes the locks more often than the others, that is the lock is more commonly used by a single owner and, in occasions, that thread could be entering the locks a number of times several order the magnitude higher. So why not to make it easier for it?		One of the solutions proposed to mitigate this problem is based on taking advantage of some observations in the distribution of locks by the programs: in most cases, due to the way the programs are structured, there is one thread that consumes the locks more often than the others, that is the lock is more commonly used by a single owner and, in occasions, that thread could be entering the locks a number of times several order the magnitude higher. So why not to make it easier for it?

Line 77:		Line 77:
	# Release, where the thread release the lock for others to acquire.		# Release, where the thread release the lock for others to acquire.
	As we can imagine that we stay more or less in the mutual exclusion area will depend on how many threads or processes we have in that area, the frequency with we use it; if we collide or not with other processes and what kind of lock we are using. We need to find ways to make these characteristics to work in our advantage.		As we can imagine that we stay more or less in the mutual exclusion area will depend on how many threads or processes we have in that area, the frequency with we use it; if we collide or not with other processes and what kind of lock we are using. We need to find ways to make these characteristics to work in our advantage.
	Biased locking exploits just one of those characteristics, the frequency. As we have mentioned before, the case where a thread uses a lock more frequently than any others is very common. In that case, we could grant ownership of a lock to that thread and just purposely neglect doing the unlock operation (to be able to do this, the object need to allow it, i.e, in Java, the object header has to have the biased bit set). In this way, the next time that the thread wants to enter the lock, it will have it already, hence gaining the time to compete for it (even if there is no other competition, there will still be the CAS), lock it and release it. Effectively it is like they never leave the critical section. Now, could this generate contention problems? Not with the same process, that could not be in that region (it has just abandoned it); nor with others, as the former process still hold the lock. These will make the lock task nimbler to the more frequent thread and longer for the less frequent. But that is exactly what we are looking for. In fact, for cases where the contention between processes is very low, there are proposals to eliminate the atomicity all together [11].		Biased locking exploits just one of those characteristics, the frequency. As we have mentioned before, the case where a thread uses a lock more frequently than any others is very common. In that case, we could grant ownership of a lock to that thread and just purposely neglect doing the unlock operation (to be able to do this, the object need to allow it, i.e, in Java, the object header has to have the biased bit set). In this way, the next time that the thread wants to enter the lock, it will have it already, hence gaining the time to compete for it (even if there is no other competition, there will still be the CAS), lock it and release it. Effectively it is like they never leave the critical section. Now, could this generate contention problems? Not with the same process, that could not be in that region (it has just abandoned it); nor with others, as the former process still hold the lock. These will make the lock task nimbler to the more frequent thread and longer for the less frequent. But that is exactly what we are looking for. In fact, for cases where the contention between processes is very low, there are proposals to eliminate the atomicity all together [[#References\|[11]]].

	There are then two issues we need to resolve: how to decide which thread is "the most frequent", that we will call '''the owner'''; and how to let any other thread not-the-owner use the lock. For the first question, we could use some gathered data or some heuristics. For instance:		There are then two issues we need to resolve: how to decide which thread is "the most frequent", that we will call '''the owner'''; and how to let any other thread not-the-owner use the lock. For the first question, we could use some gathered data or some heuristics. For instance:
Line 87:		Line 87:
	* Define a flag for biasing in an object type.		* Define a flag for biasing in an object type.
	* When entering a lock, check the flag: if asserted, then bias; if not, use a thin lock until a mechanism, for instance age, flags the biased flag.		* When entering a lock, check the flag: if asserted, then bias; if not, use a thin lock until a mechanism, for instance age, flags the biased flag.
	Regarding the question of how the main thread decides when to leave the lock. The important factor here is to do it efficiently and many proposals have been made. In Kawachiya's work [3], one of the pioneers in these techniques, the author proposes that when a new thread needs the lock, it would just stop the owner thread and enter it. This task is very expensive because implies the revocation of the owner thread. Onodera et al [12] and Vasudevan et al [10] propose hybrid methods that mix a 2 process algorithm with n-process mutual algorithms (for instance, CAS). Vasudevan's algorithm, for instance, is capable of passing the lock to the younger thread without having to suspend the owner and only uses an extra two assignments and two comparisons. Russell and Detlefs [9] also offers lock transfer, but their transfer algorithm is more expensive and it has been questioned because the difficulty to ascertain if the biased lock is actually in possession of a particular thread.		Regarding the question of how the main thread decides when to leave the lock. The important factor here is to do it efficiently and many proposals have been made. In Kawachiya's work [[#References\|[3]]], one of the pioneers in these techniques, the author proposes that when a new thread needs the lock, it would just stop the owner thread and enter it. This task is very expensive because implies the revocation of the owner thread. Onodera et al [[#References\|[12]]] and Vasudevan et al [[#References\|[10]]] propose hybrid methods that mix a 2 process algorithm with n-process mutual algorithms (for instance, CAS). Vasudevan's algorithm, for instance, is capable of passing the lock to the younger thread without having to suspend the owner and only uses an extra two assignments and two comparisons. Russell and Detlefs [[#References\|[9]]] also offers lock transfer, but their transfer algorithm is more expensive and it has been questioned because the difficulty to ascertain if the biased lock is actually in possession of a particular thread.

	Following, a biased lock snippet proposed by Vasudevan et al [10]. It first defines a structure with the id of the owner of thread and the two locks, the light weight and the heavier weight. In the biased locks we see that while the thread id is that of the owner, only the light weight lock is executed. When the thread is other than the owner, both locks are executed.The heavy weight, or not dominant, lock could be a		Following, a biased lock snippet proposed by Vasudevan et al [[#References\|[10]]]. It first defines a structure with the id of the owner of thread and the two locks, the light weight and the heavier weight. In the biased locks we see that while the thread id is that of the owner, only the light weight lock is executed. When the thread is other than the owner, both locks are executed.The heavy weight, or not dominant, lock could be a
	variant of the [http://en.wikipedia.org/wiki/Peterson%27s_algorithm Peterson's Algorithm] before and after the critical section.		variant of the [http://en.wikipedia.org/wiki/Peterson%27s_algorithm Peterson's Algorithm] before and after the critical section.

Line 114:		Line 114:
	'' }''		'' }''

	Often, the problem of using the Peterson's Algorithm is that it uses barriers and that can make the dominant and other processes to step back and spin. To solve this issue '''asymmetric locks''' [10] are used, where the non-dominant threads actually ask for permission to the dominant one to step in, making used of a flag and a grant variable. The flag indicates that there is a request from a process from a lesser thread. When the dominant is about to end with its critical section, checks if the flag is set. If so, sets the grant variable and retires with a barrier until the lesser thread ends, moment at which the latter would reset the grant variable, so the dominant can come back in.		Often, the problem of using the Peterson's Algorithm is that it uses barriers and that can make the dominant and other processes to step back and spin. To solve this issue '''asymmetric locks''' [[#References\|[10]]] are used, where the non-dominant threads actually ask for permission to the dominant one to step in, making used of a flag and a grant variable. The flag indicates that there is a request from a process from a lesser thread. When the dominant is about to end with its critical section, checks if the flag is set. If so, sets the grant variable and retires with a barrier until the lesser thread ends, moment at which the latter would reset the grant variable, so the dominant can come back in.
	==An example of biased locks: Rogers' lock==		==An example of biased locks: Rogers' lock==
	[http://www.cs.man.ac.uk/~irogers/index.php Dr. Ian Rogers] (Manchester University, Azul Systems, Google) has an extensive curriculum in computer science, going from network security to binary translators and was a program committee member for [http://pppj2011.imm.dtu.dk PPPJ2011]. He is also part of the Android mobile group at Google.		[http://www.cs.man.ac.uk/~irogers/index.php Dr. Ian Rogers] (Manchester University, Azul Systems, Google) has an extensive curriculum in computer science, going from network security to binary translators and was a program committee member for [http://pppj2011.imm.dtu.dk PPPJ2011]. He is also part of the Android mobile group at Google.

	In 2011 he presented some work on thin and biased locks ([4], [5]) where he proposed a biased lock with the following characteristics: [[File:RogersLock.PNG\|400px\|thumb\|right\|Rogers Lock State Machine (taken from [5])]]		In 2011 he presented some work on thin and biased locks [[#References\|[4]]] [[#References\|[5]]] where he proposed a biased lock with the following characteristics: [[File:RogersLock.PNG\|400px\|thumb\|right\|Rogers Lock State Machine (taken from [[#References\|[5]]] )]]

	* Use and declaration of biased bit in the object header, using existing states in that header.		* Use and declaration of biased bit in the object header, using existing states in that header.
Line 134:		Line 134:
	The object header for this model would then be like:		The object header for this model would then be like:

	[[File:ObjectHeader.PNG\|300px\|thumb\|left\|Rogers Model Object Header (taken from [5])]]		[[File:ObjectHeader.PNG\|300px\|thumb\|left\|Rogers Model Object Header (taken from [[#References\|[5]]] )]]

	Where every field is defined as, according to Rogers:		Where every field is defined as, according to Rogers: