Difference between revisions of "AllOrNothingLocks"

From CSE231 Wiki
Jump to navigation Jump to search
Line 22: Line 22:
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/package-summary.html package java.util.concurrent.locks]
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/package-summary.html package java.util.concurrent.locks]
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html ReentrantLock]
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html ReentrantLock]
 +
 +
Useful documentation:
 +
*[https://docs.oracle.com/javase/tutorial/java/nutsandbolts/while.html while loops]
 +
*[https://docs.oracle.com/javase/tutorial/essential/exceptions/finally.html finally]
 +
*[https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#yield-- Thread yield]
 +
 +
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html-- Lock]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#tryLock-- tryLock]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#unlock--- unlock]
 +
 +
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html--- ReentrantLock]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html#isHeldByCurrentThread--- isHeldByCurrentThread ]
 +
 +
* [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html ListIterator<E>]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#hasNext-- boolean hasNext()]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#next-- E next()]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#hasPrevious-- boolean hasPrevious()]
 +
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#previous-- E previous()]
  
 
=Code To Implement=
 
=Code To Implement=
Line 50: Line 68:
 
*Anytime you lock a lock object, you should/must use a <code>try/finally</code> block to unlock the lock.
 
*Anytime you lock a lock object, you should/must use a <code>try/finally</code> block to unlock the lock.
 
*Your implementation will have to make use of a nested <code>try/finally</code> block (one <code>try/finally</code> call within another).
 
*Your implementation will have to make use of a nested <code>try/finally</code> block (one <code>try/finally</code> call within another).
 
Useful documentation:
 
*[https://docs.oracle.com/javase/tutorial/java/nutsandbolts/while.html while loops]
 
*[https://docs.oracle.com/javase/tutorial/essential/exceptions/finally.html finally]
 
*[https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#yield-- Thread yield]
 
  
 
===LockUtils runWithAllLocksOrDontRunAtAll===
 
===LockUtils runWithAllLocksOrDontRunAtAll===
Line 97: Line 110:
  
 
{{Warning | If tryLockAll fails, when rolling back a ListIterator to unlock any locks you acquired, be sure to do an initial prev() to set the iterator in the correct location before looping through to unlock the rest.}}
 
{{Warning | If tryLockAll fails, when rolling back a ListIterator to unlock any locks you acquired, be sure to do an initial prev() to set the iterator in the correct location before looping through to unlock the rest.}}
 
some useful documentation:
 
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html-- Lock]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#tryLock-- tryLock]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/Lock.html#unlock--- unlock]
 
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html--- ReentrantLock]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantLock.html#isHeldByCurrentThread--- isHeldByCurrentThread ]
 
 
* [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html ListIterator<E>]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#hasNext-- boolean hasNext()]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#next-- E next()]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#hasPrevious-- boolean hasPrevious()]
 
** [https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html#previous-- E previous()]
 
  
 
=Testing Your Solution=
 
=Testing Your Solution=
 
==Correctness==
 
==Correctness==
 
{{TestSuite|TryLockingTestSuite|lock.allornothing.studio}}
 
{{TestSuite|TryLockingTestSuite|lock.allornothing.studio}}

Revision as of 18:20, 14 April 2018

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

Motivation

In addition to Ordered_Locks we can employ an all-or-nothing strategy for acquiring locks for mutual exclusion.

We gain experience with explicit locks and trying to acquire them and responding appropriately to success and failure.

Background

Check out the Lock_Ordering#Background studio.

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. In this studio we will explore the second type of locks: explicitly created Lock objects from the java.util.concurrent.locks package.

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. Lock objects are acted upon just like any other object, but we are mostly interested in the lock() method, the tryLock() method, and the unlock() method. For this studio, we will specifically use the ReentrantLock object, a class which implements the general Lock 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).

For this approach, we will make use of the tryLock() 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).

Java Util Concurrent

Refer to Oracle's official documentation for more information:

Useful documentation:

Code To Implement

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 tryLock() method. For an example of how to format a tryLock, look below:

Lock lock = ...
if (lock.tryLock()) {
	try {
		doSomething();
	} finally {
		lock.unlock();
	}
}

BankAccountTryLocking

class: BankAccountLockTrying.java Java.png
methods: tryTransferMoney
package: lock.allornothing.studio
source folder: student/src/main/java

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

Open BankAccountTryLocking.java.

A couple of notes and common issues:

  • tryLock() 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.
  • tryLock() will grab the lock if it can. There's no need to call lock() after tryLock().
  • We recommend you call the AccountUtils.checkBalanceAndTransfer(sender, receiver, amount) 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.
  • Anytime you lock a lock object, you should/must use a try/finally block to unlock the lock.
  • Your implementation will have to make use of a nested try/finally block (one try/finally call within another).

LockUtils runWithAllLocksOrDontRunAtAll

class: LockUtils.java Java.png
methods: tryLockAll
unlockAllHeldLocks
runWithAllLocksOrDontRunAtAll
package: lock.allornothing.studio
source folder: student/src/main/java

method: public static boolean tryLockAll(List<ReentrantLock> locks) Sequential.svg (sequential implementation only)

method: public static void unlockAllHeldLocks(List<ReentrantLock> locks) Sequential.svg (sequential implementation only)

method: public static boolean runWithAllLocksOrDontRunAtAll(List<ReentrantLock> locks, Runnable body) Sequential.svg (thread-safe required)

Open LockUtils.java.

For this part of the studio you will need to implement:

public static boolean tryLockAll(List<ReentrantLock> locks)

and

public static void unlockAllHeldLocks(List<ReentrantLock> locks)

so that the useful utility (shouldn't they all be useful?)

public static boolean runWithAllLocksOrDontRunAtAll(List<ReentrantLock> locks, Runnable body) {
	boolean status = tryLockAll(locks);
	if (status) {
		try {
			body.run();
		} finally {
			unlockAllHeldLocks(locks);
		}
	}
	return status;
}

produces correct thread safe behavior.

Note: in tryLockAll, you will need to call tryLock on all of the given locks. However, if one fails, you will need to unlock everything you have currently locked. A lock cannot be unlocked from a thread that doesn't hold the lock. Consider using the ListIterator interface.

Attention niels epting.svg Warning: If tryLockAll fails to acquire all of the locks, make sure to unlock any of the locks you did acquire.
Attention niels epting.svg Warning: If tryLockAll fails, when rolling back a ListIterator to unlock any locks you acquired, be sure to do an initial prev() to set the iterator in the correct location before looping through to unlock the rest.

Testing Your Solution

Correctness

class: TryLockingTestSuite.java Junit.png
package: lock.allornothing.studio
source folder: testing/src/test/java