Assignment 5

Principles of Programming Languages (201-1289101)

Concurrency -- Streams

Due June 22 1997

Questions

1. Deadlock Avoidance Strategies
2. Test Need for Synchronized
3. Streams

Question 1: Deadlock Avoidance Strategy

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());
  }    
}

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:

1. Add the identification number using a static member counting the instances of the BankAccount class.
2. Change the transfer method to implement the deadlock avoidance strategy.
3. Test that the program given above does indeed avoid the deadlock.

Notes

Question 2: Test Need for Synchronized

1. Modify the bank account to remove the synchronized qualifiers.
2. Define a class Bank that contains 3 BankAccount instances with initial balances b1, b2 and b3, and a method TotalBalance() that returns the sum of the balances of all the accounts in the bank.
3. Write a main function that creates 2 threads that enter in a loop and repeatedly exchange the contents of each pair of two accounts (a1 and a2, then a1 and a3 then a2 and a3 and again). (The class Bank should be very similar to the class TransferDeadlock() above.)
4. Explain (in your source) why if the 2 threads where running sequentially, after any number of exchanges, the account balances should be b1, b2 and b3 in some order.
5. By inserting calls to Thread.yield() at judicious places, demonstrates that a critical section is entered by the 2 threads simultaneously: at some point, TotalBalance() will not return b1+b2+b3. Draw a timing diagram (in your source) explaining the result you obtain.

Question 3: Streams

(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))))

Question 3.1: Partial-sums (Book 3.55 p.331)

For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15...

Question 3.2: stream-limit (Book 3.64 p.338)

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)