Assignment 5

Principles of Programming Languages (201-1289101)

Concurrency -- Streams

Due June 22 1997


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

Question 1: Deadlock Avoidance Strategy

Consider the BankAccount class discussed in class. Two calls to the 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);

    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:

  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.


A static member variable of a class is shared by all the instances of the class. It can be initialized in the class definition. The initialization is performed the first time the class implementation file is loaded. If it is modified, all the instances of the class can "see" the modified value. It is defined by adding the static qualifier before the variable declaration.

Question 2: Test Need for Synchronized

In the 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:
  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

You are given the following definitions:
(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)
    (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)
    (cons-stream lo (enumerate (+ lo 1) hi))))

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

Define a procedure 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...

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

Write a procedure 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))
(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance)

The end.