To avoid data corruption in multithreaded Java programs, shared data must be protected from concurrent modifications and accesses. Locking can be performed at the object level using synchronized methods, synchronized blocks, or the java.util.concurrent dynamic lock objects. However, excessive use of locking can result in deadlocks.
Wiki Markup
Additionally, synchronization should be limited to cases where it is absolutely necessary. For example, the paint(), dispose(), stop(), and destroy() methods should never be synchronized in an applet because they are always called and used from dedicated threads. Furthermore, the Thread.stop() and Thread.destroy() methods are deprecated ; (see rule THI05-J. Do not use Thread.stop() to terminate threads for more information).
This rule also applies to programs that need to work with a limited set of resources. For example, liveness issues can arise when two or more threads are waiting for each other to release resources such as database connections. These issues can be resolved by letting each waiting thread retry the operation at random intervals until they succeed in acquiring successfully acquire the resource successfully.
Noncompliant Code Example (Different Lock Orders)
This noncompliant code example can can deadlock because of excessive synchronization. The balanceAmount field represents the total balance amount available for a particular BankAccount object. Users are allowed to initiate an operation that atomically transfers a specified amount from one account to another.
| Code Block | ||
|---|---|---|
| ||
final class BankAccount {
private double balanceAmount; // Total amount in bank account
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 transfer = new Thread(new Runnable() {
public void run() {
first.depositAmount(second, amount);
}
});
transfer.start();
}
}
|
Objects of this class are prone to deadlock. An attacker who has two bank accounts can construct two threads that initiate balance transfers from two different BankAccount object instances a and b. For example, consider the following code:
| Code Block |
|---|
BankAccount a = new BankAccount(5000); BankAccount b = new BankAccount(6000); BankAccount.initiateTransfer(a, b, 1000); // starts thread 1 BankAccount.initiateTransfer(b, a, 1000); // starts thread 2 |
Each transfer is performed in its own thread. 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 amount from b to a. When executing depositAmount(), the first thread acquires a lock on object a. The second thread could acquire a lock on object b before the first thread can. 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 , because neither thread can proceed.
...
Compliant Solution (Private Static Final Lock Object)
This compliant solution avoids avoids deadlock by synchronizing on a private static final 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();
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 transfer = new Thread(new Runnable() {
@Override public void run() {
first.depositAmount(second, amount);
}
});
transfer.start();
}
}
|
...
This compliant solution ensures that multiple locks are acquired and released in the same order. It requires a consistent ordering over BankAccount objects. Consequently, the BankAccount class implements the java.lang.Comparable interface and overrides 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 longfinal AtomicLong NextIDnextID = new AtomicLong(0); // Next unused ID BankAccount(double balance) { this.balanceAmount = balance; this.lock = new Object(); this.id = this.NextID++nextID.getAndIncrement(); } @Override public int compareTo(BankAccount ba) { return (this.id > ba.id) ? 1 : (this.id < ba.id) ? -1 : 0; } // Deposits the amount from this object instance // to BankAccount instance argument ba public 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 transfer = new Thread(new Runnable() { @Override public void run() { first.depositAmount(second, amount); } }); transfer.start(); } } |
...
In this compliant solution, each BankAccount has a java.util.concurrent.locks.ReentrantLock. This design permits the depositAmount() method to attempt to acquire the locks of both accounts, to release the locks if it fails, and to try again later if necessary.
| 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);
BankAccount(double balance) {
this.balanceAmount = balance;
}
// Deposits 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 transfer = new Thread(new Runnable() {
public void run() {
try {
first.depositAmount(second, amount);
} catch (InterruptedException e) {
Thread.currentThread().interrupt(); // Reset interrupted status
}
}
});
transfer.start();
}
}
|
...
Code that uses this locking strategy has behavior similar to that of synchronized code that uses the traditional monitor lock. ReentrantLock also provides several other capabilities. For example, the tryLock() method immediately returns false when another thread already holds the lock. Further, the java.util.concurrent.locks.ReentrantReadWriteLock class has multiple-readerreaders/single-writer semantics and is useful when some threads require a lock to write information while other threads require the lock to concurrently read the information.
...
The following immutable WebRequest class encapsulates a web request received by a server:
| Code Block |
|---|
// Immutable WebRequest
public final class WebRequest {
private final long bandwidth;
private final long responseTime;
public WebRequest(long bandwidth, long responseTime) {
this.bandwidth = bandwidth;
this.responseTime = responseTime;
}
public long getBandwidth() {
return bandwidth;
}
public long getResponseTime() {
return responseTime;
}
}
|
...
This noncompliant code example monitors web requests and provides routines for calculating the average bandwidth and response time required to serve incoming requests.
| Code Block | ||
|---|---|---|
| ||
public final class WebRequestAnalyzer {
private final Vector<WebRequest> requests = new Vector<WebRequest>();
public boolean addWebRequest(WebRequest request) {
return requests.add(new WebRequest(request.getBandwidth(),
request.getResponseTime()));
}
public double getAverageBandwidth() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
return calculateAverageBandwidth(0, 0);
}
public double getAverageResponseTime() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
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();
// Acquires locks in increasing order
return calculateAverageBandwidth(++i, bandwidth);
}
}
private double calculateAverageResponseTime(int i, long responseTime) {
if (i <= -1) {
return responseTime / requests.size();
}
synchronized (requests.elementAt(i)) {
responseTime += requests.get(i).getResponseTime();
// Acquires locks in decreasing order
return calculateAverageResponseTime(--i, responseTime);
}
}
}
|
...
Unfortunately, this noncompliant code example is prone to deadlock because the recursive calls within the synchronized regions of these methods acquire the intrinsic locks in opposite numerical orders. That is, calculateAverageBandwidth() requests locks from index 0 up to requests.size() - − 1, whereas calculateAverageResponseTime() requests them from index requests.size() - − 1 down to 0. Because of recursion, previously acquired locks are never released by either method. Deadlock occurs when two threads call these methods out of order, because one thread calls calculateAverageBandwidth(), while the other calls calculateAverageResponseTime() before either method has finished executing.
For example, when there are 20 requests in the vector, and one thread calls getAverageBandwidth(), the thread 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 of WebRequest 19, the last element in the vector. Consequently, deadlock results because neither thread can acquire all of the locks required to proceed with its calculations.
Note that the addWebRequest() method also has a race condition with calculateAverageResponseTime(). While iterating over the vector, new elements can be added to the vector, invalidating the results of the previous computation. This race condition can be prevented by locking on the last element of the vector (when it contains at least one element) before inserting the element.
...
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) {
return requests.add(new WebRequest(request.getBandwidth(),
request.getResponseTime()));
}
public double getAverageBandwidth() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
return calculateAverageBandwidth(0, 0);
}
public double getAverageResponseTime() {
if (requests.size() == 0) {
throw new IllegalStateException("The vector is empty!");
}
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)) {
// Acquires locks in increasing order
responseTime += requests.get(i).getResponseTime();
return calculateAverageResponseTime(++i, responseTime);
}
}
}
|
...
Acquiring and releasing locks in the wrong order can result in deadlock.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
|---|---|---|---|---|---|
LCK07-J |
Low |
Likely |
High | P3 | L3 |
Automated Detection
Some static analysis tools can detect violations of this rule.
Related Guidelines
CWE-833. Deadlock |
Bibliography
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="38ef9f5e-fc24-4759-8a15-e6eeb6f5cc54"><ac:plain-text-body><![CDATA[ | [[JLS 2005 | AA. Bibliography#JLS 05]] | [Chapter 17, Threads and Locks | http://java.sun.com/docs/books/jls/third_edition/html/memory.html] | ]]></ac:plain-text-body></ac:structured-macro> |
<ac:structured-macro ac:name="unmigrated-wiki-markup" ac:schema-version="1" ac:macro-id="5b2504f5-5430-42f4-8a05-87d57d6e1be6"><ac:plain-text-body><![CDATA[ | [[Halloway 2000 | AA. Bibliography#Halloway 00]] |
| ]]></ac:plain-text-body></ac:structured-macro> |
| Tool | Version | Checker | Description | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Coverity | 7.5 | LOCK_INVERSION | Implemented | ||||||
| Parasoft Jtest |
| CERT.LCK07.LORD | Ensure that nested locks are ordered correctly | ||||||
| ThreadSafe |
| CCE_DL_DEADLOCK | Implemented |
Related Guidelines
CWE-833, Deadlock |
Bibliography
...