Difference between revisions of "Ordered Locks"

From CSE231 Wiki
Jump to navigation Jump to search
m (Cosgroved moved page Locking to Lock Ordering)
 
(33 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
credit for this assignment: [http://jcip.net/ Java Concurrency in Practice], Ben Choi, and Dennis Cosgrove
 +
=Motivation=
 +
Inspired by X10's isolated construct which provides mutual exclusion while avoiding deadlock, we will learn how to achieve this desirable property of deadlock freedom by ordering locks.
 +
 +
We will gain experience with implicit locks and the synchronized statement.
 +
 
=Background=
 
=Background=
 +
In Java, locks are a synchronization tool that exists to ensure whatever is protected by the lock is only accessed one thread at a time, as to avoid a possible data race. We will explore the first of two different types of locks: intrinsic locks.
  
−
In Java, locks are a synchronization tool that exists to ensure whatever is protected by the lock is only accessed one thread at a time, as to avoid a possible data race. We will explore two different types of locks: intrinsic locks and lock objects.
+
Every object has an intrinsic lock associated with the object. Intrinsic locks are accessed with the <code>synchronized</code> keyword.  
−
 
 
−
Every object has an intrinsic lock associated with the object, but lock objects are explicitly defined and instantiated locks which can be called to lock or unlock. Intrinsic locks are called with the <code>synchronized</code> keyword. Lock objects are acted upon just like any other object, but we are mostly interested in the <code>lock()</code> method, the <code>tryLock()</code> method, and the <code>unlock()</code> method. For this studio, we will specifically use the <code>ReentrantLock</code> object, a class which implements the general <code>Lock</code> interface.
 
  
−
To demonstrate how to avoid both data races and deadlock issues, we will create a method designed to transfer money between two bank accounts. Two parties should be able to asynchronously and continuously transfer money between each other without a data race (courtesy of locks) or deadlock (something you will address).
+
To demonstrate how to avoid both data races and deadlock issues, we will create a method designed to transfer money between two bank accounts. Two parties should be able to safely transfer money between each other without a data race (courtesy of locks) or deadlock (something you will address).
  
−
The two possible ways to avoid deadlock, which we will address in this studio, are: lock ordering and tryLocking.
+
In this exercise we will use lock ordering to avoid deadlock.
  
 
With lock ordering, we will control the order in which locks are acquired for two bank accounts using unique identifying values associated with the bank accounts. In this way, a transfer from bank account A to B paired with a simultaneous transfer from B to A will not lead to a scenario in which A is waiting for B’s lock forever while B is waiting for A’s lock forever, as both calls will always attempt to go for A’s lock before B’s or vice versa. For a general object, we might use the object’s hashcode as the unique identifying value, but for this assignment, we will use the account number associated with the bank account (which is guaranteed to be unique, unlike hashcodes).
 
With lock ordering, we will control the order in which locks are acquired for two bank accounts using unique identifying values associated with the bank accounts. In this way, a transfer from bank account A to B paired with a simultaneous transfer from B to A will not lead to a scenario in which A is waiting for B’s lock forever while B is waiting for A’s lock forever, as both calls will always attempt to go for A’s lock before B’s or vice versa. For a general object, we might use the object’s hashcode as the unique identifying value, but for this assignment, we will use the account number associated with the bank account (which is guaranteed to be unique, unlike hashcodes).
  
−
How would you handle the case where two objects were equal?
+
Refer to Oracle's official documentation regarding [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic locks/synchronization] for more information.
−
<spoiler show="spoiler" hide="spoiler">Use a third object</spoiler>
 
  
−
In the other approach, we will make use of the <code>tryLock()</code> method in order to attempt to acquire an object’s lock. If the object’s lock is not available at the time, we will continue to try to acquire the lock until it finally succeeds, after which we can successfully transfer funds from one bank account to another. In this approach, an asynchronous pair of transfers from A to B and B to A will not lead to deadlock as the two processes will give up on acquiring the lock until it becomes available, at which point it will finally acquire the lock. This approach does not make use of ordering, but simply relies on making lock attempts give up if the desired lock is not immediately available (and then try again later).
+
=Somewhat Dated Video=
 +
<!-- {{CollapsibleYouTube|Lecture|<youtube>qEbL51Gx3w0</youtube>}}-->
  
−
Refer to Oracle's official documentation regarding [https://docs.oracle.com/javase/tutorial/essential/concurrency/newlocks.html lock] [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/package-summary.html objects], [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html reentrant locks], and [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic locks/synchronization] for more information.
+
{{CollapsibleYouTube|Exercise|<youtube>unkJCm1hqHk</youtube>}}
  
−
=Where to Start=
+
=Code To Implement=
 +
{{CodeToImplement|BankAccountLockOrdering|transferMoney|lock.order.studio}}
  
−
Navigate to the '''locks''' directory to get started. From there, the classes you will need to modify can be found under the <code>locking.studio</code> directory. The '''core''' directory is composed of utility and building block classes we created for you. Take a look at these classes to get a better understanding of how to use them for your assignment. It does not matter which approach you choose to do first.
+
{{ThreadSafe|public static TransferResult transferMoney(Account sender, Account recipient, int amount)}}
  
  
−
==Lock Ordering==
+
As mentioned in the background section, we will attempt to prevent deadlock using a lock ordering algorithm of your making. Essentially, whenever an operation needs to use two separate locks, make sure that the locks are always acquired in a fixed order no matter how the operation is called. The general way to do this is to compare the identity hash codes of the two objects and enforce an order based on those values. However, this can lead to a rare issue in which the two objects are unique, but have the same hashcode.
  
−
Navigate to <code>LockOrdering.java</code>. As mentioned in the background section, we will attempt to prevent deadlock using a lock ordering algorithm of your making. Essentially, whenever an operation needs to use two separate locks, make sure that the locks are always acquired in a fixed order no matter how the operation is called. The best way to do this is to compare the hashcodes of the two objects and enforce an order based on those values. However, this can lead to a rare issue in which the two objects are unique, but have the same hashcode. In this case, you will need to lock a third placeholder object before locking any of the other objects. To avoid this issue entirely, however, we have assigned unique bank account numbers to each instance of the bank account object. Thus, you will not need to worry about this edge case.
+
To avoid this issue entirely, however, we have assigned unique bank account numbers to each instance of the bank account object. Thus, you will not need to worry about this edge case.
  
 
A couple of notes and common issues:
 
A couple of notes and common issues:
  
−
*You can use the ReentranLocks associated with the sender and recipient, but we recommend simply using intrinsic locks for this method. In other words, use <code>synchronized(sender)</code> or <code>synchronized(recipient)</code> to make your code simpler.
+
*While you could create a [https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/Lock.html Lock] object for each [https://www.cse.wustl.edu/~cosgroved/courses/cse231/s20/apidocs/locking/core/banking/Account.html Account] instance, we recommend simply using [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic locks] for this method. In other words, use <code>synchronized(sender)</code> and <code>synchronized(recipient)</code>.
−
*We recommend you call the <code>BankAccount.checkBalanceAndTransfer()</code> method for the sake of simplicity. This method will check that the sender and recipient are not the same person and that the sender has enough money in her account to send the specified amount to the recipient.
+
*Syntax for synchronized can be found on this [[Reference_Page#Synchronized|reference page]].
−
*Use the <code>accountNumber()</code> method to get the unique account ID of a given bank account.
+
*Invoke the not-thread-safe <code>TransferUtils.checkBalanceAndTransfer()</code> method. This method will check that the sender and recipient are not the same people and that the sender has enough money in her account to send the specified amount to the recipient.
−
*Your implementation will have to make use of a nested <code>synchronized</code> block (one <code>synchronized</code> call within another).
+
*Use the <code>uniqueIdNumber()</code> method to get the unique account ID of a given bank account.
−
 
+
*Your implementation will have to make use of a nested <code>synchronized</code> blocks (one <code>synchronized</code> call within another).
−
==Try Locking==
 
  
−
Navigate to <code>TryLocking.java</code>. As mentioned in the background section, this implementation will avoid deadlock by giving up on acquiring a lock if it is not immediately available before coming back to it later (when it might actually be available). This implementation will need to make use of the ReentrantLocks associated with the sender and recipient bank account objects. More specifically, it will have to make use of the <code>tryLock()</code> method. For an example of how to format a tryLock, look below:
+
=Not Required Problem To Contemplate=
 +
How would you handle the case where every attempt to order two objects ([https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#compareTo-T- compareTo(other)], [https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#identityHashCode-java.lang.Object- System.identityHashCode(o)], et cetera) failed?
 +
{{Spoiler|One would synchronize on a shared third object first to account for this rare case.}}
  
−
<nowiki>Lock lock = new ReentrantLock();
+
=Testing Your Solution=
−
if (lock.tryLock()) {
+
==Correctness==
−
try {
+
{{TestSuite|_LockOrderingTestSuite|lock.order.exercise}}
−
doSomething();
 
−
} finally {
 
−
lock.unlock();
 
−
}
 
−
}</nowiki>
 
−
 
 
−
A couple of notes and common issues:
 
  
−
*<code>tryLock()</code> will immediately give up and return false if the lock is not available when it is called. Thus, you will need to construct a loop that will continuously run until the desired lock is available. You can exit out of this loop in two ways: with the break keyword or by returning a valid value for the method.
+
=Pledge, Acknowledgments, Citations=
−
*Anytime you lock a lock object, you must use a <code>try/finally</code> block to unlock the lock.
+
{{Pledge|ordered-locks}}
−
*We recommend you call the <code>BankAccount.checkBalanceAndTransfer()</code> method for the sake of simplicity. This method will check that the sender and recipient are not the same people and that the sender has enough money in her account to send the specified amount to the recipient.
 
−
*Your implementation will have to make use of a nested <code>try/finally</code> block (one <code>try/finally</code> call within another).
 

Latest revision as of 00:15, 31 March 2023

credit for this assignment: Java Concurrency in Practice, Ben Choi, and Dennis Cosgrove

Motivation

Inspired by X10's isolated construct which provides mutual exclusion while avoiding deadlock, we will learn how to achieve this desirable property of deadlock freedom by ordering locks.

We will gain experience with implicit locks and the synchronized statement.

Background

In Java, locks are a synchronization tool that exists to ensure whatever is protected by the lock is only accessed one thread at a time, as to avoid a possible data race. We will explore the first of two different types of locks: intrinsic locks.

Every object has an intrinsic lock associated with the object. Intrinsic locks are accessed with the synchronized keyword.

To demonstrate how to avoid both data races and deadlock issues, we will create a method designed to transfer money between two bank accounts. Two parties should be able to safely transfer money between each other without a data race (courtesy of locks) or deadlock (something you will address).

In this exercise we will use lock ordering to avoid deadlock.

With lock ordering, we will control the order in which locks are acquired for two bank accounts using unique identifying values associated with the bank accounts. In this way, a transfer from bank account A to B paired with a simultaneous transfer from B to A will not lead to a scenario in which A is waiting for B’s lock forever while B is waiting for A’s lock forever, as both calls will always attempt to go for A’s lock before B’s or vice versa. For a general object, we might use the object’s hashcode as the unique identifying value, but for this assignment, we will use the account number associated with the bank account (which is guaranteed to be unique, unlike hashcodes).

Refer to Oracle's official documentation regarding intrinsic locks/synchronization for more information.

Somewhat Dated Video

Video: Exercise  

Code To Implement

class: BankAccountLockOrdering.java Java.png
methods: transferMoney
package: lock.order.studio
source folder: student/src/main/java

method: public static TransferResult transferMoney(Account sender, Account recipient, int amount) Sequential.svg (thread-safe required)


As mentioned in the background section, we will attempt to prevent deadlock using a lock ordering algorithm of your making. Essentially, whenever an operation needs to use two separate locks, make sure that the locks are always acquired in a fixed order no matter how the operation is called. The general way to do this is to compare the identity hash codes of the two objects and enforce an order based on those values. However, this can lead to a rare issue in which the two objects are unique, but have the same hashcode.

To avoid this issue entirely, however, we have assigned unique bank account numbers to each instance of the bank account object. Thus, you will not need to worry about this edge case.

A couple of notes and common issues:

  • While you could create a Lock object for each Account instance, we recommend simply using intrinsic locks for this method. In other words, use synchronized(sender) and synchronized(recipient).
  • Syntax for synchronized can be found on this reference page.
  • Invoke the not-thread-safe TransferUtils.checkBalanceAndTransfer() method. This method will check that the sender and recipient are not the same people and that the sender has enough money in her account to send the specified amount to the recipient.
  • Use the uniqueIdNumber() method to get the unique account ID of a given bank account.
  • Your implementation will have to make use of a nested synchronized blocks (one synchronized call within another).

Not Required Problem To Contemplate

How would you handle the case where every attempt to order two objects (compareTo(other), System.identityHashCode(o), et cetera) failed?

Testing Your Solution

Correctness

class: _LockOrderingTestSuite.java Junit.png
package: lock.order.exercise
source folder: testing/src/test/java

Pledge, Acknowledgments, Citations

file: ordered-locks-pledge-acknowledgments-citations.txt

More info about the Honor Pledge

Retrieved from "http://classes.engineering.wustl.edu/cse231/core/index.php?title=Ordered_Locks&oldid=4898"