G52CON 2008-2009: Solution to Exercise 3, Monitors

1. A savings account is shared by several people. Each person may deposit or withdraw money from the account. The current balance in the account is the sum of all deposits to date less the sum of all withdrawals to date. The balance must never become negative. Account holders are represented as processes. A process making a deposit never has to delay (except for mutual exclusion), but a withdrawal has to wait until there are sufficient funds.

   Develop a monitor to solve this problem. The monitor should have two procedures: deposit(amount) and withdraw(amount). Assume the arguments to deposit and withdraw are positive, and the monitor uses Signal and Continue.

monitor SavingsAccount {
    // Private variables
    integer balance = 0;

    // Condition variables
    condvar funds;

    // Monitor procedures ...
    procedure deposit(integer amount) {
        balance = balance + amount;
        signal(funds);
    }

    procedure withdraw(integer amount) {
        while (amount > balance) {
            wait(funds);
        }
        balance = balance - amount;
    }
}

The current balance is held in the private integer variable, balance. Mutual exclusion is implicit; condition synchronisation is achieved using the condition variable funds, which is used to indicate that funds have been deposited.

The deposit and withdraw operations are implemented as monitor procedures. Deposit simply increases the current balance by amount and signals that additional funds are now available. Deposit never blocks (except for mutual exclusion), since making a deposit is always legal, whatever the balance.

Withdraw checks to see if there are sufficient funds to cover the withdrawal. If there are, it simply decreases the balance by amount. If there are insufficient funds, it waits on the condition variable funds until a deposit operation signals that there are more funds available, at which point it tries again. The wait statement is enclosed in a while loop to ensure that the condition on which we are waiting--there being sufficient funds to cover the withdrawal--is actually true when we update the balance.

Note that, as programmed, each deposit will only allow one blocked withdrawal to be retried, even if there are now sufficient funds to allow several processes to make withdrawals. If the process which is woken following the deposit wants to make a withdrawal which exceeds the current balance, then no withdrawals will be made, even if other, smaller, withdrawals could proceed. One solution to this is to use signal_all(funds) in deposit to wake all processes wishing to make a withdrawal.