...
This noncompliant code example can deadlock because of excessive synchronization. Assume that an attacker has two bank accounts and is capable of requesting two depositAllAmountdepositAmount() operations in succession, one each from the two threads started in main().
| Code Block | ||
|---|---|---|
| ||
class BankAccount {
private intdouble balanceAmount; // Total amount in bank account
private BankAccount(intdouble balance) {
this.balanceAmount = balance;
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAllAmountdepositAmount(BankAccount ba, double amount) {
synchronized (this) {
synchronized(ba) {
ba.balanceAmount += this.balanceAmount;if(amount > balanceAmount) {
this.balanceAmount = 0; // Withdraw all amount from this instance throw new IllegalArgumentException("Transfer cannot be completed");
}
ba.displayAllAmount();balanceAmount += amount;
// Display the new balanceAmount in ba (may cause deadlock)this.balanceAmount -= amount;
}
}
}
privatepublic synchronizedstatic void displayAllAmountinitiateTransfer()final {
System.out.println(balanceAmount);
}
public static void initiateTransfer(BankAccount first,
final BankAccount firstsecond, final BankAccountdouble secondamount) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAllAmountdepositAmount(second, amount);
}
});
t.start();
}
}
|
Objects of class BankAccount represent bank accounts. The balanceAmount field represents the total balance amount available for a particular object (bank account). A user is allowed to initiate an operation deposit all amount that atomically transfers the balance a specified amount from one account to another. This is equivalent to closing a bank account and transferring the balance to a different (existing or new) account.
Objects Objects of this class are deadlock-prone. An attacker may cause the program to construct two threads that initiate balance transfers from two different BankAccount object instances, a and b. Consider the following code that does this:
| 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. The first thread atomically transfers the amount from a to b by depositing the balance from a to it in account b and then withdrawing the entire balance same amount from a. The second thread performs the reverse operation, that is, it transfers the balance from b to a and withdraws the balance from b. When executing depositAllAmountdepositAmount(), 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 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 completeing completing its transfer. Deadlock might 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.
...
| Code Block | ||
|---|---|---|
| ||
class BankAccount {
private intdouble balanceAmount; // Total amount in bank account
private static final Object lock = new Object();
private BankAccount(intdouble balance) {
this.balanceAmount = balance;
}
this.lock = new Object();
}
// Deposits // Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAllAmountdepositAmount(BankAccount ba, double amount) {
synchronized (lock) {
ba.balanceAmount += this.balanceAmount;
if (amount > balanceAmount) {
this.balanceAmount = 0; // Withdraw all amount from this instancethrow new IllegalArgumentException("Transfer cannot be completed");
}
ba.displayAllAmount();balanceAmount += amount;
// Display the new this.balanceAmount in ba (may cause deadlock)-= amount;
}
}
privatepublic static void displayAllAmount(initiateTransfer(final BankAccount first,
final BankAccount second, final double amount) {
Thread t = new synchronizedThread(new Runnable(lock) {
System.out.println(balanceAmount);
}
}
public static void initiateTransfer(final BankAccount first, final BankAccount secondrun() {
Thread t = new Thread(new Runnable() {first.depositAmount(second, amount);
public void run() {}
});
firstt.depositAllAmountstart(second);
}
});
t.start();
}}
}
|
In this scenario, if two threads with two different BankAccount objects try to transfer to each others' accounts simultaneously, deadlock cannot occur. One thread will acquire the private lock, complete its transfer, and release the lock, before the other thread can proceed.
...
| Code Block | ||
|---|---|---|
| ||
class BankAccount implements Comparable<BankAccount> {
private intdouble balanceAmount; // Total amount in bank account
private final Object lock;
private final long id; // uniqueUnique for each BankAccount
private static long nextID = 0; // nextNext unused id
private BankAccount(intdouble 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
private void depositAllAmountdepositAmount(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 ba.balanceAmount += this.balanceAmount;(amount > balanceAmount) {
this.balanceAmount = 0;throw // withdraw all amount from this instance
new IllegalArgumentException("Transfer cannot be completed");
ba.displayAllAmount(); // Display the new balanceAmount in ba (may cause deadlock)}
ba.balanceAmount += amount;
}
this.balanceAmount -= amount; }
}
private synchronized void displayAllAmount() {}
System.out.println(balanceAmount);}
}
public static void initiateTransfer(final BankAccount first,
final final BankAccount second, final double amount) {
Thread t = new Thread(new Runnable() {
public void run() {
first.depositAllAmountdepositAmount(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 proceed.
...
In this compliant solution, each BankAccount has a java.util.concurrent.locks.ReentrantLock associated with it. This permits the depositAllAmountdepositAmount() method to try acquiring both accounts' locks, but releasing the locks if it fails, and trying again later.
| Code Block | ||
|---|---|---|
| ||
class BankAccount {
private intdouble balanceAmount; // Total amount in bank account
private final Lock lock = new ReentrantLock();
private final Random number = new Random(123L);
private BankAccount(int balance) {
this.balanceAmount = balance;
}
// Deposits the amount from this object instance to BankAccount instance argument ba
private void depositAllAmount(BankAccount ba) throws InterruptedException {
while (true) {
if (this.lock.tryLock()) {
try {
if (ba.lock.tryLock()) {
try {
private BankAccount(double balance) {
bathis.balanceAmount += this.balanceAmountbalance;
}
// Deposits the amount from this object instance to this.balanceAmount = 0; // withdraw all amount from this instanceBankAccount instance argument ba
private void depositAmount(BankAccount ba, double amount) throws InterruptedException {
while (true) {
if ba.displayAllAmount(this.lock.tryLock();) {
// Display the new balanceAmount in batry {
if break;(ba.lock.tryLock()) {
}try finally {
if ba.lock.unlock();
(amount > balanceAmount) {
}
throw new }
} finally {
IllegalArgumentException("Transfer cannot be completed");
this.lock.unlock();}
}
}
ba.balanceAmount += amount;
int n = number.nextInt(1000);
int TIMEthis.balanceAmount -= 1000 + namount; //
1 second + random delay to prevent livelock
Thread.sleep(TIME)break;
}
}
private void displayAllAmount() throws} InterruptedExceptionfinally {
while (true) {
if (ba.lock.tryLockunlock()) {;
try {
System.out.println(balanceAmount);}
break;}
} 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.depositAllAmountdepositAmount(second, amount);
} catch (InterruptedException e) {
Thread.currentThread().interrupt(); // Reset interrupted status
}
}
});
t.start();
}
}
|
...