Difference between revisions of "Ordered Locks"
(21 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 | credit for this assignment: [http://jcip.net/ Java Concurrency in Practice], Ben Choi, and Dennis Cosgrove | ||
=Motivation= | =Motivation= | ||
− | X10's isolated construct provides mutual exclusion while avoiding deadlock | + | 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. | We will gain experience with implicit locks and the synchronized statement. | ||
Line 12: | Line 12: | ||
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). | 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 | + | 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). | ||
Refer to Oracle's official documentation regarding [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic locks/synchronization] for more information. | Refer to Oracle's official documentation regarding [https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html intrinsic locks/synchronization] for more information. | ||
+ | |||
+ | =Somewhat Dated Video= | ||
+ | <!-- {{CollapsibleYouTube|Lecture|<youtube>qEbL51Gx3w0</youtube>}}--> | ||
+ | |||
+ | {{CollapsibleYouTube|Exercise|<youtube>unkJCm1hqHk</youtube>}} | ||
=Code To Implement= | =Code To Implement= | ||
− | + | {{CodeToImplement|BankAccountLockOrdering|transferMoney|lock.order.studio}} | |
+ | |||
+ | {{ThreadSafe|public static TransferResult transferMoney(Account sender, Account recipient, int amount)}} | ||
+ | |||
− | + | 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. | 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. | ||
Line 28: | Line 35: | ||
A couple of notes and common issues: | A couple of notes and common issues: | ||
− | * | + | *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>. |
− | * | + | *Syntax for synchronized can be found on this [[Reference_Page#Synchronized|reference page]]. |
− | *Use the | + | *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. |
+ | *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). | *Your implementation will have to make use of a nested <code>synchronized</code> blocks (one <code>synchronized</code> call within another). | ||
− | + | =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.}} |
=Testing Your Solution= | =Testing Your Solution= | ||
==Correctness== | ==Correctness== | ||
− | {{TestSuite| | + | {{TestSuite|_LockOrderingTestSuite|lock.order.exercise}} |
+ | |||
+ | =Pledge, Acknowledgments, Citations= | ||
+ | {{Pledge|ordered-locks}} |
Latest revision as of 00:15, 31 March 2023
credit for this assignment: Java Concurrency in Practice, Ben Choi, and Dennis Cosgrove
Contents
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 | |
methods: | transferMoney | |
package: | lock.order.studio | |
source folder: | student/src/main/java |
method: public static TransferResult transferMoney(Account sender, Account recipient, int amount)
(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)
andsynchronized(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 (onesynchronized
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?
Spoiler |
One would synchronize on a shared third object first to account for this rare case. |
Testing Your Solution
Correctness
class: | _LockOrderingTestSuite.java | |
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