...
| Wiki Markup |
|---|
"The Java programming language neither prevents nor requires detection of deadlock conditions." \[[JLS 05|AA. Java References#JLS 05]\]. Deadlocks can arise when two or more threads request and release locks in different orders. Consequently, to avoid deadlock, locks should be acquired and released in the same order and synchronization should be limited to where it is absolutely necessary. For instance, to avoid deadlocks in an applet, the {{paint()}}, {{dispose()}}, {{stop()}}, and {{destroy()}} methods should not be synchronized because they are always called and used from dedicated threads. |
Deadlocks can also The advice of this guideline also applies to programs that need to work with a limited set of resources. For instance, deadlocks that can arise when two or more threads are waiting for each other to release resources such as database connections. The advice of this guideline also applies to these cases, can be mitigated by letting each thread retry the operation after some random amount of time if a requested lock is unavailable.
Noncompliant Code Example
This noncompliant code example can deadlock because of excessive synchronization. Assume that an attacker has two bank accounts and is capable of requesting two depositAmount() operations in succession, one each from the two threads started in main().
| Code Block | ||
|---|---|---|
| ||
final class BankAccount {
private double balanceAmount; // Total amount in bank account
private BankAccount(double balance) {
this.balanceAmount = balance;
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAmount(BankAccount ba, double amount) {
synchronized (this) {
synchronized(ba) {
if(amount > balanceAmount) {
throw new IllegalArgumentException("Transfer cannot be completed");
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
}
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAmount(second, amount);
}
});
t.start();
}
}
|
...
| Code Block |
|---|
BankAccount a = new BankAccount(5000); BankAccount b = new BankAccount(6000); initiateTransfer(a, b, 1000); // starts thread 1 initiateTransfer(b, a, 1000); // starts thread 2 |
The two transfers are performed in their own threads, from instance a to b and b to a, are performed in their own threads. The first thread atomically transfers the amount from a to b by depositing it in account b and then withdrawing the same amount from a. The second thread performs the reverse operation, that is, it transfers the balance from b to a. When executing depositAmount(), the first thread acquires a lock on object a. It is possible for the second thread to acquire a lock on object b before the first thread can lock on b. Subsequently, the first thread would request a lock on b which is already held by the second thread. The second thread would request a lock on a which is already held by the first thread. This constitutes a deadlock condition, as neither thread can proceed.
This noncompliant code example may or may not deadlock depending on the scheduling details of the platform. Deadlock can occur when two threads request the same two locks in different orders and each thread obtains a lock that prevents the other thread from completing its transfer. Deadlock might may not occur when two threads request the same two locks, but one thread completes its transfer before the other thread begins. Deadlock also cannot occur if the two threads request the same two locks in the same order (which would happen if they both transfer money from one account to a second account), or if two simultaneous transfers occur involving distinct accounts occur concurrently.
Compliant Solution (static internal private lock)
The deadlock can be avoided by using a private static final internal lock object before performing any account transfers.
| Code Block | ||
|---|---|---|
| ||
final class BankAccount {
private double balanceAmount; // Total amount in bank account
private static final Object lock = new Object();
private BankAccount(double balance) {
this.balanceAmount = balance;
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAmount(BankAccount ba, double amount) {
synchronized (lock) {
if (amount > balanceAmount) {
throw new IllegalArgumentException("Transfer cannot be completed");
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAmount(second, amount);
}
});
t.start();
}
}
|
...
This compliant solution ensures that multiple locks are acquired and released in the same order. It requires that an ordering over BankAccount objects is available. The ordering is enforced by having the class BankAccount implement the java.lang.Comparable interface and overriding the compareTo() method.
| Code Block | ||
|---|---|---|
| ||
final class BankAccount implements Comparable<BankAccount> { private double balanceAmount; // Total amount in bank account private final Object lock; private final long id; // Unique for each BankAccount private static long nextID = 0; // Next unused id private BankAccount(double balance) { this.balanceAmount = balance; this.lock = new Object(); this.id = this.nextID++; } public int compareTo(BankAccount ba) { if (this.id < ba.id) { return -1; } if (this.id > ba.id) { return 1; } return 0; } // Deposits the amount from this object instance to BankAccount instance argument ba privatepublic void depositAmount(BankAccount ba, double amount) { BankAccount former, latter; if (compareTo(ba) < 0) { former = this; latter = ba; } else { former = ba; latter = this; } synchronized (former) { synchronized (latter) { if (amount > balanceAmount) { throw new IllegalArgumentException("Transfer cannot be completed"); } ba.balanceAmount += amount; this.balanceAmount -= amount; } } } public static void initiateTransfer(final BankAccount first, final BankAccount second, final double amount) { Thread t = new Thread(new Runnable() { public void run() { first.depositAmount(second, amount); } }); t.start(); } } |
Whenever a transfer occurs, the two BankAccount objects are ordered so that the first object's lock is acquired before the second object's lock. Consequently, if two threads attempt transfers between the same two accounts, they will both try to acquire the first account's lock before the second account's lock, with the result that one thread will acquire both locks, complete the transfer, and release both locks before the other thread may can proceed.
Unlike the previous compliant solution, this solution incurs no performance penalty because multiple transfers can occur concurrently as long as the transfers involve distinct target accounts.
...
In this compliant solution, each BankAccount has a java.util.concurrent.locks.ReentrantLock associated with it. This permits the depositAmount() method to try acquiring both accounts' locks, but releasing the locks if it fails, and trying again later.
| Code Block | ||
|---|---|---|
| ||
final class BankAccount {
private double balanceAmount; // Total amount in bank account
private final Lock lock = new ReentrantLock();
private final Random number = new Random(123L);
private BankAccount(double balance) {
this.balanceAmount = balance;
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAmount(BankAccount ba, double amount) throws InterruptedException {
while (true) {
if (this.lock.tryLock()) {
try {
if (ba.lock.tryLock()) {
try {
if (amount > balanceAmount) {
throw new IllegalArgumentException("Transfer cannot be completed");
}
ba.balanceAmount += amount;
this.balanceAmount -= amount;
break;
} finally {
ba.lock.unlock();
}
}
} finally {
this.lock.unlock();
}
}
int n = number.nextInt(1000);
int TIME = 1000 + n; // 1 second + random delay to prevent livelock
Thread.sleep(TIME);
}
}
public static void initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread t = new Thread(new Runnable() {
public void run() {
try {
first.depositAmount(second, amount);
} catch (InterruptedException e) {
Thread.currentThread().interrupt(); // Reset interrupted status
}
}
});
t.start();
}
}
|
Deadlock is impossible in this compliant solution because no method grabs a lock and holds it indefinitely. If the current object's lock is acquired, but the the second lock is unavailable, the first lock is released and the thread sleeps for some specified amount of time before retrying.
Code that uses this lock behaves similar to synchronized code that uses the traditional monitor lock. ReentrantLock provides several other capabilities, for instance, the tryLock() method does not block waiting if another thread is already holding the lock. The class java.util.concurrent.locks.ReentrantReadWriteLock can be used when some thread requires a lock to write information while other threads require the lock to concurrently read the information.
...
Each request has a response time associated with it , as well as along with a measurement of network bandwidth required to fulfill the request.
...
| Code Block | ||
|---|---|---|
| ||
public final class WebRequestAnalyzer {
private final Vector<WebRequest> requests = new Vector<WebRequest>();
public boolean addWebRequest(WebRequest request) {
// Lock on last element to prevent data race with the calculateAverageResponseTime() method
synchronized (requests.lastElement()) {
// Defensive copying
return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()));
}
}
public double getAverageBandwidth() {
return calculateAverageBandwidth(0, 0);
}
public double getAverageResponseTime() {
return calculateAverageResponseTime(requests.size() - 1, 0);
}
private double calculateAverageBandwidth(int i, long bandwidth) {
if (i > requests.size()) {
return bandwidth / requests.size();
}
synchronized (requests.elementAt(i)) {
bandwidth += requests.get(i).getBandwidth();
return calculateAverageBandwidth(++i, bandwidth); // Acquires locks in increasing order
}
}
private double calculateAverageResponseTime(int i, long responseTime) {
if (i <= -1) {
return responseTime / requests.size();
}
synchronized (requests.elementAt(i)) {
responseTime += requests.get(i).getResponseTime();
return calculateAverageResponseTime(--i, responseTime); // Acquires locks in decreasing order
}
}
}
|
The monitoring application is built upon around class WebRequestAnalyzer that maintains a list of web requests using vector requests. The vector requests is suitably initialized after defensively copying the requests. Any thread can get the average bandwidth or average response time of all web requests by invoking the getAverageBandwidth() and getAverageResponseTime() methods.
These methods use fine-grained locking by holding locks on individual elements (web requests) of the vector. The locks permit new requests to be added while the computations are still underway. Consequently, the statistics reported by the methods are accurate at the time they return the results.
...
For example, if there are 20 requests in the vector, and one thread calls getAverageBandwidth(), it acquires the intrinsic lock of WebRequest 0, the first element in the vector. Meanwhile, if a second thread calls getAverageResponseTime(), it acquires the intrinsic lock for of WebRequest 19, the last element in the vector. Consequently, a deadlock results because neither thread can acquire all of the locks and proceed with the calculations.
...
In this compliant solution, the two calculation methods acquire and release locks in the same order, beginning with the first web request in the vector.
| Code Block | ||
|---|---|---|
| ||
public final class WebRequestAnalyzer {
private final Vector<WebRequest> requests = new Vector<WebRequest>();
public boolean addWebRequest(WebRequest request) {
// No need to lock on the last element because locks are acquired in increasing order
return requests.add(new WebRequest(request.getBandwidth(), request.getResponseTime()));
}
public double getAverageBandwidth() {
return calculateAverageBandwidth(0, 0);
}
public double getAverageResponseTime() {
return calculateAverageResponseTime(0, 0);
}
private double calculateAverageBandwidth(int i, long bandwidth) {
if (i > requests.size()) {
return bandwidth / requests.size();
}
synchronized (requests.elementAt(i)) { // Acquires locks in increasing order
bandwidth += requests.get(i).getBandwidth();
return calculateAverageBandwidth(++i, bandwidth);
}
}
private double calculateAverageResponseTime(int i, long responseTime) {
if (i > requests.size()) {
return responseTime / requests.size();
}
synchronized (requests.elementAt(i)) {
responseTime += requests.get(i).getResponseTime();
return calculateAverageResponseTime(++i, responseTime); // Acquires locks in increasing order
}
}
}
|
Consequently, while one thread is calculating the average bandwidth or response time, another thread cannot interfere or induce a deadlock. This is because the other thread would first have need to synchronize on the first WebRequest, which is impossible until the first calculation is complete.
...