Concurrency
Table of contents
Submit your solutions to the following questions as a PDF on Gradescope.
Non-reentrant locking
Consider this pseudocode for a bank account supporting concurrent access. Assume that Lock is a valid locking class, although it is not in Java. Since Lock is not reentrant, the code below is broken.
Assuming Lock is not reentrant, give an example where the withdraw method would block forever. Refer to locks using the commented operation number.
class BankAccount {
private int balance = 0;
private Lock lk = new Lock();
int getBalance() {
lk.acquire(); // Operation 1
int ans = balance;
lk.release(); // Operation 2
return ans;
}
void setBalance(int x) {
lk.acquire(); // Operation 3
balance = x;
lk.release(); // Operation 4
}
void withdraw(int amount) {
lk.acquire(); // Operation 5
int b = getBalance();
if (amount > b) {
lk.release(); // Operation 6
throw new WithdrawTooLargeException();
}
setBalance(b - amount);
lk.release(); // Operation 7
}
}
Better withdrawal
Below is a new version of the withdraw method your friend proposes. Explain why newWithdraw doesn’t block forever (unlike the original code) even if locks are not reentrant. Refer to locks using the commented operation numbers.
void newWithdraw(int amount) {
lk.acquire(); // Operation 1
lk.release(); // Operation 2
int b = getBalance();
lk.acquire(); // Operation 3
if (amount > b) {
lk.release(); // Operation 4
throw new WithdrawTooLargeException();
}
lk.release(); // Operation 5
setBalance(b - amount);
lk.acquire(); // Operation 6
lk.release(); // Operation 7
}
Then, show that newWithdraw is incorrect by giving an interleaving of two threads (both calling newWithdraw) in which a withdrawal is forgotten or lost. Refer to locks using the commented operation numbers.