transfer
method can lead to a deadlock
situation as in the following case:
import BankAccount; public class TransferDeadlock extends Thread { public static void main(String[] args) { BankAccount a1 = new BankAccount(100.0); BankAccount a2 = new BankAccount(100.0); TransferDeadlock t1 = new TransferDeadlock(a1,a2); TransferDeadlock t2 = new TransferDeadlock(a2,a1); t1.start(); t2.start(); Thread.yield(); System.out.println("Account a1 has $"+t1.x.getBalance()); System.out.println("Account a2 has $"+t2.x.getBalance()); System.out.println("Waiting for t1 to complete..."); try {t1.join();} catch (InterruptedException e) {}; System.out.println("t1 completed..."); System.out.println("Waiting for t2 to complete..."); try {t2.join();} catch (InterruptedException e) {}; System.out.println("t2 completed..."); } public BankAccount x,y; public TransferDeadlock(BankAccount x, BankAccount y) { this.x = x; this.y = y; } public void run() { System.out.println("In Thread "+Thread.currentThread()+":"); System.out.println("Start transfer"); x.transfer(50.0, y); System.out.println("After transfer "+Thread.currentThread()); } }In this case, threads t1 and t2 start each a transfer operation and acquire the monitors of objects a1 and a2 respectively. When they need to deposit the money on the other account, they then wait for each other to release the monitor of the other, while holding the monitor that the other is waiting for (read that again). This is a deadlock.
One way to avoid a deadlock in this particular situation is to implement the following strategy: bank accounts (which represent any shared resource in a more general setting) are given each a unique identification number. The transfer procedure then tries to acquire the monitors on the two accounts it needs to modify before starting any operation. The strategy is to always acquire the monitors in the same order. In our case, the transfer method will always first acquire the monitor of the bank account with the smallest identification number.
Rewrite the BankAccount class to implement this strategy. You will need to:
static
qualifier before the
variable declaration.
BankAccount
class, the deposit, withdraw and transfer
methods are synchronized to protect the modification to the state variable
balance
. Write a program to demonstrate the need for
synchronized access. The program will do the following:
(define (stream-car s) (car st)) (define (stream-cdr s) (force (cdr s))) (define (stream-null? s) (eq? s the-empty-stream)) (define (stream-ref s n) (if (= n 0) (stream-car s) (stream-ref (stream-cdr s) (- n 1)))) (define (stream-map proc s) (if (stream-null? s) the-empty-stream (cons-stream (proc (stream-car s)) (stream-map proc (stream-cdr s))))) (define (stream-filter pred s) (cond ((stream-null? s) the-empty-stream) ((pred (stream-car s)) (cons (stream-car s) (stream-filter pred (stream-cdr s)))) (else (stream-filter pred (stream-cdr s))))) ;; An infinite stream (define (integers i) (cons-stream i (integers (+ i 1)))) (define (enumerate lo hi) (if (> lo hi) the-empty-stream (cons-stream lo (enumerate (+ lo 1) hi))))
partial-sums
that takes as argument a
stream S and returns the stream whose elements are S0, S0+S1,
S0+S1+S2,...
For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15...
stream-limit
that takes as argument a stream
and a number (the tolerance). It should examine the stream until it finds
two successive elements that differ in absolute value by less than the
tolerance, and return the second of the two elements.
Using this, we could compute square roots up to a given tolerance by:
(define (sqrt-improve guess x) (average guess (/ x guess))) (define (sqrt-stream x) (define guesses (cons-stream 1.0 (stream-map (lambda (guess) (sqrt-improve guess x)) guesses))) guesses) (define (sqrt x tolerance) (stream-limit (sqrt-stream x) tolerance)